Общая постановка задачи динамического программирования

Лукиных, И. Г.

Л 841 Динамическое программирование в решении экономических задач. Учебно-методическое пособие для проведения практических занятий и самостоятельной работы: для студентов всех направлений, всех профилей подготовки всех форм обучения экономических факультетов/ И. Г. Лукиных. – Киров: ФГБОУ ВО «ВятГУ», 2017. – 48 с.

УДК 681.3.06

Учебно-методическое пособие содержит краткие теоретические
сведения об методе динамического программирования, примеры его использования при решении экономических задач, задания к практическим занятиям и для самостоятельной работы.

Тех. редактор

© ФГБОУ ВО «ВятГУ», 2017

Введение

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

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

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Ричардом Беллманом (1920-1984) для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953г. он уточнил это определение. Вклад Беллмана в динамическое программирование был увековечен в названии уравнений Беллмана, центрального результата теории динамического программирования.

Области применения метода динамического программирования:

- при разработке правил управления запасами, которые устанавливают момент пополнения запасов и размер пополняющего заказа,

- при распределении дефицитных капитальных вложений между возможными направлениями их использования,

- при разработке принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию,

- при составлении календарных планов ремонта оборудования и его замены и т.п.

Общая постановка задачи динамического программирования

Рассмотрим управляемый процесс, в результате которого система S должна быть переведена из начального состояния s₀ в конечное состояние s_n. Предполагаем, что управление X можно разбить на n шагов и принимать решение на каждом шаге. Следовательно, управление можно представить как совокупность n пошаговых управлений: X=(X₁, X₂,… X_n).

Последовательность состояний системы s₀, s₁, …, s_k-1, s_k, s_k+1,…s_nможно изобразить в виде следующей схемы:

S0

S1

Sk

Sn

X1

X2

Xk

Xk+1

Xn

…

…

Рис.1. Последовательность состояний системы

Целевая функция является показателем эффективности системы. Она зависит как от начального состояния системыs₀, так и от управления X:

(1)

Необходимо определить такое допустимое управление X, при котором целевая функция принимает максимальное (или минимальное) значение.

Основные предположения

Первое существенное предположение при решении многошаговых задач состоит в том, что состояние системы в конце каждого шага kзависит только от её состояния в начале шага и управления на данном шаге, и не зависит от того, каким образом система пришла к состоянию :

(2)

Уравнения (2) называютсяуравнениями состояний. Они выражают «отсутствие последействия», т. е. независимость состояния системы в конце каждого шага от состояний и управлений на всех предшествующих шагах.

Второе важное предположение состоит в том, что целевую функцию Z считают аддитивной функцией от показателя эффективности каждого шага:

(3)

Третье предположение заключается в том, что выбор управления на каждом шаге k зависит только от состояния системы к началу данного шага, не влияет на предшествующие шаги, т. е. в системе нет обратной связи:

(4)

Примеры решения задач динамического программирования

Рассмотрим применение метода динамического программирования на конкретных задачах.

Выбор оптимального маршрута

Постановка задачи.

Пусть известна схема возможных маршрутов движения от пункта А до пункта Б (рис.4). Схема представляет собой ориентированный граф, вершины которого соответствуют промежуточным пунктам, ребра – возможным вариантам перемещения между соседними пунктами.

А

Б

Рис.4. Схема маршрутов

Весь маршрут от пункта А до пункта Б можно разбить на n шагов. В данной схеме n=4.Состояния системы определяются следующим образом: , промежуточные состояния определяются номерами промежуточных пунктов .

Показателем эффективности каждого шага в зависимости от целей исследования может служить расстояние между двумя смежными пунктами i иj, стоимость проезда, затраты времени, топлива или иных ресурсов. Для определенности в данном примере в качестве показателя эффективности рассмотрим стоимость проезда между двумя смежными пунктами i и j. Управление в данной задаче – это выбор возможного перемещения на шаге k из пункта i в пункт j. Целевая функция определяет суммарную стоимость проезда от пункта А до пункта Б. Необходимо из всех возможных маршрутов выбрать оптимальный, чтобы общая стоимость проезда была минимальной.

Применительно к данной задаче уравнения Беллмана (10) соответствуют вычислению минимальной стоимости последующего пути из пункта i до пункта Б, начиная с шага k:

(13)

где – минимальная стоимость проезда от пункта j до конечного пункта Б.

Решение задачи.

Начинаем поиск оптимального маршрута с последнего шага (рис.5), локально-оптимальные решения каждого шага выделим жирной линией:

k=4

Б

Рис.5. Шаг k=4

Переходим к предыдущему шагу, определяем оптимальные решения на двух последних шагах (рис.6):

Шаг k=3.

Б

Z4*(6)=10

Z4*(7)=8

Рис.6. Шаг k=3

Переходим к предыдущему шагу, определяем оптимальные решения на трех последних шагах (рис.7):

Шаг k=2.

Z3*(4)=14

Z3*(5)=11

Z3*(3)=17

Рис.7. Шаг k=2

Б

Для первого шага получаем (рис.8):

Шаг k=1.

Z2*(1)=19

Z2*(2)=16

А

Б

Рис.8. Шаг k=1

Минимальная суммарная стоимость проездаот пункта А до пункта Б равна . В процессе решения получены две последовательности оптимальных решений и соответствующих состояний (пунктов), так как при k=2 существует 2 оптимальных дальнейших маршрута. На рис.8 оптимальные решения выделены непрерывными ломаными линиями от пункта А до пункта Б.

Первое оптимальное решение (маршрут А – 2 – 4 – 6 – Б):

.

Второе оптимальное решение (маршрут А – 2 – 5 – 7 – Б):

.

Постановка задачи.

Планируется деятельность трех предприятий на очередной год. Начальные средства s₀, которые следует распределить, составляют 5 усл. ед. Размеры вложения в каждое предприятие кратны 1 усл. ед. Средства x, выделенные предприятию k, приносят в конце года прибыль Функции заданы таблично (табл. 1). При решении подобных задач принято считать, что выполняются следующие предположения:

– прибыль предприятия k не зависит от вложения средств в другие предприятия;

– прибыль выражается в одних условных единицах;

– общая прибыль равна сумме прибылей, полученных от каждого предприятия.

Требуется определить, какое количество средств нужно выделить каждому предприятию, чтобы общая прибыль была наибольшей.

Таблица 1

Эффективность использования средств

x	f1(x)	f2(x)	f3(x)

Построим математическую модель задачи. Обозначим через x_k количество средств, выделенных предприятию k. Общая прибыль равна сумме прибылей предприятий:

(14)

Переменные x_k удовлетворяют следующим ограничениям:

(15)

Требуется найти переменные x₁, x₂, x₃, удовлетворяющие системе ограничений (15), при которых функция (14) достигает максимума.

Особенность модели состоит в том, что хотя ограничения линейные и переменные целочисленные, методы целочисленного линейного программирования применять нельзя, так как функции f_k(x) заданы таблично.

Процесс распределения средств можно рассматривать как трехшаговый, номер шага совпадает с номером предприятия. Выбор переменных x₁, x₂, x₃ – это выбор управления соответственно на 1, 2 и 3 шаге. Конечное состояние процесса распределения , когда все средства вложены в производство.

Графически схема распределения показана на рис. 9.

Рис.9. Схема распределения средств

Z1*(s0)

Z3*(s2)

Z2*(s1)

s0=5

Уравнения состояний имеют вид:

(16)

где s_k – параметр состояния, количество средств, оставшихся после k-го шага, т. е. эти средства остается распределить между (3 – k) оставшимися предприятиями.

Рассмотрим функцию – условную оптимальную прибыль, полученную от предприятий k, (k + 1), …, 3, если между ними оптимальным образом распределялись средства . Допустимые управления на шаге k удовлетворяют условию: .

Уравнения, связывающие оптимальную прибыль на каждом шаге, имеют вид:

(17)

Последовательно решаем уравнения, проводя условную оптимизацию каждого шага.

Решение задачи.

Шаг k=3. В табл. 1 прибыль монотонно возрастает, поэтому все средства, оставшиеся к третьему шагу, следует вложить в предприятие 3 (рис.10).

Z3*(s2)=f3(s2)

Рис.10. Распределение средств на шаге 3

При этом для возможных значений получим:

(18)

Шаг k=2.Делаем все предположения относительно остатка средств ко второму шагу, т. е. после выбора значения величина может принимать значения 0, 1, 2, 3, 4, 5. В зависимости от этого выбираем , находим и сравниваем для разных при фиксированном значения суммы .

Z3*(s2)

Рис.11. Распределение средств на шаге 2

Для каждого наибольшее из этих значений – это условная оптимальная прибыль, получаемая при оптимальном распределении средств между 2-м и 3-м предприятиями (рис.11).

Вычисления записаны в таблице 2. Для каждого значения оптимальные значения и записаны в графах 5 и 6.

Таблица 2

Оптимизация распределения средств при k=2

s1	x2	s2
			0+4=4
		6+0=6
			0+8=8
		6+4=10
		9+0=9
			0+12=12
		6+8=14
		9+4=13
		12+0=12
			0+16=16
		6+12=18
		9+8=17
		12+4=16
		15+0=15
			0+20=20
		6+16=22
		9+12=21
		12+8=20
		15+4=19
		18+0=18

Шаг k=1.Графическое представление шага представлено на рисунке 12. Условная оптимизация проведена в таблице 3.

Z3*(s2)

Z2*(s1)

s0=5

Рис.12. Распределение средств на шаге 1

Например, если , то . Прибыль, полученная от трех предприятий при условии, что 5 единиц средств будут распределены оптимально между оставшимися двумя предприятиями, равна . Значение взято из столбца 5 табл. 2 при . Если , то . Суммарная прибыль при условии оптимального распределения средств равна . Значение взято из исходных данных (табл. 1), значение – из столбца 5 табл. 2 при . Аналогично вычислены остальные значения столбца 4 табл. 3.

Таблица 3

Оптимизация распределения средств при k=1

s0	x1	s1
			0+22=22
		8+18=26
		10+14=24
		12+10=22
		14+6=20
		16+0=16

Оптимальное решение рассматриваемой задачи при выделено в таблице 3 жирным шрифтом. Максимум суммарной прибыли получаем при условии, что первому предприятию выделяется усл. ед. и между 2 и 3 предприятиями распределяются 4 усл. ед. средств. Далее оптимальный вариант распределения находим из табл. 2 при : усл. ед., усл. ед.

Достоинством метода является возможность изменения числа шагов (предприятий), проведение анализа решения на чувствительность к изменению , безразличие метода к способу задания функций .

Постановка задачи.

Пусть . Прибыль, не возвращаемая в производство . Средства, возвращаемые для дальнейшего распределения, определяются функциями .

Запишем уравнения состояния и эффективность одного шага :

, (24)

. (25)

Решение задачи.

Начинаем с шага . Подставляем в формулу (22) значение эффективности для этого шага в соответствии с формулой (25):

. (26)

Функция является линейной возрастающей функцией аргумента и достигает максимума при . Т. е. на этом шаге все средства должны быть выделены предприятию I.

Переходим к шагу . Записываем уравнение Беллмана (23) на этом шаге с учетом формулы (25), локального максимума и уравнения состояния :

(27)

Функция достигает максимума при (все средства должны быть выделены предприятию I).

Переходим к шагу . Записываем уравнение Беллмана (23) на этом шаге с учетом формулы (25), локального максимума и уравнения состояния :

(28)

Функция является линейной убывающей функцией аргумента и достигает максимума при . Т. е. в начале второго года все средства должны быть выделены предприятию II.

Переходим к шагу . Записываем уравнение Беллмана (23) на этом шаге с учетом формулы (25), локального максимума и уравнения состояния :

(29)

Функция достигает максимума при . Т. е. в начале первого года все средства должны быть выделены предприятию II. Учитывая заданное значение , получаем . Запишем полученные результаты распределения средств в таблицу (см. табл.4).

Таблица 4

Оптимальное распределения средств

Год (шаг)k	Средства в начале года	Распределение средств	Прибыль, не возвращаемая в производство

Постановка задачи.

Оборудование эксплуатируется в течение 4 лет, после чего продается. В начале каждого года можно либо продолжать эксплуатацию имеющегося оборудования, либо заменить оборудование на новое. Пусть стоимость нового оборудования постоянна и не зависит от года покупки, ликвидная стоимость зависит от возраста t продаваемого оборудования (при его замене на новое) и равна .

Затраты на содержание оборудования в течение года зависят только от возраста t оборудования и равны .

Определить оптимальную стратегию эксплуатации оборудования, чтобы суммарные затраты на эксплуатацию с учетом начальной покупки и заключительной продажи были минимальны.

Решение задачи.

Весь период эксплуатации разобьем на 4 шага. Таким образом шаг k принимает значения 1, 2, 3, 4. Параметр состояния системы на каждом шаге определяется возрастом оборудования.

В начале первого года оборудование новое, и параметр состояния принимает единственно возможное значение . В дальнейшем, к началу шага параметр состояния равен возрасту оборудования , где .

При выборе управления в конце шага возраст увеличится на 1, т. е. значение параметра состояния .

При управлении в начале шага k оборудование возраста t продается и заменяется новым, т. е. его возраст становится равен нулю: . Тогда через год эксплуатации (в конце шага k) параметр состояния .

Таким образом, уравнения состояния имеют вид:

(30)

Показатель эффективности шага также зависит от выбора управления для каждого возможного значения :

(31)

С учетом исходных данных задачи имеем:

(32)

При вариант управления единственный, поэтому эффективность шага определяем по формуле

. (33)

Далее выполняем пошаговое решение задачи в соответствии с общим алгоритмом решения задач динамического программирования.

Минимизируем условные оптимальные затраты на последнем шаге при k=4 для всех возможных значений .

(34)

В уравнениях Беллмана на этом шаге учтена заключительная продажа оборудования в конце 4-го шага по ликвидной стоимости .

Условные оптимальные затраты на остальных шагах k=3,2,1 вычисляем последовательно по формулам:

(35)

В итоге получим оптимальное значение целевой функции всей задачи:

(36)

Геометрическое решение

Решение задачи о ремонте и замене оборудования удобно проводить на графе. В этом случае задача становится похожа на задачу поиска минимального маршрута.

Граф задачи можно составить из отдельных фрагментов (рис.13), каждый из которых отображает возможный переход из состояния в состояние . По оси абсцисс будем откладывать номер шага k, по оси ординат – возраст оборудования t.

«Точка» на плоскости соответствует началу шага k эксплуатации оборудования возраста t (на схеме «точку» изображаем кружком). Перемещение к концу шага происходит в зависимости от выбранного в начале шага управления либо в «точку» при управлении , либо в «точку» при управлении .

На каждом векторе перемещения записываются соответствующие затраты в соответствии с формулами (32).

k-1,t

k,t+1

k,1

Рис.13. Фрагмент графической схемы решения

Рисуем всю графическую схему (рис.14), состоящую из четырех шагов, с разметкой затрат . Затраты вычисляем по формулам (32) и (33). Внутри кружков в конце последнего шага записываем ликвидную стоимость для каждого возможного возраста оборудования со знаком «–» (рис. 14).

Рис.14. Разметка графа в задаче о замене оборудования

-500

-1000

-125

-250

t

k

Графическая схема на рис.14 похожа на схему маршрутов между пунктами А и Б на рис.4. Отличие лишь в том, что вместо одного конечного пункта Б в данной схеме имеем 4 возможных конечных пункта , , , . При этом заранее неизвестно, в какой из них ведет минимальный маршрут. Начальное состояние определено однозначно.

При графическом решении данной задачи условные оптимальные затраты на каждом шаге, вычисляемые по формулам (35), удобно записывать в соответствующих вершинах графа (кружках). Соответствующие локальные оптимальные управления для каждого состояния системы (векторы) для наглядности выделяем двойной линией. Результат решения показан на рис.15.

Рис.15. Графическое решение задачи о замене оборудования

-500

-1000

-125

-250

2500

1900

1250

1050

650

100

t

k

4800

Минимальное значение целевой функции . Оптимальное управление соответствует непрерывной ломаной линии, составленной из локальных оптимальных управлений на каждом шаге:

, т. е. оборудование следует заменить на новое один раз через 2 года эксплуатации.

Графический метод решения задачи об оптимальных сроках замены оборудования достаточно просто и наглядно позволяет найти все варианты в случае неединственности оптимального решения.

Изменим в условии задачи функцию затрат на содержание оборудования в течение года. Пусть .

Графическая модель задачи и её решение показаны на рис.16. Минимальное значение целевой функции . Задача имеет пять оптимальных вариантов управления:

Рис.16. Пример неединственности оптимального решения

-500

-1000

-125

-250

3500

2500

2000

1250

1000

500