Лабораторная работа № 7

Решение полностью целочисленных задач с помощью первого алгоритма Гомори, а также методом ветвей и границ

Цельработы: Освоить метод отсечения Гомори для полностью целочисленных задач. Изучить алгоритм этого метода. Программно реализовать этот алгоритм.

Задания для подготовки к работе

Изучить возможные постановки задач целочисленного и частично-целочисленного программирования.

2. Ознакомиться с методами решения таких задач, в частности, с методами отсечения и методом ветвей и границ.

3. Выяснить для каких задач применяется первый алгоритм Гомори. Изучить этот алгоритм и написать реализующую его программу для ПЭВМ. Изучить и программно реализовать алгоритм метода ветвей и границ. В качестве тестовых данных использовать, решенную вручную одну из нижеследующих задач.

Варианты заданий

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

Контрольные вопросы

1. Какие задачи называют задачами линейного целочисленного (частично целочисленного, дискретного, частично дискретного) программирования?

2. Сформулируйте задачу о назначениях. В чем заключается связь между задачей о назначениях и транспортной задачей?

3. Сформулируйте задачу о ранце.

4. В чем заключается основная идея методов отсечений? Опишите первый алгоритм Гомори для полностью целочисленных задач.

5. Как строится сечение Гомори второго рода?

6. Какова роль двойственного симплекс метода (метода последовательного уточнения оценок) при применении сечений Гомори первого и второго рода?

7. В чем заключается метод ветвей и границ?

8. Что можно сказать о сложности задач дискретного программирования?