1. общие свойства транспортных задач

^1. ОБЩИЕ СВОЙСТВА ТРАНСПОРТНЫХ ЗАДАЧ

1. 
   Постановка задач
   

Пусть дана сеть (V, D), где V={1,…,n} – множество узлов, D – множество

дуг, пропускная способность дуги (i,j) равна
^dij
 0 . Для каждой дуги (i,j)

определим значение с_ij стоимости прохождения единицы потока по дуге. Транспортная модель может рассматриваться как задача наиболее экономичного распределения потока по дугам транспортной сети.
Если в сети выделен источник s V и сток t V , то задачу поиска
дуговых потоков, минимизирующих стоимость прохождения потока величины
v по сети, формально можно представить в виде
_c_ij x_ij  min, (1.1)

при условиях




_ v,


i  s,

^{ x}ij
j

• 
  ^{ x} ji j
  

 ^ 0,


^ v,
i  s,t, i  t,
(1.2)

0  x_ij  d_ij . (1.3)
Задачу (1.1) – (1.3) обычно называют линейной сетевой задачей.
Обобщим задачу на случай нескольких источников и стоков. Пусть каждому узлу i сети сопоставлено некоторое число s_i, называемое
интенсивностью узла, и V  S ∪ R ∪ T . Элементы множеств S, T и R называются
источниками, стоками и нейтральными узлами соответственно. Для всех i  S
s_i>0, в узлах i T s_i<0, нейтральные узлы имеют нулевую интенсивность.
Потоком в такой сети называется совокупность определенных для всех дуг величин x_ij , удовлетворяющих (1.3) и условию

^{ x}ij
j
 _ x _ji  s_i , i V . (1.4)
j

Результирующий “чистый” поток, протекающий через узел i, вычисляется как разность выходящего и входящего потоков. Соотношение (1.4) означает, что для любого узла сети результирующий поток через узел равен его интенсивности.
Задача (1.1), (1.3), (1.4) называется сетевой транспортной задачей.
Очевидно, задача (1.1) – (1.3) – частный случай задачи (1.1), (1.3), (1.4). С другой стороны, сеть с несколькими источниками и стоками можно свести к сети с одним обобщенным источником s и одним обобщенным стоком t, вводя дополнительные дуги с нулевой стоимостью от s к источникам и от стоков к t.

Пропускные способности новых дуг (s,i),
i  S , полагаем равными
s _j , дуг (j,t),

j T – (– s _j ). Условия (1.4) определяют тогда поток максимальной величины из источника в сток и задача (1.1), (1.3), (1.4) становится полностью идентичной

задаче (1.1) – (1.3). Поэтому задачу (1.1) – (1.3) также называют иногда сетевой транспортной задачей.
К очевидной сфере приложения задач (1.1) – (1.3) и (1.1), (1.3), (1.4) относится организация грузоперевозок в транспортной сети. В таких моделях узлы сети трактуются как пункты, соединенные сетью дорог, состоящей из конечного числа звеньев (дуг). Под интенсивностью понимается количество
продукта, производимое или потребляемое данным узлом: если i  S , то пункт i

называется производственным,
a_i  s_i
интерпретируется как запасы или

производство некоторого продукта; величина
b_i  s_i ,
i T , трактуется как

потребность в некотором продукте, а соответствующий пункт называется

пунктом потребления. Если
s_i  0 , то i – перевалочный пункт.

Для каждого звена сети известны стоимости
^cij
перевозки единицы

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

План перевозок определяется заданием величины
^xij
для каждого звена

сети. Задача состоит в формировании оптимального плана перевозок, то есть связанной с минимальными транспортными расходами схемы транспортировки груза от поставщиков к потребителям, такой, чтобы потребности в продукте пунктов потребления были удовлетворены и не допускалось затоваривание пунктов производства.
С помощью введенных обозначений, ограничения (1.4) можно переписать
в виде

 ai , i  S ,	(1.5)
 0 , i  R ,	(1.6)
 bi , i  T .	(1.7)

^{ x}ij ^{  x} ji

j
^{ x}ij
j
j

• 
  ^{ x} ji j
  

^{ x} ji ^{  x}ij
j j
Ограничения (1.5) означают, что из пунктов отправления вывозится объем грузов, равный запасу в этом пункте. Ограничения (1.7) гарантируют доставку необходимого количества груза в каждый из пунктов назначения.
Благодаря указанной интерпретации транспортная задача и получила свое название. Транспортная модель применяется также для описания ситуаций, связанных с управлением запасами, составлением расписаний, управлением движением капиталов, назначением персонала и других. Задачу о максимальном потоке, например, можно рассматривать как частный случай задачи о потоке минимальной стоимости (1.1)–(1.3), в которой все дуговые стоимости равны нулю, а v совпадает с величиной максимального потока.