3. Первый алгоритм Гомори
Следуя общей схеме методов отсечения, решим (?, C) - задачу (11, 12, 14), соответствующую (?ц, C) - задаче (11-14). Пусть x(?, C) - ее оптимальное решение. Проанализируем координаты x(?, C) на целочисленность. Если все координаты вектора x(?, C) целые, то x(?, C) = x(?ц, C). Если хотя бы одна координата, пусть xi, будет нецелой, поступим следующим образом.
Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы запишем разложение xi по небазисным переменным xi, jN
(16)
Так как xi - нецелая величина, обозначим ближайшее целое число, не превосходящее xi, через [xi] и определим дробную часть: {xi}= xi - [xi]. Очевидно, (xi)>0.
Покажем, что по i-и строке симплексной таблицы (?, C) - задачи (в которой стоит нецелая координата решения) можно определить дополнительное линейное ограничение, обладающее свойствами правильности.
Теорема. Пусть - допустимое решение (?ц, C) - задачи, тогда соотношения
, (17)
, - целое,
определяют правильное отсечение.
Доказательство.
Запишем выражение (16) в виде:
Используя для этого выражения формулу (17), получим:
или
На основании предположений теоремы о допустимости решения
(?ц, C) - задачи xi - целое. Величины [xio], - целые по определению, следовательно, zi - тоже целое.
Итак, zi определенное формулой (17), целое. Докажем что . Доказательство будем вести от противного. Пусть .-
Это значит, что . По определению дробной части . По условию теоремы x - допустимое решение (?ц, C) - задачи, поэтому . Следовательно,
Тогда должно выполняться:
Итак, из предположения отрицательности zi, сразу же получаем т.е. zi - нецелое. Поскольку ранее было показано, что zi, определенное формулой (17), является целым, то тем самым мы пришли к противоречию. Следовательно, предположение, что zi < 0, неверное. Теорема доказана.
Следствие. Любое оптимальное решение x(?, C) (?, C) - задачи, не являющееся допустимым решением (?ц, C) - задачи, не удовлетворяет условию правильного отсечения (17).
Доказательство. Пусть х (?, C) - оптимальное решение (?, C) - задачи, xi0 - дробное.
Покажем, что х (?, C) не удовлетворяет условию отсечения. Поскольку план оптимален, все небазисные переменные xi, для jN равны нулю. Поэтому . Учитывая это, подставим xio в формулу (17):
zi(x (?, C))= - {xi0}+0<0,
что противоречит условию неотрицательности zi. Следствие доказано.
Очевидно, что количество дополнительных ограничений будет нарастать по мере решения вспомогательных (?, C) - задач, оптимальные планы которых будут содержать нецелые координаты, т.е. возникает проблема размерности.
Р. Гомори предложил прием, позволяющий ограничить размеры рассматриваемых симплексных таблиц вспомогательных задач величиной (n+2) (k+1), где n - количество переменных (?, C) - задачи, k - число небазисных переменных ее. Этот прием основывается на том, что нас интересует дополнительное ограничение лишь как способ отсечения нецелочисленного оптимального решения вспомогательной задачи, полученной на данном шаге, и перехода к следующей задаче.
Последовательность (?, C) - задач пометим индексом k=0,1,…, соответствующим номеру итерации в последовательном приближении к решению исходной (?ц, C) - задачи, и обозначим (?k, C). При этом (?0, C) - задача соответствует (?, C) - задаче (задаче без требования целочисленности).
Переменную zi, которая определяется дополнительным линейным ограничением (7) и строится по некоторой нецелочисленной координате оптимального решения (?k, C) - задачи (k =0, 1, 2,…) обозначим xn+k+l.
Чтобы размерность последовательности (?k, C) - задач не возрастала, вычеркнем из симплекс-таблицы переменную, по которой построено дополнительное линейное ограничение.
После сделанных замечаний перейдем непосредственно к изложению вычислительной схемы.
1. Решим (?k, C) - задачу (вначале k = 0) методом последовательного улучшения плана.
Пусть в базис оптимального решения вошли векторы As1,…, Asm. Параметры последней симплексной таблицы обозначим через xij:
.
Если, все базисные составляющие оптимального решения x(?k, C) (?k, C) - задачи целые, то x(?k, C) = x(?ц, C). Если некоторая координата xio оптимального решения x(?k, C) нецелая, то перейдем к п. 2.
2. Если среди совокупности координат оптимального решения x(?k, C) имеется единственная нецелая координата, то дополнительное линейное ограничение (17) строится по этой координате. Если нецелых координат в x(?k, C) более одной, то выберем координату с наименьшим номером. Пусть ею оказалась xi0. Составим дополнительное линейное ограничение
(18)
(19)
3. Добавим условия (18, 19) к условиям (?k, C) - задачи. Получим новую (?k+1, C) - задачу. Так как оптимальное решение x(?k, C) (?k, C) - задачи определяло одну из вершин многогранника условий, то оно может быть выбрано в качестве первоначального опорного решения для вновь полученной задачи. А это означает, что последнюю симплексную таблицу (?k, C) - задачи можно взять в качестве исходной для (?k+1, C) - задачи, дополнив ее условием (18).
Итак, симплексная таблица для (?k+1, C) - задачи получается из последней симплексной таблицы для (?k, C) - задачи путем окаймления (i+1) - й строкой с элементами:
где - небазисные переменные (?k, C) задачи.
Получим новую задачу, переменными которой являются . Условия этой задачи разрешены относительно xsl,…, xsm переменных и новой переменной xn+k+1, а линейная форма выражена через небазисные переменные (?k, C) - задачи. Так как мы занимаемся максимизацией F(x) и решение х* для (?k, C) - задачи оптимально, то все i > 0. Поэтому процесс перехода к новому решению (?k+1, C) - задачи не может быть осуществлен по методу уточнения плана. В то же время и поэтому вектор А0 симплексной таблицы не является опорным решением для (?k+1, C) - задачи, так как решением называется вектор, все координаты которого неотрицательны и удовлетворяют условию принадлежности области ?k+l. Поэтому назовем полученный вектор псевдорешением задачи (?k+1, C) и перейдем к дальнейшему преобразованию симплекс-таблицы.
Обозначим через k номер псевдорешения (?k, C) - задачи; тогда направляющей строкой является i+k+1-я строка, k =0, 1, 2,…. Поэтому на каждом этапе преобразования таблицы вектор Ai+k+i будет выводиться из таблицы. Можно доказать, что через конечное число шагов либо будет найдено целочисленное решение, либо будет обнаружена ее неразрешимость, а тем самым неразрешимость (?ц, C) - задачи.
Если решение (?k, C) - задачи завершается построением оптимального целочисленного решения x*, то m, первых его компонент определяют решение целочисленной задачи; если среди координат х* есть дробные, то одна из дробных компонент (ранее определенным правилом) порождает дополнительное ограничение и процесс решения должен быть продолжен с новой окаймляющей строкой. Строка, используемая ранее для окаймления, вычеркивается и больше для построения расширенных задач не восстанавливается.
Процедуру решения (?k, C) - задачи (k=0, 1,…) и анализа полученного решения назовем большой итерацией. Номер большой итерации совпадает с номером решаемой (?k, C) - задачи.
Результатом большой итерации является переход к новой (?k+1, C) - задаче либо окончание решения задачи.
Сделаем некоторые пояснения к блок-схеме алгоритма.
Введем: 1) ячейку i, в которой будем запоминать номер строки, на основании которой строится очередное дополнительное линейное ограничение, 2) счетчик r, соответствующий номеру проводимой большой итерации. Обозначим x*(?r, C) оптимальное решение (?r, C) - задачи. Заметим, что обозначение (?r, C) - задача, эквивалентное (?r, C), введено в блок-схеме для удобства записи.
При некоторых условиях удается доказать теорему о конечности первого алгоритма Гомори, которую мы приведем без доказательства.
Теорема. Пусть множество оптимальных планов задачи (?0, C) ограничено и выполняются следующие условия:
1) сi - целые коэффициенты целевой функции F(x) (i =1,2,…, n), строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;
2) справедливо одно из двух утверждений: либо целевая функция ограничена снизу на Сo, либо задача (?ц, C) имеет хотя бы один план х.
Тогда первый алгоритм Гомори требует конечного числа больших итераций.