Алгоритм решения ЗЛЦП
1.Симплексным методом решить задачу без учета условия целочисленности, если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.
2.Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и сформировать правильное отсечение.
3.Неравенство, определяющее правильное отсечение введением дополнительной, неотрицательной целочисленной переменной, преобразовать в равносильное уравнение и включить его в систему ограничений.
4.Полученную расширенную задачу решить симплексным методом, если оптимальный план будет целочисленным, то задача ЛЦП решена, в противном случае вернуться к пункту 2 алгоритма.
Пример: При решении некоторой оптимизационной задачи симплексным методом получено некоторое базисное решение:
х1=2 – 1х4 + 4х5
3 3 3
х2=8 – х5
х3=18+х4+х5
Z=25 1 – 2x4 – 1x5
3 3 3
X=(2; 8; 18; 0; 0) Z=25 1
3 3
Это базисное решение оптимизировано.
Однако решение Х не удовлетворяет условию целочисленности, т.к. по первому уравнению с переменной x1=2/3-1/3x4+4/3x5 , получившей нецелочисленное значение в оптимальном решении(2/3).
Составляем правильное отсечение, в виде дополнительного ограничения.
2/3 + 1/3 х4– 4/3 х5≤0 (1)
Обращаем внимание на то, что берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при не основных переменных х4 и х5 – с противоположными знаками.
Так как дробные части:
2/3 = 0+2/3 =2/3
1/3 = 0+1/3 =1/3
-4/3 = -2+2/3 =2/3,
тогда последнее неравенство в соответствии c (1) запишется в виде:
2/3+1/3х4-2/3х5≤0 (2)–правильное отсечение.
Введя дополнительную целочисленную переменную х6 ≥ 0, получим равносильное неравенству (2) ,уравнение:
2/3+1/3х4-2/3х5 +х6=0
Включаем это уравнение в систему ограничений, после чего повторяем алгоритм решения задачи симплексным методом, применительно к расширенной задаче. Дополнительное уравнение вводится в систему, полученную на последнем шаге решения задачи(без условия целочисленности).