Транспортная задача с решением

Транспортной называется задача линейного программирования, основанная на поиске оптимальных «маршрутов перевозки» путем создания циклов. По сути задача сводится к тому, чтобы найти оптимальный способ перевозки груза из точки А в точку B при минимальных затратах.

Условие сбалансированной транспортной задачи:

Необходимо перевести 140 единиц продукта от производителей на склады. Цены перевозок по маршрутам указаны также в таблице. Требуется найти наиболее дешевый вариант перевозки.

 

B1

B2

B3

B4

 

A1

                10

                7

          12

                             5

20

A2

                 3

                 8

                 5

                           2

40

A3

                2

                14

                  4

                            6

30

A4

        7

       11

                2

                          13

50

 

15

45

20

60

140

Решение:

Сначала путем распределения 140 единиц продукта методом северо-западного угла получим опорные решения:

 

B1

B2

B3

B4

 

A1

                1510

                   57

                   12

                             5

20

A2

                   3

                 408

                             5

                             2

40

A3

                   2

                   14

                          204

                          106

30

A4

                   7

                   11

                             2

                        5013

50

 

15

45

20

60

140

В таком первоначальном варианте стоимость транспортировки будет равна 150+35+320+80+60+650=1295. Понятно, что существуют варианты более оптимальные,, нежели данный опорный вариант. Для их нахождения следует выделить один из отрицательных циклов. Например такой:

Легко проверить, что он отрицательный: 7-10+5-13= -11. После перегруппировки внутри данного цикла мы получаем следующее:

 

B1

B2

B3

B4

 

A1

              10

              57

          12

                        15 5

20

A2

               3

            408

                   5

                             2

40

A3

                   2

                   14

                          204

                          106

30

A4

         157

             11

                 2

                        3513

50

 

15

45

20

60

140

При этом варианте цена составит уже 1130 единиц, т.е. на 165 единиц меньше.

Найдем еще один отрицательный цикл:

Этот цикл также является отрицательным: 2-4+6-13= -9. Теперь, чтобы уменьшить общую цену, проведем перегруппировку в пределах этого цикла:

 

B1

B2

B3

B4

 

A1

              10

            57

         12

                  15 5

20

A2

              3

            408

                 5

                             2

40

A3

                   2

                   14

                            4

                          306

30

A4

           157

               11

        20 2

              1513

50

 

15

45

20

60

140

Теперь общая цена составляет еще меньше: 950 единиц.

Однако, здесь имеются и еще отрицательные циклы, вот один из них:

Очевидно, что этот цикл является отрицательным: 2-8+7-5= -4. Произведем перегруппировку внутри данного цикла:

 

B1

B2

B3

B4

 

A1

         10

          207

     12

                            5

20

A2

               3

  258

                 5

                  15 2

40

A3

                   2

        14

               4

                306

30

A4

         157

       11

   20 2

                1513

50

 

15

45

20

60

140

И опять таки мы получаем более рациональный ответ: 890.

Проделывая далее подобные операции мы можем найти оптимальное решение. Однако, должно быть, большую часть мы уже проделали, и наиболее оптимальное решение не будет намного отличаться от найденного, тем более, что мы уже получили огромный выигрыш в 405 единиц.

Запись опубликована в рубрике Математические методы в управлении. Добавьте в закладки постоянную ссылку.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *