Динамическое программирование. 
Теория и методы оптимизации

Во многих задача ЛП на допустимое множество ограничений накладывается дополнительное условие некоторых переменных х.. Целочисленными могут быть все переменные (полностью целочисленная задача) или часть переменных. Например, число работников-контролеров в задаче ОТК не может быть не целым.

На практике задачи целочисленного программирования (ЦП) решаются с помощью симплекс-метода, как для обычных ЗЛП. Если в результате решения вес искомые переменные будут целыми, то считается, что задача решена. В противном случае нужные переменные округляются до ближайшего целого так, чтобы не нарушались ограничения ЗЛП. Обычно этот способ решения дает хорошее целочисленное решение, близкое к оптимуму целевой функции, но только в случае, если переменные задачи велики. Если же значения переменных малы (например, булевы, 0 и 1), го подобное решение даст неприемлемые результаты.

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

Метод Гомори Запишем ЗЛП в стандартном (каноническом) виде, где Z — множество целых чисел.

Если полностью целочисленная задача ЦГ1 содержит только 2 переменные, го ее можно решить графически. Для этого сначала строится допустимая область из ограничений, как при обычной ЗЛП. Затем, считая, что допустимая область целочисленной ЗЛП состоит из точек целочисленной координатной сетки, перемещаем графически ЦФ из оптимальной вершины в ближайшую целочисленную координату. Это и считается оптимумом целочисленной задачи.

Рис. 4.4. Графический способ решения задачи ЦП

На рис. 4.4 приведен пример графического решения. Решение обычной ЗЛП позволило получить оптимальную вершину D {5,5; 1}.

Перемещая ЦФ до ближайшей целой координаты х в допустимой области, получаем решение задачи ЦП: точку С {5,1}.

В случае, если координат задачи ЦП больше двух, то графический способ неприемлем и рекомендуется использовать метод Гомори.

Его основная идея состоит в последовательном отсечении от допустимого множества решений нецелочисленной ЗЛП оптимальных нецелочисленных решений, содержащих точки с целыми координатами. Эти отсечения производятся включением в задачу дополнительных ограничений на переменные х .

Описание алгоритма Гомори.

• 1. С помощью симплекс-метода находим решение х ЗЛП без требования целочисленное™ переменных. Если все переменные х. целые, то задача решена. Иначе — шаг 2.
• 2. Среди нецелых элементов b_j, i =, m выбираем любой Ь_к, например с максимальной дробной частью.

По к-й строке симплекс-таблицы составляется дополнительное ограничение вида

В последней формуле т переменных j е своб. означает, что в системе т базисных переменных остальные переменные j = т + 1 … п — свободные.

Также в этой формуле принято обозначение целой [я] и дробной части {"} действительного числа а:

С помощью вспомогательной х_н+| > 0 переменной это ограничение представляется в виде равенства.

В симплекс-таблицу т вводится дополнительной (т + 1)-строкой с базисным элементом х"_+|:

где.

Так как Ь_п+1 <0, то такая симплекс-таблица перестает соответствовать допустимому базисному решению (опорному плану).

• 3. Для перехода к опорному плану производятся следующие операции:
  • а) строка с отрицательным свободным членом^{считается} разрешающей (на первом шаге к — н +1);
  • б) если все коэффициенты а_к > 0, то задача не имеет решения.

В противном случае номер / разрешающего столбца находится из условия.

в) совершаются преобразования симплекс-таблицы с опорным элементом а_к,. Если в новой симплекс-таблице по-прежнему есть хотя бы один отрицательный свободный член, то описанная процедура повторяется, начиная с пункта а), необходимое число раз.

Если все Ь.> 0, следовательно опорный план найден.

Надо отметить, что выбор опорного элемента а_к, гарантирует положительные значения приращений Д_; новой симплекс-таблицы. Поэтому найденный опорный план и является оптимальным.

4. Если найденное в пункте 3 решение ЗЛП удовлетворяет условию целочисленное™, то вычисления завершаются; если нет, то переходим к пункту 2.

Пример. Решить методом Гомори следующую задачу целочисленного программирования.

Введем переменные х₃, х₄ и запишем ЗЛП в каноническом виде. Так как все коэффициенты ограничений-равенств целочисленные, то целочисленность переменных х, х₂ влечет целочисленность переменных х₃, х₄. Поэтому задача полностью целочисленная и может быть использован метод Гомори (табл. 4.10).

Таблица 4.10.

Симплекс-таблица целочисленной задачи

Запишем последовательности опорных планов:

На втором шаге оптимальное решение найдено, но оно не удовлетворяет требованию целочислснности переменных. Поэтому в соответствии с (11) дополним симплекс-таблицу строкой и переменной х₅. Выполним преобразования пункта 3 алгоритма Гомори: а) строка с отрицательным свободным членом Ь_к{—½) считается разрешающей;

б) номер / разрешающего столбца находится из условия в) преобразование симплекс-таблицы с опорным элементом -1/42 приводит к тому, что все b_i. > 0, следовательно опорный план найден.

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