yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->            7.3.2. Метод потенциалов улучшения базисного распределения поставок

Исследование операций

            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

 

 

            Число уравнений для определения потенциалов поставщика и потребителя равно числу базисных клеток, т.е. , а число неизвестных в уравнениях равно , т.е. на единицу больше цикла уравнений. Поэтому при определении указанных потенциалов полагается .

            Определяем потенциалы поставщиков ui и потребителей vj по формуле (7.3)

             при                     

                    

                   

                   

                   

                   

            Заносим найденные потенциалы в таблицу 7.8. По формуле (7.4) определяем потенциалы свободных клеток.

           

           

           

           

           

           

            План перевозки, представленный в таблице 7.8, не оптимальный, т.к. потенциалы двух клеток (1,1) и (1,3) отрицательны.

            План перевозки следует улучшить за счет перераспределения груза. Перераспределение груза осуществляется по так называемому циклу пересчета.

            Цикл пересчета составляется для той свободной клетки, потенциал которой является наименьшим. В рассматриваемом случае наименьший потенциал, равный «-1», имеют клетки (1,1) и (1,3). Составим цикл пересчета для любой из них, например, для клетки (1,1).

            Цикл пересчета – это замкнутая ломаная линия, соединяющая между собой несколько клеток, отвечающая следующим условиям:

  1. среди клеток цикла одна является свободная, для которой строится цикл, остальные базисные;
  2. в каждой клетке ломаная делает поворот на 90о;
  3. свободной клетке присваивается знак «+», знаки остальных клеток чередуются. Цикл, клетки которого имеют знаки, называется означенным.

            Составим цикл пересчета для клетки (1,1)

 

 

 

 

 

 

 

 

 

            Определяем величину перемещения поставки по циклу из условия минимума среди поставок в клетках цикла со знаком «-» min (20;60;10) = 10. Увеличиваем на 10 единиц поставки в клетки со знаком «+» и уменьшаем в клетках со знаком «-». Получаем таблицу 7.9.

Таблица 7.9

           Заявки

 Запасы

20

110

40

110

60

1

           10

2

           50

5

3

0

120

1

           10

6

5

2

         110

0

100

6

3

           60

7

           40

4

1

1

2

6

2

 

 

            Определяем потенциалы поставщиков и потребителей по таблице поставок 7.9

                                                        

                            

                             

                            

                            

                            

            Проверяем план перевозки, представленный в таблице 7.9, на оптимальность, для чего определяем потенциалы свободных клеток.

           

           

           

           

           

           

            Т.к. имеются клетки с отрицательным потенциалом, план не оптимальный.

            Строим цикл пересчета для клетки (1,3)

 

 

 

 

 

 

Величина поставки min (40; 50) = 40.

            Осуществляя перемещение поставки по циклу пересчета, получаем таблицу 7.10.

Таблица 7.10

           Заявки

 Запасы

20

110

40

110

60

1

           10

2

           10

5

           40

3

0

120

1

           10

6

5

2

         110

0

100

6

3

         100

7

4

1

1

2

5

2

 

 

Определяем потенциалы поставщиков и потребителей по таблице поставок 7.10

                                          

                            

                            

                             

                            

                            

Определяем потенциалы свободных клеток таблицы поставок 7.10.

           

           

           

           

           

           

            Т.к. потенциалы всех свободных клеток положительны, план перевозки является оптимальным.

            Суммарные затраты на перевозку груза равны:

                         усл.ед.

 

23