Линейная производственная задача

Транспортная таблица 1

Потребление	b1=37	b2 =39	b3 =48	b4 =40	b5  =6
Производство
a1= 70	2 37	1 33	6	5	0	p1=
a2= 40	5	3 6	- 7 34	6	*+0	p2=
a3= 60	3	2	+     4 14	2 40	-0 6	p3=
	q1=	q2=	q3=	q4=	q5=

Следует иметь в виду, что  по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.

Обозначим через           m )

вектор симплексных множителей или потенциалов. Тогда

   D_ij = mA_ij - с_ij                     i = 1,m;    j = 1,n

откуда следует       D_ij = p_i + q_j - c_ij     i = 1,m;  j = 1,n (6)  

Один из потенциалов можно выбрать  произвольно, так как в системе (3), (4) одно уравнение линейно зависит  от остальных. Положим, что р₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем

D₁₁ = 0,  p₁ + q₁ - c₁₁ = 0, 0+q₁ –2 = 0,  q₁ = 2

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

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

D₂₃ = 0,  p₂ + q₃ - c₂₃ = 0, 2 + q₃–7 = 0, q₃ = 5

D₃₃ = 0,  p₃ + q₃ – c₃₃ = 0, p₃ + 5–4 = 0, p₃ = -1

D₃₄ = 0,  p₃ + q₄ – c₃₄ = 0, -1 + q₄ -2= 0, q₄ = 3

D₃₅ = 0,  p₃ + q₅ – c₃₅ = 0, -1 + q₅–0 = 0,q₅ = 1

Затем по формуле (6) вычисляем оценки всех свободных клеток:

D₂₁ =  p₂ + q₁ - c₂₁ = 2+2-5=-1

D₃₁ =  p₃ + q₁ - c₃₁ = -1+2-3=-2

                D₃₂ =  p₃ + q₂ – c₃₂ = -1+1-2=-2

D₁₃ =  p₁ + q₃ – c₁₃ = 0+5-6=-1

                 D₁₄ =  p₁ + q₄ – c₁₄ = 0+3-5=-2

D₁₅ =  p₁ + q₅ – c₁₅ = 0+1-0=1

                D₂₄ =  p₂ + q₄ – c₂₄ = 2+3-6=-1

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

 

Находим наибольшую положительную  оценку  max ( ) = 3 =

 

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

34				34-r		r		28		6
14	40	6		14+r	40	6-r		20	40

= 6

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

 

Транспортная таблица 2

Потребление	b1=37	b2 =39	b3 =48	b4 =40	b5  =6
Производство
a1= 70	2 37	1 33	6	5	0	p1=0
a2= 40	5	3 6	7 28	6	0 6	p2=2
a3= 60	3	2	4 20	2 40	0	p3=-1
	q1=2	q2=1	q3=5	q4=3	q5=1

 

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

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

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

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

D₂₃ = 0,  p₂ + q₃ – c₂₃ = 0, 2+ q₃-7 = 0,  q₃ = 5

D₂₅ = 0,  p₂ + q₅ – c₂₅ = 0, 2 + q₅-0 = 0,  q₅ = -2

                D₃₃ = 0,  p₃ + q₃ – c₃₃ = 0, p₃ + 5-4 = 0,  p₃ = -1

                D₃₄ = 0,  p₃ + q₄ – c₃₄ = 0, -1+ q₄-2 = 0, q₄ = 3

Находим новые оценки.

                D₂₁ =  p₂ + q₁ - c₂₁ = 2+2-5=-1

D₃₁ =  p₃ + q₁ – c₃₁ = -1+2-3=-2

D₃₂ =  p₃ + q₂ – c₃₂ = -1+1-2=-2

D₁₃ =  p₁ + q₃ – c₁₃ = 0+5-6=-1

D₁₄ =  p₁ + q₄ – c₁₄ = 0+3-5=-2

D₁₅ =  p₁ + q₅ – c₁₅ = 0-2-0=-2

D₂₄ =  p₂ + q₄ – c₂₄ = 2+3-6=-1

                D₂₅ =  p₂ + q₅ – c₂₅ = 2-2-0=0

Пришли к таблице, для которой  все   D_ij £ 0  i = 1,m;        j = 1,n

Оценки удовлетворяют условию  оптимальности, следовательно решение….

            37   33   0    0

 X=       0     6   28   0  

             0     0   20  40                   …оптимально.

 

 Общая стоимость перевозок  =37*2+33*1+6*3+28*7+20*4+40*2=481 ед. 

 

 

 

 

Литература:

1. Методические указания к выполнению курсовой работы по дисциплине “Прикладная математика” / Сост.: Колемаев В.А., Карандаев И.С., В.И. Малыхин, Т.М. Гатауллин, Ю.Г. Прохоров, Х.Х. Юнисов; ГУУ, М., 2000. 73 с.
2. Математические методы принятия решений в экономике: Учебник / Под ред. В.А. Колемаева / ГУУ. – М.: ЗАО «Финстатинформ», 1999. – 386 с.