Транспортная задача, задача о выборе, задача о размещении)

Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1, А2, А3 находится груз в количествах 90, 70, 110 тонн. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно 50, 60, 50, 40, 70 тонн груза. Расстояния в сотнях километрах между пунктами поставки и потребления приведены в матрице-таблице D:

Найти такой план перевозок, при котором общие затраты будут минимальными.

УКАЗАНИЕ. 1) Считать стоимость перевозок пропорциональной количеству груза и расстоянию, на которое этот груз перевозится, т.е. для решения задачи достаточно минимизировать общий объем плана, выраженный в тонно-километрах.
2) для решения задачи использовать методы северо-западного угла и потенциалов.

Решение.

Составим математическую модель задачи:

Обозначим - количество груза, перевезенного от поставщика i к потребителю j.

Становятся очевидными следующие ограничения (т.к. весь груз должен быть вывезен, и все потребности удовлетворены полностью):

При этом должна быть минимизирована целевая функция

Построим опорный план методом северо-западного угла:

Принцип заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки (принцип северо-западного угла), количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился.

Построим систему потенциалов. - потенциалы, соответствующие поставщикам, - потенциалы, соответствующие потребителям.
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V1 = 9 V1 = 9
U1 + V2 = 1 V2 = 1
U2 + V2 = 4 U2 = 3
U2 + V3 = 6 V3 = 3
U3 + V4 = 5 U3 = 0 V4 = 5
U3 + V5 = 3 V5 = 3

Проверим критерий оптимальности: Ui + Vj dij для свободных клеток.

U1 + V3 = 3>1 на 2
U1 + V4 = 5=5
U1 + V5 = 3<6
U2 + V1 = 12>6 на 6
U2 + V4 = 8=8
U2 + V5 = 6>5 на 1
U3 + V1 = 9>2 на 7
U3 + V2 = 1<9
U3 + V3 = 3=3

Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – ячейка (3, 1)

Перебросим в ячейку (3, 1) 50 единиц груза из ячейки (1, 1).
Чтобы компенсировать недостаток в первой строке, перебросим те же 50 единиц груза из ячейки (2, 3) в ячейку (1, 3).
Теперь чтобы компенсировать недостаток в строке 2, перебросим из ячейки
(3, 5) 50 единиц в ячейку (2, 5).

Таким образом, образовался цикл, показанный в таблице пунктиром.