Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 68
Текст из файла (страница 68)
Эта функция оптимального дохода является центральной для нашего метода. Простая характеризацня ее свойств непосредственно и интуитивно приводит к теории двойственности линейного программирования, а также к результатам Куна †Такке [1[ по квадратичному программированию. Кроме того, этот подход дает непосредственную экономическую интерпретацию рассматриваемых величин. 2. ДВОЙСТВЕННАЯ ЭАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В задаче линейного программирования требуется найти вектор х, Хя (1) хл 436 новый подход к твоими двойствтншости (п. и доставляющий максимум линейной целевой функции стх (2) при ограничЕниях в виде неравенств Ах(Ь х»0, (4) где с, с, (б) сл ана„... а,„ а„,а„...
а„„ | (6) „,а,„,,а„ Ь, Ь, (7) 1(Ь) = стх'. (8) Для того чтобы изучить поведение функции у, рассмотрим одну из компонент х) оптимального решения. Если мы заданы. Пусть ~(Ь) — максимальное значение целевой функции (2), как функции от правой части ограничения (3). Если хя— оптимальное решение задачи, то 2) 437 ДВОЙСТВЕННАЯ ЗАДАЧА увеличим х' на а, то в силу наложенного ограничения мы должны заменить правую часть (3) на Ь+ВА' 7, где ао7 аа7 АР! = (О) а 7 — /-Й столбец матрицы А. Таким образом, ыы придем к рассмотрению величины 7" (Ь+ ВАР!), представляющей собой максимальное значение функции сгу при ограничениях Ау Ь+ ВАР7 (! О) у 0. (11) Так квк вектор ко ! о жт -т.
= (1 2) о Хл где ег — /-Й единичныи вектор, удовлетворяет неравенствам (10) и (11), а доход при этом ранен с'(ко+ ае') =7 (Ь) + ась (13) мы видим, что для всех / при а)0 имеет место неравенство У (Ь + В А "') ) у (Ь) + ас . (14) 438 новый подход к тнонии двойстввнности [п. и Разлагая *) левую часть в ряд по степеням а, получим **): т .(Ь)+ ~~~рт дУ г ! +члены более высокого порядка )У'(Ь)+аср (15) Взяв достаточно малое а) О, мы видим, что для всех у ял 2— ду ,)Ь агу)ср ! (16) дУ а — агу(ср если ху)0.
2.д, т !др '(17) Следовательно, — ам=с, если ху)0. (18) !=1 Наконегц мы видим, что — = 0 для всех 1. ду (! 9) Для сформулированной выше задачи это вытекает из того факта, что изменение задачи, связанное с увеличением вели- *) Могут найтись некоторые значения Ь, для которых это разложение невозможно. Эту тр>дность лгожно обойти простым приемом, выбрав подходящее Ь, бесконечно близкое к заданному. Мы не приводим здесь соответствующей процедуры, поскольку она ничего не добавит к пониманию нашего подхода н двойственности. '*) Нетрудно показать (хотя бы методом параметрического программнрованнн), что У(Ь) явлнется выпуклой кусочно-линейной функцией, поэтому разложение (!5) либо не содержит членов высшего порядка малости, либо невозможно (в отдельных точках).
(Приап редд Предположим теперь, что хч)0. Тогда в приведенных выше рассуждениях можно допустить отрицательное значение для а, при условии, что оно достаточно близко к нулю (так что у, определяемое формулой (12), удовлетворяет неравенству (11)). Но, поскольку а(0, мы ааключаем из (!5), что 21 двойственная задача чины Ьг (которая обычно мыслится как наличное количество некоторого ресурса), не может привести к ухудшению оптимального решения по сравнению с исходньи решением, но может дать улучшение первоначального значения целевой функции.
Неравенства (16) и (19) приводят к рассмотрению век- торов сг, и, (20) нм удовлетворяюших неравенствам игА = ст и н ) О. (2! ) (22) Из неравенств (3), (4), (2!) и (22) получим; сг» ( (игЛ)» = ггг(й») ( нгЬ (23) для любых» и и, удовлетворяющих (3), (4), (21) и (22). В частности, если взять»' и и", где л' = —, дУ (24) сг»: сг»о ивтЬ,а- мтЬ (26) то два неравенства в (23) переходят в равенства.
Ибо из уравнения (!8) мы имеем, что нли »,' = О, или с! †~ ',сг";ам ! ! (или же и то и другое), тогда как из самого определения и функции У следует, что если ~„ а,"»," ( Ьь то и'; = О. 1=! (Это последнее утверждение следует из того факта, что если некоторып вид ресурсов не используется целиком, то незначительное изменение его запаса не изменит оптимального дохода.) Итак, мы показали, что 440 новый подход к твояии двойствннности 1п. и Таблица ! Палевая ф1нкциясгх пн'и гпах ппп гпах гоах гпах Прямая задача Ограниче- ния Ах <Ь Перемен- ные х неогра- нич. Целевая ф1нкция Ьти го!о шах гп!и гпах пп'и пп'и Лаойстаепная задача Ограниче- ния А и -.= с Перемен- и ы е и неогра- нич. (О "О для всех х и и, удовлетворяюгцих ограничениям (3), (4), (21) и (22). Таким образом мы получили двойственную задачу: минимизировать сггЬ при ограничениях (21) и (22).
дг Мы ввели обозначения п; для — чтобы перейти к стан- дЬ! дг' дзртной терминологии. Смысл введенной величины — оче- дЬ; виден и используется всюду в выводах. При обычных выводах двойственности и вводят как множитель Лагранжа, а затем после формальных преобразований, направленных на получение двойственных результатов, замечают, что и имеет зкономический смысл.
Интересно отметить, как конкретная формулировка задачи влияет на нап!и заключения. Если бы неравенство в ограничениях (3) было бы обратнылг, тогда нагие заключение (19) о знаке двойстве>иной переменной было бы обратным. Равенство в (3) ничего не говорило бы о знаке двойственных переменных. (Так как все ресурсы г погреблялись бы при любом допустимом плане, то возрасгание Ь; могло бы иметь резулыатом возрастание или убывание дохода.) Переход от задачи максимизации линейной формы к аадаче минимизации сделал бы обратный сл!ысл неравенств в уравнениях (! 4) 441 гглзпвния куна — тлккггл (!5), (!6), (17) н (25), а также заключения, основанные на э!оа!.
В этом случае, конечно, можно было бы определить 7(Ь) как минимальное достижимое значение целевой функции. В таблице ! даны некоторые прямые и соответствуюнгие двойственные задачи. Читатель может легко проверить эти результаты па основе изложенного выше. Э. УРАВНЕНИЯ КУНА — ТАККЕРА: КВАДРАТИЧНЫЙ СЛУЧАЙ Задача квадратичного программирования заключается в выборе вектора х таким образом, чтобы максимизировать квадратичную целевую функцию их — —,х Сх т 1 г 2 (26) при ограничениях (3) и (4). Здесь х, А и Ь вЂ” такие же, как в $ 2, а компоненты Р~ г'я (27) сн см ...с,„ ся! см ° ° сэч (28) сл! сля спа заданы.
Кроме того, матрица С предполагается положительно определенной. Пусть у(Ь) — максимальное значение целевой функции. Если х' — оптимальное решение, то У(Ь) = лгха — —, х'гСхв. 1 2 (29) Рассмотрим снова функцию 7 (Ь+ аА'Л), являюшуюся теперь максимальным значением функции р у — т у Су при г ! г 2 442 повып подход к тгогии двонстве!тности 1п и ограничениях (10) и (11). Как и прежде,у=хо+се! удовлетворяет (10) и (11), что теперь приводит к доходу рт (ло ) с~) Р„..о+ ег)тО(ео д ос!) 1 о Р(Ь)+ о ~рг — ~> с;;х 1+ —,оос ь (ЗО) г=! Таким образом, о У(Ь+ оА1~!) з У(Ь) +о (рт — т с;!хг~ -!- — востр (31) 1=! Разложив левую часть в ряд по степеням о, получим для всех !'и о)0 т и о! Ът ду 1, Ъ1 Ъ' д7 ()+ ~~ дЬ; 0+2 ~ л дЬ;дЬЬ ю=- ! о=! о=! +члены более высокого порядка'= У(Ь)+ л +о,р — ~~ сгох!)+ — о'стр (32) Взяв о достаточно чальш, мы видим, что при всех / (3 3) или, в векторных обозначениях, А и гяр — Сх.
то о (34) Предположим теперь, что х')О. Тогда в приведенном выше рассуждении можно допустить отрипательные значения для о; при этом получится обратное по отношению к (ЗЗ) неравенство. Отсюда и из (33) имеем: ~~~ — а;,=р,— ~ с!ух!, если ху >О. (Зб) ! ! о=! 41 УРАВНЕНИЯ КУПЛ вЂ” ТЛЯКЕРЛ: ОЕШИИ случай 443 Чтобы превратить (33) в равенство при всех г', введем векгор Э! (36) пл определяемый уравнением г о о А и =р — сх -!-ш Тогда ясно, что о=О и что от=О, если х))0. (37) (38) (39) Как и в й 2, из определения функшп! вепство по - -О. следует нера- (40) Уравнения (37), (38), (39) и (40) представляют собой условия оптнжаллносгт! Куна — Таклера для сформулированной выше задачи кяадрати шого программирования.
Из уравнений (32) и (Зо) находим неравенство Х ' °; Д Л ЬЬ Ь опал =-'ту "."" х )О !=!а=! интерпретацию которого мы предлагаем читателю в качестве упражнения. 4. УРАВНЕНИЯ КУНА — ТАНКЕРА: ОБЩИЙ СЛУЧАЙ Предположим, что требуется максимизировать произвольную функцию о (х) при ограничениях (3) и (4). Опрелеляя 2(Ь) как максимальное значение целевой функции, а х" как оптимальное решение и применяя обычные рассуждения, получим: 7(Ь+аА!'!)) 4'(хоФае'), а) О, ! — любое, (42) У(Ь+аА"'))~р(х'+аа), а(0, х,")О.
(43) 444 новый подход к твоппи диойствшпюсти (п. и о (ха) г(Ь) (46) мы заключаем (как в 9 3), что 2'.— дУ дз дЬ; 17 =дху «=1 С» дУ дв У' дЬ! тт дх ' «=- ! а«уатт= — —,, если х»)О. (49) «=!а=! Если заменить — в уравнениях (47) и (48) на пп то мы поду ! лучим условпн оплтпмаланоспги Куна — Гаамера для сформулированной выше общей задачи математического программирования. для всех /, (47) если х!) О, (48) БИБЛИОГРАФИЯ 1. Н. %. К и Ь и апй А.'«ГО Т и с 1«е г, Хоп!!пеаг ргопгап«пт!г!е, Ргос.
Вссопб Весне!еу Вутро«шт о1 Магйетанса! В!а!В!к» апб РгоЬаЬг!пу, Нп!гегм!у о1 Сайогша Ргсю, Вегйе1еу, 1951, рр. 481 — 492. ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА С, ! асс, Линейное программирование, М., Физматгиз, 1961. С. К а р л пи, Математпчссние методы в теории игр, программировании и энономнне, М., Изд-ао «Мир», !964.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
