Транспортная задача. Филькин Г.В. - 5 стр.

                                         4


   Следующей заполняется клетка (2,2) – вторая во второй строке по
min {40, 25-20} = 5. Второй потребитель удовлетворён и переходим ко вто-
рой строке к третьей клетке.
                           x23 = min {40-5, 20} = 20.
   Третий столбец заполнен. Следующей заполняем клетку (2, 4)
                          x24 = min {45-25, 50} = 15.
   Последней заполняем клетку (3,4).
                           x34 = min{35, 50-15} = 35.

   Получаем таблицу:

                       B
                               40        25        20        50
              A
                           5         4         1         2
                  60           40        20

                           4         2         6         3
                  40                     5         20        15

                           7         3         5         4
                  35                                         35



   Заполненных клеток должно быть m+ n – 1, т.е. 3 + 4 – 1 = 6. В нашем
случае их действительно шесть. Этот план ацикличен, значит, является
опорным. Предварительные транспортные издержки составят

                       f = 40·5 + 20·4 + 5·2 + 20·6 + 15·3 + 35·4 = 595.

   При составлении первоначального плана не учитывалась стоимость пе-
ревозки единицы груза, поэтому построенный план далёк от оптимального.

                               Метод наименьшей стоимости.

   Суть метода заключается в том, что из всей таблицы стоимостей выби-
рают наименьшую и в клетку, которая ей соответствует, помещают мень-
шее из чисел ai или bj. Затем из рассмотрения исключают либо строку, со-
ответствующую поставщику, запасы которого полностью израсходованы,
либо столбец, соответствующий потребителю, потребности которого пол-
ностью удовлетворены, либо строку и столбец одновременно (если ai = bj).
Из оставшейся части таблицы вновь выбирают клетку с наименьшей стои-