Метод Гомори
Метод Гомори является одним из методов решения задач целочисленного линейного программирования. Идея метода Гомори заключается в следующем.
Отбрасывается условие целочисленности и полученная задача линейного программирования решается симплекс-методом. Если оптимальное решение задачи является целочисленным, то оно является и решением исходной задачи. Если оптимальное решение задачи не является целочисленным, то к основным ограничениям добавляется новое линейное ограничение, обладающее следующими свойствами:
1) оптимальный нецелочисленный план задачи ему не удовлетворяет;
2) любой целочисленный план задачи ему удовлетворяет.
Затем решается расширенная задача. Процесс повторяется до получения целочисленного решения. Способы построения дополнительного линейного ограничения различны для полностью и частично целочисленных задач линейного программирования. В силу свойств 1 и 2 дополнительное ограничение еще называют отсечением Гомори, а метод Гомори - методом отсечения.
Если задача разрешима в целых числах, то через конечное число итераций оптимальный целочисленный план будет найден.
Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах.
Несмотря на точность метода Гомори, он имеет ограниченное применение. С его помощью целесообразно решать задачи небольшой размерности, поскольку число итераций может быть очень большим.
Алгоритм метода Гомори рассмотрим на конкретном примере.
Задача
Решить задачу целочисленного программирования методом Гомори.
– целые
Решение
Приведем задачу к каноническому виду.
Решаем задачу симплекс-методом.
Заполняем симплексную таблицу 0-й итерации.
| БП |
|
|
|
|
|
|
|
Симплексные отношения |
| 7 | -9 | 0 | 0 | 0 | ||||
|
|
0 | 9 | 2 | 1 | 1 | 0 | 0 | 9/2 |
|
|
0 | 7 | 0 | 3 | 0 | 1 | 0 | — |
|
|
0 | 5 | 4 | 5 | 0 | 0 | 1 | 5/4 |
|
0 | -7 | 9 | 0 | 0 | 0 | ||
Переходим к таблице 1-й итерации:
| БП |
|
|
|
|
|
|
|
Симплексные отношения |
| 7 | -9 | 0 | 0 | 0 | ||||
|
|
0 | 13/2 | 0 | -3/2 | 1 | 0 | -1/2 | |
|
|
0 | 7 | 0 | 3 | 0 | 1 | 0 | |
|
|
7 | 5/4 | 1 | 5/4 | 0 | 0 | 1/4 | |
|
|
35/4 | 0 | 71/4 | 0 | 0 | 7/4 | ||
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Так как оптимальное решение не удовлетворяет условию целочисленности, продолжим решение, используя алгоритм Гомори.
Выбираем базисную переменную с наибольшей дробной частью.
По 1-й строке строим дополнительное ограничение:
Ограничение принимает вид:
Введем в ограничение дополнительную переменную:
Домножим последнее ограничение на -1:
Припишем это ограничение к последней симплексной таблице, и, следуя методу Гомори, выполним симплексные преобразования:
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 7 | -9 | 0 | 0 | 0 | 0 | ||||
|
|
0 | 13/2 | 0 | -3/2 | 1 | 0 | -1/2 | 0 | — |
|
|
0 | 7 | 0 | 3 | 0 | 1 | 0 | 0 | 7/3 |
|
|
7 | 5/4 | 1 | 5/4 | 0 | 0 | 1/4 | 0 | 1 |
|
|
0 | -1/2 | 0 | -1/2 | 0 | 0 | -1/2 | 1 | 1 |
|
|
35/4 | 0 | 71/4 | 0 | 0 | 7/4 | 0 | ||
Просматриваем строку, содержащую отрицательное число в столбце свободных членов, и выбираем любое отрицательное число в этой строке. Выбранное число будет определять разрешающий столбец.
Ключевой столбец соответствует
.
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 5/4.
Вектор
выводим из базиса и вводим вектор
.
На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение). Для этого вам нужно только связаться со мной:
Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту. Опыт работы более 25 лет.
Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.
Переходим к таблице 1-й итерации:
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 7 | -9 | 0 | 0 | 0 | 0 | ||||
|
|
0 | 8 | 6/5 | 0 | 1 | 0 | -1/5 | 0 | 20/3 |
|
|
0 | 4 | -12/5 | 0 | 0 | 1 | -3/5 | 0 | — |
|
|
-9 | 1 | 4/5 | 1 | 0 | 0 | 1/5 | 0 | 5/4 |
|
|
0 | 0 | 2/5 | 0 | 0 | 0 | -2/5 | 1 | 0 |
|
|
-9 | -71/5 | 0 | 0 | 0 | -9/5 | 0 | ||
Переходим к таблице 2-й итерации:
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 7 | -9 | 0 | 0 | 0 | 0 | ||||
|
|
0 | 8 | 0 | 0 | 1 | 0 | 1 | -3 | 8 |
|
|
0 | 4 | 0 | 0 | 0 | 1 | -3 | 6 | — |
|
|
-9 | 1 | 0 | 1 | 0 | 0 | 1 | -2 | 1 |
|
|
7 | 0 | 1 | 0 | 0 | 0 | -1 | 5/2 | — |
|
|
-9 | 0 | 0 | 0 | 0 | -16 | 71/2 | ||
Переходим к таблице 3-й итерации:
| БП |
|
|
|
|
|
|
|
|
Симплексные отношения |
| 7 | -9 | 0 | 0 | 0 | 0 | ||||
|
|
0 | 7 | 0 | -1 | 1 | 0 | 0 | -1 | |
|
|
0 | 7 | 0 | 3 | 0 | 1 | 0 | 0 | |
|
|
0 | 1 | 0 | 1 | 0 | 0 | 1 | -2 | |
|
|
7 | 1 | 1 | 1 | 0 | 0 | 0 | 1/2 | |
|
|
7 | 0 | 16 | 0 | 0 | 0 | 7/2 | ||
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Найденное оптимальное решение удовлетворяет условию целочисленности и является решением исходной задачи.