Постановка и основные свойства транспортной задачи (стр. 2 из 7)
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)
при условиях
где 
- неудовлетворенный спрос.
Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства Аm+1, с объемом производства 
и транспортными издержками 
В таком случае Т-задача будет иметь вид
минимизировать 
при условиях
В найденном решении хопт полагаем все перевозки из фиктивного пункта Аm+1 равными нулю, т.е. 
.
Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+1 с объемом спроса 
. Пусть 
- это убытки (штраф) в пункте Аі за единицу невывезенного продукта. Обозначим через сии,n+1 = удельные транспортные издержки на перевозку единицы продукта с Аі в Вn+1. Тогда соответствующая Т-задача запишется так:
минимизировать 
(1.16)
при условиях
(1.17) – (1.18)
В найденном решении 
все перевозки 
в фиктивный пункт Вn+1 считают равными нулю.
Опорные планы Т-задачи
Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.
Последовательность коммуникаций
(1.19)
называют маршрутом, соединяющим пункты 
(рис. 2).
… 
 |
 |
. 
Рис. 2
Используя маршрут, составленный из коммуникаций, можно осуществить перевозку продукта из пункта 
в пункт 
, проходя через пункты 
.
В процессе этого движения коммуникации, стоящие на четных местах в (1.19), будут пройдены в противоположном направлении.
Маршрут (1.19), к которому добавлена коммуникация 
называется замкнутым маршрутом или циклом.
Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной).
Теорема 4. Система, составленная из векторов 
Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.