Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 5
Текст из файла (страница 5)
Для введения в круг основных идей динамического программирования и легального выяснения вычислительных аспектов будет использован пример процесса распределении ресурсов, связанный с задачей огыимизации указанного вида. При этом повсюду мы будем уделять внимание основным сведениям, касающимся времени кодирования, рабочего времени, точности, устойчивости и вычислительных планов, представляемых в виде блок-схем. Мы рассмотрим еще две задачи, приводящие к аналигическим вопросам аналогичного типа.
Источником одной из них служит процесс загрузки судов, другая связана с надежностью многокомпонентных схем. 2. ОПИСАНИЕ ПРОЦЕССА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ Прежде чем привести аналитическую формулировку, дадим чисто словесное описание класса процессов, которые мы намерены изучать. Допустим, что мы располагаем некоторым количеством экономических ресурсов. Под этим абстрактным термином могут скрываться люди, деньги, машины, расщепляющийся материал для ядерных реакторов, вода для сельскохозяйственных и промышленных целей или для производства электроэнергии, ~опливо для космического корабля и т.
д. Столкновение интересов объясняется тем, что ресурсы можно употребить многими различными способами. Каждый такой возможный способ мы называем технологическим лройессолб или производственным гпособолг. В результате употребления всех ресурсов или их части в каком-либо отдельном процессе мы получаем некоторый доход. В одних случаях доход может быть оценен в единицзх самих ресурсов (деньги могут сновз приносить деньги, мзшины могут снова производить мзшины); в других — он может быть измерен в единицах совершенно отличной природы (топливо может давать скорость, деньги могут обеспечивать надежность) и т.
д. Размер дохода зависит как от з) постяовнив млтвмхтичвской водили 25 употребленного количества ресурсов, так и от выбранного процесса. Сделаем следующие основные предположения. а) Лоходы, полученные от различных процессов, могут быль измерены общей единицей. Ь) Лоход, полученный от любого данного процесса, не зависит от того, какие количества ресурсов были выделены для других процессов. с) Общий доход может быть определен как сумма доходов, полученных от отдельных процессов.
На экономическом языке это означает, что полезность, полученная от процесса распределения в целом, может быть вычислена простым сложением полезностей, полученных от отдельных процессов. Основная задача — разделить наши ресурсы так, ыобы максимизировать общий доход. Описанная простая матемазнческая модель процесса распределения ресурсов является полезной для описания многих ситуаций. 3. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ Ладим теперь точную мзтемзтическую формулировку описанной задачи. Пусть Аг различных процессов занумеровзны в определенном порядке числами 1, 2, ..., Аг. Когда мы говорим, что рассматриваются два процессз, мы будем иметь в виду процессы 1 и 2; когда называется пять процессов, мы будем иметь в виду процессы 1, 2, 3, 4, 5, и т.
д. Порядок нумерации процессов значения не имеет, но, будучи однажды принятым, он должен твердо сохраняться впредь. Каждому процессу соответствует функция полезности. Эта функция выражает зависимость дохода при этом процессе от количества выделенных для него ресурсов. Если х; обозначает количество ресурсов, выделенных для Кто процесса, то через д;(х;) мы обозначим соответствующий доход от этого процесса. Функция полезности д;(х,) представлена на Рис 1. Форма этой кривой определяется двумя важными экономическими условиями.
Во-первых, небольшие количества выделенных ресурсов, в сущности, не дают никзких доходов и, во-вторых, дальнейшее увеличение этих количеств приводит, в конце концов, к эффекту нзсыщения 1«закон одномввныв пгонвссы васпввделвния [ГЛ. 1 убывания доходовя). Как уже говорилось, х; и е1(хг) часто выражаются в разных единицах. Предположения, касающиеся независимости процессов и аддитивности полезностей, приводят к выражению Я(хь хм ..., хм) = д,(х,)+Кя(хя)+...+ ел (хл) (1.3) для обшей полезности процесса распределения. Задача максимизации возникает оттого, что в наличии обычно имеется лишь ограниченное количество ресурсов. м$ ф с1 Распределение Расудса ат Рис. 1.
Обозначая это количество через х, мы приходим к условию. х,+ха+...+хл=х, (1.4) где х; ) О. Далее нужно максимизировать функцию Я (хь хи... ..„хл) прн хн удовлетворяющих этим ограничениям. 4. ОБ С УЖ ДЕ НИ Е Отметим попутно, что одна из наиболее значительных трудностей, встречающихся при всяком изучении экономических, промышленных или военных процессов, связзна с определением индивидуальных и совокупных функций полезности. Во многих ситуациях мы не знаем ни точного вида этих функций, ни даже того, что именно следует максимизировать. В частности, это всегда характерно для процессов с сушественным участием людей. Весьма полезным в целом ряде исследований этого рода оказывается моделирование процессов.
27 б) АППАРАТ ИАТВИАтичзского АнАлизА б, АППАРАТ МАТЕМАТИЧЕСКОГО АНАЛИЗА Для решения экстремальных задач описанного типа часто прииеняегся аппарат математического анализа. Вводя множитель Лагранжа а) А, мы образуем вспомогательную функцию Я(хь ха,..., хАУ) = =81 (хг)+Аз(хч)+ . +АА'(хл) — Х (х, +х,+...+хлу) (1.5) и приравниваем нулю ее частные производные. Этим путем получаются уравнения Ау; (х;) — Л = О, ю' = 1, 2,..., АГ.
(1.6) РазРешаЯ их относительно хь хг=бтг(л), мы находим У', из условия (1.4) Л,(Л) -~- Л, (Л) -~- ... + )г„,(Л) = х. (1.7) Таковы обычные действия для определения максимума )с. Например, если требуется минимизировать функцию гс = а,х,'+ а,х,'+... + алхл; а,) 0 (1.8) Уравнение (1.7) тогда будет иметь'вид АУ ат' — = х, (1.10) откуда 1=! х '2в; х,= (1.11) !=1 )Об „„„, бу„у„„, Луб гаазе 0 (4!3 и следующие за ним), где зтог классический метод будет сочетаться с динамическим программированием.
при х!)О, удовлетворяющих (1.4), формула (1.6) дает: 2 ! (1.9) 28 'ОДНОМЕРНЫЕ ПРОЦЕССЫ РАСПРЕДЕЛЕНИЯ 1гл. ! Таким образом, минимальное значение равно 1 М у 1 г=! !1.12) Этот пример задачи и ее решения типичен для учебников по математическому анализу. К несчастью, задачи, возникающие в сколько-нибудь важных приложениях, часто менее всего подходят под установившиеся методы и требуют более тонкого исследования, Впрочем, небезынтересно, что большзя чзсть примеров, употребляемых для иллюстрации моши аппарата математического анализа, а том числе и пример, данный выше, вовсе не нуждается в этом аппарате и может быть решена более строго и эффективно с помошью гораздо более элементарной теории нерзвенств.
б. ТРУДНОСТИ а Рпс. 2 Рассмотрим теперь несколько подробнее те принципиальные трудности, с которыми мы сталкиваемся, когда пытаемся применить методы математического анализа к задаче распределения ресурсов, описанной в Я 2 и 3. А. Относительный экстремум. То, что тангенс уг: а наклона касательной к кривой равен нулю в точке отно- ситсльного максимума или Относнлггллнли7 в точке относительного минимума, позволяет дуй мать об использовании !ь математического анализа для решения задач оптимизации !рис.
2). тг а Поответствуюшнй результат имеет место и для функциИ нескольких переменных, если рассматривзть не касательную к кривоИ, а касательную к поверхности плоскость. К сожалению, обрашение в нуль производной есть толшсо необходимое, но не достзточное условие для внутреннего экстремума. Производная равна нулю не только во всех тгтдностн внутренних экстремзльных ~очках, онз может быть тзкже равна нулю и в других внутренних точках — точках перегиба.
Например, для кривой, изображенной на рис. 3, производная и'(х) равна нулю в точках Ь, и Ь, относительного максимума, в точках а, и а, относительного минимума и в точке с„ которая является точкой перегиба. Это обстоятельство, причиняющее неудобства уже при исследовании функциИ одной переменной, становится почти непреодолимой преградой для успешного применения математического анализа в многомерных задачах максимизации, особенно, когда число независимых переменных велико. Рассмотрим адесь за- 1агла дачу максимизации функ- лглагагта ции (1.5), когда каждая функция е)(х) имеет вид, показанный на рис.
1. В и ю л эгом случзе кзждое из Рнс. 3. урзвнений (1.6) может иметь двз корня. Тзк как не ясно, кзкой корень соответствует абсолютному максимуму, мы должны испытать все комбинации значений. Эта процедура требует оценки 2м случаев. Если И=10, то имеем 1024 случая, что не так уже велико; если юг=20, число случаев превысит 10' и должно внушать известное уважение. Функции полезности еще более сложной природы будут давать гораздо большие наборы возможностей, что создает не только теоретическую трудность, но и серьезное препятствие для численного решения. Б. Огрзничения. Мы применили трздиционным обРазом метод классического анализа, не уделив внимания тому факту, что в действительности во многих ситуациях мы должны разыскивать максимум в некоторой конечной области.
Равенство производных нулю, как мы знаем, определяет внутренний экстремум, но вообще не служит признаком экстремума, который достигзется на границах области изме- "ения. В качестве примера возьмем функцию одной переменной а (х), приведенную на рис. 4. Производная Ьг(х) Равна нулю нри а, и Ь! в точках относительного минимума " максимума соответственно, но не равна нулю при х= 0 зо одномввныв пвоцвссы вясппядвлвния 1гл.
г в точке, где д(х) принимает свой абсолюпаый максимум в интервале 10, х„1. Как ни печально, это осложнение является обычным в изучении экономических и технических управляемых процессов, для которых условия вида а;(х;(Ь; (1.! 3) естественны и разумны. В задачах максимизации с многими переменными число всех возможностей, включающих точки относительного экстремума, сгационарные точки более сложной природы и точки границы, нзстолько велико, что приходится отвергнуть саму идею перебора. Важно понимать, ч~о в задачах оптимизации, которые сводятся к комбинааорным задачам, треп, Ь, г,г бующим оценки каждого Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
