Контрольная работа: Постановка и основные свойства транспортной задачи

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

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

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

. (1.7)

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

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

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

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

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

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

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

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

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

это v_j – u_i = c_ij .

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

Дадим экономическую интерпретацию условий теоремы 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).

Транспортная задача с ограниченными пропускными способностями.

Важной в практическом отношении является Т_d - задача, в которой существуют ограничения на пропускные способности коммуникаций.

Пусть - пропускная способность коммуникации A_i B_j .

Тогда (1.9)

Т-задача состоит в минимизации Ц.Ф. (1.3) при условиях (1.1), (1.2), (1.9). Даже в случае разрешимости Т-задачи, Т_d – задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. А_і , и полного ввоза продукта в п. В_j . Поэтому для Т_d – задачи вводят еще два условия:

(1.10)

(1.11)

Но и при добавочных условиях (1.10), (1.11) Т_d – задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (1.1), (1.2), (1.9) – (1.11) совместна. В противном случае Т_d – задача неразрешима.

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

если , (1.12)

если 0 < , (1.13)

если . (1.14)