Метод прогонки

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

Инструкция. Выберите количество объектов и количество групп возможных вариантов, нажмите Далее. В новом окне выберите метод прогонки.

Скачать пример оформления

Пример №1. Решить задачу методом динамического программирования в прямом и обратном времени для целевой функции, заданной таблично.
F(x₁,x₂,x₃) = f₁(x₁) + f₂(x₂) + f₃(x₃) → max
x₁ + 2x₂ + 2x₃ ≤ 5

X	0	1	2	3	4	5
f₁(x₁)	6	7	11	12	15	16
f₂(x₂)	9	11	13	15
f₃(x₃)	8	12	14	16

Решение.
I этап. Условная оптимизация. f₁(L) = max(f₁); 0 ≤ x₁ ≤ 5; x₁ = 0,1,2,3,4,5.
f₁(0) = max[6] = 6
f₁(1) = max[6, 7] = 7
f₁(2) = max[6, 7, 11] = 11
f₁(3) = max[6, 7, 11, 12] = 12
f₁(4) = max[6, 7, 11, 12, 15] = 15
f₁(5) = max[6, 7, 11, 12, 15, 16] = 16
Таблица 1 – Расчет значения функции f₁(L)

L	0	1	2	3	4	5
f₁(L)	6	7	11	12	15	16
x₁	0	1	2	3	4	5

f₂(L) = max[f₂ + f₁(L - 2x₂)]; 0 ≤ x₂ ≤ 5; x₂ = 0,1,2,3,4,5.
f₂(0) = max[9+6] = 15
f₂(1) = max[9+7] = 16
f₂(2) = max[9+11, 11+6] = 20
f₂(3) = max[9+12, 11+7] = 21
f₂(4) = max[9+15, 11+11, 13+6] = 24
f₂(5) = max[9+16, 11+12, 13+7] = 25
Таблица 2 – Расчет значения функции f₂(L)

L	0	1	2	3	4	5
f₂(L)	15	16	20	21	24	25
x₂	0	0	0	0	0	0

f₃(L) = max[f₃ + f₂(L - 2x₃)]; 0 ≤ x₃ ≤ 5; x₃ = 0,1,2,3,4,5.
f₃(0) = max[8+15] = 23
f₃(1) = max[8+16] = 24
f₃(2) = max[8+20, 12+15] = 28
f₃(3) = max[8+21, 12+16] = 29
f₃(4) = max[8+24, 12+20, 14+15] = 32
f₃(5) = max[8+25, 12+21, 14+16] = 33
Таблица 3 – Расчет значения функции f₃(L)

L	0	1	2	3	4	5
f₃(L)	23	24	28	29	32	33
x₃	0	0	0	0	0	0

II этап. Безусловная оптимизация.
Таким образом, максимум f₃(5) = 33
При этом x₃ = 0, так как f₃(5) = 33 достигается при х₃=0 (см. таблицу 3).
Остальные x распределяются следующим образом:
L = 5 - 2 * 0 = 5
f₂(5) = 25 достигается при х₂ = 0 (см. таблицу 2).
L = 5 - 2 * 0 = 5
f₁(5) = 16 достигается при х₁ = 5 (см. таблицу 1).
L = 5 - 1 * 5 = 0
В итоге наилучший вариант достигается при значениях: x₁ = 5, x₂ = 0, x₃ = 0

Пример №2. Рассмотрим задачу об оптимальном размещении капитала K = nh в m различных независимых фондах (банки, организации, фирма и т.д.), для которых известна ожидаемая прибыль f_i при капиталовложениях x_i = ih, i = 1..n. Здесь n – количество дискретных приращений h (дискрет), на которые разбит капитал К.
Пусть такие данные имеются по четырем (m=4) фондам для h = 1 млн. руб., n = 6

Решение.
I этап. Условная оптимизация.
1-й шаг: k = 4.
Предположим, что все средства в количестве x₄ = 6 отданы 4-у предприятию. В этом случае максимальный доход, как это видно из таблицы 1*, составит 0.56, следовательно:
F₄(c₄) = g₄(x₄)
Таблица 1.

0	x₁	0	1	2	3	4	5	6
x₄	f₀(x₀) / F₄(x₄)	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0
1	0.2	0	0	0	0	0	0.2	0
2	0.33	0	0	0	0	0.33	0	0
3	0.42	0	0	0	0.42	0	0	0
4	0.48	0	0	0.48	0	0	0	0
5	0.53	0	0.53	0	0	0	0	0
6	0.56	0.56*	0	0	0	0	0	0

Таблица 1*.

c₁	1	2	3	4	5	6
F₀(c₁)	0.2	0.33	0.42	0.48	0.53	0.56
x₁	1	2	3	4	5	6

2-й шаг: k = 3.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₃(c₃) = max [ g₃(x₃) + F₄(c_{3 - x₃})]
Таблица 2.

0	x₂	0	1	2	3	4	5	6
x₃	f₃(x₃) / F₃(x₃)	0	0.2	0.33	0.42	0.48	0.53	0.56
0	0	0	0.2*	0.33	0.42	0.48	0.53	0.56
1	0.15	0.15	0.35*	0.48*	0.57	0.63	0.68	0
2	0.25	0.25	0.45	0.58	0.67	0.73	0	0
3	0.4	0.4	0.6*	0.73*	0.82	0	0	0
4	0.5	0.5	0.7	0.83*	0	0	0	0
5	0.62	0.62	0.82	0	0	0	0	0
6	0.73	0.73	0	0	0	0	0	0

Заполняем таблицу 2*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₂.
Таблица 2*.

c₂	1	2	3	4	5	6
F₃(c₂)	0.2	0.35	0.48	0.6	0.73	0.83
x₂	0	1	1	3	3	4

3-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₂(c₂) = max [ g₂(x₂) + F₃(c_{2 - x₂})]
Таблица 3.

0	x₃	0	1	2	3	4	5	6
x₂	f₄(x₄) / F₂(x₂)	0	0.2	0.35	0.48	0.6	0.73	0.83
0	0	0	0.2	0.35	0.48	0.6	0.73	0.83
1	0.25	0.25*	0.45*	0.6	0.73	0.85	0.98	0
2	0.41	0.41	0.61*	0.76*	0.89	1.01	0	0
3	0.55	0.55	0.75	0.9*	1.03*	0	0	0
4	0.65	0.65	0.85	1	0	0	0	0
5	0.75	0.75	0.95	0	0	0	0	0
6	0.8	0.8	0	0	0	0	0	0

Заполняем таблицу 3*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₃.
Таблица 3*.

c₃	1	2	3	4	5	6
F₄(c₃)	0.25	0.45	0.61	0.76	0.9	1.03
x₃	1	1	2	2	3	3

4-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₁(c₁) = max [ g₁(x₁) + F₂(c_{1 - x₁})]
Таблица 4.

0	x₄	0	1	2	3	4	5	6
x₁	f₅(x₅) / F₁(x₁)	0	0.25	0.45	0.61	0.76	0.9	1.03
0	0	0	0.25	0.45	0.61	0.76	0.9	1.03
1	0.28	0.28*	0.53*	0.73*	0.89	1.04	1.18	0
2	0.45	0.45	0.7	0.9	1.06	1.21	0	0
3	0.65	0.65	0.9*	1.1*	1.26*	0	0	0
4	0.78	0.78	1.03	1.23	0	0	0	0
5	0.9	0.9	1.15	0	0	0	0	0
6	1.02	1.02	0	0	0	0	0	0

Заполняем таблицу 4*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₄.
Таблица 4*.

c₄	1	2	3	4	5	6
F₅(c₄)	0.28	0.53	0.73	0.9	1.1	1.26
x₄	1	1	1	3	3	3

II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 6 между предприятиями составляет c₁ = 6, F₁(6) = 1.26. При этом 1-му предприятию нужно выделить x₁ = 3.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₂ = c₁ - x₁ = 6 - 3 = 3.
По данным таблицы 3* максимальный доход при распределении 3 между предприятиями составляет c₂ = 3, F₂(3) = 0.61. При этом 2-му предприятию нужно выделить x₂ = 2.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₃ = c₂ - x₂ = 3 - 2 = 1.
По данным таблицы 2* максимальный доход при распределении 1 между предприятиями составляет c₃ = 1, F₃(1) = 0.2. При этом 3-му предприятию нужно выделить x₃ = 0.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₄ = c₃ - x₃ = 1 - 0 = 1.
По данным таблицы 1* максимальный доход при распределении 1 между предприятиями составляет c₄ = 1, F₄(1) = 0.20. При этом 4-му предприятию нужно выделить x₄ = 1.
Таким образом, оптимальный план инвестирования предприятия: x₁ = 3, x₂ = 2, x₃ = 0, x₄ = 1, который обеспечит максимальный доход, равный: F(6) = g₁(3) + g₂(2) + g₃(0) + g₄(1) = 0.65 + 0.41 + 0 + 0.20 = 1.26.

Пример №3. Распределите c=200 млн ден. ед. инвестиций между четырьмя министерствами республики (n=4) на реконструкцию и модернизацию производственных мощностей таким образом, чтобы суммарный прирост производства продукции всех министерств f4(с) был максимальным. Прирост выпуска продукции в каждом из министерств gi(x) в зависимости от объема выделенных средств x (0 < x < с) представлен в таблице.
По решению этой задачи найдите оптимальное распределение c=200 млн ден. ед. между первыми тремя министерствами, максимизирующее их суммарный прирост производства продукции f3(с).
Примечание. Основная задача решается с помощью процедуры прямой прогонки. Ответ на подзадачу можно получить из таблицы n-1 исходного решения.

x	f₁(x)	f₂(x)	f₃(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

Метод прогонки

Правила ввода данных

Поиск

Процесс

Сообщение