Так как
{ X, }=0,
получаем неравенство (6.3). Следовательно, мы показали, что оно не отсекает никаких допустимых целочисленных решений исходной задачи (6.1).
Сформулируем теперь этапы решения задачи целочисленного линейного программирования методом Гомори.
Этап 1. Используя симплекс-метод, решаем исходную задачу (6.1) без ограничений на целочисленность. Если задача с ослабленными ограничениями не имеет решения, то и исходная задача не имеет решения. Если решение задачи оказывается целочисленным, то оно является решением исходной задачи (6.1), и процесс поиска решения завершен.
Этап 2. Выбирается одна из нецелых компонент полученного на этапе 1 решения (как правило, выбирается компонента, имеющая наибольшую дробную часть). Исходя из выбранной компоненты строится правильное отсечение (6.3).
Этап 3. , Неравенство (6.3), полученное на этапе 2, преобразуется в равенство путем добавления новой неотрицательной переменной
{ К }-{ а,,-...-{х„,>0.
Эти соотношения присоединяем к ограничениям задачи, рассмотренной на этапе 1.
Этап 4. Решаем задачу с модифицированными на этапе 3 ограничениями. Если ее оптимальное решение является целочисленным, то это и есть оптимальное решение исходной задачи, иначе возвращаемся к этапу 2.
Оказывается что если исходная задача имеет решение, то данный алгоритм позволяет его найти за конечное число шагов.
Пример. Решить следующую задачу целочисленного линейного программирования:
шах (71+9x2)(6.4)
-Xj +32 < 6 ,
7xi+X2 <35, ХрХ2 eZ.
Решение. Область допустимых решений задачи с ослабленными ограничениями (четырехугольник ABCD), получаемой путем отбрасывания 184
требования целочисленности переменных, а также оптимальное решение этой задачи изображены на рис. 6.1.
(9/2, 7/2)
-XI +32 =6
1X1 + 92 = 63
Рис. 6.1
Добавляя в задаче с ослабленными ограничениями две новые неотрицательные переменные, приведем задачу к стандартному виду
шах (7х,+92)(6.5)
+ 32 + Хз = 6 ,
+2 +Х4 =35,
Х1,Х2,Хз,Х4 >0.
Применяя симплекс-метод (этап 1) для решения задачи (6.5), получим последнюю симплексную таблицу, определяющую оптимальное решение, в следующем виде (табл. 6.1).
Таблица 6.1
| | | | | Решение |
| | | 28/11 | 15/11 | |
| | | 7/22 | 1/22 | |
| | | -1/22 | 3/22 | |
Оптимальное значение целевой функции равное 63 достигается в точке X* ={х\,х*2,х1,х\) с координатами х\ = 9/2, х\ = 7/2, х = О, Х4 = 0. Поскольку оптимальное решение задачи с ослабленными ограничениями
не является целочисленным, то необходимо переходить к этапу 2, то есть строить правильное отсечение. Поскольку обе компоненты оптимального решения нецелочисленны и их дробные части равны, то выберем в качестве переменной, на базе которой строится отсечение, например переменную Тогда, добавляя новую неотрицательную переменную х,
получаем согласно (6.3) дополнительное ограничение следующего вида: [22j M22J I2
--X.--Хл +Хс =-.
22 22 2
(6.6)
Добавляя новое ограничение (6.6) к ограничениям задачи (6.5) получаем модифицированную задачу линейного программирования со следующей исходной симплекс-таблицей (табл. 6.2).
Таблица 6.2
| | | | | | Решение |
| | | 28/П | 15/11 | | |
| | | 7/22 | 1/22 | | |
| | | -1/22 | 3/22 | | |
| | | -7/22 | -1/22 | | -1/2 |
Продолжая решение симплекс-методом, приходим к следующей заключительной симплекс-таблице (табл. 6.3).
Таблица 6.3
Оптимальное значение целевой функции равное 59 достигается в точке X* ={xl,xl,xl,xl,xl) с координатами х* = 32/7, х*2 = 3, Х3 = 11/7, xl = О, Х5 = 0. Поскольку оптимальное решение задачи с ослабленными ограничениями опять не является целочисленным, то необходимо переходить к этапу 2, т.е. строить еще одно правильное отсечение. Поскольку две компоненты оптимального решения нецелочисленны, то выберем в