Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 180
Текст из файла (страница 180)
Чтобы превратить задачу минимизации Ь в эквивалентную ей задачу максимизации Ь', достаточно просто изменить знаки коэффициентов целевой функции на противоположные. Поскольку Ь и Ь' имеют одинаковые множества допустимых решений и для любого допустимого решения целевое значение Ь противоположно целевому значению Г, эти две задачи линейного программирования эквивалентны.
Например, пусть исходная задача имеет вид: — 2хг + Зхз Минимизировать при условиях х1+ ха=7 х1 — 2хз ( 4 х1 >О Если мы поменяем знаки коэффициентов целевой функции, то получим следую- щую задачу: Максимизировать 2х1 — Зхз при условиях х1+ хз= 7 х1 — 2хз < 4 х1 >О Теперь покажем, как преобразовать задачу линейного программирования, в которой на некоторые переменные не наложены ограничения неотрицательности, в задачу, где все переменные подчиняются этому условию. Предположим, что для некоторой переменной х ограничение неотрицагельности отсутствует. Заменим все вхождения переменной х выражением х' — х" и добавим ограничения неотрицательности х' > О и х" > О.
Так, если целевая функция содержит слагаемое с х, то оно заменяется на с х' — с х", а если ограничение г содержит слагаемое а; х, оно заменяется на а, х' — сч х'.. Любое допустимое решение х новой задачи линейного программирования соответствует допустимому решению исходной задачи с х = х' — х" и тем же самым целевым значением, следовательно, эти две задачи эквивалентны. Применив эту схему преобразования ко всем переменным, для которых нет ограничений неотрицательности, получим эквивалентную задачу линейного программирования, в которой на все переменные наложены ограничения неотрицательности. Продолжая рассмотрение нашего примера, проверяем, для всех ли переменных есть соответствуюшие ограничения неотрицательности.
Для переменной х1 такое Глава 29. Линейное программирование 881 ограничение есть, а для переменной хз — нет. Заменив переменную хз двумя переменными х~з и х~з и выполнив соответствующие преобразования, получим следующую задачу: Максимизировать 2хг — Зх~з + Зхз при условиях / я Хз Х2=7 2хз+ 2хз < 4 хмхз,хз ~ )О (29.22) хг+ х1— а;х >Ь; Е эквивалентно ограничению — абх. < — Ь; Е- Таким образом, заменив каждый коэффициент а, на — аб и каждое значение 6, на — Ь, мы получим эквивалентное ограничение вида "меньше нлн равно". Чтобы завершить преобразование нашего примера, заменим ограничение-равенство (29.22) на два неравенства, и получим: Максимизировать 2хг — Зх~з + Зхз при условиях + хз + Х'з / — 2хз — хз<7 И вЂ” Хз>7 +2х~з <4 х~з,х~з > О хг (29.23) х1 х1 хг, Теперь преобразуем ограничения-равенства в ограничения-неравенства.
Предположим, что задача линейного программирования содержит ограничение-равенство 7' (х1, хз,..., х„) = Ь. Поскольку х = у тогда и только тогда, когда справедливы оба неравенства х > у и х < у, можно заменить данное ограничение-равенство парой ограничений-неравенств г" (хмхз,...,х„) < 6 и г" (х|, хз,..., х„) > 6. Выполнив такое преобразование для всех ограничений-равенств, получим задачу линейного программирования, в которой все ограничения являются неравенствами. Наконец, можно преобразовать ограничения вида "больше илн равно" в ограничения вида "меньше или равно" путем умножения этих ограничений на — 1. Любое ограничение вида Часть ЧП.
Избранные темы 882 Теперь изменим знак ограничения (29.23). Для единообразия имен переменных переименуем х2 в х2, и х~2 в хз. Полученная стандартная форма имеет вид: (29.24) Максимизировать 2х1 — Зхз + Зхз при условиях Х1 — х1 Х1 Преобразование задач линейного программирования в каноническую форму Чтобы решать задачу линейного программирования с помощью симплекс-ме. тода, удобно записать ее в такой форме, когда некоторые ограничения заданы в виде равенств.
Говоря более точно, мы будем приводить задачу к форме, в которой только ограничения неотрицательности заданы в виде неравенств, а остальные ограничения являются равенствами. Пусть ограничение-неравенство имеет вид Е щлх3 < Ьо 3=1 (29.29) Введем новую переменную а и перепишем неравенство (29.29) в виде двух огра- ничений: а=61 — ,'~ сч х, 3=1 а > О. (29.30) (29.31) Переменная а называется всломегательной переменной (з1ас1с чапаЫе), она определяет разность (з!ас1с) между левой и правой частями выражения (29.29). Поскольку неравенство (29.29) верно тогда и только тогда, когда одновременно выполнены равенство (29.30) и неравенство (29.31), можно применить данное преобразование ко всем ограничениям-неравенствам задачи линейного программирования и получить эквивалентную задачу, в которой в виде неравенств записаны только условия неотрицательности.
При переходе от стандартной формы к канонической мы будем использовать для связанной с (-м ограничением вспомогательной переменной обозначение х„+; (вместо а). Тогда 4-е ограничение будет записано + х2 — хз ~ (7 — х2+ хз < — 7 — 2х2+ 2хз ( 4 х1,хз,хз Ъ 0 (29.25) (29.26) (29.27) (29.28) Глава 29. Линейное программирование 883 в виде равенства х„ч; — — 61 — З айх;, 1=1 (29.32) наряду с ограничением неотрицательности х„+; > О. Применяя данное преобразование ко всем ограничениям задачи линейного программирования в стандартной форме, получаем задачу в канонической форме.
Например, для задачи, заданной формулами (29.24К29.28), введя вспомогательные переменные х4, хз, ха, получим: 2х1 — Зхг + Зхз Максимизировать при условиях (29.33) х4= 7 — х1 — хг+ хз хз = — 7+ х1+ хг — хз ха = 4 — х1+ 2хг — 2хз х1,хг,хз,х4, хз, ха Ъ 0 (29.34) (29.35) (29.3б) (29.37) 2х1 — Зхг + Зхз (29.38) (29.39) (29.40) (29.41) 7- х1 — хг+ хз — 7+ х1+ хг — хз 4 — х1 + 2хг — 2хз Х4 = хз = Х6 = Для канонической формы, как и для стандартной, удобно иметь более короткий способ записи.
Как будет показано в разделе 29.3, множества базисных и небазисных переменных будут меняться в процессе работы симплекс-алгоритма. В этой задаче линейного программирования все ограничения, за исключением условий неотрицательности, являются равенствами, и все переменные подчиняются ограничениям неотрицательности. В записи каждого ограничения-равенства в левой части стоит одна переменная, а остальные переменные находятся в правой части. Более того, каждое уравнение содержит в правой части одни и те же переменные, и это только те переменные, которые входят в целевую функцию.
Переменные, находящиеся в левой части равенств, называются базисными переменными (Ьаьйс чапаЫез), а переменные, находящиеся в правой части,— небазисными переменными (попЬаз1с чапаЫез). В задачах линейного программирования, удовлетворяющих данным условиям, мы иногда будем пропускать слова "максимизировать" и "при условии", а также "ограничения неотрицательности". Для обозначения значения целевой функции мы будем использовать переменную г. Полученная форма записи называется канонической формой (61ас1с Гопп).
Каноническая форма задачи линейного программирования (29.33)-(29.37) выглядит следующим образом: Часть Ч11. Избранные темы 884 Обозначим множество индексов небазисных переменных дЧ, а множество индексов базисных переменных — В. Всегда выполняются соотношения 1дЧ) = и, 1В( = = т и дЧ 0 В = (1, 2,..., и+ тп).
Уравнения будут индексироваться элементами множества В, а переменные правых частей будут индексироваться элементами множества М. Как и в стандартной форме, мы используем Ь, с и а;3 для обозначения констант и коэффициентов. Для обозначения необязательного постоянного члена в целевой функции используется дд.
Таким образом, можно кратко описать каноническую форму с помощью кортежа (дЧ, В, А, Ь, с, дд); она служит кратким обозначением следующей канонической формы: з = дд + ~д с ху, увдт х;=Ь; — ~~~ сн х, гдедЕВ. хе дт (29.42) (29.43) При этом все переменные х подчиняются условиям неотрицательности. Поскольку сумма 2 дтадуху в выражении (29.43) вычитается, значения элементов оу противоположны коэффициентам, входящим в каноническую форму. Например, для канонической формы Хз 2Х6 хз 28 —— 6 хз 8+— 6 8хз 4 —— 3 хз 18 —— 2 6 3 Хз Ха хд = +— 6 3 2хз ха — — +— 3 3 Х5 +— 2 Х4 элементы шестерки имеют вид В = (1, 2, 4), дЧ = (3, 5, 6), дд = 28, -1/6 -1/6 1/3 8/3 2/3 -1/3 1/2 -1/2 О ащ ащ ада агз огь ага О43 О45 О46 Ь, 8 Ь= Ьг — — 4 Ь4 18 ,т ,т с = (сз сз се) = (-1/6 -1/6 -2/3~, а индексы у А, Ь и с не обязательно являются множествами последовательнйх целых чисел; они зависят от того, какие индексы входят во множества В и дЧ.
В качестве примера противоположности элементов матрицы А коэффициентам канонической формы, заметим, что Глава 29. Линейное программирование Упражнения 29.1-1. Если записать задачу линейного программирования (29.24)-(29.28) в компактной форме (29.19К29.21), чему будут равны п, т, А, б и с? 29.1-2. Укажите три допустимых решения задачи линейного программирования (29.24)-(29.28). Чему равно целевое значение для каждого решения? 29.1-3. Какими будут )У, В, А, 6, с и и для канонической формы (29.38)-(29.41)? 29.1-4. Приведите следующую задачу линейного программирования к стандартной форме: Минимизировать 2х1 + 7хз при условиях хг = 7 Зх1 + хз > 24 х1 > 0 хз< 0 29.1-5. Преобразуйте следующую задачу линейного программирования в каноническую форму: — бхз Максимизировать 2х1 при условиях + хз — хз < 7 — хз >8 + 2хз+ 2хз > 0 хмхз,хз > 0 х1 Зх| — х1 Какие переменные являются базисными, а какие небазисными? 29.1-6.
Покажите, что следующая задача линейного программирования является неразрешимой: Зхг — 2хг Максимизировать при условиях хг + хз < — 2хг — 2хз < — 10 хыхз > в уравнение для х| входит слагаемое хз/6, так что коэффициент ию равен — 1/6, а не +1/6. Часть ЧП. Избранные темы 886 29.1-7. Покажите, что следующая задача линейного программирования является неограниченной: Максимизировать при условиях х1 — хз — 2Х1+ Хз (~ — 1 — х1 — 2хз ( — 2 хм ха )~ О 29.1-8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
