Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 18
Текст из файла (страница 18)
Модель, которую мы будем подробно обсуждзть, нззывается транспортной моделью Хичкока — Купманса, хотя она независимо изучалась Канторовичем и Ароншайном. Зта частная задача была предметом широких исследований, в результате которых в настоягцее время л~ы располагаем целым рядом остроумных и моцщых методов (принадлежацгих Данцигу, Фладу, Форду и Фулкерсону) для анализа некоторых важных специальных случаев; ссылки имеются в конце этой главы. Мы рассмотрим здесь другой частный случай более обпгей задачи, который особенно хорошо поддаегся рассмотрению с помощью функциональных уравнений.
Накладываемые ограничения позволяют нам рассмотреть более близкие к реальным процессы, которые не могут быть обслужены методами, развитыми для линейных моделей. Мы покажем, что транспортную задачу Хичкока — Купманса можно трактовать как процесс распределения, к которому может быть применен метод функциональных уравнений — как непосредственно, так и в сочетании с методом множителей Лагранжа. С методической точки зрения этот процесс предоставляет нам удобный случай ввести другой мощный математический аппарат — лштод лоследовательных приближе,ний. Мы детально обсудим эти вопросы ниже, вместе с результатами нескольких численных экспериментов.
Комбинируя эти два метода анализа — функциональные уравнения и последовательные приближения, — мы можем надеяться получить решение довольно сложных задач. Зз) модель твлнспоетного нвопвсса 33. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТРАНСПОРТНОГО ПРОЦЕССА Назовем пункты, в когорых сосредоточены ресурсы, складами и пункты, в которых существует спрос на эти ресурсы, пункталш потребления. Иногда, и более образно, их называют соответственно источники и стоки (пот1 ебители). Мы можем считать их расположенными следующим образом: Сииилы 1=1:О, 2: 0я Пуииты иоиреалеиии /=1; Рг 2:Р, х; — запасы этого ресурса на Рм складе, 1=1, ..., л1, и — спрос иа этот ресурс а у-м пункте потребления, (2,94) у=1, ..., М. Предполагая, что общий запас равен общему спросу, т.
е. что залача состоит только в распределении, будем иметь: ~',х;=~г;. э у (2.95) Хотя, как мы увидим, более общая задача, когда запасы превышают спрос, может изучаться теми же методами, в случае равенства происходит существенное упрощение. Этот вопрос будет обсуждаться в 3 37.
хотя, конечно, такое приятное расположение не является ни необходимым, ни Гезльно возможным. Нас будет интересовать только тот случай, когда либо число складов, либо число пунктов потребления мало, хотя мы и будем формулировать процесс в общих терминах. Если одно из этих чисел мало, другое может быть сколь угодно большим — это не повлияет на возможность решения задачи. В дальнепшем будем предполагать, что имеется один вид ресурсов, и введем следующие величины: 166 многоэ1нгныв пяоцвссы илспввдвлвния [гл, и Пусть хц — количество ресурсов, отправляемое из 1-го склада в )-й пункт потребления, и аг (хб) — стоимость осуществления этой операции.
(2.97) Величины хО подчинены трем ограничениям: (а) Неатриггательногть. (Ь) Ограничение на запасы; общее количество ресурсов, отправленное иэ любого склада, должно равняться запасам на этом складе. (с) Ограничение на спрос: общее количество ресурсов, отправленное в любой пункт потребления, должно равняться спросу в этом пункте. (2.99) Отметим, что мы исключаем транспортировку через пере- валочные пункты, т.
е. мы не можем перемешать ресурсы из одного склада в другой и затем в пункт потребления или из склада в пункт потребления и затем в другой пункт потреб- ления. Предыдущие словесные ограничения дают следующие соотношения: (а) хы)0, м (Ь) ~ хо=хи 1=1, 2, ..., Л1, М () г „=, Г=!э,,н. г=1 Итак, мы пришли к задаче, которая состоит в определении неличин х;, удовлетворяющих предшествующим условиям, так, чтобы минимизировать общую стоимосгь перемешения ресурсов (2.99) С „х = ~ Д, (хы). с/ (2.100) 34.
ОБСУЖДЕНИЕ Ясно, что эта задача весьма сложна, если не ввести дальнейших ограничений на вид функций йы (х); но даже тогда она остается сложной, если Л( и уэг велики. Особенно инте- липачичясков пРОГРучынРовлцпв 1от ресен — сам по себе и как отправная точка для дальнейших исследований — случай, когда стоимость перевозки из любого склада в любой пункт потребления прямо пропорциональна перевозимому количеству, т. е. у;;=1;;хгр (2.101) 35. ПОДХОД С ТОЧКИ ЗРЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 11ачнем с рассмотрения случая, когда имеются два склада и произвольное число пунктов потребления. Пупкаи ппаребаеиик Р,:г, Р,:г, Скаааы О,:х, Р,:г Рн и Ключ к задаче — в том, что можно удовлетворять спрос по очереди, начиная с пункта Р , затем переходя к Р , и т л.
Как обычно, мы превращаем статический процесс в динамический с тем, чтобы применить метод функциональных уравнений. Коэффициент й;, можно ингерпреуировать как раггтонние. Задача минимизации становится тогда задачей из области линейного программирования, и, как отмечалось выше, имеется много изящных и быстрых алгоритмов длн ее решения как вручную, так и с помощью вычислительных машин. Но эти методы неприменимы, если функции стоимости нелинейны, за исключением тех случаев, когла функции ан (х) обладают опрелеленными простыми структурными свойствами, дающими возможность тем или иным образом эффективно провести линейную аппроксимацию.
108 многомБРныв ПРО!тиссы РлспРБделения 1гл. и Введем затем функции г (хн х,), определенные для И=1, 2, ..., х„ха~О следующим образом: у;т(хн х,) — величина затрат нри использовании оптил~альной политики, когда начинают соответственно с количеств хн хт на складах Й, и Е~н нри фиксированных потребностнх го гн ... ..., гя соответственно в пунктах потреблении Р„ Ра, ..., Ря. Удовлетворяя первым спрос в Ф-и пункте потребления, мы понесем затраты х; (х,,)+д, (хз ) (2.103) +1„, т(х, — х, „х — х )], (2.104) область, определяемая условиями х, +х =г где Йя — двумерная (а) 0 ( х „=-'. х Р 0(х -х. (Ь) (с) (2.105) Для М= 1 имеем: Ут (хн х,) = 8т, (х,)+ йат (х,).
(2.106) 86. ОБСУЖДЕНИЕ Ясно, что этот же самый метод может быть применен для трактовки аналогичной задачи с более чем двумя складами. Но если заботиться о численном решении, то при т!4)3 мы столкнемся с обычными трудностями, вызванными размерностью задачи. В следующих параграфах мы обсудим некоторые приемы, которые можно использовать для преодоления этих трудностей.
и уменьшим запасы ресурсов на складах О, и Оа до х, — хьч и х — х Используя принцип оптимальности, получим для М) 2 рекуррентнсе соотношение 1„(хт, х,) = ш!п(8,„ (х,„) + дл„ (хт ) + (Я,т 38) увиличвнив шага пятки Эт. ПОНИЖЕНИЕ РАЗМЕРНОСТИ 7(о сия пор мы не использовали дополнительную информацию о том, что ззпзсы равны спросу, т. е. что х,+х,= ~, ге (2.1 07) Отсюда следует, что при фиксированном спросе величину х, можно определить всякий раз, когда известна хе Следовательно, мы можем исключать пзраметр состояния х, и просто написать: 7" (хь х,) =7 (х ).
(2.108) Соотношение (2.104) перейдет в ~м(х') ш1п (Дьч(хпя)+ням(гл хьч)+ хьч +т' (х — хпт)1 (2.109) где хц удовлетворяет условиям (а) 0(х, — х,, и (Ь) 0 ( г — х,„( ~ г; — хи (2.110) а=! 38. УВЕЛИЧЕНИЕ ШАГА СЕТКИ В связи с предыдущими замечаниями обратим внимание на то, что один из способов обойти трудности, связанные с размерностью, состоит в увеличении шага сетки.
В задаче с двумя параметрами состояния можно позволить каждой переменной принимать 100 различных значений, так как вто Областью изменения переменной х, в у,(х,) служит [О, ~~~~ г,~. г ! Таким же образом общая задача, включаюсцая М складов, может быть сведена ь вычислению последовательности функций 7И вЂ” 1 переменных. Следовательно, задачи с двумя складами совсем просты; задачи с тремя складами доступны непосредственному решению; решение задач с четырьмя и более складами требует использования специальных приемов.
110 многомкгньги пгоцяссы глспввдвлвния (гл. и потребует всего 10' ячеек. Современным машинам (примерно 1960 г.) доступны задачи с такими требованиями к памяти. Следует напомнигь, что памягь, необходимая, собственно, для осуществления процесса динамического программирования, составляет приблизительно треть объема паияти машины благодаря тому, что мы имеем дело одновременно со сгарой» функцией дохода у т ,(р), «новой» функцией дохода у,(р) и новой функцией политики х,(р). Если имеются несколько функций полгпики, множигель одна ~реть должен бы~в еще уменьшен, С другой стороны, если имеются три параметра состояния, то прн 100 различных значениях каждой переменной потребовалась бы память, способная хранить 1Ов значений, что превосходит возможности сегодняшнего дня.
Но если использовать вместо ста только 20 различных значений для каждой переменной, то потребуется всего 8 ~; 1Оа значений, и задача будет еще в пределах наших возможностей. Следовательно, всегда можно работать с функциями многих переменных, «прореживая> область изменения каждой переменной. Конечно, ценой этого является меньшая точность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
