Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 201
Текст из файла (страница 201)
Исходная задача содержит только переменные хы хг и хз, поэтому оптимальное решение имеет вид х4 = 8, хг = 4 и хз = 0 с целевым значением (3 8) +(1 4) +(2 0) = 28. Заметим, что значения вспомогательных переменных в окончательном решении показывают, насколько велик резерв в каждом неравенстве. Вспомогательная переменная х4 равна 18, а значение левой части в неравенстве (29.54) равно 8+ 4+ 0 = 12, что на 18 меньше, чем значение правой части этого неравенства— 30. Вспомогательные переменные хб и хб равны нулю, и действительно, в неравенствах (29.55) и (29.56) левые и правые части равны. Обратите внимание на то, Часть ГИ. Иэбрааиые темы что, даже если коэффициенты исходной канонической формы являются целочисленными, коэффициенты последующих эквивалентных задач не обязательно целочисленны, как не обязательно целочисленны и промежуточные решения. Более того, окончательное решение задачи линейного программирования также не обязательно будет целочисленным; в данном примере это не более чем совпадение.
Замещение Формализуем процедуру замещения. Процедура Рвот получает в качестве входных данных каноническую форму задачи линейною программирования, заданную кортежем (Ю, В, А, 6, с, с), индекс 1 выводимой переменной х~ и индекс е вводимой переменной х,. Она возвращает кортеж (М, В, А, 6, с, В), описывающий новую каноническую форму. (Еще раз напомним, что элементы матриц А и А, имеющих размер иэ х и, являются числами, обратными коэффициентам канонической формы.) Р1чот(Х, В, А,6, с, с,1, е) 1 // Вычисление коэффициентов уравнения для новой // базисной переменной х,.
2 Пусть А — новая матрица размером т х п 3 Ь, = Ь!/ам 4 гвг каждого .1 6 ээ' — те) 5 аез = аб/аде 6 ае~ = 1/ам 7 // Вычисление коэффициентов остальных ограничений. 8 1вг каждого э Š — 11) 9 6э = Ьэ — аэеЬе 10 гвг каждого з е М вЂ” (е) !1 а; = а; — аеаэ 12 аа = — аэеае[ 13 // Вычисление целевой функции.
14 В= и+с,Ь, 15 1вг каждого 7' 6 Ж вЂ” 1е) 16 ст — — сэ — сеает !7 с! = — сеае~ 18 // Вычисление новых множеств базисных // и небазисных переменных. 19 Х = )э' — (е) 01Ц 20 В =  — Я 'ь.э 1е1 21 ге1пгп ()э', В, А, Ь, сс В) Процедура Р[чот работает следующим образом. В строках 3-6 вычисляются коэффициенты нового уравнения для х,; для этого уравнение, в левой части которого стоит хь переписывается так, чтобы в левой части оказалась х,.
В строках 7 — 11 оставшиеся уравнения обновляются путем подстановки правой части 9В Гнева 29. Линейное лрограчиироеание полученного нового уравнения вместо всех вхождений хе. В строках 8-12 такая же подстановка выполняется для целевой функции, а в строках 14 — 17 обновляются множества небазисных и базисных переменных. Строка 21 возвращает новую каноническую форму. Если ам = О, вызов процедуры Р[уот приведет к ошибке (деление на нуль)„однако, как будет показано в ходе доказательства лемм 29.2 и 29.12, данная процедура вызывается только тогда, югда ам ф О. Рассмотрим, как процедура Р!чот действует на значения переменных базисного решения. Лемма 29Л Рассмотрим вызов Р!чот(Аг, В, А, 6, с, с,1, е), в котором аы зй О.
Пусть значения, возвращаемые вызовом, представляют собой (М, В, А, Ь, с, В) и пусть х обозначает базисное решение после выполнения вызова. Тогда !. х = О для каждого З Е У; 2. хе = 6!/а~е,' 3. х; = 6, — а„Ь, для каждого 1 Š — (е). Доказвшельсягво. Первое утверждение верно, поскольку в базисном решении все небазисные переменные задаются равными нулю. Если мы приравняем нулю все небазисные переменные в ограничении х, = 6, — ~~~ абхз, зер? то получим, что х, = Ь; для каждого 1 е В.
Поскольку е Е В, строка 3 процедуры Р1уОТ дает хе = Ье = Ь!/а!е ~ что доказывает второе утверждение. Аналогично, используя строку 9 для каждого!1 Š — (е), мы имеем х,=Ь,=Ьй — аееЬе ~ что доказывает третье утверждение. Формальный симплекс-алгоритм Теперь мы готовы формализовать симплекс-алгоритм, юторый уже продемонстрировали на примере. Этот пример был очень удачным, однаю еще необходимо ответить на следующие вопросы. Как определить, что задача линейного программирования является разреши- мой? Что делать, если задача линейного программирования является разрешимой, однако начальное базисное решение не является допустимым? 9!е Часть еП.
Иедеанаые темы Как определить, что задача линейного программирования является неограни- ченной? ° Как выбирать вводимую и выводимую переменные? В разделе 29.5 мы покажем, как определить, является ли задача разрешимой и, в случае положительного ответа, как найти каноническую форму, в которой начальное базисное решение является допустимым. На данном этапе предположим, что имеется процедура 1М1т1АЕ1ЕЕ-Я1МРЕЕХ(А, Ь, с), которая получает на входе задачу линейного программирования в стандартной форме, т.е. матрицу А = (аб) размером т х п, т-мерный вектор 6 = (6;) и и-мерный вектор с = (с ).
Если задача неразрешима, процедура возвращает соответствующее сообщение и завершается. В противном случае она возвращает каноническую форму, начальное базисное решение которой является допустимым. Процедура 81МРеех получает на входе задачу линейного программирования в стандартной форме, описанной выше. Она возвращает и-мерный вектор х = (х ), который является оптимальным решением задачи линейного программирования, заданной формулами (29.19)-(29.21).
81МРЕЕХ(А, Ь, с) 1 (Л,В,А,Ь,с,с) = 1т!Т1АЕ1ЕЕ-Б1МРЕЕХ(А,Ь,с) 2 Пусть Ь вЂ” новый вектор длиной т 3 этййе с; > О для некоторого индекса 9 е 1Ч 4 Выбрать индекс е Е 1Ч, для которого с, > О 5 1ог каждого индекса 1 Е В 6 Иаье >О 7 сь, = 6,/а„ 8 е1яе сз, = оо 9 Выбрать индекс 1 е В, который минимизирует Ь| 10 ИЬ| == оо 11 гетцгп "задача неограниченная" 12 е1ае (1Ч,В,А,Ь,с,с) = Р1чот(?Ч,В,А,Ь,с,и,1,е) 13 Еогз = 1топ 14 юг ЕВ 15 х;=6; 16 е1зех; = О 17 ГЕтцГП (ХЫ Хг,..., Ха) Процедура 31МРЕЕХ работает следующим образом.
В строке 1 выполняется вызов упомянутой выше процедуры 1ьпт1Аиее-б~мгеех(А, Ь, с), которая нли определяет„что предложенная задача неразрешима, илн возвращает каноническую форму, базисное решение которой является допустимым. Главная часть алгоритма содержится в цикле эчЫ!е в строках 3 — 12. Если все коэффициенты целевой функции отрицательны, цикл иЫ1е завершается. В противном случае в строке 4 мы выбираем в качестве вводимой переменной некоторую переменную х„коэффициент при которой в целевой функции положителен. Хотя в качестве вводимой можно выбирать любую такую переменную, предполагается, что 913 Глава 2д Лииейиое ороерамиироеаиие используется неюе предварительно заданное детерминистическое правило. Затем, в строках 5-9, выполняется проверка каждого ограничения и выбирается то, которое более всего лимитирует величину увеличения к„не приводящего к нарушению ограничений неотрицательности; базисная переменная, связанная с этим ограничением, выбирается в качестве выводимой переменной хь Если таких переменных несколько, можно выбрать любую из них, однако предполагается, что и здесь мы используем некое предварительно заданное детерминистическое правило.
Если ни одно из ограничений не лимитирует возможносп увеличения вводимой переменной, алгоритм выдает сообщение "задача неограниченная'* (строка 11). В противном случае в строке 12 роли вводимой и выводимой переменных меняются путем вызова описанной выше процедуры Р!тот(Ь1, В, А, Ь, с, и, 1, е). В строках ! 3-16 вычисляется решение йы йз,..., кв исходной задачи линейного программирования путем присваивания всем небазисным переменным нулевого значения, всем базисным переменным й, — соответствующих значений Ь;, а строка 17 возвращает эти значения. Чтобы показать, что процедура Б!мреех работает юрректно, сначала покажем, что если в процедуре задано начальное допустимое значение и она завершилась, то при этом или возвращается допустимое решение, или сообщается, что данная задача является неограниченной.
Затем мы покажем, что процедура Я!мреех завершается; н наконец, в разделе 294 (теорема 29.10), будет показано, что возвращаемое процедурой решение является оптимальным. Лемма 29.2 Пусть задана задача линейного программирования (А, Ь, с); предположим, что вызываемая в строке 1 процедуры б!мреех процедура 1н!т!ле!ее-Б!мреех возвращает каноническую форму, базисное решение которой является допустимым.
Тогда если процедура Б!мреех возвращает решение в строке 17, это решение является допустимым решением задачи линейного программирования. Если процедура Б!мреех выводит сообщение о неограниченности в строке 11, данная задача линейного программирования является неограниченной. Доказааеельсгава. Воспользуемся следующим тройным ннварнантом цикла: в начаче каждой итерации цикла иеййе в строках 3-12 1. имеющаяся каноническая форма эквивалентна канонической форме, полученной в результате вызова процедуры 1и!т!ле!ге-Я!мреех; 2. для всех 1 Е В выполняется Ь, ) 0; 3. базисное решение, связанное с данной канонической формой, является допустимым. Инициализации. Эквивалентность канонических форм для первой итерации очевидна. В формулировке леммы предполагается, что вызов процедуры 1м!т!ле!ге-Я[мреех в строке 1 процедуры Б!МРеех возвращает каноническую форму, базисное решение которой является допустимым. Следовательно, третье утверждение справедливо.
Далее, поскольку в базисном решении каж- Чаеесь 971. Избранные есемы 914 дой базисной переменной х, присваивается значение Ьь а допустимость базисного решения предполагает неотрицательность всех базисных переменных хс, то Ь, > О. Таким образом, второе утверждение инварианта также справедливо. Ь; = Ьс — ас,Ь, (согласно строке 9 процедуры Рсчот) = Ьс — а;,(Ьс/ас,) (согласно строке 3 процедуры Рсчот) (29.76) Необходимо рассмотреть два случая; ас, > О и а„< О. Если ам > О, то, поскольку 1 выбирается так, что Ьс/ас, < Ь,/ас, для всех с' е В, (29.77) мы имеем Ь, = Ь1 — асе(Ьс/асе) > Ь, — а;,(Ь,/ас,) =Ь; — Ь, =О, (согласно (29.76)) (согласно (29.77)) и, таким образом, Ь, > О.
Если ас, < О, то, поскольку ас„Ь, и Ьс неотри- цательны, из уравнения (29.76) вытекает, что неотрицательным должно быть и значение Ь,. Сохранение. Покажем, что данный инвариант цикла сохраняется при условии, что оператор геснгп в строке 11 не выполняется. Случай выполнения этой строки мы рассмотрим при обсуждении завершения цикла. Каждая итерация цикла ьтййе меняет ролями некоторую базисную и небазисную переменные с помощью выюва процедуры Рсчот. Согласно упр. 29.3.3 новая каноническая форма эквивалентна канонической форме из предыдущей итерации, которая, согласно инварианту цикла, эквивалентна исходной канонической форме. Теперь покажем, что сохраняется вторая часть инварианта цикла.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
