Динамическое программирование

из "Математическое оптимальное программирование в экономике "

В пятидесятых годах нашего века появились первые работы, посвященные изучению многошаговых процессов принятия решений. Оказалось, что для этого хотя и не очень широкого, но часто встречающегося класса задач ни методы классического математического анализа, ни аппарат линейного программирования, ни, наконец, вариационное исчисление не дают достаточно эффективных средств решения. Требовалось создать концепцию, которая позволяла бы с единой точки зрения исследовать вопросы многошагового принятия решений. [c.64]
Такая концепция, получившая название динамического программирования, была создана американским математиком Р. Беллманом и его школой и оказалась весьма эффективной для анализа и численного решения этого типа задач. Прежде чем описывать ее сущность, как обычно, начнем с очень простой задачи, которая позволит тем не менее познакомиться с характерными чертами динамического программирования. [c.64]
Так как функции fk(W) потребуются нам для различных значений W (вычисляя/ ( ), нужно знать/ / 1(W—дг - Pff), исходя из чего будем вычислять их последовательно одну за другой при различных значениях W, фиксируя количество предметов каждого типа, погружаемых в самолет. [c.66]
Результаты этих вычислений сведены в таблицу 11. Поясним, например, предпоследнюю строку этой таблицы. При грузоподъемности самолета от 48 до 71 единицы загружается два предмета первого типа. Стоимость гру-sa при этом составит 192. [c.66]
Наибольший из полученных результатов 277, поэтому fj(70)=277, а соответствующее значение х2—1. Так строится табл. 12 функции fi(W). [c.67]
Аналогично построены таблицы значений функции fs(W) и (В7). При этих построениях всякий раз используется предыдущая таблица. [c.67]
На основании этих таблиц уже можно найти оптимальный план загрузки самолета грузоподъемностью W=83. Из таблицы 14 находим, что максимальная стоимость груза /4 (83) оказывается равной 308, а предметов четвертого типа следует погрузить всего одни, так как 4=1. Этот один предмет имеет вес 10, и, следовательно, предметов остальных типов можно загрузить лишь в пределах веса 83—10=73. Из таблиц 13 и 12 последовательно находим, что для Н7=73 не следует грузить ни предметов третьего типа, ни предметов второго типа, т. е. хз=0 и 2=0. Из таблицы 11 видно, что при W=73 следует взять три предмета первого типа, т. е. i = 3. [c.67]
Окончательно наилучший план загрузки таков следует взять три предмета первого типа и один предмет четвертого типа. Их суммарная стоимость составляет 308. [c.67]
Замечание первое. Легко видеть, что мы ие только решили поставленную задачу (найти план загрузки самолета грузоподъемностью В7=83), но сделали гораздо больше. Из таблиц 11—14 могут быть найдены оптимальные планы загрузки для самолетов любой грузоподъемности (от 0 до 87), т. е. вместо одной задачи решено целое семейство сходных между собой задач. Это характерная черта метода динамического программирования, расширив задачу, мы облегчили ее решение. [c.67]
После того как рассмотрен этот простой пример, перейдем к более общему описанию многошаговых процессов принятия решений. [c.68]
Рассмотрим задачу распределения ресурсов, состоящую в следующем имеется некоторое количество ресурса х, которое можно использовать N различными способами. Ресурсы могут быть самой различной природы (деньги, машины, люди, земля) и т. п., так же, как и способы их использования. В рассмотренной задаче ресурс — грузоподъемность самолета, а способы использования — возможность загрузки различными типами предметов. [c.68]
Функция /лг(-к) выражает, следовательно, максимальный доход, который можно получить, используя количество ресурса х, N различными способами. [c.68]
При выводе этих рекуррентных соотношений, по сути, использовался следующий очевидный принцип оптимальная стратегия обладает тем свойством, что для любого первоначального состояния и некоторого начального этапа решения последующие решения должны составлять оптимальную стратегию относительно состояния, к которому пришли в результате начального этапа решения. Этот принцип, получивший название принципа оптимальности, лежит в основе всей концепции динамического программирования. [c.69]
Соотношения ( ) позволяют заменить чрезвычайно трудоемкое вычисление максимума по N переменным в исходной задаче решением N задач, в каждой из которых максимум находится лишь по одной переменной. С их помощью могут быть решены задачи, которые иными путями решать не удается. [c.69]
Мы рассмотрели задачу с одним ресурсом. Та же идея анализа задачи, основанная на принципе оптимальности, может быть использована и в случае нескольких видов ресурсов. Однако с увеличением размерности объем вычислений быстро растет, так что реально метод динамического программирования непосредственно может быть применен в случае двух, максимум трех-четырех видов ресурсов. Это отличает его от линейного программирования, где преодолимы и большие размерности. [c.69]
Для производства определенного продукта предполагается построить несколько предприятий. Считаются известными суммарная производственная мощность этих предприятий, наибольшая и наименьшая производственные мощности каждого предприятия, известна также зависимость себестоимости продукции на каждом предприятии от его производственной мощности. Требуется так выбрать производственные мощности предприятий, чтобы суммарная себестоимость производства продукции была минимальной. [c.69]
Читателю предлагается самому построить математическую модель задачи и убедиться в возможности решить ее методом динамического программирования. [c.70]
До сих пор количество распределяемого ресурса предполагалось меняющимся дискретно. Во многих случаях оказывается естественным считать возможным непрерывное изменение. Следующая задача и дает пример такой ситуации. [c.70]

Вернуться к основной статье