Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 21
Текст из файла (страница 21)
Поиск при значениях х, равных О, 3, 2а,, дает относительный максимум в точке 25, но не абсолютный максимум, лежащий между 48 и 58. Примеры, столь яркие, как этот, конечно, маловероятны. Тем не менее мы должны всегда иметь в виду такую возможность. Предположим, что мы па самом деле определили положение максимума х; = х;(х) =х;(х; Ь) в пределах +-3 от положения истинного максимума.
Тогда, используя более мелкую сетку, например О, Ь, 25, ..., где 6 = 1ОЬ или !ООЬ, !2б многомггныв пгоцвссы илспгвдвлвния [гл. ш мы присоединяем ограничения х;(х; 8) — б х;(х)(х;(х; 3)+3, 1=1, 2, ..., Аг, (2.147) где х;!х; б) — функции, определенные первоначально при более грубой сетке. Ограничения такого типа уменьшают требования к об.сему памяти и существенно сокращают время на определение максимума процессом поиска. На применение такой идеи мы будем ссылаться в $ 11 главы 11!. 40. ПОСЛЕДОВАТЕЛЬНЫЕ ПРИБЛИЖЕНИЯ В ЗАДАЧЕ ХИЧКОКА в КУП!ч!АКСА Вернемся теперь к задаче Хичкока — Купманса вооруженные новыми методами. Мы видели, что процесс с М складами можно рассматривать непосредственно в терминах функций от М вЂ” 1 переменных и с поносные множителей Лагранжа— в терминах функций от М вЂ” 7г переменных.
Покажем теперь, каким образом можно использовать метод последовательных приближений для анализа этой задачи с помощью последовательностей функций от одной переменной. Чтобы добиться этого, поступим следующим образом. Прежде всего, пусть запасы на складках 0а, 0м ..., 0,и распределены так, чтобы любым способом удовлетворить часть требований в точках спроса.
Тогда оставшиеся запасы на 0~ и О, распределяются таким образом, чтобы удовлетворить оставшимся требованиям при минимальных издержках. Как мы знаем, решение такой задачи своди~ся к вычислению последовательностей функций от одной переменной и гаким образом может рассматриваться как стандартная операция. Это — первый |наг в методе последовательных приближений. Далее мы используем на складах 0м ..., 0м те же распределения, что и выц1е, на складе 01 — распределение, определяемое процедурой минимизации, а на складах О, и О, выбираем распределения тзк, чтобы удовлетворить оставшимся требованиям с помощью процедуры минимизации.
Это — второй шаг. б1! пяп«гГР ! — отпосцтвль~пяй мппимтм 127 1лалее мы фиксиРУем РаспРеделениЯ иа складах с)м ..., г)м, 0„ как выше, используем па складе с), распределение, определяемое предшествующей минимизацией, а затем решаем новую задачу минимизации стоимостей перевозки из складов Оа и Рм Затем процесс продолжается заким же образом. бб. СХОДИМОСТЬ 1)режде всего ясно, что последовательность функций минимальных издержек должна сходиться, так как издержки иа каждом шаге вычислений не возрастают.
Однако неясно, к чему сходится эгот процесс, и фактически нетрудно построить примеры, в которых минимум ~аким пугем ие достигается. В обоих приведенных далее примерах паш метод заключается в том, что сначала фиксируется сголбец хаа при единственном условии, что ~тхаг —— хм по не хау) г,. В примере 1 у мы распределили запзс со склада 3 довольно равномерно по точкам спросз. В примере !1 мы последовзтельпо удовлетворяем спросы каждого из потребизелей до ~ех пор, покз пе исчерпаем запас на складе 3. Затем мы вычитаем из величии спроса всех потребителей полученные ими количествз груза и решаем оставшуюся задачу с двумя источниками.
Полученное решение мы используем при определении х,. во второй итерации. Это решение определяет х«у для третьей итерации, после которой мы повторяем цикл, фиксируя ха Процесс продолжается до тех пор, пока пе получится устой. чивое распределение во всех трех типах подпроблем. В приведенных ниже примерах мы рассматриваем случай трех складов и десяти точек спроса. б1, ПРИМЕР 1 — ОТНОСИТЕЛЬНЫЙ МИНИМУМ Рассмотрим случай, когда каждая из функций пгт имев~ вид угу (х) = ас х+ (ггтхз+ ггу (х), (2.148) где с; (х) — «оргаиизациопиые расходы, или фиксированные издержки, равные нулю, если х=-й, и постоянной сси если х) О. 128 многомьрныв процвссы рлспрвдвлвния [гл.
и Коэффициенты ат приведены в столбце (х) таблицы 2.10, а ттт — в столбце (х'). Таблица 2.! 0 Источник 2 Источник ! Источник 3 Спрос ол Йо Ии «8 кз о« аа Во « о « «о « а ч о. ай ~ ыт- рсби- тель « «Й «а о« +1,0 +2,0 +3,0 +1,5 +2,5 +5,0 +З,О +6,0 +6,0 +6,0 +2,0 +1,0 +.0,01 -ьО,!О +! 0,0 +5,0 — 0,01 +0,20 +5,0 +6,0 +8,0 — 0,05 +0,01 х, — запас на складе 1=.100, х,— запас на складе 2= 80, х,— запас на складе 3=155.
Результаты, полученные методом последовательных приближений, приведены ниже в таблипе 2.11. Таблина 2.1! Политика т по. « ° з Патитикк 1 Пакетике 2 25 0 0 40 0 0 0 60 0 0 0 ЗО 0 0 20 0 0 ЗО 35 0 0 0 0 ЗО 0 10 15 0 10 ЗО Затраты = = 874,00 126,25~ = 966,00 1 2 3 4 5 6 7 8 9 !О 1 10 0 2 25 0 3 5 40 4 15 0 5 5 0 6 0 15 7 20 0 8 О !5 9 0 10 10 20 0 Затраты =1 15 15 15 15 15 15 1з !5 15 20 10 15 0 25 0 15 5 55 0 15 0 !5 5 0 !5 0 0 ЗО 20 0 15 0 0 ЗО 0 10 15 20 0 20 Затраты = +3,1 +4,1 +2,1 +1,1 +2,6 +з,о +1,0 +2,0 +2,0 +5,0 10 15 0 40 0 0 5 55 0 0 0 ЗО 0 0 20 0 0 30 35 0 0 0 0 30 0 10 15 10 0 ЗО Затраты = = 921,25 +70 +3,0 +9,0 +1,0 +1,0 +2,0 +4,0 +3',0 +5,0 +6,0 25 40 60 30 20 ЗО 35 30 25 40 335 129 52! примни и — лвсолютный»иинт1ум Продолжение лаибл.
2.!! Иааотика 5 ~ Иааитика 5 Тачиас реимиие Пааитика 7 25 0 0 40 0 0 5 55 0 0 О 30 0 0 20 0 0 30 30 0 5 0 0 30 0 25 0 0 0 40 Затраты = = 847,75 1 25 0 0 2 40 0 0 3 О 60 0 4 0 0 30 5 0 0 20 6 0 0 30 7 35 0 0 8 0 0 30 9 0 20 5 1О 0 0 40 Затраты = = 853,00 ы= = 853,00 52. ПРИМЕР 11 — АБСОЛЮТНЫЙ МИНИМУМ Рассмотрим теперь случай, когда все функции у;7(х) выпуклые *) и имекут вид а;ух+ ьуухт. числовые данные в примере сведены и таблицу 2.12. Таблица 2.12 1 ,' Истачиик З )! Истачиик 3 Источник аз о о ко оо л о о оа во = о.
с а ои ой оа = "с с.з о Сирое х хе 0,10 0,20 0,06 0,01 0,05 ~ 0,01 0,20 0,05 ' 6,0 0,0! ха — запас на складе 2 = 97, х„— за- складс 3 = 138. л, — запас на складе 1 = !00, пас на а) В этом случае любой относительный минимум азлистси абсолютвлл1. (Приле. Ррд.) 5 Р, веллиаи. с, дрейФус 1 о 3 4 5 6 7 8 9 10 1,0 2,0 З,О 1,5 '2,5 5,0 3,0 6,0 25 0 0 40 0 0 0 60 0 0 0 30 0 0 20 0 0 30 35 0 0 0 0 30 0 20 5 0 0 40 Затраты = = 853,00 25 40 0 0 0 0 35 0 0 0 Затрат 3,1 4,1 2,! 1,1 2,6 З,О 1,0 '2,0 2,0 5,0 0 0 О 0 60 0 0 30 0 20 0 30 0 0 0 30 20 5 0 40 7,0 3,0 9,0 1,0 1,0 2,0 4,0 З,О 5,0 6,0 25 0,04 40 60 0,20 20 30 35 0,10 30 25 40 130 многомвяныгт пяоцвссы васпягдвлвния !гл. и итераций приведены в таблице 2.!3.
Т а 6 а и ц а 2.13 Результаты политик» а Политика а Но»»тика а Поиинка 1 Затраты = = 1035,439 Затраты = = 1040,55 Затраты = = 1141,25 Затраты = = 1535,249 Полни»ка а Палаток» 7 По»»тика а Политика 5 Затраты = = 1020,69 Затраты = = 1022,089 Затраты = = 1026,44 Затраты = = 1031,24 1 0 0 25 2 0 0 40 3 0 0 60 4 !7 0 13 5 11 9 0 6 0 30 0 7 32 3 0 8 0 30 0 9 0 25 0 10 40 0 0 1 12 4 9 2 21 0 19 3 7 53 0 4 0 0 30 5 !1 0 9 6 0 0 30 7 33 0 2 8 0 20 1О 9 0 20 5 1О 16 0 24 0 4 21 0 0 40 0 60 0 17 0 13 11 0 9 0 0 30 32 0 3 0 20 10 0 13 12 40 0 0 15 4 6 21 0 1О 7 53 О 0 0 30 13 0 7 0 0 30 35 0 0 0 20 1О 0 20 5 9 0 31 15 4 6 21 0 19 0 60 0 0 0 30 13 0 7 0 0 30 35 0 0 0 20 10 0 13 12 16 0 24 12 7 6 21 0 19 12 48 0 0 0 30 13 0 7 0 0 30 33 2 0 0 20 1О 0 20 5 9 0 31 12 7 6 21 и 19 7 53 0 0 0 30 11 2 7 0 0 30 33 2 0 0 20 10 0 13 12 16 0 24 12 4 9 21 0 !9 12 48 0 0 0 30 13 0 7 0 0 30 33 0 2 0 20 10 0 25 0 9 0 31 13! пРимБР и — АБПОлюти119 минин! м 52~ Продолатсенве отабл.
233 Политика 1О ! Политика П ) Политика !а Политика О Затраты = = 1009,64 Затраты = Затраты = = 10!6,89 = 1013,04 Затраты = = 101'2,44 Политика 1а Политика 1! Политика 16 Политика 15 Затраты = Затраты = Затраты = = 1007,85 = 1007,75 = 1007,25 Затраты = = 1006,76 1 15 4 6 2 21 0 19 и 12 48 0 4 0 0 30 5 13 0 7 б 0 0 30 7 35 0 0 8 О 20 !О 9 0 25 0 1О 4 0 36 ! !3 8 4 2 2! 0 !9 3 20 40 0 4 0 0 30 5 13 0 7 6 0 0 30 7 33 2 0 8 0 22 8 9 0 25 0 1О 0 0 40 12 7 6 21 0 19 17 43 0 0 0 30 !3 0 7 0 0 30 33 2 0 0 20 !О 0 25 0 4 0 36 13 7 5 2! 0 19 20 40 0 0 0 30 !3 0 7 0 0 30 33 2 0 0 23 7 025 О 0 0 40 12 6 7 21 0 19 17 43 0 0 0 30 !3 0 7 0 0 30 33 1 1 0 22 8 0 25 0 4 0 36 14 7 4 20 0 20 20 40 0 0 0 30 13 0 7 0 0 30 33 2 0 0 23 7 0 25 0 0 0 40 15 6 4 21 0 19 17 43 0 0 0 30 !3 0 7 0 0 30 34 1 0 022 8 0 25 0 0 0 40 13 8 4 20 0 20 21 39 0 0 0 30 13 0 7 0 0 30 33 2 0 0 23 7 0 2э 0 0 0 40 !32 МНОГОМЕРНЫЕ ПРОПЕССЫ РАСПРЕДЕЛЕНИЯ ~ГЛ.
Продолженое табл. 2.!3 Политика 1а ~ Политика 12 Политика П Политика 20 93 8 4 20 О 20 22 38 0 33 2 0 0 23 7 0 25 0 0 0 40 9 0 25 0 10 0 0 40 Затраты = = 1006,14 Затраты = = !006,76 Затраты = =! 006,41 Затраты = = !006,04 Политика 21 Политика 22 Политика 21 Г!олнтнк* 23 13 9 3 0 21 37 0 0 30 0 8 !2 0 0 30 33 0 2 0 24 0 25 0 0 0 40 Затраты = = 1005,39 Затраты = = 1005,49 Затраты = =!005,49 Затраты = = 1005,74 1 13 8 4 2 20 0 20 3 2! 39 0 4 0 0 30 5 13 0 7 б 0 0 30 7 33 2 0 8 0 23 7 1 14 8 3 2 19 0 21 3 22 38 0 4 0 0 30 5 12 0 8 6 0 0 30 7 33 2 0 8 0 24 6 9 0 25 0 10 0 0 40 14 8 3 20 0 20 21 39 0 0 0 30 12 0 8 0 0 30 13 9 3 !9 0 21 23 37 0 0 0 30 12 0 8 0 0 30 33 2 0 0 24 6 0 25 0 0 0 40 13 9 3 20 0 20 22 38 0 0 0 30 12 0 8 0 0 30 33 2 О 0 23 7 0 25 0 0 0 40 0 0 30 !2 0 8 0 0 30 33 2 0 0 24 6 0 25 0 0 0 40 14 9 2 18 0 22 23 37 0 0 0 30 12 0 8 0 0 30 33 2 0 0 24 6 О 25 0 0 0 40 !33 бз] стохлстичвскля итвялция Прадалженлле табл.
2.И Полилика 25 ~ Политика 28 Политика 27 ~ Политика 28 Затраты = Затраты = Затраты = =1005,36 =!005,26 ! =!005,26 Затраты = = 1005,26 Интересно отметить, что хотя точность в пределах 4о,к достигается уже на третьей итерации, для получения абсолютного минимума потребовалось двадцагь восемь итераций. Кроме того, если обратиться к двадцать второму и двадцать третьему шагам, то мы видим, что не имеется никакого улучшения, когда зафиксировано распределение на первом складе, но тем не менее при фиксировании распределения на втором складе улучшение имеется. 53. СТОХАСТИЧЕСКАЯ ИТЕРАЦИЯ Выше мы действовали заранее определенным циклическим образом, в которои мы выбирали склады (г)и Ва), !Р„08) и т.
д. Легко построить примеры, когда при таком способе м!я приходим к у~ловым точкам и относительным минимумам. !!оэгому может оказаться более целесообразныч выбор двух складов па каждом шаге случайным образом. В более общем случае, когда имеется много складов, необходимо перебрать все возможные комбинации по два склада, чтобы гарантировать, что мы достиглн абсолютного минимума. 1 13 10 2 2 18 0 22 3 24 36 0 4 0 0 30 5 12 0 8 6 0 0 30 7 33 2 0 8 0 24 6 9 0 25 0 10 0 0 40 13 9 3 18 0 22 24 36 0 0 0 30 12 0 8 0 0 ЗО 33 2 0 0 25 5 0 25 0 0 0 40 13 9 3 18 0 22 24 36 0 0 0 30 12 0 8 0 0 ЗО 33 2 0 0 25 5 0 25 0 0 0 40 13 9 3 18 0 22 24 36 0 0 0 ЗО 12 0 8 0 0 30 33 2 0 0 2о 5 0 25 0 0 0 40 134 многомягныв пвоцвссы глспгвдвлвния 1гл. и Все же и тогда в пространсгвах большого числа измерений можно ожидагь ситуаций, ко~да даже такой тнп «субминимизации» не будет гарантировать достижения абсолютного минимума.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
