Метод динамического программирования

Метод динамического программирования – это инструмент, позволяющий быстро находить оптимальное решение в задачах математического программирования с дискретным множеством допустимых решений, т.е. в ситуациях, когда имеется некоторое количество различных вариантов поведения, приносящих различные результаты, среди которых необходимо выбрать наилучший. Любая задача такого рода может быть решена путем перебора всех возможных вариантов и выбора среди них наилучшего. Однако часто такой перебор очень затруднителен. В этих случаях процесс принятия оптимального решения может быть разбит на шаги и исследован методом динамического программирования. В основе вычислительных алгоритмов динамического программирования лежит следующий принцип оптимальности, сформулированный Р. Беллманом.

Принцип оптимальности.

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния s и переменную управления или решения х. Переменная s определяет, в каких состояниях может оказаться система на данном k -ом шаге. В зависимости от s на этом шаге можно применить некоторые решения, которые характеризуются переменной х_k. Применение решения х на k -ом шаге приносит некоторый результат u_k(s, x_k) и переводит систему в некоторое состояние s^'(s, x_k). Для каждого возможного состояния на k -ом шаге среди всех возможных решений выбирается оптимальное решение х_k^*, такое, чтобы результат, который достигается за шаги с k -ого по n- ый оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана f_k(s) и зависит от номера шага k и состояния системы s.

Итак решение задачи распадается на два этапа. На первом этапе, он называется условной оптимизацией, отыскивается функция Беллмана и оптимальные решения для всех возможных состояний на каждом шаге, начиная с последнего. На последнем, n -ом шаге найти оптимальное решение х_n^* и значение функции Беллмана f_n(s) совсем не сложно (f_n(s)=optimum , где optimum (это максимум или минимум) ищется по всем возможным значениям х_n). Дальнейшие же вычисления производятся согласно уравнению Беллмана – рекуррентному уравнению, связывающему функцию Беллмана на каждом шаге с функцией Беллмана, вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид

F_k(s)=optimum

Этот максимум или минимум отыскивается по всем возможным для данных k и s значениям переменной решения х_k.

После того, как функция Беллмана и соответствующие оптимальные решения найдены для всех шагов с n-ого по первый, производится второй этап решения задачи, который называется безусловной оптимизацией. Пользуясь тем, что на первом шаге (k =1) состояние системы нам известно – это ее начальное состояние s₀ – можно найти оптимальный результат за все n шагов (это f₁(s₀)) и, кроме того, оптимальное решение на первом шаге х₁^*, которое этот результат доставляет. После применения этого решения система перейдет в некоторое новое состояние s^'(s, x₁^*), зная которое можно, пользуясь результатами, полученными на этапе условной оптимизации, найти оптимальное решений на втором шаге х₂^*, и так далее вплоть до n -ого шага.

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

Пример 8. Пусть имеются четыре предприятия, между которыми распределяется 100 тыс. ден. ед. (инвестирование предприятий). Денежные средства распределяются суммами кратными 20 тыс. ден. ед. Значения прибыли предприятия в зависимости от выделенной суммы х приведены в таблице 12. Составить план распределения средств, максимизирующий общий прирост выпуска продукции.

Таблица 12

Средства х, тыс. ден. ед.	Предприятие
№1	№2	№3	№4
Прирост выпуска продукции на предприятиях, , тыс. ден. ед.

Решение:

I этап. Условная оптимизация.

Очевидно, что данная задача может быть решена просто перебором всех возможных вариантов распределения 100 тыс.ден.ед. по 4 предприятиям (всевозможных вариантов в данном примере не так уж и много). Однако попытаемся решить её более эффективным способом. Разобьём процесс оптимизации на 4 шага, и будем на каждом k -ом шаге оптимизировать инвестирование не всех предприятий сразу, а только предприятий с k -ого по 4 -ое. При этом, естественно, будем считать, что в остальные предприятия (с 1 -ого по (k-1) -ое) тоже вкладываются некоторые средства, и потому на инвестирование предприятий с k -ого по 4 -ое остаются не все средства, а некоторая сумма с_k≤100 тыс.ден.ед. Эта величина и будет являться переменной состояния системы. Переменной управления на k -ом шаге назовем величину х_k средств, вкладываемых в k -ое предприятие. В качестве функционального уравнения Беллмана f_k(с_k) на k -ом шаге в этой задаче можно выбрать максимально возможную прибыль, которую можно получить с предприятий с k -ого по 4 -ое при условии, что на их инвестирование осталось с_k средств. Очевидно, что при вложении в k -ое предприятие х_k средств, мы получим прибыль g_k(x_k), а система к (k+1)- ому шагу перейдет в состояние с_k+1=c_k-x_k, т.е. на инвестирование предприятий с (k+1)- ого до 4 -ого останется с_k+1 средств.

Итак, на первом шаге условной оптимизации при k = 4 функция Беллмана представляет собой не что иное, как прибыль только с 4-ого предприятия. При этом на его инвестирование может остаться количество средств с_k, 0 с_k 100 тыс.ден.ед. (в дальнейшем просто 100) Очевидно, чтобы получить максимум прибыли с последнего предприятия, надо вложить в него все эти средства, т.е. f₄(с₄)= g₄(с₄), x_k*=с_k.

Таблица 13

x4   с4
		-	-	-	-	-
	-		-	-	-	-
	-	-		-	-	-
	-	-	-		-	-
	-	-	-	-		-
	-	-	-	-	-

На каждом из последующих шагом для вычисления функции Беллмана приходится использовать результаты, полученные на предыдущем шаге. Пусть на втором шаге для инвестирования предприятия с третьего по четвертое осталось с₃ средств (0 с₃ 100). Тогда от вложения в третье предприятие х₃ средств будет получена прибыль g₃(x₃), а на инвестирование четвертого предприятия останется с₃₊₁=с₄=c₃-x₃ средств. Максимально возможная прибыль, которая может быть получена с этих двух предприятий будет равна

Таблица 14

x3   с3
	0+0	-	-	-	-	-
	0+16	11+0	-	-	-	-
	0+37	11+16	36+0	-	-	-
	0+46	11+37	36+16	45+0	-	-
	0+63	11+46	36+37	45+16	60+0	-
	0+80	11+63	36+46	45+37	60+16	77+0		40, 60

Максимум этого выражения f₃^*(c₃) достигается при некотором значении х₃^*, которое и является оптимальным решением на втором шаге для состояния системы с₃.

На третьем шаге для инвестирования предприятия со второго по четвертое осталось с₂ средств (0 с₂ 100). Тогда от вложения во второе предприятие х₂ средств будет получена прибыль g₂(x₂), а на инвестирование третьего и четвертого предприятий вместе останется с₂₊₁=с₃=c₂-x₂ средств. Максимально возможная прибыль, которая может быть получена с этих трех предприятий будет равна

Таблица 15

x2   с2
	0+0	-	-	-	-	-
	0+16	12+0	-	-	-	-
	0+37	12+16	26+0	-	-	-
	0+52	12+37	26+16	36+0	-	-
	0+73	12+52	26+37	36+16	54+0	-
	0+82	12+73	26+52	36+37	54+16	78+0

Максимум этого выражения f₂^*(c₂) достигается на некотором значении х₂^*, которое и является оптимальным решением на третьем шаге для состояния системы с₂.

И, наконец, четвертый шаг. Для инвестирования предприятия с первого по четвертое осталось с₁ средств (0 с₁ 100). Тогда от вложения в первое предприятие х₁ средств будет получена прибыль g₁(x₁), а на инвестирование со второго по четвертое предприятий вместе останется с₁₊₁=с₂=c₁-x₁ средств. Максимально возможная прибыль, которая может быть получена с этих предприятий будет равна

Таблица 16

x1   с1
	0+0	-	-	-	-	-
	0+16	10+0	-	-	-	-
	0+37	10+16	31+0	-	-	-
	0+52	10+37	31+16	42+0	-	-
	0+73	10+52	31+37	42+16	62+0	-
	0+85	10+73	31+52	42+37	62+16	76+0

Максимум этого выражения f₁^*(c₁) достигается на некотором значении х₁^*, которое и является оптимальным решением на третьем шаге для состояния системы с₁.

II этап. Безусловная оптимизация. Мы распределяем 100 тыс. ден.ед., т.е. 1-ый шаг: с₁ = 100, F(100)= =85 тыс. ден.ед. при х₁^*=0.

2-ой шаг: с₂ = с₁ - х₁^* =100-0=100, из таблицы 15 можем найти, что х₂^*=20.

3-ий шаг: с₃ = с₂ – х₂^* =100-20=80, из таблицы 14 находим, что х₃^*=40.

4-ый шаг: с₄ = с₃ – х₃^* =80-40=40, из таблицы 13 видим, что х₄^*=40.

Итак, оптимальный план инвестирования четырех предприятий = (0; 20; 40; 40) принесет прибыль равную =85 тыс. ден.ед. Т.е. для получения возможно большей прибыли равной 85 тыс. ден.ед. второму предприятию необходимо выделить из общей суммы 20 тыс. ден.ед., третьему и четвертому по 40 тыс. ден.ед., а первое предприятие инвестиции не получает. ■

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

1. Предприятие производит продукцию двух видов: К₁ и К₂. Объем сбыта продукции К₁ составляет не менее 70% общего объема реализации продукции обоих видов. Для изготовления продукции К₁ и К₂ используется одно и тоже сырье, суточный запас которого равен 330 кг. Расход сырья на единицу продукции К₁ равен 3 кг, а на единицу продукции К₂ - 4 кг. Цены продукции К₁ и К₂ - 10 и 20 ден.ед. соответственно. Определить оптимальное распределение сырья для изготовления продукции К₁ и К₂. Задачу решить графическим методом.

2. Для производства двух видов продукции А₁ и А₂ на фабрике использован материал трёх сортов В₁, В₂ и В₃, имеющийся на складе в количестве 594, 614 и 574 соответственно. На изготовление изделия А_j расходуется а_ij кг материала сорта В_j. Матрица расхода (а_ij) задана. От реализации единицы продукции А₁ и А₂ фабрика имеет прибыль соответственно 5 и 7 ден.ед. Используя симплекс-метод найти максимальную прибыль от реализации всей продукции.

(а _ij)=

3. Построить двойственную задачу к предыдущей задаче (задаче 2) и записать её решение. Используя найденное решение определить наиболее дефицитный ресурс. На фабрику завезли материал сорта В₁ в количестве 5 единиц. Возможно ли в этом случае увеличить прибыль и насколько? Оценить целесообразность введения в план нового вида продукции А3, если на её изготовление расходуется по 9 кг каждого сырья, а прибыль от реализации составляет 10 ден.ед.?

4. Готовая продукция заводов А_i (i= ) направляется на склады В_j (j= ). Заводы А_i производят а_i тыс. изделий (а₁= 250; а₂= 150; а₁= 400). Пропускная способность складов В_j за это время характеризуется величинами b_j тыс. изделий (b₁ = 100; b₂ = 500; b₃ = 100; b₄ = 300). Стоимость перевозки с завода А_i на склад В_j одной тысячи изделий равна С_ij.

С_ij =

Найти план перевозки готовой продукции заводов на склады с минимальными затратами. Указать склады, пропускная способность которых использована не полностью, и величину резерва складских помещений в них.

5. Для увеличения объемов выпуска пользующейся повышенным спросом продукции, изготовляемой четырьмя предприятиями, последним выделены капиталовложения в объеме 600 млн. рублей. Составить оптимальный план распределения этих капиталовложений, если прирост выпуска продукции f_j (x_i) j -ым предприятием, когда ему выделено x_i млн. рублей задается следующей таблицей.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ТЕСТИРОВАНИЯ

1. Математическая модель задачи линейной оптимизации

F = 8x₁ +6x₂ –3x₃ (max)

x₁≥0, x₂≥0, х₃≥0.

записана в форме: 1) симметричной;

2) канонической;

3) общей;

4) матричной.

2. После приведения математической модели задачи линейной оптимизации

F = 6x₁ -3x₂ +7x₃ (min)

x₁≥0, x₃≥0

к каноническому виду мы получаем:

1) F = 6x1 -3x2 +7x3 (max) xj≥0, (j= )	2) F = -6x1 +3() -7x3 (max) x1≥0, xj≥0, (j= ), x ≥0,
3) F =- 6x1 +3x2 -7x3 (max) xj≥0, (j= )	4) F = -6x1 +3x2 -7x3 (max) xj≥0, (j= )

3. На рисунке изображен случай, когда своего максимального значения функция f(х) достигает

1) в точке Е; 2) в точке В; 3) в точке А; 4) на отрезке ВД; 5) в точке F

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

1)	2)
3)	Х1 Х2 4)

5. Решая задачу линейной оптимизации графическим методом мы получаем следующую иллюстрацию. По данному рисунку можно сказать, что задача имеет:

1) множество решений на максимум; 2) ОДР несовместна; 3) единственное решение на максимум; 4) единственное решение на минимум.

6. При решении данной задачи линейного программирования графическим методом F= 8x₁ +3x₂ (max)

x₁≥0, x₂≥0

получаем следующую иллюстрацию:

1)	2)
3)	4)

7. Решение задачи максимизации находящееся в симплексной таблице является

8. Определите разрешающий элемент в следующей симплексной таблице при решении задачи максимизации:

9. После пересчета элементов данной таблицы задачи максимизации линейного программирования

мы приходим к следующей таблице

10. Экстремальные значения целевых функций двойственных задач линейного программирования связаны следующим соотношением:

1)

2)

3)

11. Модель двойственной задачи построенной к данной

f = 8х₁ - 4х₂+ 7х₃ max.

2х₁+ 3х₂ - 4х₃ 106,

5х₁+ 4 х₂ + х₃ 205,

4х₁+ 2х₂+ 8х₃ 340.

х_j 0, (j= .

принимает следующий вид:

1) φ = 8 у1 – 4 у2 + 7 у3 min 2у1 + 3 у2 – 4у3 106 5у1 +4 у2 + у3 205 4у1 + 2у2 + 8у3 340 уi 0, I =	2) φ = 106 у1 + 205 у2 +340 у3 min 2у1 + 5 у2 + 4у3 8 3у1 +4 у2 + 2 у3 -4 -4у1 + у2 + 8у3 7 уi 0, i =
3) φ = 106 у1 + 205 у2 +340 у3 max 2у1 + 5 у2 + 4у3 8 3у1 +4 у2 + 2 у3 -4 -4у1 + у2 + 8у3 7 уi 0, I =	4) φ = 8 у1 - 4 у2 + 7 у3 max 2у1 + 3 у2 - 4у3 106 5у1 +4 у2 + у3 205 4у1 + 2у2 + 8у3 340 уi 0, i =

12. При решении пары двойственных задач (одна из которых задача об оптимальном использовании ресурсов) получен следующий результат:

f() = 20x₁+10x₂+9x₃ (max); =(10; 0; 3; 0; 8; 0); =(2; 0; 4; 0; 5; 0). Значение прибыли, если в производство ввести 3 единицы наиболее дефицитного ресурса, будет равно

13. Оцените целесообразность включения в план нового вида продукции, нормы затрат ресурсов на единицу которого равны соответственно 3, 4, 2, а прибыль от реализации равна 40 ден.ед., если при решении задачи о производстве продукции при оптимальном использовании ресурсов было получено следующее решение

f() = 5x1+3x2+x3 (max) (5; 0; 24; 4; 0; 0) (0; 9; 3; 0; 2; 0).

1) нецелесообразно; 2) данное задача не разрешима; 3) целесообразно.

14. Оцените целесообразность закупки 10 единиц второго вида ресурса по цене 2,5 ден.ед., если при решении задачи о производстве продукции при оптимальном использовании ресурсов было получено следующее решение

f() = 46x1+25x2+30x3 (max) (500;405; 0; 0; 0; 20) (4; 3; 0; 0; 0; 8).

4) нецелесообразно; 5) данное задача не разрешима; 6) целесообразно.

15. План находящийся в данной таблице является

16. Для клетки (1; 4) замкнутый цикл представлен в таблице

1)               3   2 75 1 5     9   8   7   6     10   11 12   13	2)             25 3   2   1 5     9   8   7   6   125 10   11   12   13
3)             25 3   2 75 1   5   150 9   8   7   6     10   11   12   13	4)             25 3   2   1 5   150 9   8   7   6     10   11   12   13

17. Оценка свободной клетки (2; 1) равна

18. Полученный план перевозок транспортной задачи является

19. Если значение потенциала U₂ = 1, то значение потенциала V₃ будет равно

20. Для данного опорного плана, находящегося в следующей таблице, значение функции будет равно

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

1)

2) f_n(t)= max

3) f_n(x_n-1, u_n) = min (z_n(x_n-1, u_n)+f_n-1(x_n))

ОТВЕТЫ

К задачам для самостоятельного решения

1. (70, 30), f_max =1300.

2. (52; 1; 0; 84; 0), f_max =267.

3. (67/220; 0; 3/20; 0; 0), φ_min=267; да, на ∆b₁=5*(67/220)=67/44; (67/220)*9+0*9+(3/20)*9=45/11<10 – целесообразно.

4. Х₁^* = или Х₂^* = , f_min = 1850

5. =(100; 400; 100; 0) или =(200; 400; 0; 0), F(600)= = 910.

К тестовым заданиям

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: