Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 24
Текст из файла (страница 24)
ПРОЦЕССЫ СГЛАЖИВАНИЯ Рзссмотрим следующую ситузцию: мы хотим, чтобы некоторая система работала в заданном режиме, причем известно, что затраты по эксплуатзции системы зависят от отклонения ее от этого режима. Если мы попытаемся перевести систему в желаемое состояние, то мы затратим дополнительные средства, размер которых зависит от усилий, требуемых для этого преобразования. Г!роцесс, при котором целесообразно придерживаться некоторого среднего способа поведения, сочетая затраты разных типов так, чтобы максимизировать полезность всей операции, называется прог4ессож сглажпванпл. Далее мы будем рзссматривать примеры некоторых процессов этого типа из области экономики.
Затем в главах МП и !Х мы рассмотрим инженерные вопросы, аналогичные по математической постановке. 3. ПРИМЕР ПРОЦЕССА СГЛАЖИВАНИЯ Начнем наше изложение с простого примера процесса сглаживания, часго встречающегося при анализе экономических, промышленных и военных операций. На некоторую станцию обслуживания согласно графику (например, ежедневно или еженедельно) поступают требования на определенные поставки или виды обслуживания. Если станция не может удовлетворить эти требования, то она терпит убыток. Г другой стороны, в случае переукомплектования обслуживающим персоналом или перегрузки складов она также тер- 4] млтймАтическля постАнозкл задачи 145 пит убыток другого рода. Если бы этим ограничивались условия работы станции, оптимальная политика управления была бы почти очевидной.
Введем, однако, в рассмотрение аатраты на изменение уровня запасоя или обслуживания, что во многих ситуациях весьма естественно. Если теперь известны размеры требований, сильно меняющиеся во времени, и заданы затраты на пополнение запасов и размеры убытков обоих видов, то задача определения способа регулирования уровня запасов, минимизирующего полные издержки всего процесса', станозится уже нетривиальной. 4. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ Пусть гь гя, ..., г — заданная последовательность спросов, где гл — спрос на тт-и шаге. Пусть также кл — производительность системы иа Л-и шаге, к=1, 2, ..., Х, (З.1) где хе — — с — фиксированный начальный уровень В настовцем примере предположим, что требуется выполнение неравенств хл) гл, lт=1, 2,, Ат, (3.2) Другиии словами, мы настаиваем па том, чтобы спрос всегдз удовлетворялся.
Введем две функции убытков тл(хл — гл) — убытки на Л-и таге, вызванные тем, что хл) гл1 фл(хл — хл,) — убытки на й-м ша~е, вызванные тем, что хл,-Й лл и Эта последняя функция измеряет убытки, связанные с изменением уровня запасов или обслуживания. Суммарные издержки, связанные с выбором уровней хь хм ..., х , выражаются формулой С(хь х,, х,)= ~ [ол(хл — гл)-[-фл(хл — х„т)]. (З.4) л=! Наша цель — выбрать уровни х„, те=1, 2... А1, удозлетворяющие условиям хлтзг„, так, чтобы минимизировать эту функцию.
146 сглаживание и составление РАсписАний (гл. !и 6.ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ Для того, чтобы применить к этой задаче метод функциональных уравнений, рассмотрим для Л'= 1, 2, , Аг класс задач, требу!оших мгшимизации функции М С, = ~ (еа(ха — га)+ф,(ха — х„!)) (3.5) А=и в области ха==с„, 7!=)7, )с — , '1, „Аг, х,=с.
Определим семейство функций ~, (с) = ппп С , й = 1, 2, ..., АГ, (3.6) ( А) где минимум берется по всей области изменения хл, определенной выше. функция Ул(с)= ш!п (о(хх гк)+ф(хл с)) (37) определяется несложно, Обычным приемом получаем следуюшее рекуррентное соотношение: тл(с)= ш1п (е, (х, — гл) — ~ — фл(хл — с)+7, ь!(х,)) (38) и и для Л'=1, 2,, А! — 1, Таким образом, мы имеем простой алгоритм для получения численного решения рассмотренной задачи оптимизации. 6. ОБСУЖДЕНИЕ Для различных классон функций ( Ел(х) ), (фл(х) ) и ограничений того или иного типа оптимальные политики могут быть найдены в явном ниде.
Ссылки на ряд полученных в этом направлении результатов читатель найдет в библиографии в конце этой главы. 7. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ Рассмотренный процесс, так же как и процесс загрузки судна (см. й 22 главы !), является одномерным процессом с целочисленными ограничениями. Более того, экстремумы 147 7[ вычислитвльныя аспвкты здесь легко найти при помо|ни прямого срзвнения, и при целочисленных точках решетки не требуется никакой интерполяции. Область изменения величины с ограничивается автоматически и известна заранее.
В результате мы имеем короткую и прямую программу с фиксированной запятой, не вызывающую прак|ически никаких трудностей в отношении обьема памяти и заграг времени. фактически во всех примерах этого процесса, которые до сих пор ставились на машину, время вычисления определялось временем выдачи результатов на печать. В большинс|ве задач динамического программирования природа рассматриваемых величин такова, что аргумент функции в правой части может принимать значения из широкой области. Например, в процессе загрузки судна ($22 главы 1) количество единиц типа М, которые следует погрузить нз корзбль вместимости гв, может принимать любое значение между 0 н [ш/а',.[.
Оставшаяся вместимость п — штх . таким образом, может принима|ь любые значения между 0 и ш. В результа|е, прежде чем мы начнем вычисление ук(а), мы должны вычислить функцию ул,(з) во всех целых точках з между 0 и ш. Однако в рассматриваемом процессе мы можем заранее точно определить, какие значения функции у, ,(х,) понадобятся для определения г" (с). Принимая во внимание этот факт, мы экономим много машинного времени.
Чтобы убедиться в этом, заметим, что значение хл ограничено снизу требованием гл и сверху величиной гпах г„, так Я как нет смысла выбирать хл ббльшим, чем максимальное требование. Следовагельио, функция 7" +,(х ) должна быть определена для значений хл в промежутке г «-:хл( гпах г л Отсюда получаем, что, когда 7 +,(с) вычисляется с помощью соотношения у, +, (с) = ппп [рл(хл — гл) [- "Р+ | -,'-ф,(х, — с)+У, +з(х, +,)!, (3.9) 1ая сглаживания и состлвлвние Расписаний 1гл. 1и мы можем рассматривать только значения, удовлетворяющие условиям г, .
с -шахт„, г, +, (хн, =шзхг . ! и (а) (ЗЛО) Хотя для того, чаобы понизить размерность задачи максими- зации, мы сводим ее к многошаговому процессу, иодля умень- шения вычислительных трудностей мы в то же время исполь- зуем наши знания о будущих требованиях. 8. РЕЗУЛЬТАТЫ В процессе получения численных результатов мы использовали трн различных критерия. В одном случае функция издержек вследствие перегрузки е (хл — г ) принималась равной х — г . Во втором случае мы полагали: л л о (х — г,) =хв — г, для О~х — г, «М, ~ (3.1 1) и (хл — г )=М для хл — г,)М.
В третьем случае предполагалось аначнтельное увеличение убьыкон, когда перегрузка превосходит величину М; ил(хн — гл)=хл — г, 0(хл — гл---М, 1 о (м — г )=х — г -'- — (х — г — М)', 'н л л л д 2 л и (зл 2) Вшраты на увеличение производительности мы полагаем пропорциональными этому увеличению ф(х, — х,,)=иглах(х, — х,, 0), (3,13) а затраты на уменьшение производительности — равными О.
Во всех трех случаях затраты принимались не зависящими от номера шага. 11) злдячн о влижаншем сосвдя Для каждого из трех возможных критериев мы рассмотрели следуюгций график поступления требований, включающий 27 периодов: 18, 13, 9, 6, 3, 5, 8, 3, 1, 9, 18, 1 1, 4, 3, 2, 4, 5, 9, 12, 13, 12, 11, 13, 7, 1, 8, 14. (3.14) Здесь а = 2 илн 4 и М = 2 нли 4 и исходный уровень равен О. Следует заметить, что в большинстве случаев оптимальная политика не единственна.
Политика, показанная на графиках жирной линией, есть результат произвольного выбора на каждом шаге одного из двух минимизирующих значений. 9. БЛОК-СХЕМА (см. рис. 34) 10. НЕСКОЛЬКО ГРАФИЧЕСКИХ РЕЗУЛЬТАТОВ (рис. 36-451 И. ЗАДАЧИ О БЛИЖАЙШЕМ СОСЕДЕ Рассмотрим набор точек рл лежащих на однои прямои и предположим, что только между соседними точками существует некоторое взаимодействие. Пусть положение точки р; Ра ~т Ра 'Ин л определяется координатой хо Мы считаем, что совокупное взаимодействие между точками задается функцнеи 8, (м, — ха)+за(х, — х~)+...— 'Ал(хм — хл,). (3.1о) Если значения х, и х, фиксированы, то состояние системы описывается числами х„хя,..., хч и Требуешься найти такои набор этих величин, нри котором функция (3.15) минимальна.
Численное решение задачи о нахождении хь хя, ..., хл легко получить с помощью изложенного выше метода. Задачи такого типа часто встречаются в статистическои механике. В конце главы имеются ссылки на работы, в задачи о илижлйшвм соседв 17 Ю~ ги гХ Пе,тиоатат Л~ Рис. 35. График требояаний. ~ь тл и и й ат ~~ ~иЮ М ~В и и ага /о Л7 Ы П~Ржоллг аг Рис. 36. Оптииальная нагрузка согласно кратерию 1, и = 2, издсржки = 120, 162 сгллжиВАИНВ и состлВлинии Рлспттсьрий 1гл. и мому ф ь уту ю гтт и /уеаиатуат дт Рис. 37.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
