11. Задача, двойственная к транспортной. Метод потенциалов нахождения оптимального решения транспортной задачи. (с приви.Теоремы двойственности) Метод потенциалов

Если для некоторого распределения транспортной задачи выполняются условия: а) u_i + v_j = с_ij – для занятых клеток; б) u_i + v_j ≤ с_ij – для свободных клеток, то данное распределение является оптимальным.

Величины u_i называют потенциалами строк, а величины v_j называют потенциалами столбцов. Количество уравнений, удовлетворяющих условию а) равняется m+n-1 , а количество неизвестных u_i и vj равняется m+n. Решение такой системы линейных уравнений является неопределённым, поэтому одному из потенциалов нужно присвоить любое значение.(u_i =0). Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок свободных клеток: δ_ij = u_i + v_j - с_ij Если оценки всех свободных клеток меньше или равны нулю, то данное распределение является оптимальным. Если распределение не является оптимальным, то переходим к построению цикла пересчёта.

Задача двойственная к транспортной

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

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

              

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

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

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

            Тогда        

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

                                   

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

            

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

12. Несбалансированная транспортная задача и способ ее решения. Сравнение сбалансированной и несбалансированной задач; причины возникновения несбалансированности в задаче. Вопрос о соответствии оптимального решения сбалансированной транспортной задачи и несбалансированной

Транспортные задачи анализировались при условии баланса . Однако в реальных задачах это условие может не выполняться. Нарушение баланса будет иметь место при выполнении одного из неравенств:

Тогда несбалансированная ТЗ сводится к сбалансированной введением дополнительного (n+1)-го потребителя с объемом потребления либо дополнительного поставщика с объемом запаса . Стоимость перевозок по дополнительному столбцу или дополнительной строке в транспортной таблице принимается равной постоянной величине Q и сбалансированная ТЗ решается обычными методами. При чем эта ТЗ эквивалентна исходной, посколько величина целевой функции полученной ТЗ отличается от исходной ТЗ на величину либо

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