Транспортная  задача. Граф перевозок. Признак оптимальности. Метод потенциалов.

     Транспортная  задача

Пусть имеется m пунктов производства и n пунктов  потребления. Производится однородный продукт в количествах: а₁, а₂....а_m, и он потребляется в количествах:b₁, b₂….b_n. Cчитаем, что известна матрица стоимостей перевозок, состоящая из элементов C_ij:

      

Требуется найти план перевозок, т.е. матрицу X_ij, когда такую, что все потребители удовлетворены, а общая стоимость перевозок минимальная. Естественное условие: X_ij 0

      .

     Должно  выполняться:

     Если  это условие нарушено – задача не имеет решения. Можно считать, что 

     Вводится  термин «свалка»(когда суммы )

      , а стоимость C_{i n+1}= 0.

     Общая формулировка транспортной задачи.

     Минимизировать  общую сумму перевозок:

       (1)

     при условии   (2)

     i – для производителей, j – для потребителей

     Т.е. суммируем по j количество производимого:

       (3),

     суммируем по i, т.е. то, что производится на всех заводах и вводится в пункт j то количество, которое этот пункт в  силах потреблять.

       (4)

     Пример: пусть 3 пункта производства:

           7 5 20  9   +

        В1  В2  В3 В4

       

            

      - А1    11 U1=0 ! всегда 
 
 

                 А2     13 U2=-2       стоимость перевозок 
 

                 А3     17 U3=-2 
          v1=1      v2=2        v3=0      v4=-1  

      Начальное допустимое базисное решение может  быть получено методом северо-западного угла.

Допустимым  базасным решением задачи (1) – (4) называется такой набор из m*n чисел X_ij, в котором содержится ровно m+n-1 строго положительных X_ij и которые удовлетворяют всем условиям (2) – (4).

Оптимальным решением называется допустимое базисное решение, доставающее меню целевой функции, т.е. минимизирующее общую стоимость перевозок.

     Замечание: Там, где производного = потребляемого – закрытая задача.

     L(общая  стоимость перевозок) = 7*1+4*2+1*4+12*2+8*2+9*1=7+8+4+24+16+9=68

     Составим  граф перевозок:

       

           7 4 12

           1 8 9 
 
 
 
 

      6 ненулевых перевозок, следовательно, m+n-1, 3+4-1

     Граф  перевозок должен быть деревом, а  дерево это связный граф без циклов. А связный граф – это такой граф, у которого по ребрам можно попасть в любой пункт из любого, а «без циклов» - означает, что, начав движение в одном из пунктов, мы никогда в него не вернемся.

     Ребро – отрезок, соединяющий пункты.

     Дуга – ориентировочное ребро – (ребро со стрелкой).

     Признак оптимальности транспортной задачи.

     Определение: Для любого допустимого базисного решения задачи (1) – (4) могут быть найдены числа

     U_i 

     v_j   такие, что v_j-U_i=C_ij для всех базисных (ненулевых) клеток и если для выполняется - , то план оптимален.

     U_i , v_j – потенциалы.

     Будем искать «невязку» максимальную. Для удобства: .

     Численное нарушение этого неравенства  – величина «невязки».

     Вводится  перевозка в клетку, где МАКСИМАЛЬНАЯ «НЕВЯЗКА». Величина этой перевозки  определяется следующим образом:

     Алгоритм:

1. Помечаем последовательно «+» и «-» клетки цикла.
2. Из клеток, помеченных «-» выбираем ту, где перевозка минимальная.
3. Вычитаем ее из всех клеток, помеченных «-» и прибавляем ко всем клеткам, помеченным «+».

     Мы  ввели перевозку 21(+) – 11(-) – 12(+) – 22(-) – это и есть выявление цикла (по графу перевозок).

     Замечание: Если нарушается правило базисности, т.е. ненулевых клеток становится меньше, чем m+n-1, то один из нулей записывается в явном виде и на графе нулевая перевозка отмечается. Причем выбирается тот ноль из получившихся, который сохраняет связность графа и позволяет ему оставаться деревом.

     Рисуется  новая таблица:

        

                 7  5 20 9

           

     

           11      0

       

        

                 13                    1           

           17  1                 

                                  
   1  2 3 2

     L=65

     Замечание 1: Существует не менее эффективный метод – венгерский метод (см.пакеты прикладных программ).

     Замечание 2: v_j-U_i=C_ij – насколько ценнее единица продукта в одном пункте, чем в другом.

     Надо  ввести туда, где U_i+C_ij=v_j (иначе убыток). 
 
 

     Алгоритм  решения транспортной задачи методом потенциалов.

1. Строим  допустимое базисное решение методом  северо-западного угла.
2. Находим потенциалы из условия v_j-U_i=C_ij
3. Для всех пустых клеток проверяем признак оптимальности . Если он нарушается хотя бы в одной из клеток, следовательно, ищем max «невязку»: Невязка=max(v_j-U_i-C_ij)
4. Пусть max невязка находится в клетке, обозначенной i₀j₀. Чертим граф. Вводим новую перевозку из i₀ в j₀ (i₀ - производитель; j₀ – потребитель). Находим цикл.
5. Пользуясь циклом графа, помечаем клетку i₀j₀ – «+» (т.к. вводим перевозку), а все остальные клетки поочередно – «+», «-».
6. Находим min из всех клеток, помеченных «-». Пусть эта клетка: minX_ij         i₁j₁ и выводим из базиса, т.е. от производителя i₁ ничего не везем к j₁ потребителю.

Ко  всем клеткам с «+» добавляем  эту min величину, а из всех «-» - вычитаем ее. Т.о. получаем новую транспортную таблицу (таблицу издержек).

7. Возвращаемся в пункт 2.

 

     Разновидности графов:

1)   

• без циклов.

 
 

       2)

           - решение не оптимальное. 
 

     

       3)  - задача со «свалкой», цена перевозки=0. 

           «свалка» 
 

       4) 

           -вырожден. граф (вводим  искус. перевозку и вводим в  любую клетку).