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

Вариант 10

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

 

Задача закрытая (сбалансированная)

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

 

Найдём первоначальный план перевозок методом северо-западного  угла

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

 

F(x₀)=75*5+45*4+15*2+55*5+40*3+70*2=375+180+30+275+120+140=1120

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

u₁+v₁=5          

u₁+v₂=4                   

u₂+v₂=2

u₂+v₃=5

u₃+v₃=3

u₃+v₄=6

	В1	В2	В3	В4	U
А1	75 5	45 4	Х 3	Х 4	0
А2	Х 3	15 2	55 5	Х 5	-2
А3	Х 1	Х 6	40 3	70 2	-4
V	5	4	7	6

 

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

∆₁₃=с₁₃-(u₁+v₃)=3-(0+7)=-4

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

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

∆₂₄=с₂₄-(u₂+v₄)=5-(-2+6)=1

∆₃₁=с₃₁-(u₃+v₁)=1-(-4+5)=0

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

	В1	В2	В3	В4	U
А1	75 5	45 4	-4 Х 3	-2 Х 4	0
А2	0 Х 3	15 2	55 5	1 Х 5	-2
А3	0 Х 1	6 Х 6	40 3	70 2	-4
V	5	4	7	6

 

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

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

 

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

u₁+v₁=5          

u₁+v₃=0 3                  

u₂+v₂=2

u₂+v₃=5

u₃+v₃=3

u₃+v₄=2

	В1	В2	В3	В4	U
А1	75 5	Х 4	45 3	Х 4	0
А2	Х 3	60 2	10 5	Х 5	-2
А3	Х 1	Х 6	40 3	70 2	-0
V	5	-0	3	2

 

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

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

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

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

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

∆₃₁=с₃₁-(u₃+v₁)=1-(-0+5)=-4

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

 

	В1	В2	В3	В4	U
А1	75 5	4 Х 4	45 3	2 Х 4	0
А2	-4 Х 3	60 2	10 5	1 Х 5	-2
А3	-4 Х 1	6 Х 6	40 3	70 2	-0
V	5	-0	3	2

 

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

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

 

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

u₁+v₁=5          

u₁+v₃=3                 

u₂+v₁=3

u₂+v₂=2

u₃+v₃=3

u₃+v₄=2

	В1	В2	В3	В4	U
А1	60 5	Х 4	55 3	Х 4	0
А2	10 3	60 2	Х 5	Х 5	-2
А3	Х 1	Х 6	40 3	70 2	-0
V	5	4	3	2

 

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

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

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

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

∆₂₄=с₂₄-(u₂+v₄)=5-(-2+2)=5

∆₃₁=с₃₁-(u₃+v₁)=1-(-0+5)=-4

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

	В1	В2	В3	В4	U
А1	60 5	0 Х 4	55 3	2 Х 4	0
А2	10 3	60 2	4 Х 5	5 Х 5	-2
А3	-4 Х 1	2 Х 6	40 3	70 2	-0
V	5	4	3	2

 

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

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

 

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

u₁+v₁=5          

u₁+v₃=3                    

u₂+v₁=3

u₂+v₂=2

u₃+v₁=1

u₃+v₄=2

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

 

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

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

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

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

∆₂₄=с₂₄-(u₂+v₄)=5-(-2+6)=1

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

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

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