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