Первый алгоритм Гомори

3. Первый алгоритм Гомори

Следуя общей схеме методов отсечения, решим (£, C) – задачу (11, 12, 14), соответствующую (£^ц, C) – задаче (11–14). Пусть x(£, C) – ее оптимальное решение. Проанализируем координаты x(£, C) на целочисленность. Если все координаты вектора x(£, C) целые, то x(£, C) = x(£^ц, C). Если хотя бы одна координата, пусть x_i, будет нецелой, поступим следующим образом.

Обозначим через N совокупность небазисных переменных и на основании последней симплексной таблицы запишем разложение x_i по небазисным переменным x_i, jÎN

(16)

Так как x_i – нецелая величина, обозначим ближайшее целое число, не превосходящее x_i, через [x_i] и определим дробную часть: {x_i}= x_i- [x_i]. Очевидно, (x_i)>0.

Покажем, что по i-и строке симплексной таблицы (£, C) – задачи (в которой стоит нецелая координата решения) можно определить дополнительное линейное ограничение, обладающее свойствами правильности.

Теорема. Пусть - допустимое решение (£^ц, C) – задачи, тогда соотношения

, (17)

, - целое,

определяют правильное отсечение.

Доказательство.

Запишем выражение (16) в виде:

Используя для этого выражения формулу (17), получим:

или

На основании предположений теоремы о допустимости решения

(£^ц, C) – задачи x_i – целое. Величины [x_io], - целые по определению, следовательно, z_i – тоже целое.

Итак, z_i определенное формулой (17), целое. Докажем что . Доказательство будем вести от противного. Пусть .-

Это значит, что . По определению дробной части . По условию теоремы x – допустимое решение (£^ц, C) – задачи, поэтому . Следовательно,

Тогда должно выполняться:

Итак, из предположения отрицательности z_i, сразу же получаем  т.е. z_i – нецелое. Поскольку ранее было показано, что z_i, определенное формулой (17), является целым, то тем самым мы пришли к противоречию. Следовательно, предположение, что z_i < 0, неверное. Теорема доказана.

Следствие. Любое оптимальное решение x(£, C) (£, C) – задачи, не являющееся допустимым решением (£^ц, C) – задачи, не удовлетворяет условию правильного отсечения (17).

Доказательство. Пусть х (£, C) – оптимальное решение (£, C) – задачи, x_i0 – дробное.

Покажем, что х (£, C) не удовлетворяет условию отсечения. Поскольку план оптимален, все небазисные переменные x_i, для jÎN равны нулю. Поэтому . Учитывая это, подставим x_io в формулу (17):

z_i(x (£, C))= – {x_i0}+0<0,

что противоречит условию неотрицательности z_i. Следствие доказано.

Очевидно, что количество дополнительных ограничений будет нарастать по мере решения вспомогательных (£, C) – задач, оптимальные планы которых будут содержать нецелые координаты, т.е. возникает проблема размерности.

Р. Гомори предложил прием, позволяющий ограничить размеры рассматриваемых симплексных таблиц вспомогательных задач величиной (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_s1,…, 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_i0. Составим дополнительное линейное ограничение

(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), строка целевой функции в симплексной таблице учитывается при выборе строки для построения правильного отсечения;

2) справедливо одно из двух утверждений: либо целевая функция  ограничена снизу на С_o, либо задача (£^ц, C) имеет хотя бы один план х'.

Тогда первый алгоритм Гомори требует конечного числа больших итераций.

Похожие работы

Решения задачи планирования производства симплекс методом

Скачать

82416

8

19

... 0 505/103 0 792/103 669/103 500/103 Анализ Таблицы 6 позволяет сделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T. 3.4 Результат решения задачи планирования производства В результате решения поставленной задачи симплекс-методом получили набор производимой продукции x=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), который удовлетворяет всем ...

Методы исследования операций

Скачать

41740

5

1

... , 6)  сетевого планирования и управления, 7)  выбора маршрута, 8)  комбинированные. Из перечисленных выше методов математического программирования наиболее развитым и законченным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций. Линейное программирование Несмотря на требование линейности целевой функции и ограничений, в рамки линейного ...

Математические методы в экономике

Скачать

29780

1

3

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

Блочно-симметричные модели и методы проектирования систем обработки данных

Скачать

158931

0

1

... дискретного программирование для решения задач проектирование систем обработки данных. -  Сформулированы задачи диссертационного исследования. 2. БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ В данном разделе рассматриваются общая постановка блочно-симметричной задачи дискретного программирования, её особенности и свойства. Разработан общий подход решения задач ...