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

Для решения задачи используем метод наименьшего элемента, который учитывает затраты на перевозку. Выбираем клетку с наименьшим тарифом (=2) и записываем в эту поставку (=110), исключаем один из пунктов или А_i, или B_j.

ai \ bi	110	130	60	90	430	Ui
120	6	2 110	3 10	4	5	0
140	7	4 20	5	8	3 120	2
250	2 110	6	4 50	4 90	6	1
310	4	5	6	7	1 310	0
Vi	1	2	3	3	1

 

Число заполненных клеток m + n – 1 = 8.

Затраты: z = 110*2 + 10*3 + 20*4 + 120*3 + 110*2 + 50*4 + 90*4 + 310*1 = 1800

Транспортную задачу решаем методом потенциалов. Каждой строке таблицы и каждому столбцу ставится в соответствие число, называемое потенциалом.

Алгоритм метода потенциалов 

1. Потенциалы строк – U_i и столбцов – V_j удовлетворяют следующему условию: U_i + V_j = C_ij для базисных переменных (для занятых клеток). Так как система для определения потенциалов содержит на одно уравнение меньше, чем число потенциалов, то, чтобы найти решение системы потенциалов, один потенциал задаём произвольно, например, U₁=0.

Остальные потенциалы найдем, решая систему уравнений

2. Определяем характеристики для свободных неизвестных (пустых клеток) по формуле E_ij = C_ij – (U_i + V_j) и записываем их в левом нижнем углу свободных клеток. План будет оптимален, если для всех свободных неизвестных E_ij0.

E₁₁ = 6 – (1+0) > 0, E₁₄ = 4 – (3+ 0)> 0,   E₁₅ = 5 – (1+0) > 0

E₂₁ = 7 – (1+2) > 0, E₂₃ = 5 – (3+ 2)  0,   E₂₄ = 8 – (3+2) > 0

E₃₂ = 6 – (2+1) > 0, E₃₅ = 6 – (1+ 1)> 0

E₄₁ = 4 – (1+0) > 0, E₄₂ = 5 – (2+ 0)> 0,   E₄₃ = 6 – (3+0) > 0, E₄₄ = 7 – (3+0) > 0

Данный план является оптимальным.

Затраты : z = 110*2 + 10*3 + 20*4 + 120*3 + 110*2 + 50*4 + 90*4 + 310*1 = 1800