Метод динамического программирования. Функциональные уравнения Беллмана

Лекция. Метод динамического программирования. Вопросы: 1. Основные понятия. Общая постановка задачи ДП. 2. Принцип оптимальности. Функциональные уравнения Беллмана. 3. Задача оптимального распределения ресурсов. 4. Задача о замене. 5. Задача управления производством и запасами. 1.Основные понятия. Общая постановка задачи динамического программирования. Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разбит на отдельные этапы, шаги. Такие операции называются многошаговыми. Многие экономические процессы расчленяются на шаги естественным образом. Это процессы планирования и управления, развиваемые во времени. Естественным шагом может быть год, квартал, месяц и т.д. Т.о., если управление сводится к однократному принятию решения, то соответствующая задача называется одноэтапной или одношаговой. Ранее решаемые задачи линейного и нелинейного программирования – примеры подобных задач. Если управление требует некоторой последовательности принятых решений, то такая задача называется многоэтапной или многошаговой. Рассмотрим некоторую управляемую систему, характеризующуюся определенным набором параметров, задающих ее состояния. Система под влиянием управления переходит из начального состояния в конечное. Введем обозначения. 1. xi – многомерный вектор, компоненты которого определяют состояние системы на i-том шаге. Дальнейшее изменение состояния зависит только от данного состояния и не зависит от того, каким путем система перешла в него (процесс без последствия). 2. На каждом шаге выбирается одно решение, управление ui , под действием которого система переходит из предыдущего состояния xi-1 в новое xi. Это новое состояние является функцией состояния на начало шага xi-1 и принятого в начале решения ui , т.е. xi = xi ( xi-1 , ui ). 3. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага и принятого решения. Fi – приращение целевой функции задачи в результате i-того шага, аналогично, Fi = Fi ( xi-1 , ui ). Тогда значение целевой функции при переходе системы из начального состояния в конечное за n шагов . 4. На векторы состояния хi и управления ui могут быть наложены ограничения, объединение которых составляет область допустимых решений u U. 5. Требуется найти такое допустимое управление u* = (u1* ,…, un*) (для каждого шага), чтобы получить экстремальное значение функции цели F* за все n шагов. Любая последовательность действий для каждого шага, переводящая систему из начального состояния в конечное, называется стратегией управления. Допустимая стратегия управления, доставляющая функции цели экстремальное значение, называется оптимальной. 2. Принцип оптимальности. Функциональные уравнения Беллмана. Метод динамического программирования состоит в том, что оптимальное управление строится постепенно, шаг за шагом. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, т.к. управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. В основе метода динамического программирования лежит принцип оптимальности, сформулированный Беллманом. Принцип оптимальности: если некоторая последовательность решений оптимальна, то на любом шаге последующие решения образуют оптимальную стратегию по отношению к результату предыдущих решений. Другими словами, каково бы не было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге (проигрыш) плюс оптимальный выигрыш (проигрыш) на всех последующих шагах был бы максимальным (минимальным). На основе принципа оптимальности Беллмана строится схема решения многошаговой задачи, состоящая из 2-х частей: 1) Обратный ход: от последнего шага к первому получают множество возможных оптимальных («условно-оптимальных») управлений. 2) Прямой ход: от известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом. Оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага. Чтобы можно было использовать принцип оптимальности практически, необходимо записать его математически. Обозначим через z1(xn-1), z2(xn-2),…, zn(x0) условно-оптимальные значения приращений целевой функции на последнем шаге, двух последних,…, на всей последовательности шагов, соответственно. Тогда для последнего шага: z1(xn-1) = (min) {Fn(xn-1, un)}, где un – множество допустимых (возможных) управлений на n-ом шаге, xn-1 – возможные состояния системы перед n-ым шагом. Для двух последних шагов: z2(xn-2) = (min) {Fn-1(xn-2, un-1) + z1(xn-1)}. Для k последних шагов: zk(xn-k) = (min) {Fn-k+1(xn-k, un-k+1) + zk-1(xn-k+1)}. Для всех n шагов: zn(x0) = (min) {F1(x0, u1) + zn-1(x1)}. Полученные рекуррентные соотношения называют функциональными уравнениями Беллмана. При этом согласно определению zn(x0) = F*. 3. Задача оптимального распределения ресурсов. Постановка задачи. Задачи на оптимальное распределение ресурса, который можно использовать различным образом, возникают при разработке оперативных и перспективных планов особенно часто. К ним относятся задачи о распределении средств на приобретение оборудования, закупку сырья и найм специалистов; задачи о распределении товара по торговым предприятиям и складам; задачи по определению последовательности пропорций между продукцией с/х производства, предназначенной для реализации и воспроизводства и т.д. Рассмотрим задачу оптимального распределения заданного объема капиталовложений в несколько предприятий. Пусть на реконструкцию и модернизацию 4-х своих филиалов фирма имеет возможность выделить 700 млн. руб. Ожидаемый прирост прибыли зависит как от финансируемого филиала, так и от объема этого финансирования. Однако, прирост прибыли в отдельно взятом филиале не зависит от вложенных средств в другие филиалы, а общая прибыль фирмы равна сумме всех приростов по филиалам. Следует определить оптимальное распределение капиталовложений между филиалами, максимизирующее общий прирост прибыли фирмы. В данном случае речь идет об однократном распределении средств, и поэтому задача сама по себе не является динамической. Однако, ее можно наиболее просто решить как ‌«многошаговую», если объекты капиталовложений (филиалы) включать в рассмотрение последовательно, т.е. на каждом шаге к рассмотренным добавлять следующий. При таком подходе можно использовать функциональные уравнения Беллмана. Для их решения в табулированном виде общий объем капиталовложений разбивается на N интервалов с шагом (для нашей задачи положим = 100 млн. руб.). Т.е. значения функций, входящих в уравнения Беллмана, будут определяться только в точках, кратных (в нашем примере в точках 0, 100, 200,…,700). Пусть ожидаемый прирост прибыли филиалов при соответствующих капиталовложениях задан таблицей. Предприятие Прирост выпуска продукции предприятиями (X) 100 200 300 400 500 600 700 1 75 90 100 108 113 115 117 2 85 100 111 118 124 129 132 3 42 58 71 80 89 95 100 4 28 45 66 78 90 102 113 С =700 – общий объем распределяемых средств; х - объем средств, выделяемых филиалам (на каждом шаге), 0≤ х ≤C. Fi(xi) – ожидаемый прирост i-той фирмы при выделении ей хi средств. Тогда целевая функция F = F1(x1) + F2(x2) + F3(x3) + F4(x4) → max при ограничении x1 + x2 + x3 + x4 = C, xi ≥ 0, i = . Схема решения. 1. Введем последовательность функций: z1(x) – max прибыль фирмы, если x средств выделить одному 1-му филиалу; z2(x) – max прибыль фирмы, если x средств распределить между 1-м и 2-м филиалами; z3(x) – max прибыль фирмы, если х средств распределить между 3-м и двумя первыми филиалами; z4(x) – max прибыль фирмы, при распределении x средств между всеми 4-мя филиалами. Очевидно, что z4(C) = max F = F*, a zi(0) = 0. 2. «Обратный ход». Рассмотрим финансирование только 1-го филиала, тогда по определению z1(x) = F1(x). (1) Пусть теперь средства в объеме x распределяются между 1-м и 2-м филиалами: 2-му в объеме x2, тогда х – х2 = х1 выделяется 1-му. Общая прибыль двух филиалов z2(x) = (F2(x2) + z1(x – x2)). (2) Теперь включим в рассмотрение дополнительно 3-й филиал: из общей суммы х выделим 3-му филиалу х3, тогда остальная часть х – х3 оптимальным образом распределяется между двумя первыми z3(x) = (F3(x3) + z2(x – x3)). (3) Наконец, по аналогии находим z4(x) = (F4(x4) + z3(x – x4)). (4) 3. «Прямой ход». Функциональные уравнения Беллмана (1) – (4) позволяют рассчитать значения zi и Fi для всех возможных х. Среди них находим z4(C) = F* и оптимальное x4* такое, что F4(x4*) = F4*, после чего результаты вычислений просматриваются в обратном порядке. Зная x4*, находим С–х4* - объем финансирования остальных трех филиалов, а следовательно, и F3* и х3*, и т.д. до нахождения х1* и F1* = F1(x1*). Пример. Предприятие Прирост выпуска продукции предприятиями (X) 100 200 300 400 500 600 700 1 75 90 100 108 113 115 117 2 85 100 111 118 124 129 132 3 42 58 71 80 89 95 100 4 28 45 66 78 90 102 113 Решение 1. По функциональным уравнениям z1(x) = F1(x) z2(x) = (F2(x2) + z1(x – x2)) z3(x) = (F3(x3) + z2(x – x3)) z4(x) = (F4(x4) + z3(x – x4)) выполняем обратный ход x z1 = F1 F2 z2 F3 z3 F4 z4 100 75 85 85 42 85 28 85 200 90 100 160 58 160 45 160 300 100 111 175 71 202 66 202 400 108 118 190 80 218 78 230 500 113 124 201 89 233 90 247 600 115 129 211 95 248 102 268 700 117 132 219 100 261 113 284 2. Прямой ход z4(700) = F* = 284; z4(700) = F4(300) + z3(400) z3(400) = F3(200) + z2(200) z2(200) = F2(100) + z1(100) и . Ответ: F* = 284, х*= (100; 100; 200; 300) 4. Задача о замене. Постановка задачи. Оборудование со временем изнашивается и стареет морально, падает его производительность, растут издержки на ремонт. Поэтому на каком-то этапе его эксплуатация становится менее выгодной, чем замена на новое. Возникает задача определения оптимальной стратегии замены оборудования в рассматриваемый временной промежуток – плановый период (п/п) с тем, чтобы суммарная прибыль за этот период была оптимальной. Введем обозначения. r(t) – стоимость продукции, производимой за год на оборудовании возраста t; s(t) – остаточная стоимость оборудования возраста t; u(t) – эксплуатационные издержки за год оборудования возраста t; p – цена нового оборудования, которым можно заменить устаревшее: n – число лет в рассматриваемом п/п. Для дискретности решения задачи возраст оборудования t будем отсчитывать с интервалом 1 год. Управление составляют два возможных решения на каждом этапе (в начале каждого года): «сохранение» – продолжение эксплуатации имеющегося оборудования; «замена» – реализация старого оборудования по остаточной стоимости и приобретение нового по цене p. Целевая функция – суммарная прибыль за п/п F→max. Ограничения определяются критерием замены оборудования: прибыль при дальнейшей эксплуатации старого меньше прибыли после его замены с учетом всех издержек. Если прибыль от нового оборудования равна прибыли при старом, то старое сохраняется еще на год, т.к. оно уже досконально изучено. Схема решения. Задача решается методом ДП на основе принципа оптимальности Беллмана. В процессе «обратного хода» рассматриваются этапы – временные шаги от конца п/п к его началу. Введем последовательность функций: zi(t), i = – максимальная прибыль за последние i лет п/п. Очевидно, что zn(t0) = max F = F*, где t0 – возраст оборудования в начале п/п. Итак, сначала рассматриваем только последний n-ый год п/п, i = 1. Пусть в начале этого года, когда оборудование имеет возраст t лет, выбирается одно из управлений: 1) сохранение оборудования на n-ый год, тогда прибыль за оставшийся год п/п составит r(t) – u(t); 2) замена новым, продажа старого по остаточной стоимости, тогда прибыль составит s(t) – p + r(0) – u(0), где r(0) – стоимость продукции, на новом оборудовании за 1-й год его эксплуатации, u(0) – эксплуатационные издержки нового оборудования за 1-й год. Определяем оптимальное управление, исходя из критерия замены: - если s(t) – p + r(0) – u(0) ≤ r(t) – u (t), то «сохранить», - если s(t) – p + r(0) – u(0) > r(t) – u(t), то «заменить». z1(t) = max Теперь включаем в рассмотрение предпоследний шаг, (n – 1)-й год, i = 2 и установим прибыль за два последних года z2 (t). Пусть в начале (n – 1)-го года возраст оборудования t, и было принято решение о его сохранении. Тогда прибыль к концу года зависит r (t) – u (t). При этом на начало n-го года оборудование уже будет иметь возраст t+1, следовательно, в последнем году оно даст прибыль z1(t+1), а общая прибыль за два последних года составит r (t) – u (t) + z1(t+1). Если же в начале (n-1)-го года выбрано управление ”замена”, то прибыль за два последних года составит s (t) – p + r (0) – u (0) + z1(1), следовательно, z2(t) = max Аналогично для i последних лет: zi(t) = max Дойдя до последнего шага (i = n), попадаем в начало п/п, где t известно: t = t0, и, следовательно, можно начать ”прямой ход”. Задавая t0 и длительность п/п, находим F* = zn(t0) и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним. Пример. Продолжительность планового периода составляет N=8 лет t 1 2 3 4 5 6 7 8 t0=3, S=2, p=10 r(t) 26 25 25 24 24 23 22 21 20 u(t) 15 15 16 17 18 18 19 19 20 Решение 1. Обратный ход выполняем по функциональным уравнениям. t 1 2 3 4 5 6 7 8 11 10 9 7 6 5 3 2 Z \ t 1 2 3 4 5 6 7 8 11 10 9 7 6 5 3 3 3 3 21 19 16 13 13 13 13 13 13 13 30 26 22 22 22 22 22 22 22 22 37 32 31 29 29 29 29 29 29 29 43 41 38 36 35 35 35 35 35 35 52 48 45 44 44 44 44 44 44 44 59 55 53 51 51 51 51 51 51 51 66 63 60 58 58 58 58 58 58 58 сохранение замена 2. Прямой ход F* = z8(t0) = z8(3) = 58; Сохр зам сохр сохр сохр зам сохр сохр 1 2 3 4 5 6 7 8 Ответ: , замена во 2-й и 6-й годы. Пояснения к таблице: Для заполнения расчетной таблицы можно использовать следующий алгоритм. 1. Определить φ (t) = r(t) – u(t), m1 = S(t) – p + φ(0): - если m1 = const, то справа к таблице прибавляется дополнительный столбец mi; - если m1 = m1(t), то над каждой строкой zi(t) вводится дополнительная строка mi = mi(t) (или mi(t) вписывается в клетки значений zi(t) как тарифы транспортной задачи). 2. Заполнить строку z1(t), переписав из таблицы данных соответствующие значения φ(t) ≥ m1, все значения φ(t) < m1 заменить на m1. 3. Начиная с индекса i = 2, расчет по строкам производится в следующей последовательности: а) вычислить mi = m1 + zi-1(1), где zi-1(1) берется из уже заполненной строки; б) вычислить zi(t) = z1(t) + zi-1(t+1), где сумма и слагаемые образуют треугольник, у которого одна из вершин всегда в первой строке над искомым значением, а 2-ая - в последней заполненной строке следующего столбца. Получаемые значения zi(t) ≥ mi вносить в соответствующие клетки строки; начиная с первого zi(t) < mi, оставшиеся клетки заполнить значением mi; в) клетки с первым значением zi(t) < mi в процессе заполнения таблицы отделить от расположенных в строке левее разделительной границей смены управления; г) если таблица не заполнена до последней строки, перейти к п. а) и выполнить расчет для следующего значения индекса i. Замечания: 1. Для задачи об оптимальном распределении капиталовложений по полученной расчетной таблице можно получить стратегию вложения средств, например, только в первые 3 филиала, исключив из рассмотрения 4-й, или, например, для суммы в 150 млн. руб. (а не 200 ) между 4-мя филиалами, или только 3-мя первыми и т.д. Для задачи о замене по расчетной таблице можно получить решение на любой п/п длительностью, не превосходящей исходный. Это так называемый «принцип погружения» метода динамического программирования. 2. Решенную задачу о замене оборудования можно усложнить, например, допуская замену не новым оборудованием, а уже проработавшим некоторое время. При этом имеется три возможных управления: сохранить старое, купить новое, купить не новое. 5. Задача управления производством и запасами Предприятие производит партиями некоторые изделия. Оно получило заказы на n месяцев. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение. Обозначим: 1) xj – число изделий, производимых в j-м месяце; 2) yj - величина запаса к началу j-го месяца (Это число не содержит изделий, производимых в j-й месяц, величина запаса к началу 1-го месяца (y1) и к концу последнего (yn+1) заданы); 3) dj – число изделий, которые должны быть отгружены в j-й месяц; 4) - функция затрат на производство xj изделий в j-м месяце (может иметь и другой вид); 5) hj – затраты на хранение единицы запаса, переходящей из месяца j в месяц (j+1); 6) - функция затрат на производство и хранение в j-м месяце. Задача состоит в определении плана производства (х1,х2,…,хn), компоненты которого удовлетворяют условиям материального баланса xj +yj –dj = yj+1 и минимизируют суммарные затраты за весь период . По смыслу , ,. Заметим, что: 1) для любого месяца j величина запаса к концу месяца должна удовлетворять ограничениям , то есть объем производимой продукции xj в j-м месяце может быть настолько велик, что запас yj+1 удовлетворяет спрос на всех последующих месяцах, но не имеет смысла иметь yj+1 больше суммарного спроса всех последующих месяцев; 2) из балансового уравнения получим . Если учесть, что xj и yj должны быть целыми и неотрицательными, то имеем задачу целочисленного нелинейного программирования. Составим функциональные уравнения. Пусть Fk(yk+1) - минимальные затраты за первые k месяцев. Для k = 1: при и . На начальном этапе при фиксированном значении y1 исходного запаса каждому значению y2 отвечает только одно значение x1. Для k 2: при , и . Применив процедуру динамического программирования, на последнем шаге k = n определяется значение xn* оптимального решения, а остальные компоненты определяются в результате прямого хода по формуле . Пример. d1 d2 d3 a b c h1 h2 y1 y4 5 4 3 4 4 4 5 2 Решение Обратный ход 1. k=1; ; ; x 1 2 3 4 5 6 7 8 9 10 4 12 28 52 84 124 172 228 292 364 444 1 2 3 4 5 6 7 3 4 5 6 7 8 9 10 52 89 134 187 248 317 394 479 2. k=2; ; ; ; ; ; 1 2 3 4 4 3 2 1 252 199 162 141 136 ; ; 1 2 3 4 5 5 4 3 2 1 321 260 215 186 173 176 ; ; 1 2 3 4 5 6 6 5 4 3 2 1 398 329 276 239 218 213 224 ; ; 1 2 3 4 5 6 7 7 6 5 4 3 2 1 483 406 345 300 271 258 261 280 1 2 3 4 4 5 5 136 173 213 258 3. k=3; ; ; ; 1 2 3 3 2 1 262 225 201 188 Прямой ход 1. Из последней таблицы 2. По балансовому уравнению xj +yj –dj = yj+1 последовательно определяются: по таблице по таблице и . Проверка: 1) 3 + 4 + 3 + 2 = 5 + 4 + 3; 2) 52 + 84 + 52 = 188. Ответ: и .