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

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

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

Пример №1 . Решить задачу методом динамического программирования в прямом и обратном времени для целевой функции, заданной таблично.
F(x₁,x₂,x₃) = f₁(x₁) + f₂(x₂) + f₃(x₃) → max
x₁ + 2x₂ + 2x₃ ≤ 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 этап. Условная оптимизация. 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
f1(L)	6	7	11	12	15	16
x1	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
f2(L)	15	16	20	21	24	25
x2	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
f3(L)	23	24	28	29	32	33
x3	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	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.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₃(c₃) = max [ g₃(x₃) + F₄(c_{3 — 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₂.
Таблица 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.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₂(c₂) = max [ g₂(x₂) + F₃(c_{2 — 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₃.
Таблица 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.
Определяем оптимальную стратегию при распределении средств между остальными предприятиями. При этом рекуррентное соотношение Беллмана имеет вид:
F₁(c₁) = max [ g₁(x₁) + F₂(c_{1 — 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*. Для этого на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x₄.
Таблица 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 между предприятиями составляет 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 исходного решения.

Источник

Задача оптимального распределения инвестиций

Инструкция . Выберите количество предприятий и количество строк (количество вариантов эффективного вложения), нажмите Далее (см. Пример заполнения). Если доход и остатки предприятий задан в виде функций f(x) и g(x) , задача решается через этот калькулятор.

Пример №1 . Определите оптимальный план расширения производства трех предприятий, если известна их прибыль в год при отсутствии вложений и при инвестировании 1, 2, 3 или 4 млн. Определите, при каком инвестировании будет максимальный процент прироста прибыли.

f1	f2	f3	xi
40	30	35	0
90	110	95	1
395	385	270	2
440	470	630	3
620	740	700	4

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

e 2	u 3	e 3 = e 2 — u 3	f3(u 3 )	F*3(e 3 )	u3(e 3 )
1	0	1	35
1	0	95	95	1
2	0	2	35
1	1	95
2	0	270	270	2
3	0	3	35
1	2	95
2	1	270
3	0	630	630	3
4	0	4	35
1	3	95
2	2	270
3	1	630
4	0	700	700	4

2-ый шаг. k = 2.

e 1	u 2	e 2 = e 1 — u 2	f2(u 2 )	F*2(e 1 )	F1(u 2 ,e 1 )	F*2(e 2 )	u2(e 2 )
1	0	1	30	95	125	125	0
1	0	110	0	110
2	0	2	30	270	300
1	1	110	95	205
2	0	385	0	385	385	2
3	0	3	30	630	660	660	0
1	2	110	270	380
2	1	385	95	480
3	0	470	0	470
4	0	4	30	700	730
1	3	110	630	740	740	1
2	2	385	270	655
3	1	470	95	565
4	0	740	0	740

3-ый шаг. k = 1.

e 0	u 1	e 1 = e 0 — u 1	f1(u 1 )	F*1(e 0 )	F0(u 1 ,e 0 )	F*1(e 1 )	u1(e 1 )
1	0	1	40	125	165	165	0
1	0	90	0	90
2	0	2	40	385	425	425	0
1	1	90	125	215
2	0	395	0	395
3	0	3	40	660	700	700	0
1	2	90	385	475
2	1	395	125	520
3	0	440	0	440
4	0	4	40	740	780	780	0
1	3	90	660	750
2	2	395	385	780
3	1	440	125	565
4	0	620	0	620

Примечание: Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Из таблицы 3-го шага имеем F*₁(e 0 = 4 млн.руб.) = 780 тыс.руб., то есть максимальная прибыль от инвестирования e 0 = 4 млн.руб. равна 780 тыс.руб.
Из этой же таблицы получаем, что первому предприятию следует выделить u*₁(e 0 = 4 млн.руб.) = 0 млн.руб.
При этом остаток средств составит: e 1 = e 0 — u 1 , e 1 = 4 — 0 = 4 млн.руб.
Из таблицы 2-го шага имеем F*₂(e 1 = 4 млн.руб.) = 740 тыс.руб., т.е. максимальная прибыль при e 1 = 4 млн.руб. равна 740 тыс.руб.
Из этой же таблицы получаем, что второму предприятию следует выделить u*₂(e 1 = 4 млн.руб.) = 1 млн.руб.
При этом остаток средств составит: e 2 = e 1 — u 2 , e 2 = 4 — 1 = 3 млн.руб.
Последнему предприятию достается 3 млн.руб. Итак, инвестиции в размере 4 млн.руб. необходимо распределить следующим образом: первому предприятию ничего не выделять, второму предприятию выделить 1 млн.руб., третьему предприятию выделить 3 млн.руб., что обеспечит максимальную прибыль, равную 780 тыс.руб.

Пример №2 . Имеются 4 предприятия, между которыми необходимо распределить 100 тыс. усл. ед. средств. Значения прироста выпуска продукции на предприятии в зависимости от выделенных средств Х представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции.

Источник

Задача о рюкзаке

Задача о ранце
Имеются n предметов, которые необходимо поместить в рюкзак (ранец). Пусть известны вес a_j и «ценность» c_j каждого предмета (j= 1,2. ,n). Требуется заполнить рюкзак, не превышая его грузоподъемности (объема) b и максимизируя суммарную ценность груза. Получаем следующую булеву ЗЦЛП (задача о рюкзаке):

Задача о целочисленном рюкзаке
Предположим теперь, что каждый предмет имеется в неограниченном числе экземпляров, и требуется также максимизировать суммарную ценность груза, не превышая грузоподъемности. Получаем так называемую задачу о целочисленном рюкзаке:

Пример решения задачи о рюкзаке.
Задание. В рюкзак объема V = 7 кладут N = 5 предметов.Объемы, веса и количество предметов в каждой группе приведены в таблице.

Объем	1	2	3	1	1
Вес	2	3	2	4	1
Кол-во	1	3	3	1	2

Максимизировать общий вес рюкзака.

Решение. I этап. Условная оптимизация.
f₁(L) = max(2x₁); 0

Источник