Определитель матрицы ▦ Производная функции dydx График 3D Упростить выражение Графический метод решения задач нелинейного программирования ⇲ …
Примеры решений Задача Джонсона Симплекс метод Метод прогонки Задача замены оборудования Задача распределения инвестиций Параметры сетевой модели Задача коммивояжера Многоканальные СМО
Динамическое программирование / Метод прогонки

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

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

Количество объектов Количество вариантов

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

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

Фундаментальным принципом, положенным в основу теории динамического программирования, является принцип оптимальности Беллмана. Пусть
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. Пример №1. Решить задачу методом динамического программирования в прямом и обратном времени для целевой функции, заданной таблично.
F(x1,x2,x3) = f1(x1) + f2(x2) + f3(x3) → max
x1 + 2x2 + 2x3 ≤ 5
X 0 1 2 3 4 5
f1(x1) 6 7 11 12 15 16
f2(x2) 9 11 13 15    
f3(x3) 8 12 14 16    
Решение.
I этап. Условная оптимизация. f1(L) = max(f1); 0 ≤ x1 ≤ 5; x1 = 0,1,2,3,4,5.
f1(0) = max[6] = 6
f1(1) = max[6, 7] = 7
f1(2) = max[6, 7, 11] = 11
f1(3) = max[6, 7, 11, 12] = 12
f1(4) = max[6, 7, 11, 12, 15] = 15
f1(5) = max[6, 7, 11, 12, 15, 16] = 16
Таблица 1 – Расчет значения функции f1(L)
L 0 1 2 3 4 5
f1(L) 6 7 11 12 15 16
x1 0 1 2 3 4 5
f2(L) = max[f2 + f1(L - 2x2)]; 0 ≤ x2 ≤ 5; x2 = 0,1,2,3,4,5.
f2(0) = max[9+6] = 15
f2(1) = max[9+7] = 16
f2(2) = max[9+11, 11+6] = 20
f2(3) = max[9+12, 11+7] = 21
f2(4) = max[9+15, 11+11, 13+6] = 24
f2(5) = max[9+16, 11+12, 13+7] = 25
Таблица 2 – Расчет значения функции f2(L)
L 0 1 2 3 4 5
f2(L) 15 16 20 21 24 25
x2 0 0 0 0 0 0
f3(L) = max[f3 + f2(L - 2x3)]; 0 ≤ x3 ≤ 5; x3 = 0,1,2,3,4,5.
f3(0) = max[8+15] = 23
f3(1) = max[8+16] = 24
f3(2) = max[8+20, 12+15] = 28
f3(3) = max[8+21, 12+16] = 29
f3(4) = max[8+24, 12+20, 14+15] = 32
f3(5) = max[8+25, 12+21, 14+16] = 33
Таблица 3 – Расчет значения функции f3(L)
L 0 1 2 3 4 5
f3(L) 23 24 28 29 32 33
x3 0 0 0 0 0 0

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

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

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

0 x1 0 1 2 3 4 5 6
x4 f0(x0) / F4(x4) 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*.
c1 0 1 2 3 4 5 6
F0(c1) 0 0.2 0.33 0.42 0.48 0.53 0.56
x1 0 1 2 3 4 5 6
2-й шаг: k = 3.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F3(c3) = max [ g3(x3) + F4(c3 - x3)]
Таблица 2.
0 x2 0 1 2 3 4 5 6
x3 f3(x3) / F3(x3) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x2.
Таблица 2*.
c2 0 1 2 3 4 5 6
F3(c2) 0 0.2 0.35 0.48 0.6 0.73 0.83
x2 0 0 1 1 3 3 4
3-й шаг: k = 2.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F2(c2) = max [ g2(x2) + F3(c2 - x2)]
Таблица 3.
0 x3 0 1 2 3 4 5 6
x2 f4(x4) / F2(x2) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x3.
Таблица 3*.
c3 0 1 2 3 4 5 6
F4(c3) 0 0.25 0.45 0.61 0.76 0.9 1.03
x3 0 1 1 2 2 3 3
4-й шаг: k = 1.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F1(c1) = max [ g1(x1) + F2(c1 - x1)]
Таблица 4.
0 x4 0 1 2 3 4 5 6
x1 f5(x5) / F1(x1) 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x4.
Таблица 4*.
c4 0 1 2 3 4 5 6
F5(c4) 0 0.28 0.53 0.73 0.9 1.1 1.26
x4 0 1 1 1 3 3 3
II этап. Безусловная оптимизация.
1-й шаг: k = 1.
По данным таблицы 4* максимальный доход при распределении 6 между предприятиями составляет c1 = 6, F1(6) = 1.26. При этом 1-му предприятию нужно выделить x1 = 3.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c2 = c1 - x1 = 6 - 3 = 3.
По данным таблицы 3* максимальный доход при распределении 3 между предприятиями составляет c2 = 3, F2(3) = 0.61. При этом 2-му предприятию нужно выделить x2 = 2.
3-й шаг: k = 3.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c3 = c2 - x2 = 3 - 2 = 1.
По данным таблицы 2* максимальный доход при распределении 1 между предприятиями составляет c3 = 1, F3(1) = 0.2. При этом 3-му предприятию нужно выделить x3 = 0.
4-й шаг: k = 4.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c4 = c3 - x3 = 1 - 0 = 1.
По данным таблицы 1* максимальный доход при распределении 1 между предприятиями составляет c4 = 1, F4(1) = 0.20. При этом 4-му предприятию нужно выделить x4 = 1.
Таким образом, оптимальный план инвестирования предприятия: x1 = 3, x2 = 2, x3 = 0, x4 = 1, который обеспечит максимальный доход, равный: F(6) = g1(3) + g2(2) + g3(0) + g4(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 исходного решения.

Пример №4. Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом обратной прогонки.

Объем ресурса Х Величина прибыли Z(X)
1 2 3
0 0 0 0
40 25 24 27
80 38 40 45
120 60 55 58

Решение:
Задачи динамического программирования решаются методом прямой прогонки и методом обратной прогонки.
Процесс нахождения решения разбивается да две стадии:
условная оптимизация;
безусловная оптимизация.

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

I этап. Условная оптимизация.
1-ый шаг. k = 3.


e2
u3
e3= e2- u3
f3(u3)
F*3(e3)
u3(e3)

40

0
40
0

40
0
27
27
40

80


0
80
0


40
40
27


80
0
45
45
80

120



0
120
0


40
80
27

80
40
45


120
0
58
58
120
2-ый шаг. k = 2.

e1
u2
e2= e1- u2
f2(u2)
F*2(e1)
F1(u2,e1)
F*2(e2)
u2(e2)

40

0
40
0
27
27
27
0

40
0
24
0
24


80


0
80
0
45
45


40
40
24
27
51
51
40

80
0
40
0
40


120



0
120
0
58
58


40
80
24
45
69
69
40

80
40
40
27
67


120
0
55
0
55
3-ий шаг. k = 1.

e0
u1
e1= e0- u1
f1(u1)
F*1(e0)
F0(u1,e0)
F*1(e1)
u1(e1)

40

0
40
0
27
27
27
0

40
0
25
0
25


80


0
80
0
51
51


40
40
25
27
52
52
40

80
0
38
0
38


120



0
120
0
69
69


40
80
25
51
76
76
40

80
40
38
27
65


120
0
60
0
60

Поясним построение таблиц и последовательность проведения расчетов.
Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.
Из таблицы 1-го шага имеем F*3(e0 = 120) = 76. То есть максимальный доход всей системы при количестве средств e0 = 120 равен 76
Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 120) = 40
При этом остаток средств составит:
e1 = e0 - u1
e1 = 120 - 40 = 80
Из таблицы 2-го шага имеем F*2(e1 = 80) = 51. То есть максимальный доход всей системы при количестве средств e1 = 80 равен 51
Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 80) = 40
При этом остаток средств составит:
e2 = e1 - u2
e2 = 80 - 40 = 40
Последнему предприятию достается 40
Итак, инвестиции в размере 120 необходимо распределить следующим образом:
1-му предприятию выделить 40
2-му предприятию выделить 40
3-му предприятию выделить 40
Что обеспечит максимальный доход, равный 76.

Пример №5. Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом прямой прогонки.

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

0 x1 0 40 80 120
x2 f2(x2) / F1(x1) 0 25 38 60
0 0 0 25* 38 60
40 24 24 49* 62 0
80 40 40 65* 0 0
120 55 55 0 0 0

Таблица 1*.
Заполняем таблицу 1*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x1.Таблица 1*.
c1 0 40 80 120
F2(c1) 0 25 49 65
x1 0 0 40 80

2-й шаг: k = 2.
Таблица 2.
0 x2 0 40 80 120
x3 f3(x3) / F2(x2) 0 25 49 65
0 0 0 0 0 65
40 27 0 0 76* 0
80 45 0 70 0 0
120 58 58 0 0 0

Таблица 2*.
Заполняем таблицу 2*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x2.Таблица 2*.
c2 0 40 80 120
F3(c2) 0 0 0 76
x2 0 40 80 40

II этап. Безусловная оптимизация.
1-й шаг: k = 3.
По данным таблицы 2* максимальный доход при распределении 120 между предприятиями составляет c1 = 120, F3(120) = 76. При этом 3-му предприятию нужно выделить x3 = 40.
2-й шаг: k = 2.
Определим величину оставшихся денежных средств, приходящихся на долю остальных предприятий.
c2 = c1 - x1 = 120 - 40 = 80.
По данным таблицы 1* максимальный доход при распределении 80 между предприятиями составляет c2 = 80, F2(80) = 49. При этом 2-му предприятию нужно выделить x2 = 40.
На долю первого предприятия остается 40.
Таким образом, оптимальный план инвестирования предприятия:
x1 = 40
x2 = 40
x3 = 40
который обеспечит максимальный доход, равный:
F(120) = g1(40) + g2(40) + g3(40) = 25 + 24 + 27 = 76.