Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 13
Текст из файла (страница 13)
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ Следуя подходу, намеченному в 9 3, положим; ~л (х, у) = шах [д! (х,)+ д (х!) +, + д]г(х]ч)), (2.9)' (х] где максимум берется по всем тем хп которые удовлетворяют условиям (2.8,а, Ь, с). Имеем равенство (2.1О)". г((х, у)= шах д((х() а!(х,] х Ь~ (х!] у и обшее рекуррентное соотношение ввда ул((х, у)= шах [ех(хл!)+ ам(х ч] х алп Ими —,'- Л~ ! (х — а]у (ас(у), 2('.: (]дь(ас(е))).. (2.1 Ц 70 многомвяныв пяоцвссы ялспявдвлвния [гл. и 6. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ Рекуррентные соотношения, которые иы получили в предыдуших параграфах, можно использовать для нахождения численного решения способом, почти аналогичным описанному в главе 1.
Хоти качественно метод абсолютно не буде~ отличаться от развитого выше, мы сталкиваемся с сушественными количественными изменениями, когда мы исследуем вычислительный процесс с точки зрения требований к памяти, т. е. с точки зрения хранения данных и времени вычислений. Эта теория являет собой прекрасный пример того классического правила, что большая количественная разница может породизь значительное качественное отличие. При вычислениях, приведенных в главе 1, мы требовали хранения значений функции одной переменной, Ум(х) в точках сетки [7гд[. Построим в том же духе приближение для (2.11).
'!тобы определить функцию тм(х, у), например, в области 0(х(М, 0~ (у (М, договоримся, как и раньше, вычислять ее значения только в узлах сетки, скажем, при х=7гб и у=И, л,7= =О, 1..., М. Заметим, что, тогда как раньше для задания ум ~(х) нам нужно было хранить М+ 1 значений, теперь для запоминания информации о функции /м ~(х, у) нам необходимо хранить уже (М+1)' значений. Если 0 ='х~!, 0<у(!в наша основная область, а для х и у выбран шаг в 0,01, то это означае~, что вместо 1О' точек иам понадобится уже 10' точек. В действительности увеличение будет по крайней мере в три раза больше, так как одновременно с хранением зна. чений ул ~(х, у) мы должны вычислять новую функцию ум(х, у) и политику хл=хм(х, у).
7. ОБСУЖДЕНИЕ Из сказанного выше ясно, что по мере увеличения числа типов ресурсов и числа ограничений увеличивается количество независимых переменных функции дохода. Возможность непосредственного табулирования этих функций многих переменных сильно ограничена из-за огромного увеличения требований к памяти, которые не могут быть удовлетворены современными машинами, а в некоторых случаях даже машинами ближайшего будушего. динлмичвсков ПРОГРлммиэовлнив 71 Прежде чем перейти к описанию различных путей использования математической изобретательности для разрешения дилеммы размерности в специально выбранных случаях, изложим типичное применение описанного выше метода. Задача, которую мы рассматриваем ниже, иллюстрирует также способ математического рассмотрения процессов, включающих случайные эффекты.
8. ЗАДАЧА О ЗАПАСНЫХ ЧАСТЯХ Допустим, что мы собираемся отправить транспортный самолет на отдаленную базу с грузом запасных частей для самолетов. Пусть имеется АГ типов запасных частей и с каждым из них связан определенный убыток, который терпит бава, если частей этого типа не окажется в нужный момент на складе. Предположим далее, что спрос на каждый тип запасных частей описывается известным распределением Пуассона. Какое количество запасных частей каждого типа следует погрузить на самолет, чтобы минимизировать убытки базы, обусловленные нехваткой запчастей, при заданных ограничениях на вес %' и обьем 8 груза? Это — типичная задача, встречающаяся при изучении процессов замены оборудования и управления запасами. 9.
СТОХАСТИЧЕСКИЕ АСПЕКТЫ Заметим, что мы впервые столкнулись с задачей с элементами случайности. Как мы увидим, в случаях минимизации некоторого среднего убытка постановка задачи в терминах динамического программирования, а также ее численное решение идут по тому же пути, что и раньше.' Одно из болыпих преимуществ методов динамического программирования состоит в том, что к детерминированным и стохастическим процессам можно применять один и тот же подход. 10. ПОДХОД С ТОЧКИ ЗРЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Пусть ш, обозначает вес детали 1-го типа, а; — ее объем, ?ч — среднее в распределении Пуассона, описывающем спрос на этот вид запасных частей, и с; — убытки вследствие 72 многомввныв пвоцвссы Рлспввдвлвния [гл.
и неудовлетворения спроса на одну деталь г-го типа. Наконец, предположим, что нам желательно определить такую комплектпость, при которой минимизируются ожидаемые убытки при определенных ограничениях на вес и обьем. Если х; — количество деталея !-го типа, которое берется на борт, и Р (а) — вероятность потребности в з деталях, то ожидаемый от неудовлетворения спроса убыток будег равен с; ~а (л — х!) Р(г). ('2.! 2) «=в!+ ! Етт= ~Ч~~ с; ~ ~ (з — х;) Р (т, Л!)~.
(2.13) ! ! г=л.+ ! ! Математическая задача состоит в минимизации Е!т по всем хн удовлетворяюьцим трем условиям: х; = О, 1, 2,..., (= ! ~, х!а! =з. а= ! (а) (Ь) (2.14) (с) Определим теперь ~„(ю', а') как убыток, связанпыя с оптимальным выбором деталеп первых 7г типов; грузоподьемность самолета ограничена величинов ю', а объем — величиноп а'! ю' и а' могут меняться соответственно в интервалах 0(и'~тв и 0(а' а. Эта формула имеет место независимо от вида распределения спроса.
Мы проведем расчет для распределения Пуассона, так как этот тип распределения часто является превосходным приближением для наблюдаемых распределении. Кроме того, параметр Л этого распределения может быть оценен довольно легко. Если Р (», Л!) — распределение Пуассона для 1-го типа деталеп, то математическое ожидание суммарного убытка равно 73.
ВЫЧИСЛИТЕЛЬНАЯ ПРОПВДУРА Основное рекуррентное соотношение то~да примет вид ук(ш', а')=ппп ~с„~ч', (г — ха)Р(з, ),ь)+ кя ь -~- У„, (ю' — хьюм з' — хьйа)), (2.15) где хь изменяется в области 0 ( ха ( ппп ~! — ), ) — !). (2.16) Как и раньше, (х] обозначает наибольшее целое число, не превосходящее х.
В следующем параграфе мы разберем ' решение уравнения (2.15) при ограничениях (2.!4). 11. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА Поскольку учитывается каждый тип деталей, начальный шаг состоит в вычислении ожидзечого убытка от включения в комплект О, 1, 2,, деталей этого типа. Таблица ожидаемых убытков определяется допущением о том, что распределение является пуассоновским, и знанием средней величины спроса и убытков от отсутствия одной детали. При рассмотрении разных политик определяют, обращаясь к таблице, непосредственный убыток от каждого выбора.
Этот убыток прибавляется к ожидаемому убытку, связанному с оставшимися типами деталей, для того чтобы найти суммарный убыэок от применения данной политики. Затем на этой основе выбирается минимиаирующая политика. Были запрограммированы как одномерный, тзк и двумерный случаи. В первом случзе рассматривалось толы<о ограничение на вес. На расчет для одной детали расходовзлось около одной минуты, когда полная весовая нагрузка составляла 1000 фунтов, а в качестве весов деталей брались небольшие целые числа. В двумерной формулировке налагались как весовые, тзк и объемные ограничения.
Верхняя гранина, равная 30 как для веса, так и для об вема, дала в результате сетку в 900 точек, и снова вычисление для одной детали потребовало около одной минуты. Ограничение в 30 значений для каждого измерения означает, что малые детали следует укрупнять в большие группы (как зто обычно 74 МНОГОМЕРНЫЕ ПРОЦЕССЫ РЛСПРЕДЕЛЕНИЯ [ГЛ. !1 и делзется на практике), для того чтобы сделать осмысленным расчет. Граница в ЗО могла бы быть увеличена до 100 при имеюцтемся объеме памяти; вычисления потребовали бы тогда примерно в десять раз больше времени. Число «десятка получается из отношения 100з(ЗОв.
12. ПРИМЕР В этом параграфе приводятся некоторые типичные результаты. Они касаются оптимальной загрузки деталями ,У!у гр лг гг Л Л га лл «« ««7 ту 1 л,У 4 Гтаа ' Рнс. 16. Части таблицы значений функции У,«(тл, з), дающей минимальные издержки, связанные с комплектом веса тв и объема з, когда учтены все 1О типов деталей. десяти типов.
Ожидаемый спрос на каждый тип равен четырем деталям, а величина штрафа за нехватку детали любого типа равна трем. Значения весов и объемов показаны в таблице 2.1. 121 пример На рис. 16 дана часть таблицы функции ~,е(ю, а) двух переменных, представляющей собой минимальный убыток, Таблица 21 Объем и вес предметов разного типа Объем тип предмета тип предмета Объем Вее Вее 6 1О связанный с комплектом весом в и объемом л, когда учтены все 10 типов деталей. л гю гю и гбт и ,ур Рис.
17. дающей деталей На рис. 17 приведена политика, связанная с данными рис. 16. Каждое из чисел в кусках таблицы на рис. 1Т У бт 7 о тчт 5 ча а г г 1 д бг Л1 л О г7 Л Л гб Л а г1 Я И Ю 1 г,У б Ю бто вам Части таблицы значений функции лте (ев а) оптимальное число включаемых в комплект типа 1О при весовом и объемном ограничениях(ю, л). означает оптимальное число включаемых в комплект деталеп типа 1О при весовом и объемном ограничениях !гв, а). Таблица 22 Решение задачи Чксло вклмтмае- НакаплевОбъем мык в комп- Стокмость паа стоклект деталей кость ткп пред- метов Остаток веса Остаток объема Вес 5,0 5,0 8,! 13,1 22 19 19 19 13 !3 9 0 24 19 19 19 13 13 8 3 0 1О 9 8 7 6 5 4 3 2 1 3 5 7 4 2 б 5 2 3 12,0 !2,0 2,6 12,0 18,1 12,0 8,1 8,1 25,1 37,1 39,7 51,7 59,8 71,8 79,9 88,0 Таблица 2.2 воспроизводит конечную печать результатов этапа 2 вычислении !См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
