Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 27
Текст из файла (страница 27)
Таким способом часто можно обойти обычные трудности, связанные с многомерностью. Ниже мы рассмотрим процесс управления запасами, который является интересной комбинацией процессов сглаживания и замены оборудования. 1бй 21) мАтемлтнческля модель 20. ЗАДАЧА СКЛАДИРОВАНИЯ Продолжая рассмотрение одномерных процессов составления расписаний, обратимся к следующей задаче.
сПусть имеется склад фиксированной вместимости с некоторым начальным запасом товара, стоимость которого подвержена известным сезонным изменениям. Какова оптимальная политика покупки (или производства), хранения и пролажи этого товара?» Метод динамического программирования дает возможность не только создания простого вычислительного алгоритма, но и нахождения точного аналитического решения задачи с помощью основных функциональных уравнений. 21. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ Начнем с введения следующих величин:  — вместимость хранилищ склада, о — величина наличного запаса на каждом шаге. Рассмотрим сезонный товар, который мы должны заку- пить (или произвести), а затем продать в течение Ат перио- дов. Введем следулощие обозначения (индекс т указывает, что до конца остается т периодов): с; — затраты на единицу товара (покупаелюго или производимого), рк — продажная цена единицы товара, (3.35) хг †количест произведенного или купленного товара, у; — количество проданного товзра.
Нз всякую возможную политику мы должны наложить следующие огрзничения: (а) Ограничение на покупку. Запас в конце г-го периода ие может превышать вместимости склада, (Ь) Ограничение на лродтжу. Количество товара, проданного в г-й период, не может превышать количества товара, имеющегося на складе в конце (1 — 1)-го периода. (с) Оеошрицашельность. Объем товзра, купленного или продзнного в любой период, неотрицателен. 170 сГлАжиВАния и состАВлвниВ РАсписАний [Гл. тц Следствием этих ограничений являются неравенства "): Ограничения на покупку о+ ~ (х! — у!)(В, 1=1, 2, ..., !т!.
у=- ! Ограничения на продажу ! — ! ут(о+ ~', (х — у), 1~2, З,...,ттт, у=! (3.37) у, с о. Неотрицатеаьность хь у! О. Придерживаясь этих ограничений, мы хотим максимизировать суммарную прибыль, полученную при М-шаговом процессе, т. е. функцию Р = ~', (руу! — сух!). (3.38) у=! 22. РЕНУРРЕНТНЫЕ СООТНОШЕНИЯ Чтобы рассматривать эту задачу методами динамического программирования, введем последовательность функций [у" (о)[, определяемых соотношением (о)=шах Рм (у,л! (3.
39) (3.40) где максимум берется по области О~у!(о, х!)О. 'Следовательно, Г! (П) =р!хь (3.4!) (3.42) в) В неравенствах (3.3!), и только в них, авторы испочьзуют отсчет времени в прямом направлении, и индекс ! означает число прошедших периодов от начала. Далее и до конца в рассмотренной задаче применен обратный отсчет. (Орил!. рсд.) для значений о) О, !!!=1, 2... где х! и у! удовлетворяют соотношениям (3.37). Для Лт= 1, очевидно, имеем; Л (о) = !пах (р,у, — стх!), ПРЕДВАРИТЕЛЬНЫЕ ПРЕОБРАЗОВАНИЯ 171 24] Для М)2 обычным образом получаем рекуррентиое соотношение у' (о) = вах [ром — глх +~м !(о+хгг — ул!)],(ЗАЗ) лл гм ™ где мзксимум берется по облзсти (а) 6~у„~о, (Ь) х,)0, (с) о+х, — у,( В.
(344) 23. ОБСУЖДЕНИЕ 24, ПРЕДВАРИТЕЛЬНЫЕ ПРЕОБРАЗОВАНИЯ Далее оказывается удобным рассуждать в терминах уровня запасов, достигаемого к концу каждого периода. Введем величину т!+х, — ум — — и. (3.45) Теперь максимизацию по области (3.44) можно записать в виде вах [ !пах (3 А 6) Тогда соотношение (3.43) будет выглядеть так: ~м(о)= вах [рм(п, о)+т .
!(И)], (3.47) а и в где 9л (ьй о) вах (рлум слхл) л, у (ЗАЗ) Это рекуррентное соотношение является весьма простым и объем вычислений, позволяюптих найти максимальную прибыль и оптимальную политику, лишь несколько превышает возможности ручного счета. Оказывается, однако, что из рекуррентных соотношений можно получить гораздо больше. Мы можеи получить простое точное решение, которое требует только ручного счета. 172 сгллживлние и состлвление РАспислний (гл, гп и х, ул удовлетворяют неравенствам (а) о+х,— у, =и, (Ь) (о, (с) х, у,'=»О.
(3.49) с-са ' д,с-с„с Рис. 50. " -с Гс-щ Рис. 51. Когда 0 ( и -. о, этими точками являются Ум=э — и и хм — н, У =о. В этой области о,(гг, о)=щах(р,(о — и), р и — с и). (3,50) Аналогично для и ( гг ( В (и, п)=щах 1 — с (и — о), р,р — с пг). (3,51) При фиксированном о, 0 ~ о =. В, в двух случаях, изображенных на рис. 50, 51, результат можно интерпретировать геометрически. Установив природу функций ч(и, о), попытаемся выяснить аналитическую структуру последовательности (~,(о)).
Для определения функции и,(и, о) мы должны максимизировать линейную функцию по точкам, лежащим на некоторой прямой; это означает, что мы должны исследовать только граничные точки. 173 26) доктятткльство твоявмы 26. АНАЛИТИЧЕСКАЯ СТРУКТУРА Структура функций ун (о), определяемых (3.4о), не совсем проста.
Однако имеет место следуюшвй неожиданный результат: Тепрел|а. Функция ун(о) линейна но о, причем ее коэффициенты являются функциями рп ..., р, и сп ..„ с,, именно Ун(о)= Кл (Рю Ря . ° ° Рай с1 сэ .. ° с )+ +У-(Р~ Рь ..., Рн( сь сэ, ..., с )о. (ЗЛ2) Кроме того, оптимальная политика и не зависит от начального уровня о, а зависит только от продажных н закупочных цен.
26. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ Проведем доказательство по индукции. Очевидно, что ~,(о)=р1о, так как доход на нулевом шаге уэ(и) тождестпенно равен нулю. Допустим, что ун,(о)=Кн,+ Ен,о, где коэффициенты К,, и ьн, определяются Аà — 1 парой (рь сг) продажных и закупочных цен, 1=1, 2, ..., Аг — 1. Покажем, что Ун(о) имеет тот же вид, причем коэффнциешы К н ь зависЯт Уже от последовательности (Рп сг), 1=1, 2,, АУ. Как н в случае 1, пусть с )Р .
Согласно предположениюолннейностнун,(и), максимум ун,(и) должен достигаться в одной из трех точек и = О, и = о или п = В *). *) В силу (3.50), (ЗВ1) / Рно — и шах(Рм с ), 0<и<о, я,(и, о)= ~ — спи+ошах(Рм сл), о(и(В и является кусочно-линейной по и при с )р „Максимум суммы тн(и, о)+ун 1(и) поэтому может достигаться в одной иэ трех точек: и=о, и=о, и=В. При р )сн т, (и, о)=р о — сни н сумма гн(и, о)+ун ~(и) является линейной функцией и.
(Уурим. Ред.) 174 сгллживлнив и состлалвнив Расписании [Гл. кн Такилг образом, У, (э) = шах [Рм (О, э) + 7 ч, (0), сР (э, э) + Ум 1 (э), Р (В, э)+ Уч,(В)] (3.53) или 1„(э)= ах[р, +К. н К„,+7. 1э, — с ( — э) + К, + р.м,В]. (3.54) Так как в (3.54) — третья величина больше первых двух тогда и только тогда, когда сл,((чг нзначение и=В выбирается только в этом случае. Когда р (1~,(сл, максимальна вторая величина, а когда 7чг, (рл, наибольшей является первая величина. Следуег замети~ь, что во всех случаях максимизирующее значение не зависит от э.
Если сс = В, то У,(э) = (К, + Е, — с,В) + с в. (3.55) Следовательно, К,=К.,+7тт, — смВ и 7. =с, Если п=э, то г л (э) Кл — ~ + ~м- 1э (3.56) откуда К,= К , и 7- = 7 , Наконец, при и= 0 получаем: тл (э)=Кл — +рмэ (3 57) и К =К н р.,=р . В любом случае г' (э) есть линейная функция э, и новые коэффициенты зависят только от рь...,р,и с„,.„с Остается рассмотреть второй случаи, когда рм)с . Так как функции р,(гь э) и ум,(э) линейны, мы должны исследовать только точки и=О и п=В.
Здесь (э) = гпах [<р (О, э) + У,, (0), э, (В, э) +~м, (В)], (3 58) 7ч (э) = шах [Рмэ+ Км и Рмэ — смВ+Км,+рл, В]. (3 59) Мы имеем максимум при п=О, если рм,(с и при и=В, если ).л ~- с . В обоих случаях ~л(э) =К вЂ” + рл (3.60) 175 28'1 численный пвимвв если и=0. Здесь К,=К н 7. =р . С другой стороны, ул (и) (Кл-г-т. (ж — г — сггВ)+р и, (3,61) если и=В.
Здесь Км — Км г+(.л, — с В, 7. =р Теорема 1 доказана. 27. ОБСУЖДЕНИЕ рассмотрим экономическую интерпретацию этой задачи и исследуем наши аналитические результаты. Очевидно, если сл)р „мы имеем три альтернативы, зависящие от других параметров. Уравнения (3.55)--(3.57) можно истолковать следующим образом: (З.о5) определяет закупку товара в количесгве, досгаточном для заполнения склада, и издержки при этом решении в (В, и) равны с,( — в). С другой стороны, уравнение (3.56) сзначает огсугствие каких-либо действий, издержки при таком решении, очевидно, равны О. Наконец, уравнение (3.57) выражает продажу всех и единиц товара, которые были на складе к началу периода, что дает непосредственный доход рлп. Обращаясь к уравнению (3.60), где р )с, мы получаем несколько отличную интерпретацию. Здесь назначение политикой конечного уровня В означаег продажу и единиц и покупку В единиц товара, что потребует затраг, равных р ш — с В.
Выбор, как и раныне, величины а=0 означает продажу всех и единиц, что приносит доход рмп. Всего мы имеем четыре различные политики: продавагь, покупать, продавагь и покупать, ничего не предпрннимагь. Все действия предпринимаются с учетом ограничений на емкость склада или уровень запасов. 28. ЧИСЛЕННЫЙ ПРИМЕР Напомним, что р; и сг — стоимостные показатели в момент, когда остается г периодов до конца. Пронллюстрируем полученное решение на примере следующего процесса, имею. щего 10 периодов (см. таблипу 3.4). !76 сглаживания и составления ялспнсхпнй !гл. ш Таблица 34 6 3 3 ~ ! 5 5 р; 2 Мы хотим вычислигь Км, Е,е и им, коэффипиецты функции дохода и пол»пику, когда остается еше 1О периодов, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
