Решить транспортную задачу по критерию стоимости методом потенциалов

Номер варианта	Пункты отправления
	Пункты назначения
5	63     45    76
	68     28    56     32

Таблица стоимостей

1	4	1	3
3	2	2	1
5	3	6	2

х₂₁=0, х₂₂=0, х₂₃=13, х₂₄=32,

х₃₁=5, х₃₂=28, х₃₃=43, х₃₄=0,

z=63*1+13*2+32*1+5*5+28*3+43*6=488

Для каждой базисной клетки справедливо соотношение: U_i+V_j=C_ij.

Для каждой базисной клетки составляем такое уравнение и получаем систему из m+n-1 векторов с m+n переменными.

U₁+V₁=1

U₂+V₃=2

U₂+V₄=1

U₃+V₁=5

U₃+V₂=3

U₃+V₃=6

Чтобы решить эту систему примем одну переменную равной нулю.

U₁=0           V₁=1

U₂= 0          V₂= -1

U₃ = 4         V₃= 2

                    V₄=1

Для небазисных клеток находим оценки ∆_ij следующим образом: ∆_ij = U_i+V_j-C_ij  (для базисных клеток : ∆_ij = 0).

∆₁₂ =0-1-4= -5

∆₁₃ =0+2-1=1

∆₁₄ =0+1-3= -2

∆₂₁ =0+1-3= -2

∆₂₂ =0-1-2= -3

∆₃₄ =4+1-2=3 – максимальная оценка

Нарисуем цикл перерасчёта, начиная с клетки (3;4):

 Продолжение