Задача №338
Имеются три пункта поставки однородного груза А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 |
В3 |
В4 |
В5 |
|
|
А1 |
9 |
1 |
1 |
5 |
6 |
|
А2 |
6 |
4 |
6 |
8 |
5 |
|
А3 |
2 |
9 |
3 |
5 |
3 |
Найти такой
план перевозок, при котором общие затраты будут минимальными.
УКАЗАНИЕ. 1) Считать стоимость перевозок пропорциональной
количеству груза и расстоянию, на которое этот груз перевозится, т.е. для
решения задачи достаточно минимизировать общий объем плана, выраженный в
тонно-километрах.
2) для решения задачи использовать методы северо-западного
угла и потенциалов.
Составим математическую модель задачи:
Обозначим 
- количество груза,
перевезенного от поставщика i к потребителю j.
Становятся очевидными следующие ограничения (т.к. весь
груз должен быть вывезен, и все потребности удовлетворены полностью):
При этом должна быть минимизирована целевая функция
Построим
опорный план методом северо-западного угла:
|
Пункты поставки |
Пункты потребления |
Запасы |
||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
||
|
А1 |
9 50 |
1 40 |
1 |
5 |
6 |
90 |
|
А2 |
6 |
4 20 |
6 50 |
8 |
5 |
70 |
|
А3 |
2 |
9 |
3 |
5 40 |
3 70 |
110 |
|
Потребности |
50 |
60 |
50 |
40 |
70 |
270 |
Принцип
заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки
(принцип северо-западного угла), количество грузов вписывается в таблицу так,
чтобы потребности полностью удовлетворялись или груз полностью вывозился.
Построим
систему потенциалов. 
- потенциалы,
соответствующие поставщикам, 
- потенциалы, соответствующие
потребителям.
Полагаем 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
|
Пункты поставки |
|
Пункты потребления |
Запасы |
||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
|
|
V1=9 |
V2=1 |
V3=3 |
V4=5 |
V5=3 |
|
|
А1 |
U1=0 |
9 50 |
1 40 |
1 |
5 |
6 |
90 |
|
А2 |
U2=3 |
6 |
4 20 |
6 50 |
8 |
5 |
70 |
|
А3 |
U3=0 |
2 |
9 |
3 |
5 40 |
3 70 |
110 |
|
Потребности |
|
50 |
60 |
50 |
40 |
70 |
270 |
Проверим критерий оптимальности : 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).
Таким
образом, образовался цикл, показанный в таблице пунктиром.
Получаем новую таблицу, для которой повторяем расчет
потенциалов:
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1
+ V2 = 1 V2 = 1
U1
+ V3 = 1 V3 = 1
U2
+ V2 = 4 U2 = 3
U2
+ V5 = 5 V5 = 2
U3
+ V5 = 3 U3 = 1
U3
+ V1 = 2 V1 = 5
U3
+ V4 = 5 V4 = 4
|
Пункты поставки |
|
Пункты потребления |
Запасы |
||||
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||
|
|
|
V1=1 |
V2=1 |
V3=1 |
V4=4 |
V5=2 |
|
|
А1 |
U1=0 |
9 |
1 40 |
1 50 |
5 |
6 |
90 |
|
А2 |
U2=3 |
6 |
4 20 |
6 |
8 |
5 50 |
70 |
|
А3 |
U3=1 |
2 50 |
9 |
3 |
5 40 |
3 20 |
110 |
|
Потребности |
|
50 |
60 |
50 |
40 |
70 |
270 |
Проверим критерий оптимальности : Ui + Vj dij для свободных клеток.
U1
+ V1 = 1<9
U1
+ V4 = 4<5
U1
+ V5 = 2<6
U2
+ V1 = 4<6
U2
+ V3 =4<6
U2 + V4 =7<8
U3 + V2 =2<9
U3 + V3 =2<3
Критерий выполнен, значит, полученное решение оптимально.
Найдем
минимальную стоимость перевозок.
