Задание: получить целочисленное решение задачи методом Гомори или методом ветвей и границ.
Таблица 9
Варианты заданий
№ | Целевая функция | Ограничения | Тип экстр. | Метод |
max | Гомори | |||
max | Ветвей и границ | |||
min | Гомори | |||
min | Ветвей и границ | |||
min | Гомори | |||
Продолжение табл.9 | ||||
№ вар | Целевая функция | Ограничения | Тип экстр. | Метод |
min | Ветвей и границ | |||
min | Гомори | |||
min | Ветвей и границ | |||
min | Гомори | |||
min | Ветвей и границ | |||
min | Гомори | |||
min | Ветвей и границ | |||
Окончание табл.9 | ||||
№ вар | Целевая функция | Ограничения | Тип экстр. | Метод |
min | Гомори | |||
min | Ветвей и границ | |||
min | Гомори | |||
min | Ветвей и границ | |||
min | Гомори | |||
min | Ветвей и границ | |||
max | Гомори | |||
max | Ветвей и границ |
Ход работы
1. Записать математическую модель задачи.
2. Записать математическую модель задачи в канонической форме.
3. Загрузить приложение Лин_прогр.exe и ввести в программу исходные данные задачи и, используя команду Целочисленное программирование меню Решение, получить ее решение. Сформировать файл отчета.
4. Если получено нецелочисленное решение, в соответствии с алгоритмом дополнить задачу новым ограничением или разбить задачу на две новые и получить новое решение. Повторять пункт 4 до получения целочисленного решения.
5. Открыть файл отчета c помощью программы Microsoft Excel, оформить и распечатать файл отчета.
6. Записать решение задачи
Содержание отчета
1. Текст задания.
2. Математическая модель задачи.
3. Математическую модель задачи в канонической форме.
4. Симплекс-таблица решения задачи.
5. Симплекс-таблицы решения новых задач (первый и последний шаг итераций для метода ветвей и границ) и продолжения решения задачи (для метода Гомори).
6. Для метода ветвей и границ привести дерево задач.
7. Результаты решения задачи.
8. Проверка выполнения условий-ограничений задачи для найденного решения.
Вопросы для подготовки
1. Сформулируйте задачу целочисленного линейного программирования.
2. Изложите суть метода Гомори.
3. Как выбирается индексная строка в методе Гомори?
4. Как составить отсечение Гомори, если оптимальное решение является нецелочисленным?
5. Какой геометрический смысл имеет введение дополнительного ограничения в методе Гомори?
6. Изложите суть метода ветвей и границ.
7. Как составить дополнительное ограничение в методе ветвей и границ, если оптимальное решение является нецелочисленным?
8. Какой геометрический смысл имеет введение дополнительного ограничения в методе ветвей и границ?
9. Когда прекращается итерационная процедура поиска целочисленного решения в методе ветвей и границ?