Дерево решений

ЛП0:x₁= 3,x₂= 2,L= 43

x₁ ≤ 3x₁≥ 4

ЛП1:x₁= 3,x₂= 2,L= 42 ЛП2:x₁= 4,x₂= 2,L= 43

x₂≤ 2x₃≥ 3

ЛП3:x₁= 4,x₂= 2,L= 43ЛП4: решений нет

x₁≤ 4x₁≥ 5

ЛП5:x₁= 4,x₂= 2,L= 42 ЛП6:x₁= 5,x₂= 1,L= 42

x₂≤ 1x₂≥ 2

ЛП 7:x₁= 5,x₂= 1,L= 42ЛП8: решений нет

x₁≤ 5x₁≥ 6

ЛП9: x₁= 5,x₂= 1,L= 39 ЛП10:x₁= 7,x₂= 0,L= 42

Ответ:x₁= 4,x₂= 2 илиx₁= 7,x₂= 0.L = 42.

Контрольная работа на тему: «Динамическое программирование»

Задача замены оборудования.Условия. Известны характеристики станка, зависящие от его возрастаtна начало года:

r(t) – стоимость продукции, производимой за год;

u(t) – годовые эксплуатационные затраты;

s(t) – остаточная стоимость (выручка от продажи станка).

На начало планового периода в Nлет станок имеет возрастt=t₀. В начале любого года станок можно не заменять (сохранить) или продать и купить такой же новый по ценеP(включая установку и пр.). Продолжительность замены много меньше года.

Необходимо разработать оптимальную политику замены станка для N= 10 иt₀= 0..6. Исходные данные приведены в табл. (рассматривается замена одного станка). Результаты представить в виде таблицы, в клетках которой должны быть оптимальные значения критерия и переменной (заголовки столбцов – возраст от 0 до 9, заголовки строк – номера шагов).

Вариант № 26.

Тип станка – В. P= 18,S= 7.

t	0	1	2	3	4	5	6	7	8	9	10
r(t)	25	24	23	21	20	20	19	19	18	17	17
u(t)	9	10	10	11	12	13	13	14	15	16	17

Решение:

Пусть f(t) –прибыль. Тогда

Рассчитаем при скольких лет станок не выгодно держать.

Замена станка = r(0) –u(0) –P+S= 25 – 9 – 18 + 7 = 5.

t	выручка			Решение
	если сохраним станок	если заменим станок
0	r(t) – u(t) = 25 – 9 = 16	5	Сохранить
1	24 – 10 = 14	5	Сохранить
2	23 – 10 = 13	5	Сохранить
3	21 – 11 = 10	5	Сохранить
4	20 – 12 = 8	5	Сохранить
5	20 – 13 = 7	5	Сохранить
6	19 – 13 = 6	5	Сохранить
7	19 – 14 = 5	5	Замена
1	14	5	Сохранить
2	13	5	Сохранить
3	10	5	Сохранить
4	8	5	Сохранить
5	7	5	Сохранить
6	6	5	Сохранить
7	5	5	Замена

Из таблицы делаем вывод, что при возрасте 7 лет станок лучше заменить.

Составляем политику замены станка.

N \ t0	0	1	2	3	4	5	6
1	С	С	С	С	С	С	С
2	С	С	С	С	С	С	З
3	С	С	С	С	С	З	С
4	С	С	С	С	З	С	С
5	С	С	С	З	С	С	С
6	С	С	З	С	С	С	С
7	С	З	С	С	С	С	С
8	З	С	С	С	С	С	С
9	С	С	С	С	С	С	З
10	С	С	С	С	С	З	С