 |
 |
 |
 |
|
 |
 |
63
объемы вывоза из пунктов производства, а вторая — ограничениям на удовлетворение потребностей в
пунктах производства.
Построим двойственную задачу. С учетом специфической структуры матрицы транспортной задачи
вектор двойственных переменных будет иметь размерность m+n, причем его компоненты,
соответствующие первой группе ограничений, обозначим через (-u
i
), i?1: m, а второй — через v
j
, j?1:n
(рис. 3.2). Тогда двойственная задача будет иметь вид:
Переменные u
i
называют потенциалами пунктов производства, а v
j
—
потенциалами пунктов
потребления. Применяя доказанные в главе 1 теоремы двойственности (см. теорему
1.7), можно
получить критерий оптимальности для плана транспортной задачи:
Для того, чтобы допустимый план транспортной задачи х
i,j
был оптимальным, необходимо и
достаточно, чтобы нашлись такие потенциалы и
i
, v
j
, для которых
Данные условия имеют содержательную экономическую интерпретацию. Потенциалы u
i
, и v
j
можно
рассматривать как цены на перевозимый груз в пунктах производства и потребления (это, кстати,
объясняет то, зачем понадобилось обозначать соответствующую двойственную переменную через (-u
i
)).
Тогда, согласно условию (3.8), для оптимальности плана перевозок требуется, чтобы на тех маршрутах,
по которым действительно перевозится груз, его цена в пункте потребления возрастала ровно на цену
его перевозки, а в соответствии с условием (3.9) в оптимальном плане цена груза в пункте потребления
не может быть меньше его цены в пункте производства с учетом затрат на транспортировку.
3.1.4. Алгоритм метода потенциалов для транспортной задачи. Критерий (3.8)-(3.9) положен в
основу одного из методов решений транспортной задачи, получившего название метода потенциалов.
Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей
линейного программирования аналогичный метод был предложен Дж. Данцигом.
Точно так же как транспортная задача является частным случаем задачи ЛП, так и метод
потенциалов, вообще говоря, может трактоваться как разновидность симплексных процедур. Он
представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый
текущий базисный план, проверяется его оптимальность, и при необходимости определяется переход к
«лучшему» базисному плану.
Алгоритм начинается с выбора некоторого допустимого базисного плана (методы его построения
были рассмотрены в п. 3.1.2). Если данный план не вырожденный, то он содержит m + n -1 ненулевых