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

Двойственная транспортная задача ( -задача). Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней -задача.

Переменные -задачи обозначим v₁, v ₂, …, v _n, -u₁, -u₂, …, -u_m...

Теорема 3.1. -задача имеет решение и если X _опт = ,

- оптимальные решенияT и -задачи соответственно, то

. (3.1.7)

Если учесть, что u_i – стоимость единицы продукции в пункте А_і, а v_j – стоимость после перевозки в пункт B_j, то смысл теоремы будет такой:

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

Переменные u _i и v_j называют потенциалами пунктов A_i и B_j для Т-задачи.

Таким образом, теорема 3.1. утверждает, что при оптимальных решениях значения целевой функции прямой и двойственной Т-задач равны между собой.

Справедливость теоремы 3.1. следует из основной теоремы двойственной ЛП (теорема 2.5).

Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи.

Теорема 3.2. Для оптимальности плана Х ₀ Т-задачи необходимо и достаточно существование таких чисел v₁, v₂, …, v_n, -u₁, -u₂, …, -u_m, что

v_j – u_i c_ij, i = 1, …, m; j=1, …, n... (3.1.8)

При этом, если

это v_j – u_i = c_ij.

Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7).

Дадим экономическую интерпретацию условий теоремы 3.2.

Разность между потенциалами пунктов B_j и A_i , т.е. величину v_j – u_i, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта A_i в пункт B_j. Поэтому, еслиv_j – u_i < c_ij, то перевозка по коммуникации A_i B_j нерентабельна, и . Если v_j – u_i = c_ij, то такая перевозка рентабельна, и (см. Теорему 2.7)

Метод потенциалов.

Пусть имеется транспортная таблица, соответствующая начальному решению, х _il = для базисного решения переменных, х _il = 0 для свободных переменных (ячейки, соответствующие свободным переменным, остаются пустыми). Далее, нам требуется таблица расходов с заданными p_ij.

Отыскание симплекс множителей. Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u ₁, …, u_m, в нижнюю строку – значения неизвестных v ₁, …, v_n,. Эти m + n неизвестных для всех ( i, j ), соответствующих базисным переменным, должны удовлетворять линейной системе уравнений u_i + v_j = p_ij.

 

 

pll		plj		pln	ul
	. … .		. … .		. . .
pil		pij		pin	ui
	. … .		. … .		. . .
pml		pmj		pmn	um
vl	…	vj	…	vn

 

Для всех базисных решений эта система имеет треугольный вид, ранг её матрицы равен n + m – 1. Следовательно, систему всегда можно решить следующим способом.

Полагают v_n = 0. Если значения k неизвестных определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое ещё нет.

Переменные u_i и v_j симплекс - множителями. Иногда они называются также потенциалами, а этот метод решения называют методом потенциалов.

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться: