Алгоритм решения ЗЛЦП

1.Симплексным методом решить задачу без учета условия целочисленности, если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.

 

2.Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и сформировать правильное отсечение.

 

3.Неравенство, определяющее правильное отсечение введением дополнительной, неотрицательной целочисленной переменной, преобразовать в равносильное уравнение и включить его в систему ограничений.

 

4.Полученную расширенную задачу решить симплексным методом, если оптимальный план будет целочисленным, то задача ЛЦП решена, в противном случае вернуться к пункту 2 алгоритма.

 

Пример: При решении некоторой оптимизационной задачи симплексным методом получено некоторое базисное решение:

х1=21х4 + 4х5

3 3 3

х2=8 – х5

х3=18+х45

Z=25 12x41x5

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

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