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

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

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

УДК 681.3.06

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

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

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

Введение

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

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

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

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

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

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

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

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

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

Рассмотрим управляемый процесс, в результате которого система S должна быть переведена из начального состояния s0 в конечное состояние sn. Предполагаем, что управление X можно разбить на n шагов и принимать решение на каждом шаге. Следовательно, управление можно представить как совокупность n пошаговых управлений: X=(X1, X2,… Xn).

Последовательность состояний системы s0, s1, …, sk-1, sk, sk+1,…snможно изобразить в виде следующей схемы:

S0
S1
Sk
Sn
X1
X2
Xk
Xk+1
Xn
Рис.1. Последовательность состояний системы

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

Общая постановка задачи динамического программирования - student2.ru (1)

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

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

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

Общая постановка задачи динамического программирования - student2.ru (2)

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

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

Общая постановка задачи динамического программирования - student2.ru (3)

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

Общая постановка задачи динамического программирования - student2.ru (4)

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

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

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

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

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

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

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

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

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

Общая постановка задачи динамического программирования - student2.ru (13)

где Общая постановка задачи динамического программирования - student2.ru – минимальная стоимость проезда от пункта j до конечного пункта Б.

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

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

k=4

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

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

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

Шаг k=3.

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

Б
Z4*(6)=10
Z4*(7)=8
Рис.6. Шаг k=3

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

Шаг k=2.

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

Z3*(4)=14
Z3*(5)=11
Z3*(3)=17
Рис.7. Шаг k=2
Б

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

Шаг k=1.

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

Z2*(1)=19
Z2*(2)=16
А
Б
Рис.8. Шаг k=1

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

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

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

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

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

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

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

– прибыль Общая постановка задачи динамического программирования - student2.ru предприятия k не зависит от вложения средств в другие предприятия;

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

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

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

Таблица 1

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

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

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

Общая постановка задачи динамического программирования - student2.ru (14)

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

Общая постановка задачи динамического программирования - student2.ru (15)

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

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

Процесс распределения средств Общая постановка задачи динамического программирования - student2.ru можно рассматривать как трехшаговый, номер шага совпадает с номером предприятия. Выбор переменных x1, x2, x3 – это выбор управления Общая постановка задачи динамического программирования - student2.ru соответственно на 1, 2 и 3 шаге. Конечное состояние процесса распределения Общая постановка задачи динамического программирования - student2.ru , когда все средства вложены в производство.

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

Рис.9. Схема распределения средств
Z1*(s0)
Z3*(s2)
Z2*(s1)
s0=5
Общая постановка задачи динамического программирования - student2.ru
Общая постановка задачи динамического программирования - student2.ru
Общая постановка задачи динамического программирования - student2.ru

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

Общая постановка задачи динамического программирования - student2.ru (16)

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

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

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

Общая постановка задачи динамического программирования - student2.ru (17)

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

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

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

Z3*(s2)=f3(s2)
Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
Рис.10. Распределение средств на шаге 3

При этом для возможных значений Общая постановка задачи динамического программирования - student2.ru получим:

Общая постановка задачи динамического программирования - student2.ru (18)

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

Z3*(s2)
Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
Рис.11. Распределение средств на шаге 2

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

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

Таблица 2

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

s1 x2 s2 Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
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
Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
Рис.12. Распределение средств на шаге 1

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

Таблица 3

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

s0 x1 s1 Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
0+22=22    
8+18=26
10+14=24    
12+10=22    
14+6=20    
16+0=16    

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

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

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

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

Запишем уравнения состояния и эффективность одного шага Общая постановка задачи динамического программирования - student2.ru :

Общая постановка задачи динамического программирования - student2.ru , (24)

Общая постановка задачи динамического программирования - student2.ru . (25)

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

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

Общая постановка задачи динамического программирования - student2.ru . (26)

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

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

Общая постановка задачи динамического программирования - student2.ru (27)

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

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

Общая постановка задачи динамического программирования - student2.ru (28)

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

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

Общая постановка задачи динамического программирования - student2.ru (29)

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

Таблица 4

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

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

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

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

Затраты на содержание оборудования в течение года зависят только от возраста t оборудования и равны Общая постановка задачи динамического программирования - student2.ru .

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

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

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

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

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

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

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

Общая постановка задачи динамического программирования - student2.ru (30)

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

Общая постановка задачи динамического программирования - student2.ru (31)

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

Общая постановка задачи динамического программирования - student2.ru (32)

При Общая постановка задачи динамического программирования - student2.ru вариант управления единственный, поэтому эффективность шага определяем по формуле

Общая постановка задачи динамического программирования - student2.ru . (33)

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

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

Общая постановка задачи динамического программирования - student2.ru (34)

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

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

Общая постановка задачи динамического программирования - student2.ru (35)

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

Общая постановка задачи динамического программирования - student2.ru (36)

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

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

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

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

На каждом векторе перемещения записываются соответствующие затраты Общая постановка задачи динамического программирования - student2.ru в соответствии с формулами (32).

k-1,t
k,t+1
k,1
Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
Рис.13. Фрагмент графической схемы решения

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

Рис.14. Разметка графа в задаче о замене оборудования  
-500
-1000
-125
-250
Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
t
k

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

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

Рис.15. Графическое решение задачи о замене оборудования
-500
-1000
-125
-250
2500
1900
1250
1050
650
100
Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru Общая постановка задачи динамического программирования - student2.ru
t
k
4800

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

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

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

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

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

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

Рис.16. Пример неединственности оптимального решения
-500
-1000
-125
-250
3500
2500
2000
1250
1000
500

Наши рекомендации