9.17. метод отсечения для целочисленных задач линейного программирования

9.17. метод отсечения для целочисленных задач линейного программирования

Дана полностью целочисленная задача линейного програм-vuipOBaiuM:

л

/= Е УМ (max),

(9.47)

ft

£ aiJXj=bi, i = l, 2, m,

(9.48)

j-1

x^<iJ-, 2, л, x} — целое, j'= 1, 2,и.

(9.49) (9.50)

Методы отсечений опираются на следующее утверждение; если ослабление задачи (9.47)—(9.50) имеет нецелочисленное оптимальное опорное решение а0, то существует неравенство вида

t (9-51>

которому а0 не удовлетворяет, а любое допустимое решение исходной целочисленной задачи — удовлетворяет.

Неравенство (9.51), обладающее указанными свойствами, называют правильным отсечением. Правильное отсечение, например, можно построить следующим образом.

Симплекс-таблицу для ослабления задачи (9.47)—(9.50) приведем к базису а0, все оценки которого не положительны. Ц полученной таблице выбираем строку с дробным свободным членом dp:

Обозначим через [а„] целую часть числа ак {q — , 2, л) т. е. ближайшее целое число, не превосходящее aw, а через [dp] — целую часть числа dr. Правильное отсечение в этом случае имеет вид

... +(ap„-[apn]) x^dp-[dpJ. О Рассмотрим симплекс-таблицу

Так как [1/2] = 0, [-5/2]=-3, [1] = 1, [0] = 0, [3/2]= 1, то по первой строке можно построить правильное отсечение (1/2) xt +(1/2) дг2> 1/2. Аналогично, по второй строке строится правильное отсечение (1/2) Х + (2/3) х{21/3. 0

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

Для решения целочисленной задачи линейного программирования (9.47)—(9.50) методом отсечений необходимо выполнить ряд последовательных шагов. На каждом шаге решается задача линейного программирования; если эта задача оказывается нера^ зрешимой, то и исходная целочисленная задача является неразрешимой.

Первый шаг. Находим оптимальное опорное решение

/?1 = (хг. хг' xi1*) ослабления целочисленной задачи

(9.47)~(9.50). Если р окажется целочисленным, то оно — искомое. В противном случае строим правильное отсечение, записываем его в виде

ZWx;-xn+l=zAw,x„^0, j-v

и добавляем к системе ограничений исходной задачи.

лг-й шаг (к^2). Находим оптимальное опорное решение fik=(xk х* ...; х(~ xfiu ...; х**і*_і) ослабления задачи, построенной на предыдущем шаге. Если fik целочисленно, то ик={хк),

xfh ...; х[к)) — оптимальное решение исходной задачи (9,47)— (9.50). В противном случае строим правильное отсечение

£ Xf* Xj—х„+к= Д , x„+Jt> 0 и добавляем его к системе ограни-j-i

чений задачи, полученной на (к — 1)-м шаге. После этого выполняем (к+ 1)-й шаг.

При определенных условиях всегда можно гарантировать конечность этого алгоритма, т. е. через конечное число шагов либо будет найдено оптимальное решение, либо установлено, что задача неразрешима.