2. Нахождение оптимального плана методом потенциалов

2.1. Расчет потенциалов

Рассматриваемая транспортная задача содержит три поставщика (склады) и четыре потребителя (магазины). Им соответствуют потенциалы u₁,u₂ иu₃ для поставщиков и потенциалыv₁,v₂,v₃ и v₄ для потребителей.

Потенциалы поставщиков u_iи потребителейv_jнаходятся путем решения системы уравнений:

v_j – u_i = c_ij,

которые составляются для всех занятых клеток.

Выпишем эту систему уравнений для вычисления их значений.

Занятая клетка	Уравнение
(1, 1) (1, 2) (2, 2) (2, 3) (3, 3) (3, 4)	v1 – u1 = 4 v2 – u1 = 2 v2 – u2 = 3 v3 – u2 = 3 v3 – u3 = 2 v4 – u3 = 6

Эта система содержит 6 уравнений и 7 неизвестных. Полагая u₁= 0, найдем последовательно все потенциалы:v₁= 4,v₂= 2,u₂= -1,v₃= 2,u₃ = 0,v₄= 0 и занесем найденные значения в таблицу.

Таблица 3

	25	30	35	40
50	4	2	5	0	u1 = 0
	25	25
30	1	3	3	0	u2 = -1
		5	25
50	5	4	2	6	u3 = 0
			10	40
	v1 = 4	v2 = 2	v3 = 2	v4 = 0	Z = 260

Расчет потенциалов можно проводить, не решая систему уравнений, а непосредственно в таблице. Так, если известен потенциал поставщика u_i, то для вычисления потенциала потребителяv_j, соответствующего занятой клетке (i, j), следует использовать уравнение

v_j =u_i+с_ij.

Таким способом можно определить потенциалы всех поставщиков, которым соответствуют занятые клетки в i-й строке.

Например, если известно, что u₁= 0, то можно найти значения потенциалов первого и второго потребителя, которым соответствуют занятые клетки в первой строке:v₁=u₁+c₁₁= 0 + 4 = 4,v₂=u₁+c₁₂= 0 + 2 = 2.

В том случае, когда известен потенциал потребителя v_j, для вычисления потенциала поставщика u_i, соответствующего занятой клетке (i, j), следует использовать уравнение

u_i =v_j–с_ij.

Например, если известно, что v₃= 2, то можно найти значения второго и третьего поставщика, которым соответствуют занятые клетки в третьем столбце: u₂ = v₃  – c₂₃ = 2 – 3 = -1,u₃ = v₃  – c₃₃ = 2 – 2 = 0.

2.2. Проверка оптимальности

После того как все потенциалы найдены, следует для всех свободных клеток вычислить разности :

Δ₂₁= 4 – (-1 + 1) = 4, Δ₃₁= 4 – (0 + 5) = -1,

Δ₃₂= 2 – (0 + 4) = -2, Δ₁₃= 2 – (0 + 5) = -3,

Δ₁₄= 0 – (0 + 0) = 0, Δ₂₄= 0 – (0 + -1) = 1.

Среди вычисленных разностей имеются положительные. Значит, опорный план, построенный выше, не является оптимальным.

Замечание. По своему экономическому смыслу величина характеризует изменение в общих затратах на перевозки, которое произойдет, если будет осуществлена перевозка единицы груза от поставщикаi потребителю j. Поэтому, если > 0, то это означает, что существует свободное направление перевозки груза, экономящее затраты, т.е. текущий план перевозок не оптимален. Если же все , то это означает, что нет свободных направлений перевозок, экономящих затраты, т.е. текущий план перевозок оптимален.

Следующим этапом является построение нового опорного плана с меньшим значением целевой функции.