Первый алгоритм Гомори (аддитивный)

Идея: задача решается симплекс-методом «с ослабленными ограничениями» (без условия целочисленности на переменные). Затем подбирается дополнительное линейное ограничение, обеспечивающее за конечное число шагов получение оптимального целочисленного решения или установление факта его отсутствия.

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

В выпуклой оболочке все угловые точки имеют только целочисленные координаты, но из-за трудности ее построения оболочки строится «промежуточный» многогранник, охватывающий всю целостную оболочку; полностью содержащийся в области допустимых решений, угловые точки которого содержат хотя бы одну целочисленную координату.

Такое построение осуществляется путем введения на каждом шаге дополнительного линейного ограничения, который уменьшает исходный многогранник решения путем отсечения от него некоторой части, при этом не исключая ни одного целочисленного решения.

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

Для изложения вводим следующие понятия:

Пусть а - действительное число. Целой частью числа а – [a] – есть максимальное целое, не превосходящее данного числа. Дробная часть числа а – q_a- разность между числом и его целой частью: q_a= а-[a]; 0≤ q_a≤1

Основным понятием в методе отсечения является понятие «правильного отсечения».

Определение: пусть Х^*- оптимальный нецелочисленный план (ослабленной задачи). Неравенство a х<b называется правильным отсечением (отсечением Гомори), если оно удовлетворяет следующим условиям:

1. условие отсечения: Х^* не удовлетворяет этому ограничению a х^*≥b

2. условие правильности: для всякого произвольного целочисленного плана Х` a Х<sup>`</sup><b

Необходимым условием применения первого алгоритма Гомори (аддитивного) является целочисленность всех коэффициентов и элементов правых частей.

 

Алгоритм Гомори состоит из двух шагов:

1. Решается ослабленная задача симплекс-методом. Если оптимальный план целочисленный, то он является решением исходной задачи, в противном случае переходим к пункту № 2.

2. Вводится дополнительное линейное ограничение - правильное отсечение и переходим к пункту № 1, решая ослабленную задачу с дополнительным ограничением.

Процесс присоединения дополнительных ограничений продолжается до тех пор, пока:

· Либо не будет найдено целочисленное решение задачи

· Либо не будет установлено, что такого решения нет.

Условие неразрешимости целочисленной задачи:

Это возможно, если для дробного значения переменной задачи x_j (которая не является недобавочной, неизбыточной переменной) все коэффициенты a_ij в данной строке симплекс-таблицы оптимального решения окажутся не целыми.

Схема алгоритма

1. Пусть в результате решения ослабленной задачи получен оптимальный план, имеющий хотя бы одну нецелочисленную компоненту.

Замечание: 1-й алгоритм Гомори решает только полностью целочис­ленные задачи, поэтому результатом его решения может быть опти­мальный план только с целочисленными компонентами.

2. В симплекс-таблице оптимального решения выбираем значение базисной переменной задачи Х^*_j с наибольшей дробной частью. Если таких переменных несколько, то выбираем любую.

Этой переменной соответствует строка симплекс-таблицы, на­зываемая строкой, производящей отсечение (производящей стро­кой).

Выписывается уравнение

(полагая, что первые m перемен­ных базисные для данного оптимального решения).

На основании этой строки, предполагаем, что m первые перемен­ные являются базисными, и т.к. коэффициенты целевой функции - целые числа, то зна­чение целевой функции на целочисленном решении также должно быть целочисленно.

Представим каждый коэффициент данной строки в виде целой и дробной частей.

Тогда 0<q_j<1

0≤q_j<1

q_j - положительная дробь

q_ij - неотрицательная дробь

Переносим все целые части коэффициентов в одну сторону, ос­тавляя все дробные в другой:

Так как все переменные x_m+1,...,x_n принимают целочисленные значения и силу их небазисности, то правая часть уравнения является целочисленной. Сле­довательно, в силу неотрицательности дробных частей и переменных зада­чи и левая часть должна быть неотрицательна:

, следовательно,

Так как q_j<1, заменяя в правой части q_j, получим строгое нера­венство

Так как левая часть неравенства должна принимать целые зна­чения, то, следовательно, необходимое условие ее целочисленности можно записать только в следующем виде:

Вводя остаточную переменную S_j (переменную Гомори), получим

Где S_j – неотрицательная добавочная переменная, которая по определению должна принимать целочисленное значение, что для данной системы ограничений при x_j=0 имеет вид:

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

Вывод: строится ограничение, которому не удовлетворяет оптимальный нецелочисленный план. Следовательно, надо решить задачу с исходной целевой функцией и расширенной системой ограничений.

 

Метод ветвей и границ.

Идея метода: пусть решена задача без условия целочисленности и х^*_r – целочисленная переменная, значение которой в оптимальном плане является дробным. Тогда интервал [х^*_r]< х _r<[х^*_r]+1 не содержит допустимых решений с целочисленной координатой х_r. Следовательно, допустимое решение с целочисленной координатой х_r удовлетворяет одному из следующих условий: [ х _r≤[х^*_r] или х _r≥[х^*_r]+1.

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

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

Геометрическая интерпретация:

Вырезаем «полосу», не содержащую решение с целочисленной координатой х₁. Затем решаем каждую из подзадач. Если полученный оптимум окажется допустимым для целочисленной задачи, то значение его фиксируется как наилучшее, и при этом нет необходимости продолжать ветвление данной подзадачи. В противном случае подзадача, в свою очередь, разбивается на две подзадачи при условие целочисленности значений, которые в оптимальном плане не оказались целыми. Как только полученное допустимое целочисленное решение одной из подзадач окажется лучше имеющегося, то одно фиксируется вместо зафиксированного ранее.

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

Эффективность вычислительной схемы существенно повышается с введением понятия «граница», на основе которого делается вывод о необходимости дальнейшего разбиения каждой из подзадач.

Суть: если оптимальное решение подзадачи без условия целочисленности обеспечивает худшее значение целевой функции, чем имеющееся ранее, то подзадача далее не рассматривается, и говорят, что она прозондированна, и ее можно вычеркнуть из списка подзадач, порожденных исходной задачей. Другими словами, как только получено допустимое целочисленное решение, соответствующее значение целевой функции может быть использовано в качестве верхней (в случае минимизации) или нижней (в случае максимизации) границы, наличие которой позволяет формализовать процедуру исключения прозондированных задач. Этот метод позволяет решать как полностью, так и частично целочисленные задачи.