Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 11
Текст из файла (страница 11)
Печатание занимает около одной минуты на предмет; перфорация требует такого же количества времени. Однако необходимо печатать лишь окончательное оптимальное поведение, а отперфорнрованные данные можно записывать на барабан, тратя на это ничтожное время. одномеяпые пяоцессы Распяеделения [гл, а Блок-схема вычислительной программы приведена на рис. 12. Таблица 1.2 содержит численные данные для небольшой задачи, включающей 8 типов предметов и судно грузопод.ьемностыо 100 единиц.
Таблица 1.3 дает оптимальное решение Рис. 12. Блок-схема программы ххя численного реше- ния задачи о загр1зне корабля. для этои задачи. На рнс. 13 мы видим, как ош имальнын доход зависит от грузоподъемности. Здесь же покззано, насколшсо неправильно может вести себя оптимальное поведение при переходе от одного значения грузопод.ьемности к другому. Это в результат ограничения целочисленными решениями. Совершенствование вычислительных машин идет так быстро, что к тому моменту, когда эта книга выйдет из печати, указанные выше значения затрат времени на операции могут показаться несколько старомодными. Читатель, знакомый со налвжногть многокомпонвнт!4ых схим 57 271 свойс)вами самых последних цифровых вычислительных машин, может легко внести необходимые изменения. Таблица 1.2 Значение груза Номер типз Значение груза Номер типа Вес Вес 72 60 441 27 1О 16 24 20 50 94) 20 !8 14 1') Табаица 1.3 Часто г)огруженнмз преаметаа г-го типа 4(а) «а=3 «,=1 «а=3 «г= ! «,=3 л)=1 «,=2 «,=2 27.
НАДЕЖНОСТЬ МНОГОНОМПОНЕНТНЫХ СХЕМ Обратимся теперь к рзссмотрению задачи из совершенно другой области. Мы выбираем эту задачу, чтобы проиллк)- стрнровать процесс распределения, в котором функция оценки не является аддитивной. Одной из основных задач, возникающих при конструировании любо~о узла сложной аппаратуры, является задача надежности. Вот)рос приобретает чрезвычайно серьезный характер в связи с производстьом таких устройств, как, например, цифровая вычислительная машина. Одно неверное срабатывание какой-либо из тысяч электронных ламп, одна ошибка в какой-либо из миллионов операций — и все вычисления идут насмарку.
100 95 91 89 87 85 83 81 384 373 351 340 328 317 308 297 «а=4 «,=1 «,=3 «,=4 .тз — ! «,=1 «,=1 58 одномввныв пвоцвссы влспвидвлвния 1гл. т Во многих случаях задачу можно поставить как задачу, включающую построение надежного устройства из менее надежных компонент, Стандартный путь решения опирается на Рис. 13. Результаты численного решения для небольшой задачи о загрузке корабля, вмещающего восемь типов предметов с заданными весами и ценностями и судно грузоподъемностью в 100 единиц. возиожность дублирования компонент. Для некоторых типов простых схем получающуюся математическую задачу, как мы увидим, можно трзктовать с помощью методов динамического программирования.
~В 970 ч ч Р00 907 ь 900 107 ч,ч й д й , ььд 1 ф 0 10 Л7 Ю 40 дд Ю 10 Ю 90 100 - Ругааадьсмнасть судна а) 10 Ю 90 40 Ю Ю 70 Ю Ю 100 г — сггугааадагмнасть аудна а! 59 26) дхвливовлнив компонвнт 28. НАДЕЖНОСТЬ НА ОСНОВЕ ДУБЛИРОВАНИЯ КОМПОНЕНТ Допустим, что устройство, которое мы хотим сконструировать, можно считать состоящим из некоторого числа последовательных ступеней (рис. 14). гтадежноепгь устройства будет определяться как вероятность его безотказной - — СЛ работы. Принимая ио в ни- Ступепьг Стуинь у 0тупепь Ф мзние последовзтельное рзс- Рис. 14, положение, эту полную вероятность можно взять равной произведению вероятностей безотказной работы отдельных ступеней. Если надежность слишком мала для эффективного использования, мы можем исправить положение, размещая в каждой ступени параллельно компоненты-дублеры.
В результате структурная схема устрой- ства будет выглядеть так, как это Ступ гпь 1 ь п~упьпь а показано на рис. 15. Мы предполагаем, что в каж- ЕЛ дои своей ступени устройство снабжено перек.чючательными схемами, " которые облздают свойством подключения новой компоненты в схему, когда старая компонента Е3 отказывает, Надежность какой- либо отдельной ступени будет те. нерь зависеть довольно сложным образом от числа парзллельно дейРис. 15. ствующих компонент и типаисполь- зуемой переключательной схемы. Практические ограничения по стоимости, весу, объему и, возможно, дополнительные ошибки, вносимые переключательными схемами, препятствуют использованию в каждой ступени сколь угодно большого числа компонент-дублеров и тем самым делают невозможной совершенно безотказную работу.
Задача, которую мы хотим здесь рассмотреть, заключается в определении наиболее эффективного решения, использующего идею дублирования, однако с ограничениями вышеуказанного т ила. 60 одномвнпыв пноцвссы Рлспнвдвлвния [гл. ! 29. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ Для /=1, ..., А! обозначим 1+ ту — число компонент-д! блерол, используемых к У-й ступени, где гп =О, 1, ...; тт(т ) — вероятность безотказной работы у-й ступени, когда в ней используется !+гну компонент.
(1.39) Мы будем предполагать, что функции Еу(т ) нам заданы; их конкретный вид нас интересовать не будет. Надежность Х-ступенчатого устройства тогда дается выражением Рн= П ЕУ(тт). ! ! Пусть с.— стоимость одной компоненты в усй ступени. Если не учитывать стоимость переключательных систем, то задача, которую мы хотим решить, есть задача максими- зации рч при условиях л! (а) ~~ ~ тус (с, (1.41) (Ь) т = О, 1,...
При записи этих условий мы будем предполагать, что в каждой ступени должна быть обязательно использована по крайней мере одна компонента. Обозначим черезов,(с) значение р ., определенное в (1.40), даваемое некоторым оптимальным поведением. Тогда для АУ) 2 у,(с)=шах [р (т )~~,(с — т„с,)], Ш где т, удовлетворяет соотношениям (а) т =0,1,...,~ (ь) т,с, (С.
(1.42) (!.43) Пока мы исследуем только нрос!ой частный случай. Более сложная модель будег рассмотрена в главе !! в связи с двумерными процессами распределения. 61 80] ПАРлллельныв ОПБРлции Для Аг=! мы имеем Л(с)= х (] — ),. (1.44) В $ 27 главы !! будет приведено подробное обсуждение численного решения в случае, когда учитываются также и весовые ограничения. 30. ПАРАЛЛЕЛЬНЫЕ ОПЕРАЦИИ Если имеются две цифровые вычислительные машины или если досгупна одна из более современных машин, допускаюшзя параллельные операции, которые могут выполняться одновременно, предшествуюшие про~сауры можно существенно улучшить. Допустим, что мы хотим максимизировать функцию )' х в1 (х!)+ ' ' '+ апач(хам) (1.
45) в области х, +...-г- хгг+ хм+1+... + х,л,— — х, (1.46) где хт)0. Положим х1+...-1- хя —— .У1, ,,+, + "+х =Л (1.47) и ~м(у)= шах [д,(х,)+...+2(,(х )], х1+...+ х22 Р Лх(уя)= шак (8 +,(х,,)+... + ххЧ 1-Ц.. + хях=х1 (1.48) + Еагг(хам)] функции )'к(у1) и Лм(уя) могут быть вычислены рекурсивно посредством рассмотренного выше алгоритма. Как точько это сделано, мы можем определить решение для первоначальной задачи, максимизируя гл (у1) + !222(уя) в области значений у1+у,=х, у1, у, ~0. Главное заключается в том, что ул(у,) и )гл1(уг) можно вычислять одновременно.
Эаот процесс, конечно, можно продолжать далее в зависимости ог имеюшихся в распоряжении приспособлений параллельного действия, емкости памяти и т. д. ОДНОМЕРНЫЕ ПРОЦЕССЫ РЯСПРЕДЕЛЕНИЯ [гл. у!„! (х) = шах [г в1, (у) +Л!! (х — у)), (1.49) Хия(х) = !пав [Лве(у)+Ли(х — у)[ н т. д. Функция У!ам может быть поэтому вычислена в 10 ша- гов. 31. ЗАКЛЮЧЕНИЕ Цель этой главы состояла в том, чтобы ввести читателя в методологию динамического программирования, за!Рагивая как вычислительный, так и теоретический аспекты.
Для того чтобы познакоми~ь читателя с эгапами, которые имеют место при численном решении задач оптимизации на основе метода функциональных уравнений, мы подробно рассмотрели две частные задачи — общую задачу распределения ресурсов и затем характерный процесс загрузки .судна. Вывод, который мы можем сделать из э!ого анализа, заключается в том, что задача определения максимума фун!щии Я(х1,..., хл)=д!(х!)+...
+их(хх) (1.00) на множестве значений хп определенном соотношениями Х Х1=Х, х1~0, (а) !=! (1.б 1) а! (Х, ~йп х; =хм, хц,..., хы, (Ь) (с) есть обычная задача, легко и красиво решаемая посредством алгоритма, доставляемого динамическим программированием. Если мы заранее знаем, !то оптимальные выборы у! и уя Х лежат в окрестности —, мы можем почти вдвое сократить 2' требования к памяти, а также полное необходимое вычислительное время. Это — очень важное замечание для нашей даль.
нейшей работы, когда проблема емкости памяти приобретает особую остроту. Если все д1(х) одинзковы и требуется решение только частных задач, вычислительное время можно уменьшить весьма основательно. Так, чтобы вычислитьу!Рм(х), мы буден писать: коммнитлРии и вивлиоГРА4 ия Необходимое вычислительное время, цо существу, прямо пропорционально Аг. Для бочьшинства задач этого типа время для каждого шага будет порядка секунды. КОММЕИТАРИИ И БИБЛИОГРАФИЯ ф 1. Детальное изложение основ теории динамического про- граммироваиин читатель может найти в книге: К.
В е !1«па и, Отпав!с Ргойгащщ!ИЕ, Рппсс!оп 1!пкегвйу Рпяв, Рппсе!оп, )чге«ч кегле«ч 1957 [Русский перевод: Р. Б е л л и а н, Динамическое программирование, ИЛ, 1960), Обсуждение связи применяемых здесь идей и классических идей итерации и непрерывных гртпп ПРеобразований приведено в книге: К. В е)1щ а и, Айарбче Соп!го) Ргоссввем А. Ощйей Тонг, Рппсе!оп Спп егм!у Ргевв, Рппсе!оп, Нечг 3егвеуч 1961 [Русский перевод; Р.
Б е л л и а н, Процессы регтаирования с адаптацией, изд-во «Наука», 1964). С экономическими исследованиями и работами в области исследования операций, лежащими в основе задач, рассматриваемых нами а первых трех главах, можно познакомиться по ннигам: К. Л Агго«ч, Б. Каг)!и апй Н. Бсаг), Б!огВев !п йе Майе!набов) Тйсогу о1 )пчел!огу апй Ргойлсйоп, Б!ап1огй Пп!четв|!у Ргевя, Б!ап1огй, Сашогпга, !958. К.
0 о г1гп а и, Р. А. Ба т ц е)в оп апй К. Бо)о чг, Ыпеаг Ргоягащщгпй апй Есопощ1с Апа1ув!в, Мс0гаж-Нгй Вооа Со» 1пс., Кеж Уогй, 1958. Тт. 0 а 1 с, Т1«е Тйеогу о1 Ыпеаг Есопоппс Мог)е1я, Мс0гачг-НН Вона Со., )пс., )Чечг Уогй, 1960 [р«сский перевод: Д. Г е й л, Теория линейных экономических моделей, ИЛ, 1963). С. С. Н о) г, Г. М о й ! 81 ! а п Б Л М н ! й, Н. Б ! щ о и, Р1аппгпй Ргойоспоп, )пчепгопея апй й!ог!«Рогсе, Ргсп!ке Нан, )пс., Епй1ечгоой С)!!)я, )меч« Зегвеу, 1960.
К. А. Но«та г й, )Уупащ!с Ргойгапип!И8 апй Магйоч Ргосеввев, 3онп 'и'!)еу апй Боля, 74еч«уогй, 1960. [Русский перевод: Р. Ховард, Динамическое программирование и марковские процессы, «Сов. радио», 1964.) Б. К а г1)п, Майещайса) Мейойв апй Тйеогу !п Оащев, Рго8- гап»щ!ИЕ апй Есопощкя, Айй!воп-'«чея1еу РцЫМЫпй Со., Кеайп8, Мавяасйпвенв, 1959. [Русский перевод: С. Карлин, Матсматические методы в теории игр, программировании и эконо»гикс, «Мир», 1964.[ А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
