Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 17
Текст из файла (страница 17)
Матрица Аз 0 0 0 1 не является единичной, поэтому найдем для нее обратную матрицу. Для этого записываем рядом две матрицы: нашу матрицу Аз и ЕДиничную. Далее сводим матрицу Аз к единичной путем элементарных преобразоааний строк. Полученная в результате преобразований матрица на месте единичной матрицы и является обратной к нашей матрице Аз. Напомним, что элементарными преобрам»ваннами матрицы являются: а) перестановка двух строк; Ь) умножение строки на число отличное от нуля и с) прибавление к одной строке другой строки, умноженной на любое число. На первом этапе мы умножили третью строку на -1, из первой строки вычли вторую. На втором этапе из первой строки вычли четвертую, умноженную на 5. На третьем этапе из второй строки вычли четвертую, а к третьей строке прибавили удвоенную четвертую.
/1 — ! 0 -53 !о ! о Таким образом, получили, что Аз ' —— 0 0 0 1 3 4 Далее находим разложения векторов а,а по базису а,а,а,а: 94 95 9 ! Симплекс-метод 1.4. Эйдачи Задачи линейного программирования в канонической форме с за- данной первоначальной крайней точкой. ХЗ>0, 5=1,2,3, хб (О~ ! 1). х7+ х2+ хэ шах; 1.1. -х, + х2+ хз = 2, Зх, — ХЗ+ хз = О, 2Х~ + хг + Зхз+ хб — шах; 1.2.
х~ + 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)х — с- +со,если у ~ Ь, при х- +со или х — -со.
Поэтому 7 (у) = пэах ((у — 6)х — с) = (+, уФЬ. Найдем вторую сопряженную к >. Нетрудно видеть, что э "(х): = гоах ((х,у) — >'(у)) = шах ху — 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, -( .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
