Задача 5

Ресурсы	А	В	Запас ресурса
1 2 3	4 2 6	1 2 3	16 22 36
Цена продукции	2+t	13-t, где

Решене:

Продукт А затратный

16/1 = 16 – можно выпустить 16 ед-ц продукта В.

22/2 = 11 – оптим-е реш-е при t=0

36/3 = 12

Критерий – максимум дохода.

Модель:

Требуется определить такое

x*(t) (1)

при котором

(2)

при условии, что МДР

X: (3)

(4)

(5)

(6)

(7)

Это ЗЛП. Для решения ЗЛП должна быть приведена к ОЗЛП. . Заметим, что МДР (3)-(6) не изменяется во времени. Во времени меняются лишь параметры целевой функции. Это означает, что для всего временного отрезка МДР будет одно и то же. МДР можно определить геометрически в плоскости двух свободных переменных – товарных выпусков.

Приведём задачу к основной, введя: ,

(8)

Тогда ОЗЛП:

(9)

(10)

(11)

(9)-(11) – 3 уравнения с 5ю неизвестными, они определяют МДР

взять в качестве свободных переменных возьмем x_A, x_B – т.к. через них удобнее выразить базисные:

При t = 0 задачу можно формально решить геометрически в плоскости товарных выпусков :

Z1=0: аналогично для z2 и z3.

Задача

Задачу решить методом динамического программирования (принципу Беллмана).

Решение:

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

1ый способ реализации на рисунке:

1 – 3 – 7 – 9 – 10 – оптимальная траектория.

2ой способ реализации – по таблице. По принципу Беллмана решение надо начинать при условии, что находимся в 4ой зоне (в узлах 8 и 9) и организуем связь из узлов 4ой зоны в узел 5ой зоны.

Из пунктов 4 зоны	Затраты, С
	В пункт 5 зоны						Минимальные затраты
8	1						1
9	4						4
Из пунктов 3 зоны	Из пунктов						Минимальные затраты
	8			9
5	7 + 1			5 + 4			8
6	3 + 1			4 + 4			4
7	7 + 1			1 + 4			5
Из пунктов 2 зоны	Из пунктов						Минимальные затраты
	5		6			7
2	10 + 8		12 + 4			-	16
3	5 + 8		10 + 4			7 + 5	12
4	-		15 + 4			13 + 5	18
Из пункта 1 зоны	Из пунктов						Минимальные затраты
	2	3			4
1	2 + 16	5 + 12			1 + 18		17

Управление (траектория) из 8 в 9 – вынужденное

с ценой 1 и 4 тыс. руб., эти показатели

одновременно минимальные7 – из исходных данных

1 – из данных 1го шага