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

Математические методы в экономике ...

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

Динамическое программирование — математический метод поиска оптимальных решений по управлению многошаговыми процессами, в ко¬торых состояние исследуемых систем изменяется во времени или по¬этапно. Подобные системы и процессы имеют широкое распростране¬ние в реальном мире, а необходимость эффективного управления ими объективно определяет важность и актуальность использования мате¬матических методов решения соответствующих управленческих задач. Теоретической основой метода динамического программирования (ДП) является принцип оптимальности, имеющий широкую сферу приложе¬ний в экономике, технике, естествознании, военном деле.

В качестве фазовой переменной х, определяющей состояние системы в ходе процесса распределения инвестиций, примем суммарный объем средств, выделенных предприятиям после каждого шага процесса. Именно, переменная х1 представляет объем средств, выделенных предприятиям после первого шага процесса (т. е. только предприятию П1), х2 — объем средств, выделенных после второго шага (предприятиям П1 и П2), х3— объем средств, выделенных после третьего шага процесса (всем предприятиям П1, П2 и П3). Поскольку в начальный момент общая сумма выделенных средств равна 0, то начальное состояние системы характеризуется значением х0=0. По условию задачи общая сумма инвестируемых средств равна 5 усл. ден. ед., т. е. обязательно выполняется условие хз = 5. Поскольку по смыслу задачи на каждом шаге процесса значения фазовой переменной не убывают, то выполняется ограничение хi ≤ 5. Отметим, что проведенный выбор фазовой переменной с указанным экономическим смыслом не является единственно возможным. Например, в рассматриваемой задаче можно было выбрать в качестве переменной х остаток нераспределенных средств.В качестве управляющей переменной и примем объем средств, выделяемых предприятиям на каждом из шагов процесса. Именно, переменная u1 представляет объем средств, выделяемых предприятию П1 (на 1-м шаге процесса), u2 - объем средств, выделяемых предприятию П2 (на 2-м шаге), и3 — объем средств, выделяемых предприятию П3 (на 3-м шаге). Будем считать, что средства предприятиям выделяются суммами по целому числу усл. ден. ед.; соответственно все управления принимают только целочисленные значения 0, 1, 2,... .Функция процесса xi = fi(xi-1,ui), определяющая закон изменения состояния системы, для данной задачи представляется формулойxi=xi-1 + uiи имеет следующий простой смысл: суммарный объем средств xi выделенных предприятиям нарастающим итогом после текущего шага с номером i, равен суммарному объему средств xi-1, выделенных предприятиям после предшествующего шага с номером i-1 (или, что то же самое, до текущего шага), плюс объем средств ui, выделенных предприятию Пi на текущем шаге.Функция zi, определяющая частный экономический эффект на шаге с номером i процесса, зависит только от объема ui инвестированных средств в предприятие Пi, т. е. zi = zi(ui), и определяется по таблице данных задачи по столбцу, отвечающему этому предприятию. Например, z1(2) = 4 (из столбца, отвечающего предприятию П1), z2(3)=6, z3(4)=9.На этом действия, предписываемые пп. 1-5 разд. 1.7 гл. 1 выполнены, что означает завершение математической формализации поставленной задачи, т. е. построение соответствующей экономико-математической модели. Заметим, что после проведенной указанным образом формализации основные допущения метода ДП выполняются: отсутствие последействия следует из явных формул для вычисления xi и zi, а аддитивность целевой функцииZ = zi(u1)+z2(u2)+z3(u3)обусловлена самой постановкой задачи.Тем самым можно непосредственно приступить к расчетам в соответствии с методом ДП. Эти расчеты проводятся в три этапа: предварительный этап, этап условной оптимизации и этап безусловной оптимизации. На предварительном этапе и на этапе условной оптимизации результаты расчетов заносятся во вспомогательную и основную таблицы той структуры, которая приведена в разд. 1,7 гл.1. На этапе безусловной оптимизации строится оптимальное решение задачи с использованием информации, содержащейся в основных таблицах.Предварительный этап. Данный этап решения задачи проводится в естественном порядке для i = 1, 2, 3 и не связан непосредственно с вычислением функций Беллмана Bi(xi). Заполняются только первая строка вспомогательной таблицы и четыре левых столбца основной таблицы.i = 1.Вспомогательная таблица заполняется соответственно начальному условию х0=0 и имеет видx 00B0(x0)Заполнение основной таблицы проводится следующим образом. Для заданного единственного допустимого значения х0=0 выбираем все возможные значения управления u1 (оно может принимать все целочисленные значения от 0 до 5 включительно) и заносим их во второй столбец таблицы. По формуле x1= x0+u1 (следующей из общей формулы xi = xi-1 + ui при i = 1) проводим расчет соответствующих значений переменной xi и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли z1 берем из столбца таблицы исходных данных задачи, отвечающего предприятию П1 для u1=1 по этой таблице z1 = 2, для u1= 2 по таблице z1 = 4 и т. д. Для u1=0 по условию задачи z1 = 0. Получаем следующую основную таблицу:x0u1x1z1B1(x1)z1 +B1B0(x0)00001122243364485510На этом заполнение левой части основной таблицы завершено причем таблица имеет только один строчный фрагмент. Переходим к следующему шагу.i = 2На втором шаге в первую строку вспомогательной таблицы внесем все значения переменной х1, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Получаем следующую вспомогательную таблицу:x 1012345B1(x1)Для заполнения основной таблицы на данном шаге будем, аналогично предшествующему шагу, последовательно выбирать все допустимые значения х1, внесенные во вспомогательную таблицу, и проводить соответствующие расчеты. Каждому значению х1 будет соответствовать свой строчный фрагмент основной таблицы; разделяются соседние строчные фрагменты горизонтальной линией.Для значения х1 = 0 выбираем все возможные значения управления u2 (оно может принимать все целочисленные значения от 0 до 5 включительно) и заносим их во второй столбец таблицы. По формуле x2= x1+u2 (следующей из общей формулы xi=xi-1 + ui при i=2) проводим расчет соответствующих значений переменной x2 и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли z2 берем из столбца таблицы исходных данных задачи, отвечающего предприятию П2: для и2 = 1 по этой таблице z2 = 1, для и2 = 2 по таблице z2= 2 и т. д. На этом завершается заполнение первого строчного фрагмента основной таблицы, соответствующего х1 = 0; этот фрагмент имеет следующий вид:x1u2x2z2B2(x2)z2 +B2B1(x1)000011122233644105512Для следующего допустимого значения х1 = 1 строим следующий строчный фрагмент. При этом управление и2 может принимать все целочисленные значения от 0 до 4 включительно (поскольку после выделения предприятию П1 средств в объеме х1 = 1 свободных средств остается 5-1=4). Проводя расчеты по тем же формулам, получим второй строчный фрагмент следующего вида:x1u2x2z2B2(x2)z2 +B2B1(x1)00001112223364410Аналогично формируются строчные фрагменты таблицы и для x1 = 2,3,4,5. Ясно, что с увеличением значения x1 множество допустимых значений управления u2 сужается, и для x1 = 5 допустимым является только одно значение u2 = 0. В результате получаем следующую основную таблицу:x1u2x2z2B2(x2)z2 +B2B1(x1)000011122233644105512101012123234645102020131242356303014125240401515050Построенная таблица разделена на 6 строчных фрагментов - столько же, сколько различных значений может принимать переменная х1. Переходим к следующему (последнему) шагу.i = 3На третьем шаге в первую строку вспомогательной таблицы внесем все значения переменной х2, рассчитанные на предшествующем шаге и фигурирующие в третьем столбце предыдущей основной таблицы. Эти значения многократно повторяются, но вносим их только по одному разу (за счет этого, в частности, сокращается объем вычислений). Получаем следующую вспомогательную таблицу:х2012345В2(х2)Для заполнения основной таблицы поступаем рассмотренным выше образом. Некоторая особенность данного последнего шага заключается в том, что поскольку сумма инвестируемых средств должна быть строго равна 5 усл. ден. ед., то для любого значения х2 управление u3 может принимать только одно значение, дополняющее х2 до 5. При этом всегда x3 = 5, а значения z3, как обычно, берутся из столбца таблицы исходных данных задачи, отвечающего предприятию П3. Соответственно основная таблица имеет компактный вид:х2u3x3z3B3(x3)z3 +B3B2(x2)0551014592358325641535050На этом предварительный этап решения задачи завершен. Подчеркнем, что вторые строки вспомогательных таблиц и три правых столбца основных таблиц остались незаполненными. Заполнение этих фрагментов таблиц будет проведено на следующем этапе условной оптимизации, к проведению которого мы приступаем.Этап условной оптимизации. Данный этап решения задачи непосредственно связан с вычислением функций Беллмана Bi(xi) и проводится в обратном порядке для i = 3,2,1. На данном этапе заполняются фрагменты таблиц, оставленные незаполненными на предыдущем предварительном этапе. На этом же этапе расставляются и знаки « ˅» указывающие те условно-оптимальные значения управления, на которых достигаются промежуточные максимумы — эти значения и составляют функцию ũ i(xi-1) , введенную в гл. 1.Для удобства изложения мы еще раз приведем все вспомогательные и основные таблицы в порядке их окончательного заполнения; этот прием носит чисто методический характер и призван облегчить понимание логики решения.