Алгоритмы - построение и анализ (1021735), страница 180
Текст из файла (страница 180)
< — Ь; Е- Таким образом, заменив каждый коэффициент а, на — аб и каждое значение 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. Пусть имеется задача линейного программирования общего вида с и переменными и т ограничениями. Предположим, что мы преобразовали ее в стандартную форму. Укажите верхнюю границу числа переменных и ограничений в полученной задаче. 29.1-9. Приведите пример задачи линейного программирования, для которой допустимая область является неограниченной, но оптимальное целевое значение конечно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
