На трёх станциях сосредоточен однородный груз, который следует перевезти в четыре пункта назначения

Пример 1:

На трёх станциях сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.

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

 

Поставщик	B1	B2	B3	B4	Запасы груза
A1	4	6	19	21	100
A2	29	4	8	6	150
A3	7	11	13	14	200
Потребность	220	80	75	75

Решение от преподавателя:

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100 + 150 + 200 = 450
∑b = 220 + 80 + 75 + 75 = 450
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	4	6	19	21	100
2	29	4	8	6	150
3	7	11	13	14	200
Потребности	220	80	75	75

Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

	1	2	3	4	Запасы
1	4[100]	6	19	21	100
2	29	4[80]	8	6[70]	150
3	7[120]	11	13[75]	14[5]	200
Потребности	220	80	75	75

Значение целевой функции для этого опорного плана равно:
F(x) = 4*100 + 4*80 + 6*70 + 7*120 + 13*75 + 14*5 = 3025
Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₃ + v₁ = 7; 4 + u₃ = 7; u₃ = 3
u₃ + v₃ = 13; 3 + v₃ = 13; v₃ = 10
u₃ + v₄ = 14; 3 + v₄ = 14; v₄ = 11
u₂ + v₄ = 6; 11 + u₂ = 6; u₂ = -5
u₂ + v₂ = 4; -5 + v₂ = 4; v₂ = 9

	v1=4	v2=9	v3=10	v4=11
u1=0	4[100]	6	19	21
u2=-5	29	4[80]	8	6[70]
u3=3	7[120]	11	13[75]	14[5]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(1;2): 0 + 9 > 6; ∆₁₂ = 0 + 9 - 6 = 3
(3;2): 3 + 9 > 11; ∆₃₂ = 3 + 9 - 11 = 1
max(3,1) = 3
Выбираем максимальную оценку свободной клетки (1;2): 6
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	4[100][-]	6[+]	19	21	100
2	29	4[80][-]	8	6[70][+]	150
3	7[120][+]	11	13[75]	14[5][-]	200
Потребности	220	80	75	75

Цикл приведен в таблице (1,2 → 1,1 → 3,1 → 3,4 → 2,4 → 2,2).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	4[95]	6[5]	19	21	100
2	29	4[75]	8	6[75]	150
3	7[125]	11	13[75]	14	200
Потребности	220	80	75	75

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 4; 0 + v₁ = 4; v₁ = 4
u₃ + v₁ = 7; 4 + u₃ = 7; u₃ = 3
u₃ + v₃ = 13; 3 + v₃ = 13; v₃ = 10
u₁ + v₂ = 6; 0 + v₂ = 6; v₂ = 6
u₂ + v₂ = 4; 6 + u₂ = 4; u₂ = -2
u₂ + v₄ = 6; -2 + v₄ = 6; v₄ = 8

	v1=4	v2=6	v3=10	v4=8
u1=0	4[95]	6[5]	19	21
u2=-2	29	4[75]	8	6[75]
u3=3	7[125]	11	13[75]	14

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 4*95 + 6*5 + 4*75 + 6*75 + 7*125 + 13*75 = 3010