Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 66
Текст из файла (страница 66)
Лемма !4,1, Если отсечение (!4.1!) добавлямпся к оптинальной таблице задачи ЛП, то никакие целочисленные допустимые точки не исключаются и новая таблица является базисной, недопустимой относительно прямой задачи, если у,о не целочисленно, и допустимой относительно двойственной задачи.
Гл, 14. Ллеоришм отеекоюигеа плоскосюи Доказательство. То, что добавление (14.11) не исключает целочисленных допустимых точек, вытекает из того факта, что это отсечение явилось следствием ограничений на целочисленность из исходной задачи ЦЛП. Новая переменная недостатка з является норгосебиге ДРОБНАЯ ДВОЙСТВЕННАЯ Ьей1 п решить ослабление задачи ЦЛП, получив оптимальное решение х*; допусм имо.
="да"; мьие х" не иелочисленно и допусшомо="да" до Ьей!п выбрать производящую строку г; добавить порожденное отсечение Гомори и соответствующую базис. ную переменную з; применить двойственный симплеис-алгоритм; и двойственная задача неограниченна гьеп допустггмо:="нет", положить х' равным новому оптимуму епд епб Рис.
!4,3. Дробный двойственный алгоритм для задачи ЦЛП. (14, 12) (14.13) (14. 14) (14.15) гпах х„ Зх, +2х, <б, — Зх;+2х, (О, х ) О целочисленно. На рис. 14.4 показаны эти ограничения на плоскости с координатамн х, и х,. Выбранная задача очень проста и имеет целочисленный вой базисной переменной и вместе с оптимальным базисом 93 образует новый базис. Если д;„не целочислепно, то)ы)О и, следовательно, базисное решение содержит в= — )со откуда следует, что оно недопустимо относительно прямой задачи. Оно остается допустимым относительно двойственной задачи, так как нулевая строка не изменяется. Теперь должно быть ясно, как продолжать этот процесс.
Если дана таблица с базисным решением, которое недопустимо относительно прямой задачи и допустимо относительно двойственной задачи, то наиболее естественно применить двойственный симплекс- алгоритм, описанный в 5 3.6. Одно или более замешений либо приведут к новому непрерывному оптимуму, либо укажут, что прямая задача недопустима. Эта последняя возможность должна означать, что в исходной задаче ЦЛП не было целочисленных допустимых точек. На рис. 14.3 приведен набросок описанного алгоритма, обычно называемого дробным двойспгвенным алеорггпгмом, поскольку в используемой таблице имеются дробные элементы и сохраняется допустимость относительно двойственной задачи.
Рассмотрим полностью работу этого алгоритма на примере. Пример 14.2. Рассмотрим задачу ЦЛП !4.б Отсечение Гомера" 34! оптимум в точке х=(1, !). Добавляя переменные недостатка х, и х„получаем таблицу в стандартной форме для задачи, являющейся ослаблением данной задачи: х! ха хз хч (14.16) После двух замещений получается оптимальная таблица; (14.17) х! ха = соответствующая решению х-=(1, 3(2) и стоимостн г= — х,= — 3!2, что проиллюстрировано иа рис. !4.4. Поскольку решение ослаблен- ха о О О 1 2 3 х, Рис. !4,4. Решение ослабленной задачи !(ЛП из оримера !4.2. ной задачи не целочисленно, порождаем отсечение. Нулевое уравнение имеет вид з+ ха+4 хе 2 ! ! 3 а (14.)В) Гл.
14. Алгораигм отсеиающса илоасосшн что приводит к отсечению ! ! ! 4 ха+ 4 хе ~ ~2. (14.19) Подставляя сюда вместо х, и хе ограничения из таблицы (14.16), получаем, что это неравенство эквивалентно неравенству ха<1, (14.20) представленному на рис. !4.5 как первое отсечение, хз 3 О О 3 Х! Рис !4.5. Решение задачи ЦЛП с помощью двух отсечений. Если бы мы выбрали в качестве производящей первую или втс рую строку, то получили бы соответственно отсечение ! 1 о хз — -о х, в 0 (14. 21) или ! 1 1 — х,+ — х ) —.
4 4 " 2' (14.22) Первое из этих неравенств эквивалентно нерзвенству х~ (1, (14,23) а второе совпадает с неравенством, полученным выше из нулевой строки. !4.!. Оигеегение Гамори Выбирая в качестве производящей строки строку О, добавляем к таблице (14.17) уравнение ! ! 1 — хг — х +з~= — —, (14.24) в результате чего получаем х~ хг хг кг гг хг = кг = ег (! 4.25) Производя двойственное замещение относительно указанного веду- щего элемента, получим вторую оптимальную таблицу (14.26) хг = хг = хг ~ которое эквивалентно отсечению х,)хгс Добавляя к таблице (14.26) соответствующую строку 2 2 2 — — х — — 3;+з = —— Згзг+гЗ (14.281 (14,29) и еще раз проводя оптимизацию с помогцью двойственного симплекс- алгоритма, приходим к заключительной оптимальной таблице хг хг хг кг гг ег (14.30) хг хг хг = хг =- которой соответствует второй оптимум х=(2!3, !), все еще не являющнйся целочисленным.
Нулевая строка целочисленна н поэтому порождает тривиальное отсечение. Первая строка порождает отсечение 2 2 2 3 4+3 ! Зг (14.27) Гл. 44. Алгоритм отсекающие плоскости соответствующей решению х=(1, 1), как показано на рис. !4.5.С) Нам нужно теперь рассмотреть вопрос о конечности процедуры: откуда известно, что эта процедура после конечного числа шагов останавливается, выдавая целочисленное решение? Однако сначала изучим один метод борьбы с вырожденностью, что очен важно при анализе многих алгоритмов для задачи ЦЛП, основанных на симплекс-методе. 4 4.2 Лексикографическое упорядочение Метод Блэнда, обеспечивающий конечность симплекс-алгоритма (см. 3 2.7), является относительно недавним изобретением в истории линейного программирования.
Классический же метод основан на лексикографическом упорядочении векторов таблицы, для описания которого нам потребуется следующее определение. Определение 14.2. Ненулевой вектор о б 1то называется лексиквграфически положительным, если первая его ненулевая компонента больше нуля - Если о=О, будем говорить, что о лексикографически равен нулю, и о будем называть лексикографически отрицательным, если вектор — и лексикографически положителен. Эти условия можно запясать соответственно в виде о)0, о=О, о<0. Будем говорить, что вектор о Е ссо лексикографически больше, чем сс Е !т" (и писать и)си), тогда и только тогда, когда вектор о — си лексикографически положителен; аналогично можно определить отношения лексикографически меньше и лексикографически равно. Термины лексикографически минимально (!ех-ппп) и лексикографически максимально ()ех-гпах) также определяются очевидным образом.
Д Пример !4.3. со! (О, О, 1, 0) ) со! (О, О, О, 2), со!(0, 3, 1, 2) < со!(1, 2, 4, 8). Пример 14.4. Сопоставим буквам а, Ь, с,... числа 1, 2, З,.„и отсутствию буквы сопоставим О. Тогда каждое слово можно представить как вектор в 2", где и — некоторое число, большее, чем длина любого слова. При этом лексикографическое упорядочение векторов, кодирующих слова, в точности соответствует упорядочению слов, используемому в словарях. Например, Ьад со! (2, 1, 4, О, О, О, ...1, ноод со)(7, 15, !5, 4, О, О, О, ...), !4.е. Декоикоерафичеокое уаорядочекие поэтому при нашем кодировании Ьад к поод.
Отметим также, что Ьад < Ьабе. П Идея состоит в том, чтобы разрешать неоднозначности в симплекс- алгоритме, используя лексикографический критерий. Таким образом, когда в прямом симплекс-алгоритме мы приходим к выбору строки по правилу [ъ~ '~е (14,3!) мы разрешаем неоднозначности, используя критерий )ех-ппп ~ — '~, па,,> о Ье (14.32) где, как обычно, а,— вектор, составленный из чисел, стоящих в 1-й строке таблицы.
Когда не возникает неоднозначностей, то это эквивалентно (14.31), так как в этом случае выбор ведущей строки будет определяться первой компонентой пм вектора а,. Однако, в случае когда имеется неопределенность, критерий (14.32) будет основывать решение на первой компоненте, для которой не возникает неопределенностей. Пример 14.5. Для приведенной ниже части таблицы ! получаем а„ /! 1 3 аее ( 4 ' $ 4 †' = со! (2, 1, 10, 1, ...), ае поэтому операция нахождения лексикографического минимума (14.32) разрешит неопределенность между строками 1 и 3, выбрав строку 3 С) Заметим, что в произвольной задаче ЛП этот выбор лексикографического минимума будет однозначен, поскольку никакие две строки не будут пропорциональны.
(Почемур) Основное приложение описанных понятий к ЛП можно сформулировать в виде следующей теоремы, которая дает отличный от правила Блэнда способ устранения зацикливания. Гл. г4. Алгоритм отсекаютей плоскости !ех-пнп Я пас ) о счл <14.ЗЗ) Доказательство. Проверим вначале, что строки а,, Г= 1, ..., т, остаются лексикографически положительными после замещения. В «-й строке получаем а, =а,~а„, где а„> О.
Поэтому а, ) О, если а,>0, Если с'Ф«и асл>О,то а, а, ! а; а, 1 а =а — — =а 1 — — — 1>0 ! — го 1 а, |а; агг) согласно лексикографическому выбору. Наконец, если 1чь« и ам<0, то )а 1а огг гг поэтому а, действительно остается лексикографически положительным после каждого замещения. Вектор а, при замегцении переходит в а,=а,— — =а,+ ) а„ погас ! аог ~ аг а.г гг так как а„(0 и а,)0 по условию. Таким образом, нулевая строка строго лексикографически возрастает и, следовательно, никогда не может вернуться к предыдущему значению при выполнении замещений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
