Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 17
Текст из файла (страница 17)
х~ + 2ХЗ + 5хз — хб = 4, х~ — ХЗ вЂ” хЗ + 2хб = 1~ бх, + х2 + 4хз — 5хб гпах; 1.3. Зх, + х2 — хз + хб = 4, 5Х7 + х2 + хз — хб = 4, х, + х2 +хЗ+ хб — ~шах; х; >О, 5 = 1,2,3,4, 1.4. Х7 + ЗХЗ + хз + 2хб = 5, 2х7 — хз+ хб = 1, хо=(0,1 0,1). х, + ХЗ + хз + х, + х, — шах; ХЗ >О, 2 = 1,...,5, 1.5. 2х7 + Зхз + 5хз + 7хб + 9ХЗ = 19, Х7 — ХЗ + хб -!-2ХЗ вЂ” — 2, хе=(0,0,1,2,0). 5 = 1,2,3,4, х;>О, х~+х2+х3+ хб Бах х, +х2+хз+Зхб = 3, Х7 + Х2 ХЗ + Хб х! Х2+ ХЗ+ Хб 11 х,=(О,О,О, 1). х;>О, 5=1,...,5, + 2хз + хб + бхз -~шел; + Зхз + хб + 9х5 —— 18, + 2хб+ 8ХЗ = 13, хз + хз — — 3, х~ + 2х2 х~ + Зх2 х~ + 5хг хб = (О, 1, 2, О, 1). 5 = 1,...,6, х; > О, + хз + хб — Х5 — хб + хз + Зхб + Зхб + 2хб = 7, — хз +х5 — хб = — 2, +хз+ хб + хб +2хб=5, Х! Х2 2Х7 + ХЗ х~ ХЗ хе = (О 0 2 0 1 1).
+ хз + Зхб — ХЗ вЂ” 2хб+ х7 -~ пЗак; + Зхб+ х7 — — 8, + 2хз + 2хб + ЗХЗ = 15, + Зхз+ 2хб+ 2х5 — Зхб+ Зх7 — — 11, хЗ +Зхб+ Х5 2хб ! ХЗ = 5, 3 = 1,...,7, хо =(1,00,1,0,1,4). хз > О, Глава 2. Линейное программирование о О ! 2 хб=АЗ аб= Π— 1 1 0 Разложением вектора Ь является вектор (1,2,1,1) ненулевык координат крайней точки.
Составим первую симплексную таблицу Разрешающий столбец а . В качестве разрешающей строки можно взять строки а и аб. Возьмем для определенности строку а . Тогда ! = 1, 5 б 6 разрешающая строка аб. Заменяем в базисе вектор а на вектор а и для нового базиса строим вторую симплексную таблицу: Вектор 25 > О, поэтому точка й = (4,2,0,1,0,0) является решением задачи и Я,„= 7.
Полученная крайняя точка содержит только три положительные координаты. Значит, решенная нами задача является вырожденной. Х7+ ХЗ х~ + 2х2 1.9. х ~ + ЗХЗ ХЗ х,>0, 5=1,2,3,4, хб — — (0,0, 1, 1). х.>0 5=1234 хб = (1,0,0, 1). 96 Глава 2. Линейное программирование 5 2. Двойственность в линейном программировании 2.1. Элементы выпуклого анализа. Преобразование Лежандра Напомним определение выпуклого множества и выпуклой функции.
Множество А С К" называется вынуклым, если для любых двух точек а~ и а» из А и любого числа 1 Е (О, 1) элемент 1а~ + (1 — 1)а» Е А. Пусть задана Функция >: К" — К: = К ы ( — со) ы (+со). С каждой такой функцией > связываются два множества: доги >' = (х !,Г(х) < +оо ) — эффективное множество и ер1 У: = ((а, х) б К х К" ( а > Г(х)) — надграфин,г. Функция > называется выпуклой, если надграфик >' — выпуклое множество.
Функция > называется замкнутой, если надграфик > — замкнутое множество. Функция > называется собственной, если >(х) > — со '4Г х и богп > ~ О. Ясно, что сумма двух выпуклых функций является функцией выпуклой. Но суперпозиция двух выпуклых функций не всегда является выпуклой функцией. Попробуйте привести пример! Пусть >; К" — К вЂ” некоторая функция. Преобразованием Лежандра функции Г (или сопряженной функцией к > ) называется функция ~'(у): = ах ((х,у) - У(х)) Из определения 7' видно, что 7' — верхняя грань семейства аффинных Функций (х,у) — >(х).
Ее надграфик является выпуклым множеством (как пересечение выпуклых множеств — полупространств). Следовательно, Г' — выпуклая функция. Из определения сопряженной функции следует неравенство Юнга: (х, у) < У(х) + У (у) 42 х, у б К . Функция г"(х): = шах ((х,у) — Г'(у)), являющаяся сопряженной к >', называется второй сопряженной к >. В теории двойственности для задач линейною программирования важной является следуюшая теорема выпуклого анализа. Теорема Феихеля — Моро. (Гл. б, п. О.З.) Собственная функиия совпадает со своей второи сопряженной (>(х) г— я 7" (х)) тогда и только тогда, когда она выпукла и замкнута (т.
е. когда ег нодгрофик ер1 > — выпуклое и эомкн> тое мноэкество). 42. Двойственность в линейном программировании 97 2.2. Примеры >7рнмер Е Найти первую н вторую сопряженные (в смысле Лежандра) функции к функции >(х) = ах» + Ьх+ с в зависимости от значений параметров а Ь с Решение. По определению сопряженной функции ~'(у) = »пах ((х, у) — Г(х) ) = гпах (ху — ах» — Ьх — сэ) = » = шах( — ах + (у — Ь)х — с). ь 2 Если а > О, то парабола — ах'+(у — Ь)х — с = — а(х — к=41 + 1— ":ь)- — с 24 4а достигает своего максимума — — с при х = "--.
Поэтому н-ь>' -ь 4а 2а (у-ь)' У'(у) = — с. 4а Найдем вторую сопряженную к >. По определению (у- ь)' (х): = гпах ((х, у) — > (у)) = глах(ху — + с~ = ь т 4а (у — Ь вЂ” 2ах) = гпах41— + ах + Ьх + с~. г 4а Парабола и(у): = — ~~4,~'*Р + ах» + Ьх + с достигает своего максимума при у = Ь+ 2ах. Следовательно, (у — Ь вЂ” 2ах)» (х) = гпах(- +ах +Ьх+с~ =ах +Ьх+с. г 1 4а Если а =О, тофункция (у — 6)х — с- +со,если у ~ Ь, при х- +со или х — -со.
Поэтому ,Г (у) = пэах ((у — 6)х — с) = (+, уФЬ. Найдем вторую сопряженную к 7. Нетрудно видеть, что э "(х): = гоах ((х,у) — >'(у)) = шах ху — 4( ' " ' = Ьх+с. У Если а < О, то парабола -ах + (у — 6)х — с с осями, направленными вверх, стремится к +со при х — +со. Значит, >"(у) = +со. Найдем вторую сопряженную к >. Нетрудно видеть, что / (х): = гоах ((х, у) — > (у)) = пюх (ху — (+ос)) = -со. 98 Глава 2.
Лнвейное щюграммнроваине Пример 2. Найти первую и вторую сопряженные (в смысле Лежандра) функции к функции Г(х) = е'. Решение. По определению сопряженной функции У (У) — шах ((х У) — г(х)) = так(ху — е ) = тах У(х), е где у(х); = ху — е*. Найдем максимум функции у(х). Имеем у'(х) = у — е* = 0 с> х = !ну при у > О. Поскольку ув(х) = — е* < О, то по достаточному условию экстремума гладкой функции при у > 0 в этой точке будет достигаться максимум этой функции.
Подставляя х = 1и в у(х), находим, что тах у(х) = у!ау — у. х= пу Если у = О, то очевидно, что тах у(х) = гпах( — е*) = О. Если у < О, й то у(х) — +оа при х — -аа. Таким образом, (У1пу-у, у>О, У (У) = так(ху — е*) = ~ О, у = О +со, у<0, Найдем вторую сопряженную к 2. По определению ( (у!пу — у, у > 0,1 у*'( ): = тах ((х,у) — у (у)) = тах ~ху — ( О, у = О, ~ = +аз, у<0 = тах (тах (ху — у1п у + у), О) . г>о Нетрудно видеть, что функция и(у): = ху — у!ну+ у достигает своего максимума при у > 0 в точке обращения в нуль своей производной. Действительно, 1 и (У) = х — 1п у — 1 + 1 = х — !п у = 0 с> у = е* ! 1 в (у) = — — < 0 при У > О, у Подставляя эта значение у в выражение для /"(х), получаем 2"(х) = тах(шах(ху — У1пу+ у),0) = тах(е О) = е~.
г>о Равенспю г "(х) = У(х) = е* следует также непосредственно из теоремы Фенхеля — Моро, поскольку функция е* является выпуклой и замкнутой. в 2. Двойственность в линейном программирования 2.3. Вывод двойственных задач 2.3.1. Вывод задачи двойственной к задаче в общей форме рассмотрим задачу линейного программирования в обшей форме (с,х) — пип; Ах < Ь. Обозначим через Я(Ь); = т!и ((с,х) ! Ах < Ь) — Я фУнкцию (р), рассматривая аргумент Ь как параметр в задаче (Р).
Овределевне. Двойствеиной задачей к задаче линейного программирования в обшей форме называется залача нахождения второй сопряженной (в смысле Лежандра) функции Я" (Ь) для Я-функции задачи (Р), Для нахождения второй сопряженной необходимо найти вначале первую сопряженную функцию к функции Я(Ь): Я'(у) = тах((у, Ь) — Я(Ь)) = п1ах((у, Ь) — п1!п((с, х) ! Ах < Ь) ) = = та ((у,Ь) — (,х) ~ Ах < Ь) 1 шах((У,Ах) — (Сх)), У <О, иначе тах((А"у — ох)), у<0, (О, А'у=с, у<0, -( .
' ' =( +со, иначе ( +со, иначе. Найдем сопряженную в смысле Лежандра функцию к функции Я'(у), т.е. вторую сопряженную к функции Я(6): Я" (6) = тах((У,Ь) — Я*(у)) = тах((У,Ь) ~ А У = с, У < О). г г Таким образом, двойственной задачей к задаче линейного программирования в обшей форме является следующая задача: (Ь,у)- тах; А'у=с, у<0. Для задачи линейного программирования в нормальной форме: (с,х) -~ тах; Ах < Ь, х > О, выпишем без доказательства двойственную задачу (попробуйте сделать это самостоятельно): (Ь,у) пип; А'у > с, У > О. Как мы видим, двойственнал задача в этом случае обладает определенной симметрией по отношению к исходной. Элементы Ь и с меняются местами, максимум меняется на минимум, матрица А меняется на транспонированную, и матричное неравенство меняет знак.
4' Глава 2. Линейное программирование 2.3.2. Вывод задачи двойственной к двойственной задаче для задачи линейного программирования в общей форме Покажем, что понятие «двойственности» введено правильно, т.е. лвойственная задача к двойственной является исходной задачей. (Ьу)- тах; Ау=с, у<0 Для того, чтобы вывести двойственную задачу к задаче (Р"*) надо вначале свести ее к задаче линейного программирования в общей форме, для которой уже известна двойственная задача.
Вначале сведем задачу на минимум. Затем заменим равенство А'у = с на два неравенства с < А'у < с с» А'у < с, -А'у < — с. Получим эквивалентную задачу линейного программирования в общей форме: ( — Ь,у) — пнп; — А' у < — с Двойственная к ней будет следующая задача: ((с, — с, 0), (х, хэ, хэ)) — гпах; .! (А -Ау) х' =-Ь, х <О, '<О, х <О. з б 2. Двойственность в линейном программировании 10! 2.3.3. Вывод задачи двойственной к задаче в канонической форме Задачу линейного программирования в канонической форме (с,х) «тах; Ах=Ь, х>0, (Рь) сведем ее к задаче на минимум: ( с,х)-«пцп, Ах — 6, х>0, при этом ЯВ = — Яр' Обозначимчерез Я(Ь) = т1п(( — с,х) ! Ах = 6 х > О) — Я функцию « задачи (Р'), рассматривая аргумент Ь как параметр в задаче (Р'). Найдем первую сопряженную функцию к функции Я(Ь): Я (Ь )=шах((Ь',Ь)-Я(6)) =так((6",Ь) — пнп(( — с х) !Ах = Ь, х > О)) = ь Ь = тах((Ь', Ь) + (с, х) ! Ах = Ь, х > О) = гпах((6', Ах) + (с х) ! х > О) = »,* » А*Ь" < 0 = пъах((А'Ь' + с, х) ! х > О) = ( » 1 +оо, Найдем сопряженную в смысле Лежанара функцию к функции Я"(Ь ), т.е.
вторую сопря;кенную к функции Я(Ь): Перепишем зту задачу в виде (с,х' — х)- тах; А(х — х)+х = — Ь, х'<О, х <О, х <О. Обозначая х = * — х, и учитывая, что равенство А(х' — хэ) + х' = — Ь э эквивалентно неравенству А(х' — х') > -Ь, поскольку х' < О, а ограничений на знак х уже не будет, получим — (с, х) «тах; — Ах > — Ь. Заменяя тах на ппп и умножая матричное неравенство на — !, придем к задаче, являющейся двойственной к залаче (Р"), которая совпадает с исходной задачей (Р) (с, а) «т!п; Ах < Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
