В клетках каждой из следующих таблиц указаны значения величины - тарифы перевозки единицы груза из i-го пункта отправления (от поставщика с номером i) в j-й пункт назначения (потребителю с номером j). В столбце справа за пределами таблицы записаны запасы груза (продукции, товара) в i-м пункте отправления; внизу под таблицей, за ее пределами, указаны потребности в грузе в j-м пункте назначения.
15 23 26 19 18 300
18 30 35 25 40 350
12 14 22 20 35 130
10 28 23 19 30 70
145 195 200 140 170
Решение
Проверка сбалансированности транспортной задачи
Общие запасы продукции:
i=14ai=300+350+130+70=850
Общие потребности потребителей:
j=15bj=145+195+200+140+170=850
Т.к. суммарные запасы равны суммарным потребностям, то имеем сбалансированную транспортную задачу.
Математическая модель задачи
Обозначим: xij – объем перевозки от i-го производителя j-му потребителю (i=1,4, j=1,5).
Тогда суммарная стоимость перевозок равна (целевая функция):
ZX=i=14j=15cijxij
Ограничения:
Запасы груза у поставщиков:
j=15x1j=300
j=15x2j=350
j=15x3j=130
j=15x4j=70
Потребности потребителей
i=14xi1=145
i=14xi2=195
i=14xi3=200
i=14xi4=140
i=14xi5=170
Объем перевозок не может быть отрицательным числом
xij≥0 (i=1,4, j=1,5)
Найдем опорный план перевозок методом наименьшей стоимости (таблица 1)
Определяем клетку с наименьшей стоимостью – это клетка (4,1). Помещаем в нее максимально возможную перевозку: 70. При этом запасы четвертого поставщика исчерпаны, поэтому остальные клетки четвертой строки вычеркиваем из рассмотрения. Потребности первого потребителя уменьшились и стали равны: 145-70=75.
Среди оставшихся клеток снова ищем клетку с наименьшей стоимостью. Это клетка (3,1). Помещаем в нее максимально возможную перевозку: 75, а в остальные клетки первого столбца вычеркиваем из рассмотрения, т.к. потребности первого потребителя удовлетворены. Запасы третьего поставщика уменьшились и стали равны 130-75=55.
Среди оставшихся клеток снова ищем клетку с наименьшей стоимостью. Это клетка (3,2). Помещаем в нее максимально возможную перевозку: 55, а остальные клетки третьей строки вычеркиваем из рассмотрения, т.к. запасы третьего потребителя исчерпаны. Потребности второго потребителя уменьшились и стали равны: 195-55=140.
Среди оставшихся клеток снова ищем клетку с наименьшей стоимостью. Это клетка (1,5). Помещаем в нее максимально возможную перевозку: 170. Запасы первого поставщика уменьшились и стали равны: 300-170=130. Потребности пятого потребителя удовлетворены, поэтому остальные клетки пятого столбца вычеркиваем из рассмотрения.
Среди оставшихся клеток снова ищем клетку с наименьшей стоимостью. Это клетка (1,4). Помещаем в нее перевозку: 130. Запасы первого поставщика исчерпаны, остальные клетки первой строки не рассматриваем. Потребности четвертого потребителя уменьшились и стали равны: 10.
Среди оставшихся клеток снова ищем клетку с наименьшей стоимостью. Это клетка (2,4). Помещаем в нее перевозку: 10. Запасы второго поставщика уменьшились и стали равны: 340-140=200. Потребности четвертого потребителя удовлетворены.
Среди оставшихся клеток снова ищем клетку с наименьшей стоимостью. Это клетка (2,2). Помещаем в нее перевозку: 140. Запасы второго поставщика уменьшились и стали равны: 350-10=340
. Потребности второго потребителя удовлетворены.
Последнюю пустую клетку (2,3) заполняем нераспределенной перевозкой: 200.
Количество заполненных клеток равно 8=4+5-1, поэтому опорный план невырожденный.
Полученный опорный план представлен в таблице 1.
Таблица 1
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
15
23
26
19
18 300
130
170
A2
18
30
35
25
40 350
140
200
10
A3
12
14
22
20
35 130
75
55
A4
10
28
23
19
30 70
70
Потребности 145 195 200 140 170
Стоимость перевозок при этом плане равна:
Z1=130∙19+170∙18+140∙30+200∙35+10∙25+75∙12+55∙14+70∙10=19350
Проверка опорного плана (таблица 1) на оптимальность методом потенциалов
Определим потенциалы каждого поставщика Ai и каждого потребителя Bj.
Для этого поставим в соответствие: поставщику Ai – потенциал pi (i=1,4); потребителю Bj – потенциал qj (j=1,5).
Для каждой заполненной клетки составим уравнение pi+qj=cij. Получим и решим систему уравнений. Поскольку число неизвестных превышает на 1 число уравнений, то положим, например, p2=0.
p1+q4=19p1+q5=18p2+q2=30p2+q3=35p2+q4=25p3+q1=12p3+q2=14p4+q1=10⟺p1=-6p2=0p3=-16p4=-18q1=28q2=30q3=35q4=25q5=24
Занесем найденные потенциалы в таблицу с опорным планом. В результате получим таблицу 2.
Таблица 2
Поставщики Потребители pi
B1
B2
B3
B4
B5
A1
15
23
26
19
18 -6
130
170
A2
18
30
35
25
40 0
140
200
10
A3
12
14
22
20
35 -16
75
55
A4
10
28
23
19
30 -18
70
qj
28 30 35 25 24
Для каждой свободной клетки найдем оценку ∆ ij=pi+qj-cij.
∆ 11=28-6-15=7
∆ 12=30-6-23=1
∆ 13=35-6-26=3
∆21=28+0-18=10
∆ 25=24+0-40=-16
∆ 33=35-16-22=-3
∆ 34=25-16-20=-11
∆ 35=24-16-35=-27
∆ 42=30-18-28=-16
∆ 43=35-18-23=-6
∆ 44=25-18-19=-12
∆ 45=24-18-30=-24
Среди оценок ∆ ij есть положительные, значит, найденный опорный план (таблица 1) не является оптимальным. Максимальная оценка – в клетке (2,1). Клетку (2,1) будем заполнять с помощью цикла пересчета. Цикл строим в таблице 3. Перемещаем по циклу минимальную перевозку в «минусовых» клетках: 75
Таблица 3
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
15
23
26
19
18 300
130
170
A2
+ 18 – 30
35
25
40 350
140
200
10
A3
– 12 + 14
22
20
35 130
75
55
A4
10
28
23
19
30 70
70
Потребности 145 195 200 140 170
Получим новый опорный план, представленный в таблице 4.
Таблица 4
Поставщики Потребители Запасы
B1
B2
B3
B4
B5
A1
15
23
26
19
18 300
130
170
A2
18
30
35
25
40 350
75
65
200
10
A3
12
14
22
20
35 130
130
A4
10
28
23
19
30 70
70
Потребности 145 195 200 140 170
Стоимость перевозок при этом плане равна:
Z2=130∙19+170∙18+75∙18+65∙30+200∙35+10∙25+130∙14+70∙10=18600
Проверка опорного плана (таблица 4) на оптимальность методом потенциалов
Для каждой заполненной клетки составим уравнение pi+qj=cij
Задать вопрос
на новый заказ в Автор24.
