Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 19
Текст из файла (страница 19)
Впоследствии лгы обсудим, как избежать потери точности при таком подходе, в связи с методом последовательных приближений. 39. ПРИМЕНЕНИЕ МНОЖИТЕЛЯ ЛАГРАНЖА К ЗАДАЧЕ С ТРЕМЯ СКЛАДАМИ Как мы уже отмечали, если имеются три склада, то с вычислительной точки зрения задачу лгожно рассматривать в терминах последовательностей функций двух переменных. Но если ввести множигель Лагранжа, задача сведется к вычислению последовательности функций одной переменной.
Займемся теперь этим детально. Рассмотрим задачу с тремя складами, в которой имеется количество х, на первом складе и неограниченные количества на втором и третьем складах: г),; х, Р,;г, Ря: со Р,:гя )Эа. оо — л — г пянмвнвнив множитвля ллгялнжа 111 Предположим, что стоимость перевозки такая же, как и выше, и что за каждую единицу, перевезенную из //я, мы плзтим дополнительно )ч и за каждую единицу, перевезенную из Оа, дополнительно платим 1. В этом случае общие издержки задаются выражением а !г л! Ч~~ К;, (х;,) + Л ~ хя/+ ~~ х„.
(2.111) /=! /=! !.=!/ ! л // Х = + х. / чя ха/ — — х,+х,— / г/, /= ! /=. ! (2.112) У т.е. У х„является фиксированной величиной, так как запасы /=- ! равны спросу. Следовательно, при желании мы могли бы совсем исключить третий член в (2.111). Положим //г(х!) равной наименьшему значению функции (2.111), где минимум берегся по области ~, х„.=хь /= ! хьь х„, хго ) О.
(а) (2.113) (Ь) Чтобы получиаь рекуррентное соотношение для /м, мы, как и раньше, удовлетворим сначала спрос в /!/-и пункте потребления. Мы приходим к уравнению гл( !) 1К!//( !м)+Кя/г( ам)+КО( ам)+ "и + Ххаж+ хам -1-Ул ! (х! — хгл)), (2.114) Первой мыслью читателя може~ быгь мысль о том, что следовало бы использовать два множителя Лагранжа. Однако в этом нег необходимости, что видно из следуюшик соображении. Допустим, что а меняется до тек пор, пока для минимизирующих значении х;, мы не будем имегь равенства !г ~~ хя/=хе Тогда автоматически получим: /=1 112 многомьиныв пиоцвссы влспгвдвлвиия [гл.
и где Я,„ — область, задаваелгая условиями (а) х| и+ хгл+ хал = гл (Ь) 0 хм~хи (с) ~гл' Згг (2.115) Минимизация по переменным х и ха может быть выполнена заранее в явном-виде или численнсь Пусть где о, — новая область, определяемая условиями хгм+хам=гн хаас хгм хам)0.
(а) (Ь) (2.117) Тогда рекуррентная формула (2.114) примет вид (х,)= пнп (8ьт(хщ, Л)+лм(х,„; Л)+ О к1т гл +~к,(х, — х, )). (2.1!8) Параметр Л теперь изменяется между — со и +оп, пока общее количество, перевозимое из Ом не станет равным хг — начальному уровню ресурсов в О,. Перевозимое из Оа количество будет тогда автоматически равняться хг —— и = ~ч~~ гг — х1 — хг. ! 1 40. ПРИМЕР 1 — ДВА СКЛАДА, ДЕСЯТЬ ПУНКТОВ ПОТРЕБЛЕНИЯ В первом численном примере — перевозка из двух складов в десять пунктов потребления — мы будем считать, что стоимость перевозки представляе~ гобои квадратичную функцию от перевозимого количества плюс «организационные» расходы, Под «организационными» расходами мы понимаем затраты, не зависящие от перевозимого количества и равные нулю, когда перевозка не производится.
Стоимости приведены в таблице 2.6. д (хл; Л)=пни (8гг«(хгл)+дал~ха„)+Лхгм+ха,), (2.116) 'л 113 401 ПРИМЕР ! Таблипа 2.6 Ит скллдз 2 Потреби- тели Спрос ортзнизл. пиа жые л дз рксколы 2 3,1 4,1 2,1 0,01 1,1 0,1 2,6 3,0 — 0,01 1О 5 1,0 0,2 2,0 2,0 5,0 0,0! 0,05 Ь,О 6,0 Этой таблицей надо пользоваться следующим образом. Каждая функция 8О1х) имеет вид ды(х)=а;,х+Ьмх'+с; (х), (2.119) где с;,(х) — то, что обычно называют «организационными» расходами, или «постоятшыми издержками»; сы(х) равно О, если х = О, и равно постоянной с;, если х ) О.
Коэффициент при х ищется в столбце «х», коэффициент при х' — в столбце «х'», «организационные» расходы— в столбце с соответствующим названием. Таблица 27 Из склзлз 2 ~ Издержки Нзкоплениые издержки Потребители Из склада ! 1 2 3 4 5 6 7 8 !О 1 2 4 6 7 8 9 1О 10 25 15 0 20 0 0 20 1,0 2,0 3,0 1,5 2,5 5,0 3,0 6,0 0 0 40 0 0 !5 0 15 10 0 10,00 51,00 99,25 22,50 1'2,50 45,00 60,00 30,00 20,00 120,00 1О 25 45 !5 15 20 15 1О 20 10,00 61,00 160,25 182,75 195,25 240,25 300,25 330,25 350,25 470,25 114 многомррньш процвссы рдспрядвлвния [гл.
и Так, стоимость перевозок количества х из склада 1 к потребителю 3 равна Зх †, '0,01х'! из склада 1 к потребителю 2 равна 1+ 2х, если х) О, и О, если х=О. Предположидг, что надо перевезти 100 единиц из склада 1 и 80 единиц из склада 2. Оптимальное решение приведено в таблице 2.7. Расчет на вычислительной машине Лжонниак Корпорации ЯАХР занял 2 мину1ы для вычислений и 4 минуты для вывода результагов. 41. БЛОК.
СХЕМА ПРОГРАММЫ ДЛЯ СЛУЧАЯ ДВУХ СКЛАДОВ !ом. рис. 27) 42. ПРИМЕР й — ТРИ СКЛАДА, ДЕСЯТЬ ПУНКТОВ ПОТРЕБЛЕНИЯ Лобавии к примеру! третий склад. Показатели стоимости его перевозок приведены в таблице 2.8. Табанил 2.8 На склада а Органнааднонныс рассады Спрос Погрсбнгслн На складе 3 имеюгся 155 дополнительных единиц и, как показано выше, на такую же величину увеличен спрос. При использовании метода множителей Лагранжа выбор 1,=2,0 дает нужный резулыат. Оптимальное решение приведено в таблице 2.9. 1 б 7 0 10 25 40 60 30 20 30 35 30 23 40 116 многомьрныв процвссы рдспрвдвлвния [гл. и Таблица 29 Поеребиеели Склад!~ Складр Склад а ~ Иадерыки Накоалекиые иадержки 1 ~ 25 0 0 ! 25,00 0 0 55 0 0 30 0 20 0 30 0 5 0 ЗО 2" 81,00 130,75 30,00 20,00 65,00 110,00 96,00 а 0 0 40 о0,00 240,00 Расчет для каждого значения ), занял 7 минут.
43. ПОСЛЕДОВАТЕЛЬНЫЕ ПРИБЛИЖЕНИЯ вЂ” 1 Одним из путей преодоления трудностей, связанных с размерностью, является привлечение наиболее мощного из всех средств анализа — метода последовательных приближений. Схема негода в общих чертах выглядит следующим образом. Т(ля заданного функционального уравнения мы угадываем решение. Если предполагаемое решение не является истинным, то мы делаем поправку, определяемую самим функциональным уравнением, надеясь получить таким путем лучшее приближение к решению. Процесс продолжается до тех пор, пока мы или не получим решение или не подойдем к нему с требуемой сгепенью точности.
Один из путей использования этого подхода состоит в следующем. Пусть заданное уравнение, решение которого мы ищем, имеет вид Т(и)=0 (2.120) и пусть уравнение 8(п)=0 легче решить. Запишем исходное уравнение в ваде Ю(п) = З(гг) — Т(и), (2.121) и пусть за первое приближение и, взято решение уравнения З(гг) =О. Пусть следующее приближение и, определяется из уравнения 8(иа) = Ю(гг ) — Т(во) (2. 122) 2 3 4 б 7 8 9 10 40 0 0 0 30 0- 0 0 25,00 106,00 236,75 266,75 286,75 351,75 461,75 557,75 607,75 847,75 44] пРиБлижении В пРостРхнстВР политик 117 и вообще (л-.,'-1)-е приближение получзегся из л-го приближения с помощью уравнения 8(гг„„) = 8(и„) — Т(п„). (2.123) Если 8(п) выбрано подходящим образом и Т(п) обладает соответствующими свойствами, то последовательность ]гг„] будет сходиться к решению уравнения Т(п)=0.
Много рзбот посвящено применению эгого метода к исследованию дифференциальных уравнений — как обыкновенных, так и в частных производных; кроме того, сделаны некоторые предварительные попытки применения его к функциональным уравнениям динамического программирования. Ссылки на соответствующие результаты и Не~оды даны в конце главы. Однако в соответствии с нашей общей программой мы будем действовать формально, просто демонстрируя различные подходы. Для иллюстрации конкретных применений метода будут приведены результаты некоторых численных расчетов.
Имеется множно разных путей применения основных идей, но эта область фактически еиде не исследована. 44. ПРИБЛИЖЕНИЕ В ПРОСТРАНСТВЕ ПОЛИТИК 11рототипом уравнения динамического программирования в общем виде является уравнение Х(р)=шах(у(р, д)+У(Т(р, д))]. (2.124) Здесь р — параметр состояния, а г) — решение. Классический подход к этому уравнению в обы щой ситуации, когда нельзя найти точное аналитическое решение, заключается в угадывании начальной функции га(р), а затем в определении последова1ельности функций с помощью рекуррентного соотношения 1„„(р)=шах ~д(р, г))+1„(Т(р, ц))], л=О, 1, ... (2.125) а В сбщем нетрудно устзновигь сходимость этой последовзтельности к решению уравнения (2.124), кроме того, условия, обеспечивающие сходимость, обычно гарантируют также и единственность решения.
Заметим, что в уравнение (2.!24) входят в действительности две неизвестные функции: функция дохода У(р) и функция 11 Я многомг ныя пвопнгоы ялспидвлвнпя (гл. и политпксс 7(Р). Они, конечно, не являются независимыми, ~ак как одна определяет другую. При заданной фушпши дохода 7 (Р) функпия политики определяется с помощью операпии максимизапии правой части уравнения (2.124), при заданной функпии политики 7(Р) функция 7(Р) определяется как решение уравнения 7 (Р) =а(р, в) +7 (7 (р, 7)), (2.126) где д=д(р). Это уравнение обычно разрешается прямым итерированием.
Признание равнопенности двух функций т" (Р) и д(Р) дает нам возможность сильно увеличить сферу действия метода последовательных приближений. В дополнение к предложенному выше способу приближения с помощью соотношения (2.!2о), мы можем рассмотреть новьш тпап приближения, представляющий особый интерес для теории многошаговых процессов решения, приближаю!я в пространстве политик. Вместо того чтобы начинать с угадывания нида функции 7(7У), мы будем начинать с угадывания вида функции д(Р). Срответствуюшая функция дохода ~,(Р) определяется как решение уравнения 7а(Р)=Ы(Р йо)+7я(7 (Р, ~7о)) (2127) где д„=да(Р).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
