Курсовая работа: Методы отсечения

Р. Гомори предложил прием, позволяющий ограничить размеры рассматриваемых симплексных таблиц вспомогательных задач величиной (n+2) (k+1), где n – количество переменных (£, C) – задачи, k – число небазисных переменных ее. Этот прием основывается на том, что нас интересует дополнительное ограничение лишь как способ отсечения нецелочисленного оптимального решения вспомогательной задачи, полученной на данном шаге, и перехода к следующей задаче.

Последовательность (£, C) – задач пометим индексом k=0,1,…, соответствующим номеру итерации в последовательном приближении к решению исходной (£^ц , C) – задачи, и обозначим (£_k , C). При этом (£₀ , C) – задача соответствует (£, C) – задаче (задаче без требования целочисленности).

Переменную z_i , которая определяется дополнительным линейным ограничением (7) и строится по некоторой нецелочисленной координате оптимального решения (£_k , C) – задачи (k =0, 1, 2,…) обозначим x_{n + k + l} .

Чтобы размерность последовательности (£_k , C) – задач не возрастала, вычеркнем из симплекс-таблицы переменную, по которой построено дополнительное линейное ограничение.

После сделанных замечаний перейдем непосредственно к изложению вычислительной схемы.

1 . Решим (£_k , C) – задачу (вначале k = 0) методом последовательного улучшения плана.

Пусть в базис оптимального решения вошли векторы A_{s 1} ,…, A_sm . Параметры последней симплексной таблицы обозначим через x_ij :

.

Если, все базисные составляющие оптимального решения x(£_k , C) (£_k , C) – задачи целые, то x(£_k , C) = x(£^ц , C). Если некоторая координата x_io оптимального решения x(£_k , C) нецелая, то перейдем к п. 2.

2 . Если среди совокупности координат оптимального решения x(£_k , C) имеется единственная нецелая координата, то дополнительное линейное ограничение (17) строится по этой координате. Если нецелых координат в x(£_k , C) более одной, то выберем координату с наименьшим номером. Пусть ею оказалась x_{i 0} . Составим дополнительное линейное ограничение

(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) задачи.

Получим новую задачу, переменными которой являются . Условия этой задачи разрешены относительно x_sl ,…, x_sm переменных и новой переменной x_{n + k +1} , а линейная форма выражена через небазисные переменные (£_k , C) – задачи. Так как мы занимаемся максимизацией F(x) и решение х* для (£_k , C) – задачи оптимально, то все D_i > 0. Поэтому процесс перехода к новому решению (£_{k +1} , C) – задачи не может быть осуществлен по методу уточнения плана. В то же время и поэтому вектор А₀ симплексной таблицы не является опорным решением для (£_{k +1} , C) – задачи, так как решением называется вектор, все координаты которого неотрицательны и удовлетворяют условию принадлежности области £_{k + l} . Поэтому назовем полученный вектор псевдорешением задачи (£_{k +1} , C) и перейдем к дальнейшему преобразованию симплекс-таблицы.

Обозначим через k номер псевдорешения (£_k , C) – задачи; тогда направляющей строкой является i+k+1-я строка, k =0, 1, 2,…. Поэтому на каждом этапе преобразования таблицы вектор A_{i + 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), введено в блок-схеме для удобства записи.

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

Теорема. Пусть множество оптимальных планов задачи (£₀ , C) ограничено и выполняются следующие условия:

1) с_i – целые коэффициенты целевой функции F(x) (i =1,2,…, n), строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;