В m пунктах отправления (ПО) имеется однородный груз в количествах а1,а2,....,ат. Этот груз нужно перевести в n пунктов назначения (ПН), потребности которых равны b1,b2,....,bт.. Стоимость перевозки единицы груза из i-го ПО в j-ый ПН равна сij.
Требуется решить транспортную задачу методом потенциалов и составить план перевозки грузов из ПО в ПН, при котором суммарные расходы на перевозку будут минимальными.
bj
ai 100 200 200 300
100 1 3 4 1
200 5 2 2 7
400 4 4 3 6
200 7 2 5 3
Решение
Суммарные запасы Σ аі = 100+200+400+200=900 ,
суммарные потребности Σ bj=100+200+200+300=800.
Σ аі ≠ Σ bj, запасы не равняются потребностям, то есть это открытая модель транспортной задачи, т.е. задача является не сбалансированной. Вводим фиктивного потребителя с потребностями b5 = 900800=100.
Составим математическую модель задачи.
Пусть хіj – количество груза, которое планируется перевезти от поставщика Аі потребителю Вj (это план перевозок). Тогда общая стоимость всех перевозок будет : Z = Σ Σ Cij хij, ее необходимо минимизировать.
Количество единиц груза не может быть отрицательной, поэтому
хіj ≥ 0.
Из условия задачи вытекает, что должны выполняться такие условия :
Σ хіj = аі , i =1,2,3,4, то есть весь груз со складов Аі необходимо вывезти.
Кроме того нужды потребителей Вj должны быть полностью удовлетворены, то есть Σ хіj = bj , j = 1,2,3,4,5.
Таким образом, математическая модель задачи имеет вид :
1413509120650Z = Σ Σ Cij хіj → min
Σ хіj = аі , і=1,2,3,4
Σ хіj = bj , j = 1,2,3,4,5.
хіj ≥ 0
00Z = Σ Σ Cij хіj → min
Σ хіj = аі , і=1,2,3,4
Σ хіj = bj , j = 1,2,3,4,5.
хіj ≥ 0
Для поиска начального опорного плана используем метод
“минимального элемента”.
Составим транспортную таблицу, в углы клеток запишем заданные тарифы Сіj, а в середины клеток будем последовательно заносить значения хіj по схеме :
Из всей таблицы стоимостей выбираем клетку АіВj с наименьшей стоимостью Сіj, то есть ищем min Сіj , и заносим в нее число хіj = min {аі , bj }
.
Потом вычеркиваем и больше не рассматриваем строку, которая отвечает поставщику, запасы которого полностью исчерпаны, или столбец, который отвечает потребителю, нужды которого полностью удовлетворенны.
В части таблицы, которая осталась после вычеркивания, снова ищем min Сіj и процесс распределения продолжаем до тех пор, пока все запасы не будут исчерпаны, а нужды – удовлетворены.
Таблица 1
В1 В2 В3 В4 В5
аі аі
А1 ___ 1 ___ 3 ___ 4
1 ___ 0
0
100
100
А2 ___ 5
2 ___ 2 ___ 7 ___ 0
200
0
200
А3
4 ___ 4
3 ___ 6
0
100
200
100
400 200,100
___ 7 ___ 2 ___ 5
3 ___ 0
А4
200
200
bj
100 200 200 300 100
bj
200
, строку А1 вычёркиваем.
, строку А2 и столбец В2 вычёркиваем.
, столбец В3 вычёркиваем.
.
, столбец В1 вычёркиваем.
В итоге таблица заполнена полностью