Реферат: Линейное и динамическое программирование

Таблица 1

Потребл Произв	b1 =48	b2 =30	b3 =29	b4 =40	b5 =8
a1 =40	40 3	6	4	* 3	0	p1 =0
a2 =45	8 2	30 3	7 1	3	0	p2 =-1
a3 =70	6	5	22 1	40 4	8 0	p3 =-1
q1 =3	q2 =4	q3 =2	q4 =5	q5 =1

Обозначим через m(p₁ , p₂ ,…, p_m , q₁ , q₂ ,…, q_n ) вектор симплексных множителей или потенциалов. Тогда D_ij =mA_ij -c_ij , iÎN_m , jÎN_n , откуда следует

D_ij =p_i +q_j -c_ij , iÎN_m , jÎN_n

Положим, что p₁ =0. Ос­тальные потенциалы находим из условия, что для базисных клеток D_ij =0. В данном случае получаем

D₁₁ =0, p₁ +q₁ -c₁₁ =0, 0+q₁ -3=0, q₁ =3

D₂₁ =0, p₂ +q₁ -c₂₁ =0, p₂ +3-2=0, p₂ = -1

D₂₃ =0, p₂ +q₃ -c₂₃ =0, -1+q₃ -1=0, q₃ =2

аналогично, получим: q₂ =4, р₃ =-1, q₄ =5, q₅ =1.

Затем вычисляем оценки всех свободных клеток:

D₁₂ =p₁ +q₂ -c₁₂ =0+4-6= -2

D₁₃ =p₁ +q₃ -c₁₃ =0+2-4=-2

D₁₄ =2; D₁₅ =1; D₂₄ =1; D₂₅ =0; D₃₁ = -4; D₃₂ = -2

Находим наибольшую положительную оценку:

mах(D_ij >0)=2=D₁₄ ,

Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами зве­нья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-23-21-11. Производим перераспределение поставок вдоль цикла пересчета:

40	*	40-r	r	33	7
8	30	7	®	8+r	7-r	®	15	30
22	40	22+r	40-r	29	33

r_max =7

Получаем второе базисное допустимое решение:

Таблица 2

Потребл Произв	b1 =48	b2 =30	b3 =29	b4 =40	b5 =8
a1 =40	33 3	6	4	7 3	0	p1 =0
a2 =45	15 2	30 3	1	3	0	p2 =-1
a3 =70	6	* 5	29 1	33 4	8 0	p3 =1
q1 =3	q2 =4	q3 =0	q4 =3	q5 = -1

Находим новые потенциалы. Новые оценки:

D₁₂ = -2; D₁₃ = -4; D₁₅ = -1; D₂₃ = -2; D₂₄ = -1; D₂₅ = -2; D₃₁ = -2; D₃₂ =0. Поскольку все D_ij £0 решение является оптимальным:

33 0 0 7

X_{о pt1} = 15 30 0 0

0 0 29 33