Задача 37

Имеется три пункта поставки однородного груза А1, А2, А3 и пять пунктов потребления груза B1, B2, B3, B4. На пунктах А1, А2, А3 находится груз соответственно в количестве150, 250, 200 тонн. В пункты B1, B2, B3, B4 требуется доставить соответственно 180, 120, 90, 105 и 105 тонн груза. Затраты на перевозку 1 т. груза между пунктами поставки и пунктами потребления приведены в матрице С (в тыс. руб.):

14

6

4

9

4

17

10

9

11

5

15

11

6

13

8


где Сij – стоимость перевозки 1 тонны груза от поставщика с номером i (i=1, 2 ,3) к потребителю с номером j (j=1, 2, 3, 4, 5).

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


Решение:

Данные задачи запишем в виде матрицы перевозок (таблица 1).

Базы

Потребители

Запасы

B1

B2

B3

B4

B5

А1

14

6

4

9

4

150

А2

17

10

9

11

5

250

А3

15

11

6

13

8

200

Потребности

180

120

90

105

105


В правом верхнем углу каждой клетки проставлены тарифы, взятые из матрицы С.

1. Проверяем сбалансированность данных задачи: сумма всех запасов (150+250+200)=600 равна сумме всех потребностей (180+120+90+105+105)=600

2. Составляем первоначальный опорный план поставок методом минимального тарифа по всей матрице перевозок. В каждую из клеток вписываем максимально возможную поставку с учетом запасов и потребностей (см. таблицу 2).


Базы

Потребители

Запасы


B1

B2

B3

B4

B5

А1

14


6

+      .                       

4

90        

9

4

-    60

150

А2

17

10

 -   120

9

11

85

5

+    45

250

А3

15

180

11

6

13

20

8

200

Потребности

180

120

90

105

105


3. Количество заполненных клеток в таблице 2 равно 7.

Их должно быть m+n-1=3+5-1=7

Значит, план невырожденный.

Из таблицы видно, что:

X13=90; X15=60; X22=120; X24=85; X25=45; X31=180; X34=20.

Стоимость перевозок, соответствующая первому опорному плану, определяется с помощью тарифов:

Z1=4*90+4*60+10*120+11*85+5*45+15*180+13*20=5920 тыс. руб.

Вычислим потенциалы из условия:

αi + βj=Cij  (для заполненных клеток)

Примем α1=0, тогда  α2 =1; α3=3; β1=12; β2=9; β3=4; β4 =10 β5=4

4. Проверим план на оптимальность. Оптимальный план должен удовлетворять условию:

αi + βj<Cij    (для пустых клеток)

Проверка показала, что для клеток (1, 2), (1, 4), (3, 2) и (3, 4) условие оптимальности не выполняется. Загрузим неоптимальную клетку (1, 2) (или любую другую) за счет перераспределения груза в других клетках.

Построим цикл пересчета, который показан на рисунке 2.

Наименьшая из поставок, отмеченных знаком “-“ равна 60. Перемещая ее по циклу, приходим к новому плану, показанному в таблице 3.



Базы

Потребители

Запасы


B1

B2

B3

B4

B5

А1

14


6

+    60                       

4

-    90        

9

4

150

А2

17

10

-    60

9

11

+    85

5

    105

250

А3

15

180

11

6

+        .

13

-    20

8

200

Потребности

180

120

90

105

105


Z2=6*60+4*90+10*60+11*85+5*105+15*180+13*20=5740 тыс. руб.

Вычислим новые потенциалы:

примем α1=0, тогда  α2 =4; α3=6; β1=9; β2=6; β3=4; β4 =7 β5=1

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

Построим цикл пересчета, который показан на рисунке 3.

Наименьшая из поставок, отмеченных знаком “-“ равна 20. Перемещая ее по циклу, приходим к новому плану, показанному в таблице 4.

Базы

Потребители

Запасы


B1

B2

B3

B4

B5

А1

14


6

    80                       

4

    70        

9

4

150

А2

17

10

   40

9

11

    105

5

    105

250

А3

15

180

11

6

20        

13

   

8

200

Потребности

180

120

90

105

105



Z3=6*80+4*70+10*40+11*105+5*105+15*180+6*20=5660 тыс. руб.

Вычислим новые потенциалы:

примем α1=0, тогда  α2 =4; α3=2; β1=13; β2=6; β3=4; β4 =7 β5=1

Проверим на оптимальность пустые клетки. Проверка показала, что все клетки удовлетворяют условию:

αi + βj<Cij    (для пустых клеток)

Значит, полученный в таблице 4 план оптимален.

Ответ.

Оптимальный план перевозок:

X12=80; X13=70; X22=40; X24=105; X25=105; X31=180; X33=20

Расходы по его осуществлению минимальны и сотавляют

Zmin=5660 тыс. руб.