Линейное математическое программирование, страница 30


Клетка (2,3)

 


Клетка (3,1)

 


Клетка (3,3)

 


Клетка (3,4)

 


            Т.к. все оценки свободных клеток не отрицательны, план оптимальный. Таким образом, минимальные затраты на перевозку грузов равны 760 усл.ед.

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

            7.3.2. Метод потенциалов улучшения базисного распределения поставок

            Поставим в соответствие каждому поставщику некоторую величину ui, которую назовем потенциалом поставщика и каждому потребителю – некоторую величину vj, которую назовем потенциалом потребителя.

            Потенциалы поставщиков и потребителей определяются из условия

                        , где                                                                               (7.3)

cij – действительные тарифы перевозки от і-того поставщика к j-тому потребителю, взятые для всех базисных клеток.

            По найденным потенциалам поставщика и потребителя определяются потенциалы свободных клеток по формуле

                        , где                                                                    (7.4)

cij – тарифы свободных клеток.

            Если потенциалы всех свободных клеток положительны или равны нулю, то получен оптимальный план решения ТЗ. Если это условие не выполняется, план перевозки должен быть улучшен.

            Определим потенциалы поставщиков и потребителей, а также потенциалы свободных клеток для базисного распределения поставок, полученного ранее методом наименьших затрат (таблица 7.8)

Таблица 7.8

           Заявки

 Запасы

20

110

40

110

60

1

2

           60

5

3

0

120

1

           20

6

5

2

         100

-1

100

6

3

           50

7

           40

4

           10

1

2

2

6

3