Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Примеры решений Задача Джонсона Симплекс метод Метод прогонки Задача замены оборудования Задача распределения инвестиций Параметры сетевой модели Задача коммивояжера Многоканальные СМО

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

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

Фундаментальным принципом, положенным в основу теории динамического программирования, является принцип оптимальности Беллмана. Пусть
f1(x1) - максимальный доход, полученный на этапе 1, при заданном значении x1
f2(x2) - максимальный доход, полученный на этапах 1 и 2, при заданном значении x2;
f2(x3) - максимальный доход, полученный на этапах 1, 2, 3, при заданном значении x3.
Тогда рекуррентное соотношение динамического программирования будет иметь следующий вид:
f0(x0) = 0
fj(xj) = max{Rj(kj) + fj-1(xj-1)}, j = 1,2,3
где максимум берется по допустимым проектам kj.
Так как cj(kj) = xj–xj-1, следовательно,
xj-1 =xj – cj(kj) ≥ 0
Откуда cj(kj) ≤ xj

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

Для процедуры обратной прогонки определим состояния системы yj следующим образом:
y1 - объем капиталовложений, распределенных на этапах 1, 2, 3.
y2 - объем капиталовложений, распределенных на этапах 2, 3.
y3 - объем капиталовложений, распределенных на этапе 3.
Пусть
f3(y3) - максимальный доход, полученный на этапе 3, при заданном значении
f2{y2) -максимальный доход, полученный на этапах 2, 3, при заданном значении y2;
f1(y1) - максимальный доход, полученный на этапах 1, 2, 3 при заданном значении y1
Тогда рекуррентное соотношение динамического программирования для процедуры обратной прогонки будет иметь следующий вид:
f3(y3) = 0
fj(yj) = max{Rj(kj) + fj+1(yj – cj(kj))}, j = 1,2,3.

где максимум берется по допустимым проектам kj, т.е. cj(kj) ≤ yj

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

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

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

0 x1 0 50 100 150 200 250
x4 f0(x0) / F4(x4) 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*.
c1 0 50 100 150 200 250
F0(c1) 0 18 24 31 38 54
x1 0 50 100 150 200 250

2-й шаг: k = 3.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F3(c3) = max [ g3(x3) + F4(c3 - x3)]
Таблица 2.
0 x2 0 50 100 150 200 250
x3 f3(x3) / F3(x3) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x2.
Таблица 2*.
c2 0 50 100 150 200 250
F3(c2) 0 18 35 41 48 59
x2 0 0 50 100 150 200

3-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F2(c2) = max [ g2(x2) + F3(c2 - x2)]
Таблица 3.
0 x3 0 50 100 150 200 250
x2 f4(x4) / F2(x2) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x3.
Таблица 3*.
c3 0 50 100 150 200 250
F4(c3) 0 19 37 54 61 67
x3 0 50 50 50 100 150

4-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F1(c1) = max [ g1(x1) + F2(c1 - x1)]
Таблица 4.
0 x4 0 50 100 150 200 250
x1 f5(x5) / F1(x1) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x4.
Таблица 4*.
c4 0 50 100 150 200 250
F5(c4) 0 19 37 55 72 79
x4 0 0 50 50 50 100

II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 250 между предприятиями составляет c1 = 250, F1(250) = 79. При этом 1-му предприятию нужно выделить x1 = 100.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c2 = c1 - x1 = 250 - 100 = 150.
По данным таблицы 3* максимальный доход при распределении 150 между предприятиями составляет c2 = 150, F2(150) = 54. При этом 2-му предприятию нужно выделить x2 = 50.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c3 = c2 - x2 = 150 - 50 = 100.
По данным таблицы 2* максимальный доход при распределении 100 между предприятиями составляет c3 = 100, F3(100) = 35. При этом 3-му предприятию нужно выделить x3 = 50.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c4 = c3 - x3 = 100 - 50 = 50.
По данным таблицы 1* максимальный доход при распределении 50 между предприятиями составляет c4 = 50, F4(50) = 18. При этом 4-му предприятию нужно выделить x4 = 50.
Таким образом, оптимальный план инвестирования предприятия:
x1 = 100
x2 = 50
x3 = 50
x4 = 50
который обеспечит максимальный доход, равный:
F(250) = g1(100) + g2(50) + g3(50) + g4(50) = 25 + 19 + 17 + 18 = 79.

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

0 x1 0 50 100 150 200 250
x2 f2(x2) / F1(x1) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x1.
Таблица 1*.
c1 0 50 100 150 200 250
F2(c1) 0 19 37 44 53 62
x1 0 50 50 100 50 50

2-й шаг: k = 2.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №1, 2. При этом рекуррентное соотношение Беллмана имеет вид: F2(c2) = max(x2 ≤ c2)(g2(x2) + F1(c2-x2))
Таблица 2.
0 x2 0 50 100 150 200 250
x3 f3(x3) / F2(x2) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x2.
Таблица 2*.
c2 0 50 100 150 200 250
F3(c2) 0 19 37 54 61 70
x2 0 0 0 50 50 50

3-й шаг: k = 3.
Определяем оптимальную стратегию при распределении денежных средств между предприятиями №1, 2, 3. При этом рекуррентное соотношение Беллмана имеет вид: F3(c3) = max(x3 ≤ c3)(g3(x3) + F2(c3-x3))
Таблица 3.
0 x3 0 50 100 150 200 250
x4 f4(x4) / F3(x3) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x3.
Таблица 3*.
c3 0 50 100 150 200 250
F4(c3) 0 0 0 0 0 79
x3 0 50 100 150 200 50

II этап. Безусловная оптимизация.
1-й шаг: k = 4.
По данным таблицы 3* максимальный доход при распределении 250 между предприятиями составляет c1 = 250, F4(250) = 79. При этом 4-му предприятию нужно выделить x4 = 50.
2-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c2 = c1 - x1 = 250 - 50 = 200.
По данным таблицы 2* максимальный доход при распределении 200 между предприятиями составляет c2 = 200, F3(200) = 61. При этом 3-му предприятию нужно выделить x3 = 50.
3-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c3 = c2 - x2 = 200 - 50 = 150.
По данным таблицы 1* максимальный доход при распределении 150 между предприятиями составляет c3 = 150, F2(150) = 44. При этом 2-му предприятию нужно выделить x2 = 100.
На долю первого предприятия остается 50.
Таким образом, оптимальный план инвестирования предприятия:
x1 = 50
x2 = 100
x3 = 50
x4 = 50
который обеспечит максимальный доход, равный:
F(250) = g1(50) + g2(100) + g3(50) + g4(50) = 18 + 26 + 17 + 18 = 79.