Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 49
Текст из файла (страница 49)
кн решение большого числа задач этого типа, перечислены в конце этой главы. Переходя к получению численного решения, мы ясно видим, что дискретная задача може~ быть сформулирована как задача линейного программирования. Мы должны максимизировать линейную форму г — ~ Е (г) = ~~ гл (т7) я=о (7.10) 6. ИСПОЛЬЗОВАНИЕ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Определим дзя Ат=1,2,...; с,— О; с,— О функцию (сп с,), равную суммарному выпуску автомобилей за тт' этапов, причем первоначальный запас стали равен со первоначальная заводская мощность равна с„ и используется оптимальная политика.
(7. ! 1) Мы имеем: ут (с„са) = а, сь (7. 12) и вообще у (с„с,) = шах 1г +Ум, (аа г„са+ аа г )) (7. 13) при ограничениях (7.5), (7.6) и (7.7). Чтобы исследовать выполнимость решения в этом направлении, подсчитаем переменные, предполагая, что нас интересует 30-шзговый процесс. С тремя дополнительными неизвестными, вводимыми на каждом шаге, мы получаем задачу, включающую 90 переменных, связанных 120 соотношениями. Эта задача хоть и не огромного, но тем не менее порядочного размера. Если же мы хотим определить зависимость решения от с, и с, (первоначальных запасов стали и первоначальной мотцности заводов), то прямой метод этого типа может потребовать совершенно немыслимого времени.
Мы хотим вместо этого представить численный метод, который автоматически дает зависимость решения от с, н с,. 301 игглгьтозаниг ВГРшгш д,ш Аг= 2, 3, , где максимиззциЯ пРоисходит ПО области в г-пространстве, определенной нерзвенствами . + * + = и гя <а,си г,(се (а) (Ь) (с) (4) (7. 14) В следующем разделе мы рассмотрим численное определение последовательности (у,(сн с,ц.
6. ИССЛЕДОВАНИЕ ВЕРШИН Область и пространстве переменных (з„з„г„), определенная неравенствами (7. 14), имеет форму, показанную на рис. 7о. Вершины, перенумерованные на рис. 75, имеют следующее значение в рамках нашего процесса: 1. В случае, если заводская могцность не вносит ограничений, вся имеющаяся в распоряжении сталь направляется на производство но- га Вой стали. 2.
Направить максимально возможное количество стали на производство стали; сгаль, оставшуюся после удовлетворения заводских мощностей, направить на Б расширение этих мощностей. Рис. 75. Область изменения величин 3 )(опустимая часть запасов стали предназначается на производство автомобилей, остаток — на производство стали. 4. Случай, когда заводские мощности недостаточны для обработки всей имеющейся в распоряжении стали.
Эта вершина изображает распределение стали для сталелитепного производства до предела заводских мощностей, распределение ее в автомобильном производстве вплоть до допустимоя доли и назначение оставшейся стали на расширение заводских мощностей. Зба мпогоп!Агоиыв пгоизводстивнныв пвоцвссы 1гл, ун (си с!) = шах (ш 1п (а! с„с, — г, — г ) + !»! +Ум !(ая г„с!+ аа лм)1, (7.15) где максимизация теперь происходит по области г„г ~0, 2,+2,„(сн г««-.
с!. (а) (Ь) (с) (7.16) '7. УМЕНЬШЕНИЕ РАЗМЕРНОСТИ И ДИАПАЗОНА ИЗМЕНЕНИЯ ВЕЛИЧИН Покзжем теперь, что мы можем свести задачу к последовательности одномерных задач и одновременно ввести «стягивающее» преобразование. Этим мы хотим сказать, что б. Направить максимально возможное количество стали на производство стали, а остаток — на производство автомобилей. 6. Направить все текущие запасы стали на расширение заводских мощностей. 7. Производить максимально возможное количество автомобилей, а с оставшейся сталью расширять заводские мощности.
Очевидно, что все эти условия не встречаются сразу, а зависят от производственных мощностей и запзсов стали, которые изменяются в течение процесса. Из этой семерки только первые пять случаев представляют реальную возможность, так как вершины б и 7 заканчивают процесс — новая сталь не производится. Можно показать, что максимизация по вершинам области дает либо оптимум, либо очень хорошее приближение по мере произвольного возрастания числа шагов.
Здесь, так как нас прежде всего интересует указание общего подхода к задачам такого типа, мы будем считать максимизацию по вершинам точной. Во всяком случае вычисление этого типа дает полезное приближение в пространстве политик. Если бы мы хотели идти с самого начала, не имея никзких предвзятых суждений о положении мзксимума, мы должны были бы делать следующее. Соотношение (7.13) может быть записано в виде 7) уменьшвниа Рлзмввг!ости вглнчин 809 мы можем гарантировать, чго число возможных состояний системы не возрастает на протяжении времени. Прежде всего из линейности всех ограничений и функций производства ясно, что 7 (си с„) является однородной функцией первой степени с, и см Следовательно, для с„сз) О мы имеем: 7!г(сг,сз) = с! ум~1, — ') = сз~ (-г,1 ). (7.17) Отсюда следует, что нам надо вычислять только у „(1,х) или Ум(х, 1).
Возвращаясь к (7.13), мы имеем; г', (1, сз) = шах («я + Ум !(аз «„с, + а, «,„)) = г*! =шах~«„+а,«,~м !~1, 11. (7.18) Теперь мы видим, что вычисление г" (1,с,) для с,— О зависит только от знания г ,(1, сз) для с, =- О. Это и есть требуемое уменьшение размерности. Однако перед нами еще трудность расширяющегося диапазона для см так как относя+ аз «„, шение ." ' может быть много больше, чеи сз/с!. Чтобы избежать этой трудности, покажем, что мы можем вычислить 7 (1,х) и/ (х,1)для О(х(1, зная Уч з(1,х) и Ул !(х, 1) для О =.х -1. Целесообразно ввести две функции вместо одной, чтобы сохранить фиксированным интересующий нас интервал.
Возвращаясь к (7.18), имеем: (1, с,) = шах ~ г, + аз«,Ум, (1, " + ' "-') ~ (для а,«, ) с, + аз«, ) (7.19) = шах(«~+ (с, + аз«~)г,ч ! ( (для а,«,-=с,+ а,«,„). Используя это уравнение и учитывая замечания о максимизации по вершинам, мы получим очень простую вычислизельную схему. З10 многошлговыБ пРОизводстзвин!яв пРОцвссы [гл, чп 8. ТЕХНИКА ВЫЧИСЛЕНИЙ Упрощения, введенные с помощью преобразований $ 7, являются самыми значительными в этом частном исследовании. Что касается программирования, то тем самым получаются следующие результаты: (а) сокращение времени и объема памяти с у' до 2Т *) и (Ь) дальнейшее значительное сокращение, вызываемое устранением расширяющейся сетки.
Разовьем подробно эти два пункта. Обычно, чтобы выразить все возможные состояния системы, определенной двумя независимыми параметрами (здесь с,— запасы стали и е,— зазодская мощность), необходимо построить сетку значений г,(сп с,) в пространстве (сп с,), а затем интерполировать по этой двумерной области, чтобы определить (м (е'„е',), т. е. количество стали, предназначенной для производства автомобилей в течение процесса, состоящего из АГ шагов, в котором первоначальные значения равны с, и е„, где с,, е, не являются точкой сетки. Эта функция необходима для последУющего вычислениЯ фУнкций Ум+, (си сэ). Если интеР- валы [О,е,[ и [О,сэ[ разделены на п частей этой сеткой, мы должны вычислить н запомнить для дальнейшего использования л' значений 7,(снеэ).
Потребность во времени становится даже более серьезной из-за дополнительных логических операция, необходимых при рассмотрении двумерной системы. Вот чем обьясняется экономия, проистекзющзя из сведения к одномерной форме. Возможность расширения сетки является серьезным препятствием в некоторых процессах динамического программирования. Говоря нематематически, ситуация такова: чтобы рассчитать условия в момент времени Е мы дол.кны зна~ь заранее все возможные состояния, которые могли бы существовзть в момент времени 1 — 1. В нашем конкретном приложении, чтобы определить количество автомобилей, произведенных зз Аг периодов, мы должны знзть их количество за Аг — 1 периодов для всех допустимых запасов стали н мощностей. Но после одного периода производства ззпасы или мощность (либо то и другое) могут возрасти. Поэтому для вычисления (м(си с,) необходима величина 7 ч ,(с„ с„), *) речь идет о характере зависимости этих характеристик от числа шагов.
(Примо ред.) 312 многошаговыв производстввнныв пропвссэя [гл. чп где с,' может быть больше с, и аналогично с', больше сь Следовательно, область, по которой может быть вычислена У,(с„га), меньше, чем область, в котоРой известна У,, (сь с,). !!оэтому надо начинать расчеты Ат-го шага с рассмотрения большой области, чтобы завершить вычисления с умеренным диапазоном значений с, и са Методика 6 7, обходящая это препятствие, является реальным и значительным прогрессом. Заслуживает внимания одна новая черта этой задачи— оптимизация по трехмерной области. Методы решения общих многомерных задач такого типа мало исследованы.
Здесь, конечно, нас спасают природа функций и наши аребования о том, что должны быть рассмотрены только вершины области. Г!рограммз для определения и оценки подходящих вершин изображена схематически на рис. 76. Таблица 7! Анализ типичной ситуации на узкие места. Пятнадцатншаговый процесс с параметрами а, = 0,2; ал = 2; а, = 0,4 и исходными даннымн с, = 1, с, = ! Информаниа, получасмаа непосрел сталино при вычислсннак Фактические усвоен» прн нспольаованни оп- тимальной политики сталь, распре- лелсниан в акт о праны ы- лсвности фактическое условие а на- чале этапа нормированное ус- ловие (ст, са) в начале втапа вер- шина этап Суммарное распределение в автомобильной промышленности ! 2 3 4 5 6 7 8 9 10 !1 12 13 14 15 (1; 1) (1; 0,5) (1; 0,7) (1; 0,585?) (1; 0,642) (1; 0,61 1) (1; 0,626) (1; 0,620) (1; 0,588) (1; 0,586) (1; 0,573) (1; 0,579) (1; 0,576) (1; 0,577) (1; 0,577) (!'1 !) (2; 1) (2; 1,4) (2,8; 1,64) (3,28; 2,096) (4,192; 2,57) (5,14; 3,22) (6,44; 3,988) (7,976; 4,4536) (8,9072; 5,2196) (10,4392; 5,9817) (11,9634; 6,9268) (13,8536; 7,9797) (15,9594; 9,2086) (! 8,4172; 10,6226) 0 0 0 0 О 0 0 1.288 1,595 1,781 2,008 2,393 2,771 3, 192 3,683 818 д) стапионагнын Рост 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
