Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 29
Текст из файла (страница 29)
Рассмотрим сначала случай, когда 1»=2, р=4. Сохраняя прежние обозначения для величин и», и» и х, получаем следуюшие два условия на и» в виде неравенств, которым должны удовлетворять требования в те будушие периоды, на которые влияет решение, принягое в момент Ь: х,— т,— г...—,п»»+»г»,+и»=-т»,„, х» — 㻠— г» 1 — т»+я+ и», + и»+ (3.93) + п»ы+ и»-» -г.
и»-я+ и»-»~ т»»». 381 рршвнив, основлннов на здравом смыслв 185 Группнруя члены и переносн некоторые из них в правую часть (учитывая, что сса+оа —— га), имеем; 1 и,(х„— г„, — га,е-с-оа-а+ ил-с= Ес оа ( х„— теес — теде — га.з+ иаы+ (3.94) + -с+па-а+ — а+па- = Е. Если предположить, что затраты пропорциональны числу салфеток и не зависят, как и раньше, от времени, то ссаес можно положить равным гаер Это имеет место в силу того, что при исследовании вопросз об отправке возможно большего числа салфеток в обычную стирку можно предположить, что в дальнейшем все салфетки будут посылзться в срочную стирку.
Выбереас теперь о =-ш!п(Ен Е,(и,, =та,,), ге), 8 — э» рсдес — оа р,дее —... — эа — г„, —... таед-с ~ гаер о оа-редел оа-редел ° овес гаее " — таед теедес С (3.96) Я вЂ” о» вЂ” иа, —... — одер, — та р ...— т„ре)г,рр Здесь Р— с7 соотношений и оа(т. ") Решение, принятое в момент А, оказывает влияние в момент не ранее окончания срочной ((д — 1)-дневной) стирки и не позже, чем будут выстираны все салфетки (в оригинале индексы и и р перепутаны). (Прим. ред.) что решает задачу.
Числессссый пример для о = 20, с) = 2, р= 4 приводит к следуюсцим результатам: й 1 2 3 4 5 6 7 8 9 га 3 5 6 4 9 2 1 10 1 оа 3 5 2 4 9 0 1 10 1 и„О 0 4 0 0 2 0 0 0 х„, 17 12 6 9 5 5 1О 9 8 Перейдем к рассмотрению общего случая. Неравенствами; которым мы должны удовлетпорить, будут е); !86 сглАжиялниБ и состАВЛБниБ РАсписАний [Гл. н! Используем эти неравенства для определения границ вл. Чтобы сделать значение вл как можно ббльшим, положим в неравенствах (3.96) пль! равными О, 1~ 1. Это, как и раньше, допустимо, так как увеличение вл на единицу и !9 уменьшение вл„ нз единицу не влияет на величину ~, ву 1=1 Положив в нерзвенствах о ы — — 0 для всех 1~1 и перенеся члены в разные части неравенств, получаем следующие ограничения; Л вЂ” 1 Л+ 9 Оа — ~ Гп л †а+! !=А+! л †! а+9+! — гп л †9+9 1=а+а вл -= о— 1= (3.97) л+Р— ! пл~ о — ~~ гв 1=Л+Р— 9 вл ~ ' л.
В качестве примера рассмотрим случай, когда о=20, р=5, 9=2 (см. таблицу 3.5). Отмеченное звездочкой число 4 полу- чено следующим образом: 4=пни(20 — 8 — 0 — 3 — 2, 20 — 0 — 2 — 14, 20 — 14 — 1,8). (3.98) Таблица 35 гл 1 10 2 ~ 8 3 2 14 1 вл ) 1 ) 8 ( О ! 4* О 1 ) 14 ) 1 ил О ! 2 2 ! 4 ! 3 ! 1 О ( О лл„( 19 9 ! 9 ! 3 ( 5 ( 14 ! ( 4 39. ЗАДАЧА УПРАВЛЕНИЯ ЗАПАСАМИ Существует большое число процессов, заключающихся в образовании запасов с целью обеспечения неизвестного спроса в будущем. Здесь мы рассмотрим только простой случай, когда известно рзспределение величины будущего спросз. 187 39) зддачл 3'пнлилвния запасами Рассмотрим процесс образования запасов товара одного наииенования.
Предположим, что в каждый из конечного числа промежутков времени производятся заказы на дальнейшие поставки этого товара на склад и эти заказы немедленно выполняются. После того как заказ на товар сделан и удовлетворен, на него возникает спрос. Этот спрос удовлетворяется по мере возможностей, причем каждое превышение спроса над уровнем запасов ведет к убыткаль Допустим, что известны следуюшие функции: (а) т (з) Лз — вероятность того, что величина спроса находится между з и а+ттз; (Ь) А (а) — стоимость заказа партии размером г единиц дая пополнения уровня запасов; (3.99) (с) р(а) — стоимость заказа партии размером л единиц для покрытия неудовлетворенного спроса, или размер штрафа. Для простоты предположим, что эти функции не зависят от времени.
Наша цель — определить политику заказов, которая минимизировала бы ожидаемые расходы за весь М-шаговый процесс. Введем теперь следуюшую функцию: (х) — математическое ожидание издержек для Ж-шагом вого процесса при начальном запасе х и оптииальной (3.100) политике заказов. (3.101) Следовательно, У~(х)= шги ~А(у — х)+ ~ р(з — у)р(з)Из~. (3.102) у» к у Обычные рассуждения, основзнные нз перечислении всех возможностей, соответствующих различным случаям превышения Предположим, что на первом шаге мы заказали у — х единиц, так что уровень запасов поднимается до у.
Тогда ожидаемые издержки задаются функцией Уг(у — х)= ) р(з — у) р(з)~й. у !88 сглАживание и состхеление РАсписАИЕИ [Гл. и! спроса над уровнем запасов и уровня запасов над спросом, приводят к рекуррентному соотношению ОЪ г.( ~=.' 'РЬ вЂ” )ч-1н — к)~И~*ч- ! уж к у 0» у ) (ЗЗ08) ~г.— в~1,юак1г.— о — ир~~к1, ~ у о и) 2. Мы рекомендуем читателю сравнить эту задачу с задачей 8 10 главы П. Там мы имели дело с ожидаемыми текущими издержками, связанными с принятием определенного решения; здесь же мы имеем случайные текущие издержки, связанные с решением, и новое состояние, которое также случайно.
В обоих случаях мы встречаемся с одной и той же формализацией. 40, ОБСУЖДЕНИЕ С вычислительной стороны мы имеем осуществимый алгоритм вычисления последовательности [ Г' (х)[ и оптимальной политики заказов [у„(х)[. Однако при различных предположениях относительно функциИ л(а), р(е) и ю(а) мы можем продолжить исследование и получить простую характеристику оптимальной политики.
Особенно интересен случай, когда л(г) и р(з) — линейные функции вида й (г) = ле, л ) О, '( р(е)=рг, р)0. ) (3. 104) Здесь мы можем показать, что оптимальная политика имеет очень простую и понятную структуру, именно: для каждого И существует такой уровень запасов Яч, что если х)8м, мы ничего не заказываем, если же х(8м, мы заказываем о — „с, поднимая уровень запасов до о' . На первый взгляд приведенные выше функциональные уравнения не похожи на соотношения, полученные в задаче о замене оборудования и ее обобщениях. Если, однако, мы 189 411 дальнейшие упион1вния рассмотрим только дискретные значения уровня ззпасов и дискретные значения величины спроса, мы получим уравнения следующего вида: У,(1)=ш!п~й(/ — 1)+ ~ р(г — у)Р,-!-~„,(0) ~', са,+ / г= у-1.! г / 1 + Х Ул-~0 Г)Рг~ (3105) г=а для 1= О, 1, 2...,, М, в=1, 2, Мы увидим далее, что уравнение оптимального управления запасами можно рассматривать как частный случай общего уравнения для марковских процессов решения, рассмотренных в главе Х1.
41, ДАЛЬНЕЙШИЕ УПРОЩЕНИЯ я'; — величина спроса, 1; — Расходы на хранение единицы товара в течение следующего периода, 5; — организационные издержки (затраты на совершение сделки), л; — величина заказа. (3.1 06) Мы требуем, чтобы весь спрос удовлетворялся, н хотим минимизировать суммарные издержки. Считается, что заказ требует только организационных затрат: фактические расходы "1 Описанная ниже задача, но существу, отличается от предшествующей.
Учитываются единовременные затраты, сзазанные с самим актом заказа, и затраты на хранение. Решается задача о компромиссном выборе между политиками Регулярных многочисленных закупок н малого времени хранения и политиками Редких закупок н длительного хранения. (Прим. ред) В некоторых случаях детерминированная задача управления запасами, которая представляет собой одномерную задачу, требующую вычисления последовательности функций одной переменной (это достаточно простая задача для вычислительной машины), может быть сведена к еще более простой задаче, для решения которой достаточно ручного счета *). х(ля 1-го периода, 1=1, 2, ..., )ч', определим следующие величины: сглаживании и состзвлвнив влспислнип [гл. щ г-1 ш(п [Я,+ ~", '5; 1фа+Р(/ — 1)] 7<~ а=7 й=л-г! Я;+ гч(1 — 1) Р (1) = ш1п (3.107) где Р(1)=8, и гп(0)=0.
Следовательно, мы вычисляем одну функцию одной переменной вместо последовательности функция одной переменноп. 42. ПЛАНИРОВАНИЕ ПРОИЗВОДСТВЕННОЙ ЛИНИИ Последняя задача, которую мы хотим рассмотреть, представляет собой простой пример из важного класса задач, связанных с организацией производства.
К очень немногим задачам этого класса найдены подходы, а так как решение, на закупку товаров мы не включаем, так как предполагается, что стоимость заказа линеппо зависит от его обхема, причем стоимость единицы товара постоянна. Отсюда следует, что, за исключением организационных расходов, суммарная стоимость заготовки одинакова для любой программы удовлетворения спроса. Пусть 7 обозначает запас товаров в начале периода.
Легко доказать следующие утверждения. 1. Существует оптимальная программа, для которон!х; = 0 для всех Е Иначе говори, если в начале периода имеется излишек товара, то мы не производим никаких заказов. 2. Сугцествует такая оптимальная программа, что для всех г или х, = О, или для некоторого и, 1 й ( М, х; = Иначе говоря, заказываем как раз столько товара, 7=! сколько нужно для удовлетворения будущего спроса в течение некоторого будущего периода 7г. 3. Существует такая оптимальная программа, что если спрос 4. удовлетворяется некоторым заказом хи., Р*(1*, то Ыв г=1ь*+ 1,, 1ч — 1, также удовлетворяется этим заказом. 4. Если для периода 1 мы имеем 1= О, то в оптимальной политике периоды 1, 2, ..., 1 — 1 можно рассматривать независимо от оставшейся части процесса.
Обозначив через Г(1) минимальные издержки за периоды 1, 2,, К мы получаем: 43] млтвмлтичвскля постлновкл злдлчи 19! которым мы располагаем, весьма изящно, по-видимому, целесообразно его здесь привести. Его можно использовать, чтобы получить приближенные решения более сложных взриантов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
