Процедура прогонки

Процедура прямой прогонки

Фундаментальным принципом, положенным в основу теории динамического программирования, является принцип оптимальности Беллмана. Пусть
f₁(x₁) - максимальный доход, полученный на этапе 1, при заданном значении x₁
f₂(x₂) - максимальный доход, полученный на этапах 1 и 2, при заданном значении x₂;
f₂(x₃) - максимальный доход, полученный на этапах 1, 2, 3, при заданном значении x₃.
Тогда рекуррентное соотношение динамического программирования будет иметь следующий вид: f₀(x₀) = 0 f_j(x_j) = max{R_j(k_j) + f_j_-1(x_j_-1)}, j = 1,2,3 где максимум берется по допустимым проектам k_j.
Так как c_j(k_j) = x_j–x_j_-1, следовательно,
x_j_-1 =x_j – c_j(k_j) ≥ 0
Откуда c_j(k_j) ≤ x_j

Процедура обратной прогонки

Для процедуры обратной прогонки определим состояния системы y_j следующим образом:
y₁ - объем капиталовложений, распределенных на этапах 1, 2, 3.
y₂ - объем капиталовложений, распределенных на этапах 2, 3.
y₃ - объем капиталовложений, распределенных на этапе 3.
Пусть
f₃(y₃) - максимальный доход, полученный на этапе 3, при заданном значении
f2{y₂) -максимальный доход, полученный на этапах 2, 3, при заданном значении y₂;
f₁(y₁) - максимальный доход, полученный на этапах 1, 2, 3 при заданном значении y₁
Тогда рекуррентное соотношение динамического программирования для процедуры обратной прогонки будет иметь следующий вид: f₃(y₃) = 0 f_j(y_j) = max{R_j(k_j) + f_j₊₁(y_j – c_j(k_j))}, j = 1,2,3.
где максимум берется по допустимым проектам k_j, т.е. c_j(k_j) ≤ y_j

На стадии условной оптимизации определяются условные оптимальные выигрыши и условные оптимальные управления.
Прямая прогонка: от первого шага к последнему.
Обратная прогонка: от последнего шага к первому.
На стадии безусловной оптимизации строится оптимальное решение исходной задачи и определяется max (min).
Прямая прогонка: от последнего шага к первому.
Обратная прогонка: от первого шага к последнему.

Пример. Оптимальное распределение ресурсов.
Совет директоров фирмы рассматривает предложение по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме.
Для модернизации предприятий совет директоров инвестирует средства в объеме 250 млн. р. с дискретностью 50 млн. р. Прирост выпуска продукции зависит от выделенной суммы, его значения предоставлены предприятиями и содержатся в таблице.
Найти предложение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.
Исходные данные задачи выбрать в таблицах 3.1, 3.2 в соответствии с вариантом.

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

0	x₁	0	50	100	150	200	250
x₄	f₀(x₀) / F₄(x₄)	0	0	0	0	0	0
0	0	0	0	0	0	0	0
50	18	0	0	0	0	18	0
100	24	0	0	0	24	0	0
150	31	0	0	31	0	0	0
200	38	0	38	0	0	0	0
250	54	54*	0	0	0	0	0

Таблица 1*.

c₁	50	100	150	200	250
F₀(c₁)	18	24	31	38	54
x₁	50	100	150	200	250

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

0	x₂	0	50	100	150	200	250
x₃	f₃(x₃) / F₃(x₃)	0	18	24	31	38	54
0	0	0	18*	24	31	38	54
50	17	17	35*	41	48	55	0
100	23	23	41*	47	54	0	0
150	30	30	48*	54	0	0	0
200	41	41	59*	0	0	0	0
250	51	51	0	0	0	0	0

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

c₂	50	100	150	200	250
F₃(c₂)	18	35	41	48	59
x₂	0	50	100	150	200

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

0	x₃	0	50	100	150	200	250
x₂	f₄(x₄) / F₂(x₂)	0	18	35	41	48	59
0	0	0	18	35	41	48	59
50	19	19*	37*	54*	60	67	0
100	26	26	44	61*	67	0	0
150	32	32	50	67*	0	0	0
200	39	39	57	0	0	0	0
250	49	49	0	0	0	0	0

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

c₃	50	100	150	200	250
F₄(c₃)	19	37	54	61	67
x₃	50	50	50	100	150

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

0	x₄	0	50	100	150	200	250
x₁	f₅(x₅) / F₁(x₁)	0	19	37	54	61	67
0	0	0	19*	37	54	61	67
50	18	18	37*	55*	72*	79	0
100	25	25	44	62	79*	0	0
150	34	34	53	71	0	0	0
200	43	43	62	0	0	0	0
250	49	49	0	0	0	0	0

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

c₄	50	100	150	200	250
F₅(c₄)	19	37	55	72	79
x₄	0	50	50	50	100

II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 250 между предприятиями составляет c₁ = 250, F₁(250) = 79. При этом 1-му предприятию нужно выделить x₁ = 100.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₂ = c₁ - x₁ = 250 - 100 = 150.
По данным таблицы 3* максимальный доход при распределении 150 между предприятиями составляет c₂ = 150, F₂(150) = 54. При этом 2-му предприятию нужно выделить x₂ = 50.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₃ = c₂ - x₂ = 150 - 50 = 100.
По данным таблицы 2* максимальный доход при распределении 100 между предприятиями составляет c₃ = 100, F₃(100) = 35. При этом 3-му предприятию нужно выделить x₃ = 50.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₄ = c₃ - x₃ = 100 - 50 = 50.
По данным таблицы 1* максимальный доход при распределении 50 между предприятиями составляет c₄ = 50, F₄(50) = 18. При этом 4-му предприятию нужно выделить x₄ = 50.
Таким образом, оптимальный план инвестирования предприятия:
x₁ = 100
x₂ = 50
x₃ = 50
x₄ = 50
который обеспечит максимальный доход, равный:
F(250) = g₁(100) + g₂(50) + g₃(50) + g₄(50) = 25 + 19 + 17 + 18 = 79.

Метод прямой прогонки.
I этап. Условная оптимизация.
1-й шаг: k = 1.
Предположим, что все средства в количестве x₁ = 250 отданы первому предприятию.
Таблица 1.

0	x₁	0	50	100	150	200	250
x₂	f₂(x₂) / F₁(x₁)	0	18	25	34	43	49
0	0	0	18	25	34	43	49
50	19	19*	37*	44	53*	62*	0
100	26	26	44*	51	60	0	0
150	32	32	50	57	0	0	0
200	39	39	57	0	0	0	0
250	49	49	0	0	0	0	0

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

c₁	50	100	150	200	250
F₂(c₁)	19	37	44	53	62
x₁	50	50	100	50	50

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

0	x₂	0	50	100	150	200	250
x₃	f₃(x₃) / F₂(x₂)	0	19	37	44	53	62
0	0	0	19*	37*	44	53	62
50	17	17	36	54*	61*	70*	0
100	23	23	42	60	67	0	0
150	30	30	49	67	0	0	0
200	41	41	60	0	0	0	0
250	51	51	0	0	0	0	0

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

c₂	50	100	150	200	250
F₃(c₂)	19	37	54	61	70
x₂	0	0	50	50	50

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

0	x₃	0	50	100	150	200	250
x₄	f₄(x₄) / F₃(x₃)	0	19	37	54	61	70
0	0	0	0	0	0	0	70
50	18	0	0	0	0	79*	0
100	24	0	0	0	78	0	0
150	31	0	0	68	0	0	0
200	38	0	57	0	0	0	0
250	54	54	0	0	0	0	0

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

c₃	50	100	150	200	250
F₄(c₃)	0	0	0	0	79
x₃	50	100	150	200	50

II этап. Безусловная оптимизация.
1-й шаг: k = 4.
По данным таблицы 3* максимальный доход при распределении 250 между предприятиями составляет c₁ = 250, F₄(250) = 79. При этом 4-му предприятию нужно выделить x₄ = 50.
2-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₂ = c₁ - x₁ = 250 - 50 = 200.
По данным таблицы 2* максимальный доход при распределении 200 между предприятиями составляет c₂ = 200, F₃(200) = 61. При этом 3-му предприятию нужно выделить x₃ = 50.
3-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c₃ = c₂ - x₂ = 200 - 50 = 150.
По данным таблицы 1* максимальный доход при распределении 150 между предприятиями составляет c₃ = 150, F₂(150) = 44. При этом 2-му предприятию нужно выделить x₂ = 100.
На долю первого предприятия остается 50.
Таким образом, оптимальный план инвестирования предприятия:
x₁ = 50
x₂ = 100
x₃ = 50
x₄ = 50
который обеспечит максимальный доход, равный:
F(250) = g₁(50) + g₂(100) + g₃(50) + g₄(50) = 18 + 26 + 17 + 18 = 79.

Объекты / Стадии	№1	№2	№3	№4
A₁	2	5	4	3
A₂	1	4	2	6
A₃	3	4	3	4

Процедура прогонки

Процедура прямой прогонки

Процедура обратной прогонки

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

Поиск

Процесс

Сообщение