Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 10
Текст из файла (страница 10)
х~ /х/ — л бов. Соседняя таблипа тогда определяет оптимзльное втоЛсч/ла // о /г рое решение. Лналогичпым образом все выходные гзб- Х вЂ” т— лицы поведений обрабаты- ваются в порядке, обратном /г — / — /~ тому, в котором они вычис- лялись. Единственная инфор///тл /г =// л Опал мания, используемая на этом пути, — множество таблиц Рнс. 1О. поведения ( х„(х) ).
Таблицы доходов ( га(х)! были существенны для образования последовательности результатов, но онн не являются необходимыми в этой второй фазе вычислении. Дадим подробное обьяспенне блок-схемы (рис. 1О) для второй фазы решения задачи распределения. Эта п 1. Мы начинаем с рассмотрения задачи, включающей /т/ способов производства и начзльное количество ресурсов /см Ячейка /а содержит переменную, обозначающую число способов; х обозначает количество ресурсов.
Э т а п 2. Определим поведение, соответствующее вышеуказанной ситуации. Это повлечет за собой табличный просмотр, использую~див таблину х„(х), полученную в первой фазе. Последовательность ( ха (х) ) этих таблип поведений, образованных в фазе 1, обычно запоминается на ленте или перфокартах и, следовательно, должна по мере надобности вводиться в оперативную память. Соответствующее поведение запоминается в ячейке я. Олин полезный пРием 2й) Этап 3. Номер рассматриваемо~о способа и поведение печатаются, образуя одну строку таблицы окончательных результатов.
Э т а и 4. Наличные ресурсы сокращаются на уже распределенное количество и, а число рассматриваемых способов уменьшается на единицу. Э т а и б. Если еще остается сколько-нибудь способов, мы возвращаемся к этапу 2. Это требует просмотра некоторой новой таблицы поведений, вложенной в память. Если никаких способов не остается, вычисления прекращаютсн. На этом заканчивается исследование того, как получается решение для частных значений ж и Ф в динамическом программировании. 20.
ОДИН ПОЛЕЗНЫЙ ПРИЕМ Заметим, что результаты фазы 1 обрабатываются в порядке обратном их получению. Если имеется запоминающее устройство на магнитной ленте, обработка легко осущестнляется с помощью команд «считывания в обратном направлении». Для машин с ограниченным вспомогательным запоминающим устройством результаты нужно последовательно перфорировать на картах. Здесь мы рекомендуем следующий прием, успев- 12олв адресов поль далньл но применяемый на маши- (12дваа«льи адресов) /22двоа«На«Свае) пе Джонниак. Выберем или изготовим карту такого формата, Рис. 11. который лает возможность вставить ее в мэссиз в перевернутом виде (т.
е. вниз 12-й строкой, которая является первой на большинстве машин) без считывания данных с карты. Например, такая карта, часть стандартной системы ввода машины Джонниак, покааана на рис. 11. Когда такая карта перевертывается (так что адрес остается еще в левой половине карты), то сначала читается верхняя строка, а не нижняя.
Однако после считывания всех 12 строк те же самые данные записываются в те же ячейки, в которых они появились бы, если бы карта была вставлена обычным образом, Это позволяет нам поместить весь ввод этапа 1 на одну карту, начиная с последней лй !гл. и одномвяныя пвопвссы васпявдвлвния карты (т. е. лицом вниз), достигая при этом желаемой инверсии расположения для этапа 2. Если требуется хранение карты, то каждой из АГ вводимых таблиц этапа ! должна предшествовать карта переноса (порядок следования обратный), чтобы выделить признак копна таблицы на протяжении этапа 2 вычислений.
21. УСТОЙЧИВОСТЬ Целый ряд очень интересных математических вопросов возникает в связи с использованным нами приближенным методом. Они не только представляют интерес для аналитика, но имеют также первостепенную важность для успешного применения наших численных методов. Все этн вопросы относятся к понятию устойчивости. Мы брали уравнение н заменяли его родственным ураянением, в котором л~аксимизаггия выполнялась по более узкой конечной области значений и рассматриваемые функции вычислялись только в конечном множестве точек.
Так как обе эти операпии, вообще говоря, вносят ошибки, немедленно возникает вопрос об их величине на каждом шаге, а также о росте этих ошибок при увеличении числа шагов. Задачи этой общей природы были широко исследованы для обыкновенных дифференциальных уравнений и уравнений н чащных производных, но для функциональных уравнений динамического программирования было получено очень мало результатов. Мы кратко коснемся этой задачи в главе Х!!. 22. ПРОЦЕСС ЗАГРУЗНИ СУДНА В качестве первой иллюстрации общих методов, описанных на предшествующих странипах, рассмотрим простой тип аадач, которые часто возникают при загрузке судов и упаковке грузов.
Допустим, что необходимо загрузить корабль грузом, составленным из отдельных предметов различных типов. Так как эти отдельные предметы имеют различные весз и стоимости, возникает задача о том, как загрузи~ь судно ограниченной грузоподъемности грузом наибольшей пенности. С помощью простого видоизменения ситуапий читатель сможет представить себе много вопросов подобного рода. 24) овгуждинни 23. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ Предположим, что мы имеем судно максимальной грузоподьемнос!и л, груз которого должен состоять из различным количеств предметов М различных типов. Пусть сч — стоимость отдельного предмета 1-го типа, ) гл; — вес отдельного предмета Ого типа, ~ (1.31) х; — число отдельных предмстоа Ыго типа, взятых для погрузки.
Тогда задача определения груза наибольшей ценности Есть задача максимизации линейной форл!ы м Е„(х)= У хгв! г=! (1.32) при условиях л', хгтиг(л, !=! х;=О, 1,2, (а) (1 33) (Ь) Знзчения (пг, ш!), естественно, берутся положительными. 24. ОБСУЖДЕНИЕ ва и ~а (1.34) Нетрудно показать, что при наличии условия (1.ЗЗ), которое допускает только дискретное множество значений, предыдущее решение уже не всегда будет правильным. В настоян!ее время не существует точного решения для поставленной задачи, имеющего простую аналитическую форму. Если бы условие (1.33) сводилось просто к ограничению х; ) О, задача была бы совсем несложной и ее решение можно было бы определить следующим образом. Рассмотрим отношение †', 1 = 1, , тч', и пусть а — индекс, для которого это отношение принимает максимальное значение.
Затем выберем только предметы типа сй при этом мы получим максимальную стоимость груза 54 одномвяньш пяоцвссы глспввдвлвния 1гл. 1 Округление решения для задачи с непрерывным измене- нием переменных до ближайшего целого числа может при- вести к решению, далекому от оптимального. Рассмотрим, например, следующую задачу, включающую три различных типа предметов: л= 100 — максимальная грузоподъемность, ш,=49, в,= 20, ша=50, па= 75, ша=51, па=102. 25. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ Для х) 0 и ТтГ=1, 2, ... определим функцию У„(~) = шах 7-м (~) 1х,1 где максимизация совершается по множеству значений лн определяемому (1.33).
Тогда Л(з)=~ — „' ~'н (1.37) причем [ш) обозначает наибольшее пелое число, меньшее или равное ш. Поступая как в 3 10, где можно нанти общее рекуррентное соотношение, мы получаем простую формулу ~„(г) = шах (.'г,„п „+~л (г — х тпгг))! "Л Если бы не условие целочисленности, мы погрузили бы 100 102 — 1,96 предметов типа 3 и имели бы стоимость 100 °:= 50 51 =200. Так как эго пе разрешается, мы мо.кем подвергнуться соблазну округлить 1,96 до 1 и ваягь один предмет типа ф чтобы покрыть нзбыточпып вес. Это поведение дает ценность 122. Однако настоящий оптимум легко определяется простым перебором; он равен !50 и достигается посредством погрузки двух единиц типа 2.
Ввиду такой скрытоп природы точного аналитического решения представляет интерес укааать простой алгоритм, основанный на предыдущем рассмотрении общих процессов распределения, который быстро дает решение. 26) оястждянив вычислительной пяоцвдтвы 55 здесь х, пробегает значения из множества О, 1, 2, ..., ~— (1.38) В следующем параграфе мы опишем программу, употребляемую для вычисления как последовательности (у,(«) ), так и оптимального выбора хн 26, ОБСУЖДЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ Основные вычисления могут быть выражены в 2о командах, Поскольку выполнение этого неболыного числа команд повторяется тысячи раз, можно с уверенностью сказать, что из миллисекунд складываются секунды.
Фактически, с точностью до времени ввода и вывода, все время вычислений, по су~цеству, определяется агнии 25 командами. Они выполняют: (а) оценку и;х; для выбора груза в х; предметов Ьго типа; (Ь) просмотр таблицы для оптимального дохода ~а,(« — шах;), получаемого от ! — 1 предметов предшествующего типа при оставшейся емкости (« — ш;х;); (с) максимизацию (а) + (Ь) по всем неотрицательным целым х, не превосходящим наиболыпего целого числа, содержашегося в «/юг Вычислительное время зависит от распределения весов шн Однако можно указать следующую полезную оценку. Если М вЂ” число типов предметов, « — максимальный допустимый вес грузов, ш — среднее из шн 0,00о — время, затрачиваемое на вычисление хгва +У,,(« — х;ш;) при данных значениях хн пн шв « н т'„ о то вычислительное г « время =0,005(=~ «Дг секуни 2и) Время ввода и вывода является функцией количества требуемой информации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
