Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 197
Текст из файла (страница 197)
Теперь покажем, как преобразовать задачу линейного программирования, в которой на некоторые переменные не наложены ограничения неотрицательности, в задачу, в которой все переменные подчиняются этому условию. Предположим, что для некоторой переменной ху ограничение неотрицательности отсутствует. Заменим все вхождения переменной хз выражением х' — х" и добавим ограничения неотрицательности х' > О и х" > О. Так, если целевая функция содержит слагаемое с.х., то оно заменяется на с х' — с х", а если ограничение е содержит слагаемое ачх, оно заменяется на а; х' — а,ух". Любое допустимое решение х новой задачи линейного программирования соответствует допустимому решению исходной задачи с х = х' — х". и тем же самым целевым значением.
Точно так з же и любое допустимое решение х исходной задачи линейного программирования соответствует допустимому решению х новой задачи линейного программирования с х~ = х, и хх~ = О, если хз > О, или с хп = -ху и хе = О, если з 3 з ' 3 з 3 х < О. Две указанные задачи линейного программирования имеют одно и то же целевое значение независимо от знака хз.
Следовательно, эти две задачи эквивалентны. Применив эту схему преобразования ко всем переменным, для которых нет ограничений иеотрицательности, получим эквивалентную задачу линейного программирования, в которой на все переменные наложены ограничения неотрицательиости. Продолжая рассмотрение нашего примера, проверяем, для всех ли переменных есп соответствующие ограничения неотрицательности.
Для переменной х1 Часть ИЛ Иэаранные темы Зхз максимизировать 2х1 — Зхз + при условиях и хз — — 7 2хз <4 > О. Х! + Х2 х! — 2хз + I и Х1,Х2,Х2 (29.22) Теперь преобразуем ограничения-равенства в ограничения-неравенства. Предположим, что задача линейного программирования содержит ограничение-равенство ДХ1,хз,...,х„) = Ь. Поскольку х = р тогда и только тогда, когда справедливы оба неравенства, х > у и х < у, можно заменить данное ограничение-равенство парой ограничений-неравенств ДХ1,хз,..., х„) < Ь и ДХ1, хз,..., Х„) > Ь. Выполнив такое преобразование для всех ограничений- равенств, получим задачу линейного программирования, в которой все ограничения являются неравенствами.
Наконец можно преобразовать ограничения вида "больше или равно" в ограничения вида "меньше или равно" путем умножения этих ограничений на — 1. Любое ограничение вида а,,х, >Ь; Е 1=1 эквивалентно ограничению — а;.х. < — Ь; . 1=1 Таким образом, заменив каждый коэффициент а! на — а! и каждое значение Ь на — Ь, мы получим эквивалентное ограничение вида "меньше или равно". Чтобы завершить преобразование нашего примера, заменим ограничение-равенство (29.22) двумя неравенствами и получим максимизировать 2х! — Зх~з + при условиях ЗХ2 I Х! + Хз I Х! + Х2 2Х2 + / и Х1 Х2 Х2 хн <7 2 хз >7 2хз <4 > О. (29.23) такое ограничение есть, а для переменной хз — нет. Заменив переменную хз переменными х~з и х~з и выполнив соответствующие преобразования, получим следующую задачу: Глава 29.
Пинеяное лраграчмирование 895 Теперь изменим знак ограничения (29.23). Для единообразия имен переменных переименуем х~г в хг, а х~г — в хз. Полученная стандартная форма имеет вид максимизировать 2х! — Зхг + Зхз при условиях х! + хг — хз < 7 (29.24) (29.25) (29.26) (29.27) (29.28) < — 7 — — хг + хз х! — 2хг + 2хз хг, хг, хз < 4 > О.
а!х <Ь; Е г=! (29.29) Введем новую переменную 8 и перепишем неравенство (29.29) в виде двух огра- ничений: 8 = Ь; — ~~! а!эху (29.30) (29.31) 8>0 Переменная 8 называется всламогагвяльлой переменной (81аси капаЫе), так как она определяет разность (з!аск) между левой и правой частями выражения (29.29). (Всюре вы узнаете, почему удобно записывать ограничения в виде, когда в левой части находятся только вспомогательные переменные.) Поскольку неравенство (29.29) верно тогда и только тогда, когда одновременно выполнены равенство (29.30) и неравенство (29.31),можно применить данное преобразование ко всем ограничениям-неравенствам задачи линейного программирования и получить эквивалентную задачу, в которой в виде неравенств записаны только условия неотрицательности.
При переходе от стандартной формы к канонической мы будем использовать для связанной с 1-м ограничением вспомогательной переменной обозначение х„+, (вместо 8). Тогда г-е ограничение будет записано в виде равенства Хя+ Ь Х~ ~ а43Х! (29.32) наряду с ограничением неотрицательности х„.!.! > О.
Преобразование задач линейного программирования в каноническую форму Чтобы эффективно решать задачу линейного программирования с помощью симплекс-метода, удобно записать ее в такой форме, когда некоторые ограничения заданы в виде равенств. Говоря более точно, мы будем приводить задачу к форме, в которой толью ограничения неотрицательности заданы в виде неравенств, а остальные ограничения являются равенствами. Пусть ограничение-неравенство имеет вид В9б Часть Лт Избранные тены максимизировать 2х1 — Зхг при условиях х4 = 7 — х1 — хг + Зхз + хз (29.33) (29.34) (29.35) (29.36) (29.37) хб = — 7 + х1 + хг хз — 2хз О. хб= 4 — х1 +2хг Х1,Х2, ХЗ,Х4,хб,Хб ~ В этой задаче линейного программирования все ограничения, за исключением условий неотрицательности, являются равенствами и все переменные подчиняются ограничениям неотрицательности.
В записи каждого ограничения-равенства в левой части находится одна переменная, а остальные переменные находятся в правой части. Более того, в правой части каждого уравнения содержатся одни и те же переменные, и это только те переменные, которые входят в целевую функцию. Переменные, находящиеся в левой части равенств, называются базискмми переменными (Ьагйс чапаЫез), а переменные, находящиеся в правой части,— небазисньгми переменными (попЬаз1с чапаЫеб). В задачах линейного программирования, удовлетворяющих указанным условиям, мы будем иногда опускать слова "максимизировать" и анри условиях", а также явные ограничения неотрицательности. Для обозначения значения целевой функции мы будем использовать переменную г.
Полученная форма записи называется канонической 4яормой (51ас)с Гопп). Если записать задачу линейного программирования (29.33К29.37) в канонической форме, можно получить 2х1 — Зхг + Зхз х4 = 7 Х1 х2 + хз хб = — 7+ х1+ хг — хз хб = 4 — х1 + 2х2 — 2хз . (29.38) (29.39) (29.40) (29.41) Для канонической формы, как и для стандартной, удобно иметь более короткий способ записи.
Как будет показано в разделе 29.3, множества базисных и небазисных переменных в процессе работы симплекс-алгоритма будут меняться. Обозначим множество индексов небазисных переменных как 1н', а множество индексов базисных переменных — как В. Всегда выполняются соотношения )Ю~ = и, ~В! = т и 1У О В = (1, 2,..., и + т). Уравнения будут индексироваться элементами множества В, а переменные правых частей будут индексироваться элементами множества )и'.
Как и в стандартной форме, мы используем 61, с и оп для обозначения констант и коэффициентов. Для обозначения необязательного постоянного члена в целевой функции используется е (позже вы узнаете, что включение константного члена в целевую функцию упрощает определение ее значения). Таким образом, можно кратко описать каноническую форму с помо- Применив данное преобразование ко всем ограничениям задачи линейного прозраммирования в стандартной форме, получаем задачу в канонической форме. Например, для задачи, заданной формулами (29.24) — (29.28), введя вспомогательные переменные х4 хб и хб, получим Гэаеа 29, Линейное ярогра24марование З97 щью кортежа (Х, В, А, Ь, с, о); она служит кратким обозначением канонической формы з = о + ~~~ с х .
уев хг = Ьг — ~~ь абх для 2 е В, эбФ (29.42) (29.43) в которой все переменные х подчиняются условиям неотрицательности. Поскольку сумма 2 72 аг.х в выражении (29.43) вычитается, значения элементов аг. противоположны коэффициентам, входящим в каноническую форму. Например, для канонической формы 6 хб + 6 2хб Х2 = хг = 3 хб + 2 мы имеем В = (1, 2,4), Х = (3,5,6), О2З атб атб -1/б -1/6 1/3 А = агз агб агб = 8/3 2/3 — 1/3 а4з а4б а4б 1/2 — 1/2 0 — )=( 4) с = ( сз сб сб ) = ( -1/6 -1/6 -2/3 ) и о = 28.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
