Транспортная задача

 

Опорная клетка (1; 4) [+25] далее (1; 1) [-25] (3; 1) [+25] (3; 4) [-25]

	В1	В2	В3	В4	Запасы
А1	Х 5	Х 4	95 3	25 4	120
А2	10 3	60 2	Х 5	Х 5	70
А3	65 1	Х 6	Х 3	45 2	110
потребности	75	60	95	70

 

Найдём потенциалы u_i+v_j=c_ij. u_i=0

u₁+v₃=3          

u₁+v₄=4                    

u₂+v₁=3

u₂+v₂=2

u₃+v₁=1

u₃+v₄=2

	В1	В2	В3	В4	U
А1	Х 5	Х 4	95 3	25 4	0
А2	10 3	60 2	Х 5	Х 5	-0
А3	65 1	Х 6	Х 3	45 2	-2
V	3	2	3	4

 

Вычислим разности для  свободных клеток:

∆₁₂=с₁₂-(u₁+v₂)=4-(0+2)=2

∆₁₃=с₁₃-(u₁+v₂)=4-(0+2)=2

∆₂₃=с₂₃-(u₂+v₃)=5-(-0+3)=2

∆₂₄=с₂₄-(u₂+v₄)=5-(-0+4)=1

∆₃₂=с₃₂-(u₃+v₂)=6-(-2+2)=6

∆₃₃=с₃₃-(u₃+v₃)=3-(-2+3)=2

	В1	В2	В3	В4	U
А1	2 Х 5	2 Х 4	95 3	25 4	0
А2	10 3	60 2	2 Х 5	1 Х 5	-0
А3	65 1	6 Х 6	2 Х 3	45 2	-2
V	3	2	3	4

 

Т.к. все разности неотрицательны Δc_ij ≥ 0, найден оптимальный план перевозок

Ответ:

	В1	В2	В3	В4	Запасы
А1	Х 5	Х 4	95 3	25 4	120
А2	10 3	60 2	Х 5	Х 5	70
А3	65 1	Х 6	Х 3	45 2	110
потребности	75	60	95	70

 

F(x₀)=95*3+25*4+10*3+60*2+65*1+45*2=285+30+120+65+90=590