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

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

Проверим сбалансированность задачи.
Суммарные запасы товара у поставщиков: .
Суммарная потребность в товаре: .
Задача сбалансированная или закрытая, значит, имеет решение.
2) Построим начальный план перевозок методом минимального тарифа.
160 120 100 150 170
250 0
180 –6
270 –5
12 11 9 10 18
Поочередно распределили поставки в клетки с наименьшими тарифами из имеющихся на каждом шаге: (2,4), (2,2), (3,1), (1,3), (3,5), (1,2) и (1,5).
Суммарная стоимость перевозок равна
11∙90+9∙100+18∙60+5∙30+4∙150+7∙160+13∙110 = 6270.
3) Проверим невырожденность полученного плана перевозок .
m+n–1=3+5–1=7, где m – число поставщиков, n – число потребителей.
Число занятых клеток (клетки с поставками) равно 7.
Оба результата совпали, значит, план не вырожден.
4) Проверим полученный план на оптимальность методом потенциалов

.
m+n–1=3+5–1=7, где m – число поставщиков, n – число потребителей.
Число занятых клеток (клетки с поставками) равно 7.
Оба результата совпали, значит, план не вырожден.
4) Проверим полученный план на оптимальность методом потенциалов