Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 28
Текст из файла (страница 28)
е. решение, которое следует принять в начале процесса. Так как у»(в)» р»о, мы заключаем, что К,=О, Е,=р, н »О=О. Отсюда (3.62) К» —— О, Е» = 2, п, = О. Заметим, что са)ра! это значиг, что мы должны обратиться к уравнениям (Зд55) — (3.57). Так как Е, (ра, применимо уравнение (357), которое даег значения К„=О, Е,=З, и,=О. (3.63) Для третьего от конца периода вследствие (3.63) н соотношений са) ра и Еа) са можем использовать уравнение (3.55). Следовательно, К»=В, Ее=2, и»=13. (3.64) получаем: (3.65) гг»а=о ! Для этого конкретного примера можем сделать следующие выводы. При оптимальной политике прибыль составляет 6В+7о, где о — запас в начале процесса и  — вместимость Продолжая этот процесс, К,=В, Е, Ке= ЗВ, Е Ке= 4В Ее Кт= 5В, Ее Ка=6В Еа К,=6В, Е, Кы = 6В* Е»е и,=О, и,=В, па=В, и,=В, па=В, иа !77 аадачх о поставщика склада.
Оптимальная полигика требует, чгобы в течение первых двух периодов не предпринималось никаких действий, и трегьем периоде было продано и и куплено В единиц, в течение четвертого и па~ого периодов склад оставался заполненным, в течение шестого периода было продано В и куплено В единиц, в седьмом периоде продано В, а в восьмом куплено В единиц, которые следует продать в девятом периоде. 29. ВЫВОДЫ Мы установили следующие результаты: 1. Оптимальный доход за АГ шагов является лиггепнов функцией начального уровня, коэффициенты которой зависят ог продажных и закупочных цен. 2. Оптимальная политика на любом шаге не зависит от уровня запасов в начале любого шага.
3. Опгимальная политика всегда имеет следую!цую простую структуру: не покупать и пе продавать в течение А первых периодов !1« может равнячься нулк«) и затем в течение оставшихся периодов держать склад либо пустым, либо заполненным. ЗО. ЗАДАЧА О ПОСТАВЩИКЕ Эта задача сильно отличается от только что рассмотренной по формулировке, но имеет аналогичную аналитическую структуру.
Она формулируется следующим образом. «Поставщик знае~, что в связи с обедами, которые он обязался обслуживать в течение следующих л дней, ему потребуегся в у-и день г чистых салфеток, /=1, 2, ..., п. Можно пользоваться двумя видами с~ирки: один требует у — 1 дней и стоит Ь центов за салфетку, срочная стирка требует «7 — 1 дней, д(р, и стоит с центов за салфетку, с ) Ь. Перед началом процесса поставщик не имеет салфеток и покупает их по цене а центов за штуку.
Как следует поставщику закупать и стирать салфетки, чтобы минимизировать суммарные затраты за и дней?» Можно указать несколько различных подходов к этой задаче. Мы укажем три способа: один приводит к функциям большего числз переменных, второй — к весьма простому 1тз сГлАжиВАние и состАВление Расписаний [Гл. и! аналитическому решению и, такил1 образом, к очень простому численному решению, третий дает простое непосредственное решение. В основе второго подхода лежит важная идея, с помощью которон упрощаются многие задачи вариационного исчисления. Несмотря на существование тривиального решения, ниже мы обсудим эту идею, так как мы будем обра|цагься к ней в связи с процессами с «узкими местамиа и при рассмотрении последовательных приближений.
31. ПОДХОД С ТОЧКИ ЗРЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ вЂ” 1 Первый подход к задаче с помощью методов динамического прогрзммировзния состоит в следующем. Состояние процессз в любой момент может быть определено номером шзгз, т. е. днем, и числом салфеток, которые следует получить из стирки через 1, 2, ..., р — 1 дней. На какой информации мы должны бззировать наше решение о покупке некоторого числа салфеток и как организовать стирку использованных салфеток? Нетрудно сформулировааь задачу на этом пути, используя метод функциональных уравнений.
К сожалению, если р велико, нас погубит размерность. Как мы увидим, денствительная размерность этой задачи в измененной форл|улировке равна р — в. На примере этой задачи мы очень хорошо проследим, как различные методы могут быть применены к одному и тому же процессу. 32. ПОДХОД С ТОЧКИ ЗРЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ вЂ” П Вместо упомянутого выше подхода будем действовать обычным образом с помощью уравнений, описывающих процесс, и на некотороп стадии решения привлечем метод динамического программирования. Прежде всего из приведенной формулировки задачи ясно, что мы можем закупить все салфетки одновременно перед началом процесса.
В таком случае начинаем с решения более простой задачи определения процесса стирки, если начальное количество салфеток равно Ю. 321 динамичвсков пвогваммивовлив -и Очевидно, (3.66) 8) шах гд. д (3,67) х„=(хд, — гд д)+ и, д+пд р ) где ив=па=О для й(0. Издержки л-го дня равны !гид+си,, 1=1, 2, ..., М вЂ” 1. (3.68) Следовательно, суммарные расходы составляют: С =6 '5', та +с ~, ид.
(3.69) Задача состоит в минимизации величины С при следующих ограничениях на ид: 0 <ид(гд, (3. 70) хд ~ гд, /г= 1, 2, ..., Д7, (а) (Ь) Чтобы проиллюстрировать этот метод, рассмОтрим сначала два частных случая: 7=1, р=2, 7=1, р=з, (а) (Ь) (3.71] а затем и общий случай. Сделаем теперь упрощающее предположение, что все использованные к концу дня салфетки немедленно отправляются в стирку, в срочную илн обычную.
Тогда процесс продолжается следующим образом. В конце 7г-го дня поставщик делит гд, количество имеющихся грязных салфеток, на две части: гд=ид+вд, ид салфеток посылаются в (р — 1)-дневную стирку и ъд — в (7 — 1)-дневную. Продолжая таким образом, мы видим, что количество хд чистых салфеток в начале й-го дня определяется следующим рекуррентны и соотношением: (зо сгллживлнив и согтлплгнив илспислний [ги. ги 33. АНАЛИТИЧЕСКОЕ РЕШЕНИЕ ДЛЯ с=), )а=2 Здесь уравнения (3.67) принимают вид хт= з х,=(х, — г,)+ сто хз = (хз — т'з) + гтз + оь (3.72) х -т=(х -з — гл-з)+ ил-з~~п»-з х,=(хч-т г».з)+тг -з~и -з.
Теперь выразим х» через и„и тз». Это — важный прием, с помощью которого мы существенно понижаем размерность процесса. С ннм мы еще встретимся ниже. Мы имеем: хз=8„ хз = (8, — г ) + ин хз — — (8 — г, — гз) + (л, + из) + и„ хз=(с '3 гз гз)+(зтз+згз+згз)+ -[- из+ пз, (3.73) х„,=(л — г, — г,—...— г„з)+(згз+ и,-,'— + из+... + и„з) + (из + из+... + ол з), х„=(8 — г, — г,—...— г„,)+(и, +и,+ + з+...+гз» )+(из+от+".-+из з) Так как 㻠— — тт»+о», то можно записать *): х»=8 — и»-т (о»=0), уз=(, 2, ..., и.
(3,74) ") Результат можно получить проще. Так как прн з) =1, р=2 (322) илзсет вид х» — х»,= — г», + и» з+о»-з= (о»-з — о»-з) то х„ = — о», + с, где константа с определяетсн начальнйм условием х,=5, оз=й, (Прим. ред) !вб) лнллитичвсков ввшвнии для 6=1, р=3 (!) 1з1 Обрашаясь к (3.69), мы хотим минимизировать !ч — 1 м — ! С = с ~Х ', г„+ (Ь вЂ” с) й=! ь=! (3.75) по всем оа при ограничениях (а) 0 =па(гм (3. 76) (Ь) 8 — оь ! га или о — га ) ва оь=ш!п(гм 8 — га„„!), 1=1, 2..... Аг — 1.
(3.77) Это равенство определяет структуру оптимальной политики. Используя явный вид решения (3.77), нетрудно определить минимизируюшее значение о'. 34. АНАЛИТИЧЕСКОЕ РЕШЕНИЕ ДЛЯ 4=а, р= я+1 Выписав соответствующие уравнения, нетрудно видеть, что случай !7= Ь, р= Ь + 1 приводит к системе уравнении того же типа, что и выше. Это показывает, что уровень трудности задачи определяется разностью р — 7. Зб. АНАЛИТИЧЕСКОЕ РЕШЕНИЕ ДЛЯ 4=1, р=3 6) Чтобы проиллюстрировать метод, применимый к обшему случаю, рассмотрим случай, когда !7=1, р=3.
Уравнения (3.67) принимают вид х,=8, ха =х, — г,+и, ха =х,— г,+и, хт — — ха — га+ иа+ о, (3.78) ха=Ха-! Гя.г+ ия-!+он-а. Так как (с — Ь))0, мы хотим выбрать оа как можно ббльшиии. Следовательно, 36) лнллитичвсков яннннив для с7=1, р=3 (и) 183 36. АНАЛИТИЧЕСКОЕ РЕШЕНИЕ ДЛЯ д=1, р=3 (И) Наша задача сводится к максимизации линейной формы л 7.,= 'У, 'сл а=с (3.83) нри ограничениях вида ссс= о„ йя~тс,+ ьь (а) (3.84) йч~о„+э г„)сь=-О. (Ь) где Й» †облас, определяемая условиями (а) х=--о„=-- О, о .
с ) оь т о 'сст ~ ест — с + ол га„с)эа,,)О, (3.88) гл,) ол,~ О. У„т (х) = шах (ол, с+ тс, ], (3.87) Выбрав оь мы имеем задачу того же типа для остальных переменных оа, о„..., эл, Определим последовательность функций (сь(х)), л=!, 2, ..., Ас — 1, следующим образом: у„(х)=шах ~~~ еп (3.85) нас а 1ва сгллии»ВЙВ» и сОстАВлении Р»спис»ниВ [гл. »»! где х)пх,=-0, ~ Ь - и,+ВА,, т,)п ~0. Следовательно, У„(~) = гп1~ [Ь~ + тх! (3.89) Опираясь на принцип оптимальности, иы видим, что ~»(х)= »пах [и» вЂ” ,'— г»»г(ппп(т» ь Ь»„— о»))1, (390) о»=»» где п»= пни [х, Ь»,д[ для Ь=1, 2,, „, Аà — 1.
37. АНАЛИТИЧЕСКОЕ РЕШЕНИЕ С помошью элементарных выкладок теперь можно показать, что У» (х) = ш1п [Р», х + 6»1 (3.91) где Р» = а1п [Р»ы+Ь» в 1;1»ы+ Ь»»[, Рл, — — Ь, ) (3.92) Я» = пип[Р»» и т», + Я»„,) и Г»=1, 2, ..., Аà — 1. Более того, аналогичный резул»лат имеет место в обшем случае, при любом целом значении р — у. Мы провели этот анализ, чтобы показать, что метод функциональных уравнений можно использовать для получения явных аналитических решении в ряде задач составления расписаний, аналогичных поставленной в задаче 3 36. 38. РЕШЕНИЕ, ОСНОВАННОЕ НА ЗДРАВОМ СМЫСЛЕ Покажем теперь, чго начальную задачу, сформулирован- ную в $ 30, можно решить с помощью очень простых рас- суждения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
