Вычислительная схема

Оптимальное решение задачи методом динамического программирования находится на основе функционального уравнения (1). Чтобы определить его, необходимо:

1) записать функциональное уравнение для последнего состояния процесса (ему соответствует ):

2) найти из дискретного набора его значений при некоторых фиксированных и из соответствующих допустимых областей (так как , то . В результате после первого шага известно решение U_n и соответствующее значение функции ;

3) уменьшить значение l на единицу и записать соответствующее функциональное уравнение. При оно имеет вид

(2)

4) найти условно-оптимальное решение на основе выражения (2);

5) проверить, чему равно значение l. Если , расчет условно-оптимальных решений закончен, при этом найдено оптимальное решение задачи для первого состояния процесса. Если, перейти к выполнению п. 3;

6) вычислить оптимальное решение задачи для каждого последующего шага процесса, двигаясь от конца расчетов к началу.

Пример 1. Оптимальное распределение инвестиций.

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

Средства с , тыс. ден. ед.	Предприятия
	№1	№2	№3	№4
	Прирост, тыс. ден. ед.
	g1(x)	g2(x)	g3(x)	g4(x)
20	12	14	11	16
40	28	26	24	25
60	39	40	43	36
80	47	51	51	49
100	69	68	68	72

Решение

Пусть п = 1. В соответствии с формулой

в зависимости от начальной суммы с получаем с учетом исходных данных значения , помещенные в таблице 1.

Таблица 1

20	12
40	28
60	39
80	47
100	69

Предположим теперь, что средства вкладываются в два предприятия. Тогда в соответствии с формулой

прибыль от вложения средств в два предприятия будем вычислять по формуле

Рассматриваемому шагу соответствует таблица 2.

Таблица 2

х с	0	20	40	60	80	100
20	0+12	14+0	-	-	-	-	14	20
40	0+28	14+12	26+0	-	-	-	28	0
60	0+39	14+28	26+12	40+0	-	-	42	20
80	0+47	14+39	26+28	40+12	51+0	-	54	40
100	0+69	14+47	26+39	40+28	51+12	68+0	69	0

Расчет значений приведен в таблице 3. Здесь использована формула

Таблица 3

х с	0	20	40	60	80	100
20	0+14	11+0	-	-	-	-	14	0
40	0+28	11+14	24+0	-	-	-	28	0
60	0+42	11+28	24+14	43+0	-	-	43	60
80	0+54	11+42	24+28	43+14	51+0	-	57	60
100	0+69	11+54	24+42	43+28	51+14	68+0	71	60

Аналогичным образом находятся значения :

и таблица будет иметь вид:

Таблица 4

х с	0	20	40	60	80	100
20	0+14	16+0	-	-	-	-	16	20
40	0+28	16+14	25+0	-	-	-	30	20
60	0+43	16+28	25+14	36+0	-	-	44	20
80	0+57	16+43	25+28	36+14	49+0	-	59	20
100	0+71	16+57	25+43	36+28	49+14	72+0	73	20

Полученные данные предыдущих четырех таблиц заносим в сводную таблицу 5:

Таблица 5

с
0	0	0	0	0	0	0	0	0
20	20	12	20	14	0	14	20	16
40	40	28	0	28	0	28	20	30
60	60	39	20	42	60	43	20	44
80	80	47	40	54	60	57	20	59
100	100	69	0	69	60	71	20	73

Из таблицы 5 видно, что наибольший прирост выпуска продукции, который могут дать четыре предприятия при распределении между ними 100 тыс. ден. ед. (с = 100), составляет 73 тыс. ден.ед. При этом четвертому предприятию должно быть выделено 20 тыс. ден.ед., а остальным трем — 100 - 20 = 80 тыс. ден. ед.

Из той же таблицы видно, что оптимальное распределение оставшихся 80 тыс. ден. ед. между тремя предприятиями обеспечит общий прирост продукции на них на сумму 57 тыс. ден. ед. при условии, что третьему предприятию будет выделено 60 тыс. ден.ед. (остается 80-60=20 тыс. ден. ед). Остальным двум предприятиям выделяется сумма в 20 тыс. ден. ед., прирост при этом составит 14 тыс. ден. ед при условии, что вся сумма будет выделена второму предприятию.

Итак, максимальный прирост выпуска продукции на четырех предприятиях при распределении между ними 100 тыс. ден. ед. составляет 73 тыс. ден. ед. и будет получен, если первому предприятию средств не выделять, второму выделить 20 тыс. ден. ед, третьему выделить 60 тыс. ден. ед и четвертому – 20 тыс. ден. ед.

Пример 2: Задача о нахождении оптимального маршрута перевозки грузов

На данной сети дорог (рисунок) имеется несколько маршрутов, по которым можно доставлять груз из пункта 1 в пункт 10. Известны стоимости перевозки единицы груза между пунктами сети.

Требуется:

• найти на сети наиболее экономичный маршрут доставки груза из пункта 1 в пункт 10 и соответствующие ему затраты;

• выписать оптимальные маршруты перевозки груза из всех остальных пунктов сети в пункт 10 и указать отвечающие им минимальные затраты на доставку.

Решение

Разобьем все пункты сети на подмножества (таблица 5.1).

Таблица 5.1

I	II	III	IV	V
1	2 3	4 5 6	7 8 9	10

К подмножеству I отнесем пункт 1, к подмножеству II – пункты, в которые можно попасть непосредственно из пункта 1 (таковыми будут 2, 3 и 4), к подмножеству III отнесем пункты, в которые можно попасть непосредственно из любого пункта подмножества II (таковыми будут 5, 6 и 7), и т. д.

В результате движение транспорта из пункта 1 в пункт 10 можно рассматривать как четырехшаговый процесс: на первом шаге транспорт перемещается из пунктов подмножества IV в пункт подмножества V (таблица 5.2), на втором шаге – из пунктов подмножества III в пункты подмножества IV (таблица 5.3) и т. д.

Таблица 5.2 – Первый шаг

Начальный пункт	Конечный пункт	Общие минимальные затраты	Конечный пункт на оптимальном маршруте
	10
8	5	5	10
9	2	2	10

Таблица 5.3 – Второй шаг

Начальный пункт	Конечный пункт		Общие минимальные затраты	Конечный пункт на оптимальном маршруте
	8	9
5	5+7	–	12	8
6	5+9	2+6	8	9
7	-	2+1	3	9

Таблица 5.4 – Третий шаг

Начальный пункт	Конечный пункт			Общие минимальные затраты	Конечный пункт на оптимальном маршруте
	5	6	7
2	12 + 6	–	3 + 1	4	7
3	12 + 4	8 + 3	3 + 5	8	7
4	12 + 4	8 + 8	3 + 2	5	7

Таблица 5.5 – Четвертый шаг

Начальный пункт	Конечный пункт			Общие минимальные затраты	Конечный пункт на оптимальном маршруте
	2	3	4
1	4 + 4	8 + 8	5 + 4	8	2

Двигаясь от таблицы 5.5 к таблице 5.2, определим оптимальный маршрут (1–2–7–9–10 затраты составляют 8).

Оптимальные пути из остальных пунктов до пункта 10:

(2–7–9–10) – затраты 4;

(3–7–9–10) – затраты 8;

(4–7–9–10) – затраты 5;

(5–8–10) – затраты 12;

(6–9–10) – затраты 8;

(7–9–10) – затраты 3;

(8–10) – затраты 5;

(9–10) – затраты 2.