Метод Гомори является
одним из методов решения задач целочисленного линейного программирования. Идея
метода Гомори заключается в следующем.
Отбрасывается условие целочисленности и
полученная
задача линейного программирования
решается
симплекс-методом.
Если оптимальное решение задачи является целочисленным, то оно является и
решением исходной задачи. Если оптимальное решение задачи не является целочисленным, то к основным
ограничениям добавляется новое линейное ограничение, обладающее следующими
свойствами:
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.
Вектор
выводим из базиса и вводим вектор
.
На сайте можно заказать решение контрольной или самостоятельной работы, домашнего задания, отдельных задач. Для этого вам нужно только связаться со мной:
ВКонтакте
WhatsApp
Telegram
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту СберБанка. Опыт работы более 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
|
|
В индексной строке все члены неотрицательные, поэтому получено
следующее решение задачи линейного программирования
(выписываем из столбца свободных членов):
Найденное оптимальное решение удовлетворяет условию целочисленности и является решением исходной задачи.