Задача №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

 

         Критерий выполнен, значит, полученное решение оптимально.

         Найдем минимальную стоимость перевозок.