Тема 8. Динамическое и целочисленное программирование

 

Студент должен знать алгоритм решения задач целочисленного программирования (метод Гомори), методы решения задач динамического программирования (в частности, решение задачи выбора кратчайшего пути) и уметь применять на практических примерах.

 

Примерные тестовые задания, предлагаемые в этой теме:

1. Задачи, в которых на все или некоторые переменные наложено условие целочисленности , решаются в разделе математического программирования:

1) динамическое программирование;

*2) целочисленное программирование;

3) транспортная задача.

 

2. Дробная часть числа равна:

*1) ; 2) ; 3) ; 4) .

3. Целая часть числа равна:

*1) –2; 2) –1; 3) 1; 4) 2.

 

4. Дана сеть дорог, для которой указаны расстояния между пунктами:

Кратчайшее расстояние из пункта 6 в пункт 10 составит:

*1) 7; 2) 2; 3) 5; 4) 3; 5) 10.

 

5. Дана сеть дорог, для которой указаны расстояния между пунктами:

Кратчайшее расстояние из пункта 2 в пункт 10 соответствует пути:

1) 2 – 5 – 8 – 10; 2) 2 – 6 – 8 – 10; *3) 2 – 6 – 9 – 10.

 

6. Дана сеть дорог, для которой указаны расстояния между пунктами:

Длина пути равна:

 

*1) 18; 2) 17; 3) 20; 4) 16.

 

7. Признаком отсутствия целочисленного решения служит:

1) появление в симплексной таблице одной строки с дробным свободным членом;

2) появление в симплексной таблице хотя бы одной строки с дробным свободным членом;

*3) появление в симплексной таблице хотя бы одной строки с дробным свободным членом и целыми остальными коэффициентами;

4) появление в симплексной таблице хотя бы одной строки с дробным свободным членом и дробными остальными коэффициентами;

5)появление в симплексной таблице хотя бы одной строки с целым свободным членом и дробными остальными коэффициентами.

 

8. При решении задачи симплексным методом получили симплексную таблицу, содержащую оптимальный план.

базисные переменные	коэф-т целевой функции	свободные члены

Для получения целочисленного плана правильное отсечение имеет вид:

 

*1) ;

2) ;

3) ;

4) .

 

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА ДЛЯ ПОДГОТОВКИ К ТЕСТИРОВАНИЮ

Учебники

1. Кузнецов, А. В. Высшая математика: Математическое программирование: учеб. для вузов / А.В. Кузнецов, В.А. Сакович, Н.И. Холод; под ред. А.В. Кузнецова. — Мн.: Выш. шк., 1994. — 286 с.

2. Кузнецов, Ю. Н. Математическое программирование: учеб. пособие / Ю. Н. Кузнецов, В. И. Кузубов, А. В. Волощенко. — М.: Высш. шк., 1980. — 300 с.

Задачники

3. Кузнецов, А. В. Руководство к решению задач по математическому программированию / учеб. для вузов; под ред. А. В. Кузнецова. — Мн.: Выш. шк., 2001. — 448с.

4. Кузнецов, А. В. Сборник задач по математическому программированию: учеб. пособие для экон. спец. вузов / А. В. Кузнецов, Г. И. Новикова, Н. И. Холод. — Мн.: Выш. шк., 1985. — 143 с.

5. Сборник задач и упражнений по высшей математике: Математическое программирование: учеб. пособие / А. В. Кузнецов [и др.]; под ред. А. В. Кузнецова. — Мн.: Выш. шк., 1995. — 382 с.