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

1) R=Rц – целочисленный многогранник;

2) Rц = £ц;

3) R* – множество опорных решений задачи (£ц, C) содержится в многограннике Rц.

Доказательство. Докажем, что R – целочисленный многогранник. По условию теоремы £ – многогранник, поэтому множество его целых точек (оно обозначено через £ц) конечно. Поскольку R – выпуклая линейная оболочка этого конечного множества точек, R – тоже многогранник.

По самому определению выпуклой линейной оболочки, она содержит все опорные планы множества, на которое она натянута, т.е. многогранник R содержит все целочисленные точки £ц. Поэтому R – целочисленный многогранник. Обозначим его через Rц. Первая часть теоремы доказана.

Докажем, что Rц совпадает с £ц. Так как R – выпуклая оболочка точек множества £ц, то £ц ÍRц.

Покажем, что справедливо также и противоположное неравенство–включение, т.е. RцÍ£ц. Для этого выберем некоторый произвольный элемент х°ÎRц. Поскольку Rц содержит все опорные решения задачи (£ц, C), то х° удовлетворяет условиям задачи (£ц, C), т.е. х°Î£ц. Но поскольку произвольный элемент из Rц принадлежит £ц, то очевидно, что справедливоRцÍ£ц. Сопоставляя противоположные включения RцÍ£ц и £цÍRц приходим к выводу: что £ц=Rц. Вторая часть теоремы также доказана.

Доказательство 3-го пункта теоремы является совершенно очевидным. Так как R* – множество опорных решений задачи (£ц, C), то R*Í£ц но £ц=Rц, поэтому R*ÍRц

Теорема доказана.

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

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

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

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

Алгоритм Р. Гомори состоит из следующих процедур:

1.  Решается (£, C) – задача, соответствующая исходной (£ц, C) – задаче.

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

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

При этом свойства, которыми должно обладать каждое из дополнительных ограничений при переходе от одной задачи к другой следующие:

1)  дополнительное ограничение должно быть линейным, чтобы оставаться в области применимости аппарата линейного программирования;

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

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

                     (15)

определяет правильное отсечение, если удовлетворяет

а) условию отсечения: x(£, C) удовлетворяет неравенству (15)

б) условию правильности: любое допустимое решение задачи (£ц, C), удовлетворяет неравенству (15).

Методы, основанные на использовании процедуры построения правильных отсечений, получили название методов отсечения.

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

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

Обозначим через 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 – число небазисных переменных ее. Этот прием основывается на том, что нас интересует дополнительное ограничение лишь как способ отсечения нецелочисленного оптимального решения вспомогательной задачи, полученной на данном шаге, и перехода к следующей задаче.

Страницы: 1, 2, 3, 4, 5, 6, 7