Имеются три пункта поставки однородного груза A1

Проверка сбалансированности транспортной задачи
Общий объем груза у поставщиков:
i=13ai=200+350+290=840
Объем груза, необходимый потребителям:
j=14bj=150+100+250+340=840
Т.к. суммарные запасы равны суммарным потребностям, то имеем сбалансированную транспортную задачу.
Сведем исходные данные в таблицу 1.
Таблица 1
Поставщики Потребности Запасы
B1
B2
B3
B4
A1
9
4
6
6 200
A2
17
11
15
7 350
A3
20
9
15
25 290
Потребности 150 100 250 340
Найдем опорный план методом наименьших тарифов.
Определяем клетку с наименьшим тарифом. Это клетка (1,2) Помещаем в нее максимально возможную перевозку 100, а в остальные клетки второго столбца вычеркиваем из рассмотрения, т.к. потребности второго потребителя удовлетворены. Запасы первого поставщика уменьшились и стали равны 200–100=100.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (1,3) и (1,4). Выбираем любую их них, например (1,3), т.к. через них можно выполнить одинаковые перевозки. Помещаем в нее максимально возможную перевозку: 100. Запасы первого поставщика исчерпаны, поэтому клетки первой строки вычеркиваем из рассмотрения. Потребности второго третьего потребителя уменьшились и стали равны: 250–100=150.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (2,4). Помещаем в нее максимально возможную перевозку: 340. Потребности четвертого потребителя удовлетворены, поэтому остальные клетки четвертого столбца вычеркиваем из рассмотрения. Запасы второго поставщика уменьшились и стали равны: 350–340=10.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетки (2,3) и (3,3). Выбираем клетку (3,3), т.к. в нее можно поместить большую перевозку. Помещаем в нее максимально возможную перевозку: 150. Потребности третьего потребителя удовлетворены . Запасы третьего поставщика уменьшились и стали равны: 290–150=140.
Среди оставшихся клеток снова ищем клетку с наименьшим тарифом. Это клетка (2,1). Помещаем в нее максимально возможную перевозку: 10. Запасы второго поставщика исчерпаны. Потребности первого потребителя уменьшились и стали равны 150–10=140.
Последнюю пустую клетку (3,1) заполняем нераспределенной перевозкой: 140.
Количество заполненных клеток равно 6=3+4-1, поэтому опорный план невырожденный. Полученный опорный план представлен в таблице 2.
Таблица 2
Поставщики Потребности Запасы
B1
B2
B3
B4
A1
9
4
6
6 200
100
100
A2
17
11
15
7 350
10
340
A3
20
9
15
25 290
140
150
Потребности 150 100 250 340
Проверка опорного плана (таблица 2) на оптимальность методом потенциалов
Определим потенциалы каждого поставщика Ai и каждого потребителя Bj.
Для этого поставим в соответствие:
поставщику A1 – потенциал p1;
поставщику A2 – потенциал p2
поставщику A3 - потенциал p3;
потребителю B1 – потенциал q1;
потребителю B2 – потенциал q2;
потребителю B3 – потенциал q3;
потребителю B4 – потенциал q4.
Для каждой заполненной клетки составим уравнение pi+qj=cij. Получим и решим систему уравнений. Поскольку число неизвестных превышает на 1 число уравнений, то положим, например, p1=0.
p1+q2=4p1+q3=6p2+q1=17p2+q4=7p3+q1=20p3+q3=15⟺p1=0p2=6p3=9q1=11q2=4q3=6q4=1
Занесем найденные потенциалы в таблицу с опорным планом. В результате получим таблицу 3.
Таблица 3
Поставщики Потребности pi
B1
B2
B3
B4
A1
9
4
6
6 0
100
100
A2
17
11
15
7 6
10
340
A3
20
9
15
25 9
140
150
qj
11 4 6 1
Для каждой свободной клетки найдем оценку ∆ ij=pi+qj-cij.
∆ 11=11+0-9=2
∆ 14=1+0-6=-5
∆22=4+6-11=-1
∆ 23=6+6-15=-3
∆ 32=4+9-9=4
∆ 34=1+9-25=-15
Среди оценок ∆ ij есть положительные, значит, найденный опорный план (таблица 2) является оптимальным