Двойственная пара транспортных задач

Построим двойственную задачу простейшей транспортной задачи (Т-задачи). Предварительно изменим знаки в выражении критерия и в условиях по пунктам назначения. Тогда модель прямой задачи примет вид:

Здесь слева от равенств записаны сопоставленные им двойственные переменные. Модель двойственной задачи запишем по правилам, приведенным в разд. 4.11.3:

;

Если C_ij перенести в левую часть, то согласно (5.19) условия двойственной задачи приобретают смысл признака оптимальности "Δ_ij£0.

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

Из теорем двойственности известно, что в оптимальном решении критерии прямой и двойственной задач равны. Для рассматриваемой двойственной пары это означает, что

(5.21)

Отсюда находим:

Учитывая линейность (5.21), полный дифференциал запишем в виде

Изменения a_i и b_j могут быть только равными, иначе нарушится сбалансированность задачи. Если положить D a_i= D b_j =1, то получим

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