Постановка задачи и алгоритм решения
Идея такого алгоритма заключается в следующем: вначале условие целочисленности не принимается во внимание и симплекс- методом отыскивается оптимальный план. Если этот план нецелочисленный, составляется дополнительное ограничение, которому удовлетворяет любое целочисленное решение, но заведомо не удовлетворяет найденное.
После введения этого ограничения в задачу план становится недопустимым, и решение продолжается опять до получения оптимума. Если новый оптимальный план также окажется нецелочисленным, снова формулируется дополнительное ограничение и для расширенной задачи снова находится оптимум и т. д.
Геометрически дополнительному ограничению соответствует гиперплоскость, которая отсекает от многогранника решений какую-то часть вместе с вершиной, которой соответствует нецелочисленное решение. При этом все точки с целочисленными координатами остаются в новом многограннике, так что через несколько операций такая точка становится вершиной с целочисленными координатами (рис. 13.1).
(координаты целые)
^Оі і
Пусть требуется найти максимум целевой функции
(13.1)
^тах = + Р2*2 + - + ЛЛ, при ограничениях
а\ 1*1 + <*12*2 +~.
+ а1„х„<а1(13.2)
ат\х\ *ат2х2 + - + атпхп^ат Xj>О / = 1, П.
Не нарушая общности, можно предположить, что все коэффициенты системы (13.2) выражаются целыми числами. Приводим систему к виду
(13.3)
ах 1*1 + апх2 +... + а1пхп + ух = ах атххх + ат2х 2 + ...+ атпхп + Ут ~ ат
где yj — выравнивающие неизвестные.
Отметим, ЧТО целочисленность переменных Xj влечет за собой целочисленность переменных yg.
Составим первую симплекс-таблицу и после / шагов получим оптимальный план, который можно представить последней симп-лекс-таблицей.
Таблица 13.1 Общий вид первой симплекс-таблицы решения задачи целочисленного программирования с
Б Свободный член Ух- Уе Хе+\ Хп Хх Ьх ьи Ь\п Хе ьел\ bu btn Уе+1 Ь?+\ b(t+1)1 b(t+Dt b?+1 \п Ут Ьт bm\- bmi bmn z
^тах Q Ях- Яе Яп
Если все свободные члены целые - задача решена. Для удобства все базисные переменные обозначим г)Д/ = 1,/и), а все свободные переменные = 1, п, тогда таблица примет вид (табл. 13.2):
Таблица 13.2 С
Б Свободный член і, Пі Ьх Ам- b\i] b\n Л/ bt bi ,... bv bin Лт Ьт bm і- bmj Ьщп 7
^тах Q Я\- 1] Яп
С целью упрощения в таблице опущены:
а) столбцы, соответствующие базисным переменным;
б) целевая строка;
в) контрольный столбец.
Пусть свободный член bt является дробным, в этой же строка среди коэффициентов by могут быть как дробные, так и целые. Обозначим буквой п с соответствующими индексами антье от by и Ь{.
Е(Ьу) = пу\ E(bj) = щ.
Вычислим разности между соответствующими коэффициентами и Е:
a h п <13'4)
Р i=bi~»r
Эти разности удовлетворяют условиям
0<|3,у(1;
0SM. <13'5)
Выпишем из таблицы выражение для г|, и заменим в нем коэффициенты согласно условию (13.4), тогда получим:
Л/ = 0/1 +Я/іМЧі) + - + (Рш + + л/;
л л (13.6)
Л/ = Е + 2 Ру(Чу)+Р/-
у=1 у= 1
Перепишем последнее выражение в другом виде
+ (13.7)
j J
Если и г),- — целые, то из правой части (13.7) следует, что 5/ — целое; так как ^ > 0; rj/ > 0, а из средней части (13.7) следует Si > -P/j учитывая выражение (13.5), заключаем, что St может принимать значения: 0, 1,2, ...
и т. д.Вывод. При любых целых неотрицательных г], и St принимает целые неотрицательные значения.
Введем в задачу дополнительное ограничение (табл. 13.3), используя подчеркнутую часть выражения (13.7).
Дополнительному ограничению удовлетворяет любой целочисленный план издания, в то же время найденный ранее оптимальный план для расширенной задачи является недопустимым, так как Si = -bi < 0.
Для расширенной задачи обычным путем отыскивается снача-ла допустимый план, а затем оптимальный. с
Б Х^ Свободный член їх... Лі bx bxx- bxij b\n Лт ~ЬтХ ~Ьц— -bmj ~bmn $ -р/ -Рп- -P* ~P/„ Z Q Ях- qj Я„
Если в какой-либо строке таблицы (кроме строки Z) свободный член дробный, а все прочие коэффициенты целые, целочисленных решений нет.
Пример
^max = 2*1 + х2 ~ Зх3; х\ + - 2х3 + Уі = 4;
5xj - х3 + >>2 = 12; 2х{ - х2 + Зх3 + = 4; xj>0]j= Ь_3; Л^О; /= 1, 3.
После двух шагов применения симплекс-метода приходим к оптимальному плану, представленному в табл. 13.4.
Решение оптимальное, но дробное х = (16/7; 4/7; 0).
Выбираем среди свободных членов дробный, например, 4/7 из первой строки. По формулам (13.6) находим коэффициент дополнительного ограничения:
Рп =-у-(-1)=|; Pi2 =|-о=|;
Р13=-1-(-1) = 0; pj =1-0 = 1
Ограничение Sj имеет вид: Уз У\ *з Свободный член *2 -1/7 2/7 -1 4/7 У2 -15/7 -5/7 -6 4/7 Х\ 3/7 1/7 1 16/7 Z 5/7 4/7 4 36/7 Введем это ограничение в табл. 13.4 и получим следующее:
Таблица 13.5 ^3 Уі *з , Свободный член *2 -1/7 2/7 -1 4/7 Уг -15/7 -5/7 -6 4/7 3/7 1/7 1 16/7 -6/7 -2/7 0 -4/7 Z 5/7 4/7 4 36/7 Применяя теорему, находим допустимое решение, представлен-ное в табл. 13.6.
Таблица 13.6 Уз *з Свободный член *2 -1 1 -1 0 Уг 0 -5/2 -6 2 0 1/2 1 2 У\ 3 -7/2 0 2 Z -1 2 4 4
Полученный план неоптимален (в последней строке имеются отрицательные элементы): после еще одного шага получаем оптимальный план, но нецелочисленный, поэтому составляем дополнительное ограничение по первой строке и получаем табл. 13.7. Уз *з Свободный член *2 1/3 -1/6 -1 2/3 Уг 0 -5/2 -6 2 0 1/2 1 2 Уъ 1/3 -7/6 0 2/3 -1/3 -5/6 0 -2/3 Z 1/3 5/6 4 14/3
Pll = і/з Pi2 = 5/6
Pi3 = 0
Pi =2/3
Применяя теорему о нахождении допустимого плана, получаем одновременно оптимальный и целочисленный план.