9.3 Двойственная задача

            Запишем транспортную задачу в матричном виде

            A- матрица ограничений, имеющая в соответствии с векторами х и b вид :

              

            Двойственная задача к транспортной задаче в матричном виде будет иметь вид

у- произвольного знака.

            Распишем двойственную задачу в скалярном виде. Обозначим компоненты вектора

                        

            Тогда

                        

и ограничения двойственной задачи будут иметь вид :

                                   

или  в общем виде двойственная задача

            

            Двойственные переменные i, i=1,...,m, j, j=1,...,n, называются платежами, а

                                   

- псевдостоимость перевозок единицы груза из пункта i в пункт j, i=1,...,m, j=1,...,n.

9.4 Теоремы двойственности

            ИЗ теории двойственности ЛП практический интерес представляет вторая теорема двойственности, из которой получается следующий критерий.

            Критерий оптимальности транспортной задачи

            План перевозок

                                   

является оптимальным планом тогда и только тогда, когда найдется система платежей

                                   

для которой выполняются условия :

                    Доказательство. Сформулируем вторую теорему двойственности в терминах переменных транспортной задачи.

            Ели

                        

удовлетворяют ограничениям прямой задачи, а

                        

удовлетворяют ограничениям двойственной задачи, то для оптимальности плана

                        

необходимо и достаточно выполнение условий

            

            Условие а) выполняется для любых допустимых решений прямой задачи, так как

                                   

            Условие b) можно расписать как следствие о дополняющей нежесткости, а именно

            

            Итак, для базисных переменных

                                   

имеем равенство

            

 а для небазисных переменных

                                     

достаточно выполнения допустимости двойственных переменных                                       

 Таким образом имеем условия 1) и 2) критерия.

Критерий доказан.

9.5 Построение опорного плана транспортной задачи

            Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:                                                  

            Базисными клетками транспортной таблицы являются клетки с от-

личными от нуля положительными перевозками, остальные клетки -  свободные. Базисные клетки образуют опорный план транспортной задачи, если выполняются два условия:

            1) сумма перевозок в каждой строке равна запасу   в данной

строке;

            2) сумма перевозок в каждом столбце равна соответствующему

столбцу спросу

                                               

            Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок

                                               

            Опорный план называется вырожденным, если число ненулевых перевозок

                                               

 меньше и n+m-1, опорный план - невырожден, если число

ненулевых перевозок равно n+m-1.

            Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.