Найти оптимальный план перевозок груза

Сущность транспортной задачи состоит в нахождении плана перевозок однородного груза (уголь, картошка, цемент и т.п.) от определенных поставщиков к определенным же потребителям. Известны возможности каждого поставщика и каждого потребителя в этом грузе. Также известен тариф - стоимость перевозки единицы груза по каждому маршруту.
Транспортная задача может быть решена одним из методов, если мы имеем закрытую модель задачи. Задача имеет закрытую модель, если суммарные ресурсы поставщиков равны суммарным потребностям потребителей. Это значит, что задача решается только тогда, когда
i=1nai=k=1mbk,
где ai - количество единиц груза, которыми обладает i-й поставщик, а bk - количество единиц груза, составляющие потребность -го потребителя.
В заданной задаче находим суммарные ресурсы и суммарные потребности:
i=14ai=30+24+43+11=108,
k=15bk=16+29+13+21+29=108.
Таким образом, имеем закрытую модель транспортной задачи.
Начинается решение задачи с составления исходного плана перевозок.
Строим исходный план перевозок по правилу северо-западного угла. Т.е. начинаем заполнять таблицу перевозок, начиная с левой верхней клетки таблицы. При заполнении анализируем величину потребности (оставшейся) с величиной потребностей (не удовлетворенной) и заполняем клетку минимальным значением этих величин. Затем «двигаемся» по строке или столбцу неудовлетворенной потребности или ресурса в соседнюю клетку . Это повторяем, пока не составим план перевозок, выбирающий все ресурсы и удовлетворяющий все потребности. Число занятых клеток при этом должно быть равно m+n-1, где m - число поставщиков, n число потребителей. В нашем случае это значение равно 4+5-1=8.
Поставщики и
их мощности Потребители и их спрос
В1
В2
В3 В4
В5
16 29 13 21 29
А1
30 3
16 8
14 1 5 4
А2
24 6 6
15 3
9 1 2
А3 43 2 4 5
4 8
21 7
18
А4
11 5 6 7 2 3
11
Величина груза, перевозимого по каждому маршруту, указана красными цифрами.
Оценим построенное решение. Для этого выписываем матрицу затрат и в ней подчеркиваем элементы, соответствующие занятым клеткам построенного (исходного) решения.
3 8 1 5 4 +0
6 6 3 1 2 +2
2 4 5 8 7 +0
5 6 7 2 3 +4
-3 -8 -5 -8 -7
Справа и снизу подобраны числа - потенциалы, прибавление которых к строкам и столбцам матрицы затрат приводит к получению матрицы оценок. В этой матрице нулевые значения имеют элементы, соответствующие занятым клеткам построенного решения.
Построенное (исходное) решение представлено справа в таблице ниже. Его оценочная матрица в этой же таблице слева.
+5
+5 0 0 -4 -3 -3
16 14
5 0 0 -5 -3
15 32639085090318770850909- 2603585090+
-1 -4 0 0 0
326390908054+ 21- 18
6 2 6 -2 0
11
-5 -5
D=min{9,21}=9
Мы видим, что построенный план перевозок не оптимальный, так как в матрице оценок имеются отрицательные оценки.
Выбираем клетку (2;4) с отрицательной оценкой и строим цикл пересчета полученного плана перевозок