Решить транспортную задачу. Имеются четыре пункта поставки однородного груза A1, A2, A3, A4, в каждом из которых находится груз соответственно в количестве a1, a2, a3, a4 тонн и пять пунктов потребления этого груза B1, B2, B3, B4, B5. В пункты B1, B2, B3, B4, B5 требуется доставить соответственно b1, b2, b3, b4, b5 тонн груза. Транспортные расходы при перевозке единицы груза из пункта Ai в пункт Bj равны cij, где i=1, 2, 3, 4, j=1, 2, 3, 4, 5. Найти такой план закрепления потребителей за поставщиками, чтобы затраты по перевозкам были минимальными, учитывая:
,
,
.
Решение:
xij – стоимость перевозки груза из i-го пункта поставки в j-й пункт назначения, xij≥0, i=1,4, j=1,5.
Тогда общие затраты на перевозки равны:
F=i=14j=15cijxij
(1)
Сведем исходные данные в таблицу 1.
Таблица 1
Пункты отправления Пункты назначения
Запасы
B1
B2
B3
B4
B5
A1
17 20 29 26 25 15
A2
3 4 5 15 24 15
A3
19 2 22 4 13 15
A4
20 27 1 17 19 15
Потребности 11 11 11 11 16
Найдем суммарные запасы:
i=14ai=15+15+15+15=60
Найдем суммарные потребности:
j=15bj=11+11+11+11+16=60
Т.к. суммарные запасы равны суммарным потребностям, то имеем закрытую модель транспортной задачи.
Построение исходного опорного плана методом минимальных тарифов.
В таблице 1 находим клетку с наименьшей себестоимостью. Это клетка (4, 3). В нее записываем перевозку, которая максимально удовлетворит потребности третьего пункта назначения из соответствующего запаса пункта A4 – . Таким образом, потребности в третьем пункте назначения полностью удовлетворены (отразим это в последней строке). Поэтому в остальных клетках третьего столбца проставляем нули. Запасы в четвертом пункте назначения уменьшились на 11, отразим это в последнем столбце.
Снова находим клетку с наименьшей себестоимостью. Это клетка (3, 2). В нее записываем перевозку, которая максимально удовлетворит потребности во втором пункте назначения из соответствующего запаса пункта A3 – 11. Таким образом, потребности во втором пункте назначения полностью удовлетворены (отразим это в последней строке). Поэтому в остальных клетках второго столбца проставляем нули. Запасы груза в третьем пункте отправления уменьшились на 11, отразим это в последнем столбце.
Снова находим клетку с наименьшей себестоимостью. Это клетка (2, 1). В нее записываем перевозку, которая максимально удовлетворит потребности первого пунк4та назначения из соответствующего запаса пункта отправления A2 – 11. Таким образом, запасы во втором пункте отправления полностью исчерпаны (отразим это в последнем столбце), поэтому в остальных клетках первого столбца проставляем нули. Запасы груза во втором пункте отправления уменьшились на 11, отразим это в последнем столбце.
Снова находим клетку с наименьшей себестоимостью. Это клетка (3, 4). В нее записываем поставку, которая максимально удовлетворит потребности в четвертом пункте назначения из соответствующего запаса пункта A3 – 4 (не забывая, что запасы уже уменьшались). Таким образом, запасы в третьем пункте полностью исчерпаны (отразим это в последнем столбце), поэтому в остальных пустых клетках третьей строки проставляем нули. Потребности в четвертом пункте назначения уменьшились на 4 (отразим это в последней строке).
Снова находим клетку с наименьшей себестоимостью. Это клетка (2, 4). В нее записываем поставку, которая максимально удовлетворит потребности в четвертом пункте назначения из соответствующего запаса пункта A2 – 4 (не забывая, что запасы и потребности уже уменьшались). Таким образом, запасы во втором пункте полностью исчерпаны (отразим это в последнем столбце), поэтому в остальных пустых клетках второй строки проставляем нули. Потребности в четвертом пункте назначения уменьшились на 4 (отразим это в последней строке).
Снова находим клетку с наименьшей себестоимостью. Это клетка (4, 4). В нее записываем поставку, которая максимально удовлетворит потребности в четвертом пункте назначения из соответствующего запаса пункта A4 – 3 (не забывая, что запасы и потребности уже уменьшались). Таким образом, запасы в четвертом пункте уменьшились на 3 (отразим это в последнем столбце). Потребности в четвертом пункте назначения уменьшились на 3 (отразим это в последней строке).
Снова находим клетку с наименьшей себестоимостью. Это клетка (4, 5). В нее записываем поставку, которая максимально удовлетворит потребности в пятом пункте назначения из соответствующего запаса пункта A4 – 1 (не забывая, что запасы и потребности уже уменьшались). Таким образом, запасы в четвертом пункте уменьшились на 1 (отразим это в последнем столбце). Потребности в пятом пункте назначения уменьшились на 1 (отразим это в последней строке).
Снова находим клетку с наименьшей себестоимостью. Это клетка (1, 5). В нее записываем поставку, которая максимально удовлетворит потребности в пятом пункте назначения из соответствующего запаса пункта A1 – 15 (не забывая, что запасы и потребности уже уменьшались). Таким образом, запасы в первом пункте исчерпаны полностью1 (отразим это в последнем столбце). Потребности в пятом пункте назначения полностью удовлетворены (отразим это в последней строке).
В результате получаем опорный план, представленный в таблице 2.
Таблица 2
Пункты отправления Пункты назначения
Запасы
B1
B2
B3
B4
B5
A1
17
0 20
0 29
0 26
0 25
15 15
A2
3
11 4
0 5
0 15
4 24
0 15
A3
19
0 2
11 22
0 4
4 13
0 15
A4
20
0 27
0 1
11 17
3 19
1 15
Потребности 11 11 11 11 16
Проверим опорный план на вырожденность. Количество ненулевых клеток равно 8. Значение n+m-1 тоже равно 8. Значит, полученный план – невырожденный.
Себестоимость перевозок при данном опорном плане:
F=25∙15+3∙1+15∙4+2∙1+4∙4+1∙11+17∙3+19∙1=537
Проверка опорного плана на оптимальность. Чтобы установить, является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции любое возможное перераспределение перевозок.
План распределения выпуска будет оптимальным лишь в том случае, когда целевая функция имеет минимальное значение, т.е. когда дальнейшее уменьшение затрат на перевозку будет невозможно.
Проверим найденный план на оптимальность методом потенциалов.
Находим потенциалы ui каждого поставщика и vj каждого потребителя, составив для каждой занятой клетки уравнение vj+ui=cij.
u1+v5=25u2+v1=3u2+v4=15u3+v2=2u3+v4=4u4+v3=1u4+v4=17u4+v5=19⟺u1=0u2=-8u3=-19u4=-6v1=11v2=21v3=7v4=23v5=25
Для каждой свободной клетки находим величину ∆ ij=ui+vj-cij.
∆ 11=0+11-17=-6
∆ 12=0+21-20=1>0
∆ 13=0+7-29=-22
∆ 14=0+23-26=-3
∆ 22=-8+21-4=9>0
∆ 23=-8+7-5=-6
∆ 25=-8+25-24=-7
∆ 31=-19+11-19=-27
∆ 33=-19+7-22=-34
∆35=-19+25-13=-7
∆ 41=-6+11-20=-15
∆ 42=-6+21-27=-12
Среди оценок ∆ ij есть положительные, значит, найденный опорный план не является оптимальным.
Максимальная оценка ∆ 22=9, следовательно, клетку (2,2) следует заполнить, изменив объемы поставок в соседних клетках с помощью цикла.
Цикл строим в таблице 3. Проставляем в связанных клетках «–» и «+», перераспределяем минимальное значение в минусовых клетках: 4. Получили новый опорный план.
Таблица 3
Пункты отправления Пункты назначения
Запасы
B1
B2
B3
B4
B5
A1
17
0 20
0 29
0 26
0 25
15 15
A2
3
11 +4
4 5
0 –15
0 24
0 15
A3
19
0 –2
7 22
0 +4
8 13
0 15
A4
20
0 27
0 1
11 17
3 19
1 15
Потребности 11 11 11 11 16
Проверим новый план на оптимальность методом потенциалов.
Находим потенциалы ui каждого поставщика и vj каждого потребителя, составив для каждой занятой клетки уравнение vj+ui=cij.
u1+v5=25u2+v1=3u2+v2=4u3+v2=2u3+v4=4u4+v3=1u4+v4=17u4+v5=19⟺u1=0u2=-17u3=-19u4=-6v1=20v2=21v3=7v4=23v5=25
Для каждой свободной клетки находим величину ∆ ij=ui+vj-cij.
∆ 11=0+20-17=3>0
∆ 12=0+21-20=1>0
∆ 13=0+7-29=-22
∆ 14=0+23-26=-3
∆ 24=-17+23-15=-9
∆ 23=-17+7-5=-15
∆ 25=-17+25-24=-18
∆ 31=-19+20-19=-18
∆ 33=-19+7-22=-34
∆35=-19+25-13=-7
∆ 41=-6+20-20=-6
∆ 42=-6+21-27=-12
Среди оценок ∆ ij есть положительные, значит, найденный опорный план не является оптимальным.
Максимальная оценка ∆ 11=3, следовательно, клетку (1,1) следует заполнить, изменив объемы поставок в соседних клетках с помощью цикла.
Цикл строим в таблице 4. Проставляем в связанных клетках «–» и «+», перераспределяем минимальное значение в минусовых клетках: 4. Получили новый опорный план.
Таблица 4
Пункты отправления Пункты назначения
Запасы
B1
B2
B3
B4
B5
A1
+17
3 20
0 29
0 26
0 –25
12 15
A2
–3
8 +4
7 5
0 15
0 24
0 15
A3
19
0 –2
4 22
0 +4
11 13
0 15
A4
20
0 27
0 1
11 –17
0 +19
4 15
Потребности 11 11 11 11 16
Проверим новый план на оптимальность методом потенциалов.
Находим потенциалы ui каждого поставщика и vj каждого потребителя, составив для каждой занятой клетки уравнение vj+ui=cij.
u1+v5=25u2+v1=3u2+v2=4u3+v2=2u3+v4=4u4+v3=1u1+v1=17u4+v5=19⟺u1=0u2=-14u3=-16u4=-6v1=17v2=18v3=7v4=20v5=25
Для каждой свободной клетки находим величину ∆ ij=ui+vj-cij.
∆ 44=-6+20-17=-3
∆ 12=0+18-20=-2
∆ 13=0+7-29=-22
∆ 14=0+20-26=-26
∆ 24=-14+20-15=-9
∆ 23=-14+7-5=-12
∆ 25=-14+25-24=-13
∆ 31=-16+17-19=-18
∆ 33=-16+7-22=-31
∆35=-16+25-13=-4
∆ 41=-6+17-20=-9
∆ 42=-6+18-27=-15
Среди оценок ∆ ij нет положительных, значит, найденный опорный план (представлен в таблице 4) является оптимальным.
Стоимость перевозок при данном опорном плане:
F=17∙3+25∙12+3∙8+4∙7+2∙4+4∙11+1∙11+19∙4=542
X*=38000740000110120110004 – оптимальный план перевозок, при котором стоимость перевозок минимальна и равна 517.
