Метод Гомори

Краткая теория

Метод Гомори является одним из методов решения задач целочисленного линейного программирования. Идея метода Гомори заключается в следующем.

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

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.

Вектор  выводим из базиса и вводим вектор .

Переходим к таблице 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  

В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):

Найденное оптимальное решение удовлетворяет условию целочисленности и является решением исходной задачи.

К оглавлению решебника по методам оптимальных решений