Постановка и основные свойства транспортной задачи

,

Учитывая условие баланса (1.6), получим

,

т.е. первое уравнение системы (1.1) тоже удовлетворяется.

Таким образом, ранг системы уравнений (1.1), (1.2) .

Докажем, что ранг системы ур

авнений (1.1), (1.2) равен точно . Для этого составим матрицу из первых () компонентов векторов

Очевидно, что эта матрица не вырождена. Поэтому векторы {} образуют базис. Так как базис системы состоит из () векторов, то и ранг системы (1.1), (1.2) .

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

Переменные -задачи обозначим v1, v 2., v n, – u1, – u2., – um…

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

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

. (1.7)

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

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

Переменные uiиvj называют потенциалами пунктов AiиBj для Т-задачи.

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

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

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

Теорема 2. Для оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, что

vj – ui cij, i = 1., m; j=1., n… (1.8)

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

это vj – ui = cij.

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

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

Разность между потенциалами пунктов BjиAi, т.е. величину vj – ui, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта Ai в пункт Bj. Поэтому, если vj – ui < cij, то перевозка по коммуникации Ai Bj нерентабельна, и . Если vj – ui = cij, то такая перевозка рентабельна, и (см. Теорему 2.7).

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

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

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

Тогда (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. Для оптимальности плана Х0 Тd – задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, при которых

если , (1.12)

если 0 <, (1.13)

если. (1.14)

Смысл условий оптимальности (1.12) – (1.14) состоит в следующем:

если приращение стоимости продукта vj – uj меньше транспортных расходов cij, то такая перевозка убыточна, а потому . Если же приращение стоимости продукта vj – uj больше транспортных расходов cij (3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е. .

Таким образом, теорема 3.3 по существу выражает принцип рентабельности для Td – задачи.

Открытые транспортные модели. Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми. Возможные два случая:

1)

2)

В первом случае полное удовлетворение спроса невозможно.

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

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

(1.15)

при условиях

где - неудовлетворенный спрос.

 Скачать реферат