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

Методы Гомори

Цель работы

Ознакомиться с методами целочисленного линейного программирования.

Методические указания

Для решения задач использовать методы Гомори (исходные тексты программ, реализующих эти методы, находятся в файле lab_opt.arj).

Порядок выполнения работы

1. Решить задачу из лабораторной работы №6 в предположении, что все переменные являются целочисленными.

2. Сгенерировать задачу линейного программирования небольшой размерности и выполнить ручной просчет одним из методов Гомори (по указанию преподавателя). Проиллюстрировать полученные отсечения графически.

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

1. ,

2. ,

3. ,

4. ,

5. .

6. .

7. .

8. .

Система ограничений одинакова для всех вариантов и имеет вид:

.

Содержание отчета

Отчет по работе должен содержать титульный лист, цель работы, вариант задания, графическую иллюстрацию решения с полученными отсечениями, выводы.

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

1. Первый алгоритм Гомори.

2. Второй алгоритм Гомори.

3. Третий алгоритм Гомори.

4. Понятие лексикографического отсечения.