Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 17
Текст из файла (страница 17)
(273) х» Важно отметить, что таблица функции Н,(х) одна, непрерывно пополняемая аналогично таблице у (х), а не множество таблиц, как таблицы политик. Поэтому ее всегда можно хранить в оперативной памяти. Число Н,(х) есть значение Ч~~ Й!(х!), используемое для определения следующего »=! значения ).
Величина 7 (х) + »Н ,(х) есть фактический доход при политике, оптимальной относительно множителя Лагранжа ). 26, ЗАДАЧА С МНОГИМИ УРОВНЯМИ Задача, которую мы только что рассматривали, иллюстрирует интересный аспект постановки задач динамического программирования. Благодаря существенной зависимости трудности решения от числа параметров состояния некоторые задачи, кажущиеся чрезвычайно трудными с обычной точки зрения, оказываются на самом деле простыми с точки зрения динамического программиронания, и наоборот. В приведенной выше задаче мы столкнулись с задачами выбора политик на двух уровнях.
На первый взгляд, более простой задачей была задача оптимального (с точки зрения 97 261 МНОГОМЕРНОЕ ПРОСТРАНСТВО ПОЛИТИК извлечения прибыли) распределения фиксированных расходов на производство и расходов на рекламу. Более трудной могла показаться задача оптимального разделения наличного капитала между производством и рекламой таким образом, чтобы оптимальное же использование ассигнованных средств максимизировало прибыль. На самом деле это не так.
Первая формулировка приводит к двумерной задаче. Эта задача была решена сведением к последовательности одномерных задач с помощью множителя Лагранжа. Каждая такая одномерная задача была в действительности описанной выше задачей второго типа. Выбирая множитель Х=О и производя максимизацию по области 0(х +ум(х, (2.74) мы можем решить задачу распределения с двумя уровнями. Одномерная постановка задачи имела бы вид 1л(х)= шах (гм(х, уч)+1м,(х — х„— ум)).
(2.75) О к +к к Это замечание остается в силе для широкого класса задач со многими уровнями. Ниже в этой главе мы рассмотрим транспортные задачи, в которых требуется найти план оптимальной перевозки грузов из небольшого числа источников в большое число пунктов потребления. Соображения, которые мы использовали выше, показывают, что задача оптимальной перевозки из одного производящего центра в небольшое число складов и затем в пункты потребления не является существенно более трудной.
26. МНОГОМЕРНОЕ ПРОСТРАНСТВО ПОЛИТИК В модели рекламы мы хотели максимизировзть функцию по двум переменным. В 9 23 мы упомянули, что уравнение (х) = шах (г (х ул) — л'у,+1м, (х — х,)) (2.76) 0 у ~со можно было бы заменить уравнением 1,, (х) = шах Я,„(хл) +1 (х — х, )1 (2.77) 98 л!цогомвгп!ав нгоцгссы Рлспгвдвлвпия [гл.
н где !;1,(х )= шах (гы(х у ) — Лу ). (2.78) Г <лл 27. ПРОБЛЕМА НАДЕЖНОСТИ Рассмотрим теперь более детально проблему надежности, уже обсуждавшуюся в Я 27 — 28 главы 1. Предполагаем, чго при использовании 1+т компонент в )ьй ступени вероятность успешного функции!!ирования этой ступени задается известной функцией ч!7(тт). Предположим дзлее, что имеются два типз огрзничений, по стопа!оста и по вегу, Пусть ст — стоимость отдельной компоненты в )чй ступени и шт — ее вес.
Тогда суммарные вес и цена задаются выражениями Ф С =~стд Ф %' — ~ч ! шгт,. (2.79) 7=! Задача, которую мы хотим рассмотреть, состоит в максимизации общей надежности Я = Ц 87(т)) (2.80) т ! Это замечание имеет не только попутный ин!ерес. Если программировать уравнение (2.76) непосредственно, го для каждого значения х надо было бы вычислить все допустимые пары (хл„у,) и в резулшате величина г,(х,, у,)— — лу, вычпслллагл бы заново для одних и !ех же х м м и у много раз. В!!числив сна шла функцию 0 (х, ), л!ы избежим ненужного повторения. Это упрощение происходит за счет того, что переменная ух фигурирует только в целевой функции и не входит в аргумент функции )" „ Мы увидим, что этот способ будет использован многократно. Он имеет как аналитическое, так и вычислительное значение прн решении задачи о хранении на складе (глава !!!).
2о'1 ЧИСЛРНПЫй ПРИМЕР по всем тс при Ограничениях (а) т1=0, 1, (Ь) сттт - с, 1 1 и (с) Л=1 (2.81) 28. ВВЕДЕНИЕ МНОЖИТЕЛЯ ЛАГРАНЖА Чтобы не иметь дела с последовательностями функций двух переменных, введем множитель Лагранжа. Рассмотрим новую задачу максимизации выражения М вЂ” Л ~, 'ссм ~и срт(т )~ е Л=1 (2.82) по всем тд удовлетворявшим только первым двум ограничениям (2.81).
Полагая Г (с) равной этому максимальному значению, где с то же, что в (2.81,Ь), получаем рекуррентное соотношение г",(с)= шах (ун(тст)е и лУ, л (с — т, см)) (2.83) О сс «1с!с для АЛ=2, 3, ... и соотношение ул (с) = шах 1срл (т,) е ЕРП 'з). (2.84) О ссс . 1с!с~1 Бше раз отметим, чго каждое т; может принимать только значения О, 1, 2, ... 29. ЧИСЛЕННЫЙ ПРИМЕР Численное решение задач упомянутого выше вида может быть получено совсеч просто.
(Блок-схема программы дана' в й ЗО.) Для иллюстрации рассмотрим устройство с четырьмя типами компонент, для которых цены, веса и вероятности успешного функционирования даются таблицей 2.5. 4' многомврныв проциссы распрздвлвния [гл. и Как и раньше, предположим, что может быть использован каждый из этих четырех типов компонент. Кроме того, если Таблица 2.5 веронепосуь успеыноя работы тнп нонпаненеы цена Вес использованы сну дополнительных компонент анто типа, вероятность успешной работы )-и ступени дзется формулой р )летне (2.85) При допустимом количестве в 100 единиц стоимостных затрат и 104 единицы веса мы хотим определить число элементов кзждого типз, которое максимизирует общую вероятность успешного функционирования, задаваемую, как и выше, выражением П р/(тт) /= 1 (2.86) (2.87) Величину Л надо определить так, чтобы Я т,тиг = 104.
Начав с Л=0,001, мы получим: б уб (100) = П р, (т,) ехр ( — Лла,ли,) = 0,8882, (239) л ! Начав с уравнения г", (с) = о продолжаем по обгцей у;(с)=шах (пе,.) для 1=2, 3, ..., где 0,90 0,75 0,05 0,80 , 0,85 гпах оа, (т,) в- хассана, не~ 1с/сс1 формуле [~8б(тб) е с с/. а(с тлел)[, 0~ т, ~ [Л. (2.88) 101 ововшвнив и значения т,=2, т,=З, т,=4, т,=2, т,=2, с общим весом ~ т!св! = 97. Вероятность успешной работы равна а= ! 0,8882 е"! = 0,977, Теперь уменьшим ) до 0,0008 с тем, чтобы увеличвть общий использованный вес.
Результат таков: Уа(100)= 09063 т! — — 2, та=3, та=4, та=3, та=2 а ~~ ' татя! = 104. г=! Вероятность успешной работы равна (0,9063. е'а!") = 0,984. Вто и есть решение задачи. Машинное время, затрзченное на вычисление, составило 4 минуты. Стоит заметить, что эта же самая задача с пятьюдесятью типами компонент потребовала бы приблизительно 50 минут, так как время, требуемое для решения задачи таким способом, по существу, пропорн,ионально числу типов компонент *).
Причина, по которой мы не говорим «прямо пропорционально>, — в необходимости поиска истинного значения ),. 30. БЛОК-СХЕМА ПРОГРАММЫ !см. рис. 26) 3!. ОБОБЩЕНИЕ Рассмотрим теперь более близкий к действительности нариант предыдушеИ задачи. Вместо предположения о том, что мы свободны в выборе только числа компонент, предположим, что у нас имеется выбор типз компонент, используемых в каждой ступени, скажем, выбор между типом А и типом В. Пусть с!(А) и тр!(А) обозначают стоимость и вес одной компоне>пы типа А в Бй ступени; са!В) и ю!(В)— соответствующие величины для компоне!пы типа В.
Мы могли бы при желании учесть возможность комбинациИ типов компонент в каждой ступени, сохрзнин в силе последу!ощне рассуждения. Как и раньше, мы хотим при задзнных общих ограничениях по стоимости и весу определить, какоИ тип компоненты *) Точнее, числу ступеней. (Прим. ред.) 1ОЗ охов!ценив н в каком количестве использовать в каждой ступени, чтобы максимизировать надежность устройства. Пусть грг(т;; А), лл,(гл;; В) обозначают надежность ькй ступени, когда параллельно используются тг компонент типа А и В соотвегсгвенно, Как н выше, рассмотрич последовательность функций (ул,(с, в) ], где г „(с, тс), по определению, есть максилшльная надежность М-ступенного устройства прн ограничениях с по стоимости и гв по весу.
Тогда 1;(с, гв)=шах[шах мг(тг1 А), шах ллг(лг;, В)], (2.90) Фл лгг где в первом выражении область изменения 1 ( т, ( в1п ( [сусл (А)], [вг~вг (А)Ц, а во втором— 1 ( т, ( ппп ', [с,'с, (В)], [вГв, (В)]]. Как и прежде, т, может принимать только значения 1, 2... Для произвольного М имеем рекурренгную формулу гк(с, гв)= шах (шах гам(т„„А) Х Ф ХУм ~ [с' — с,(А) т „, в — тел (А) т,]; вах м(ил; В) х', и УС[м 1[с — с,(В) т „в — в .(В) т,] [, (2.91) где в первом вырзжении 1-- гл (пни([сгс, (А)], [в/в„(А)]], (292) и во втором 1-=т -.в1п([с1сл(В)], [в1вт(В)][. (299) В обоих случаях т, может принимать только целые значения 1,2, Выяснив, как формулируется двумерный вариант задачи, мы можем ввести множитель Лагранжа и поступать, как выше, чтобы получить одномерный вариант.
!04 многомееные пеоцессы ехспееделения 1гл. и йй. ТРАНСПОРТНАЯ ЗАДАЧА ХИЧКОКА †КУПМАН В математической экономике большое значение имеет задача наиболее эффективно~о перемещения ресурсов нз одного пункта в другой. Это — один частный случай общей проблемы определения структуры оптимальной сети (где, конечно, понятие «оптимальности» зависит от того, как будет использоваться сеть). Задачи такого типа постоянно возникают в экономической, индустриальной, вычислительной областях, в области электроники, связи и организации. Относительно немногие из этих захватывающих топологических задач рассматривались детально, и ни одна из них не поддавалась простому анализу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
