Методы отсечения

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

(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, для jÎN равны нулю. Поэтому . Учитывая это, подставим 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) – задачи оптимально, то все Di > 0. Поэтому процесс перехода к новому решению (£k+1, C) – задачи не может быть осуществлен по методу уточнения плана. В то же время и поэтому вектор А0 симплексной таблицы не является опорным решением для (£k+1, C) – задачи, так как решением называется вектор, все координаты которого неотрицательны и удовлетворяют условию принадлежности области £k+l. Поэтому назовем полученный вектор псевдорешением задачи (£k+1, C) и перейдем к дальнейшему преобразованию симплекс-таблицы.

 Скачать реферат