2015-02-04
289
Полученная расширенная задача решается симплекс-методом. Если найденный план удовлетворяет условию целочисленности, то задача целочисленного линейного программирования (6.1) решена. В противном случае повторяются этапы 2-4.
Если задача разрешима в целых числах, то после конечного числа шагов (итераций) оптимальный целочисленный план будет найден.
Примечание: Если в процессе решения задачи линейного целочисленного программирования, заданной изначально в канонической форме и являющейся полностью целочисленной, появится уравнение (выражающее основную переменную через свободные) с дробным свободным членом и целыми коэффициентами при свободных переменных, то данное уравнение не имеет решение в целых числах. В данном случае и исходная задача линейного целочисленного программирования не имеет целочисленного оптимального решения.
Пример 6.2. Решить следующую задачу целочисленного линейного программирования методом Гомори:
.
Решение:
