Транспортная задача

1. Транспортная  задача в сетевой форме. Метод  потенциалов

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

Содержательная постановка задачи (организация грузоперевозок в транспортной сети).

Есть множество  географических пунктов, в которых сосредоточено производство некоторого однородного продукта. Для каждого пункта задана величина – мощность пункта. Выпуск продукции осуществляется в пунктах производства, для которых . Остальные являются пунктами потребления ( ). Также могут рассматриваться транзитные пункты (развилки) , где .  Пункты соединены дорогами (их множество обозначим ), некоторые из которых имеют ограниченную пропускную способность ( ). Стоимость перевозки груза по дороге пропорциональна количеству груза, тариф перевозки единицы груза равен .

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

Задачи определения плана, минимизирующего затраты на перевозки, которые с математической точки зрения полностью идентичны (1)-(3), (4), также называют транспортными задачами в сетевой постановке.

Пример содержательной постановки

Сеть трубопроводов связывает  две станции опреснения воды с  двумя городами. Ежедневное предложение опреснительных станций составляет 40 и 50 миллионов литров воды, города ежедневно потребляют 30 и 60 миллион литров воды. Каждая станция трубопроводами соединена с каждым городом непосредственно, однако они могут также перекачивать воду в города через специальную насосную станцию. Кроме того, станция 1 может транспортировать воду на станцию 2, а город 1 - в город 2. Определена стоимость перекачки 1л воды по каждой трубе. 

Найти наиболее экономный  вариант снабжения двух городов  опресненной водой.

 

Математическая модель задачи.

Представим транспортную сеть в виде конечного графа  , на которой пунктам соответствуют узлы, а дорогам – дуги. Каждой вершине сопоставлено некоторое число b_i, называемое интенсивностью вершины (мощностью узла) . Граф , вершинам которого сопоставлены значения интенсивностей b_i, будем называть сетью. Если b_i > 0, то вершина i называется источником, если b_i < 0, то — стоком, а если b_i = 0, то — нейтральной (транзитной) вершиной. Множество источников, стоков и нейтральных вершин обозначим соответственно V⁺, V^-, V⁰.

Потоком (flow) по сети называется функция , , определенная на множестве дуг и такая, что

,                                                               (1)

.                                                (2)

 

где D_i – множество дуг, исходящих из вершины i, a – множество дуг, входящих в нее.

 

Величина  называется величиной потока (value of flow) по дуге (дуговым потоком) и содержательно интерпретируется как количество продукта, пропускаемого по данной дуге.

Соотношение (1) – условие сохранения потока (flow conservation), означает, что для любой вершины сети разность выходящего и входящего потоков равна ее интенсивности.

Если дополнительно для  каждой дуги сети определены величины , называемые пропускными способностями, то вместо ограничения (2) имеем

.                                                        (2*)

Пропускная способность  – это верхняя граница потока, возможного поданной дуге.

Для каждой дуги определим значения ≥ 0, называемые тарифами (стоимостью перемещения единицы продукта по дуге), тогда суммарная стоимость потока Х примет вид

.                                                             (3)

Математическая модель сетевой ТЗ в виде ЗЛП имеет  вид:

,                                                              

            

.                                               

 

Очевидно, что задача минимизации  функции (3) при ограничениях (1)-(2) является задачей линейного программирования.

Обозначим через  матрицу инцидентности графа. Тогда в матричной форме задача записывается так:

                                                                  (5)

 

2. Критерий  оптимальности базисного плана

Для простоты обоснования  метода потенциалов для сетевой ТЗ рассмотрим ТЗ без ограничений на пропускные способности (ЗЛП (1),(2),(3)). Построим двойственную к ней задачу, используя двойственные переменные :

  двойственная        (замена переменных)    

 

Таким образом, имеем двойственную к (5) задачу:

                                                                (6)

 

Критерий оптимальности базисного потока. Неравенства

                                                              (8)

достаточны, а в случае невырожденности и необходимы для оптимальности базисного потока.

Доказательство. Сформулируем вторую теорему двойственности в терминах переменных транспортной задачи.

Ели удовлетворяют ограничениям прямой задачи, а удовлетворяют ограничениям двойственной задачи, то для оптимальности плана необходимо и достаточно выполнение условий дополнительной нежесткости

a) ;

b) .

Условие а) выполняется  для любых допустимых решений  прямой задачи, так как 

.

Условие b) можно  расписать как следствие о  дополняющей нежесткости, а именно

1. если , то ;
2. если , то .

Итак, для  базисных переменных имеем равенство

, ,                                               .(9)

а для небазисных переменных достаточно выполнения допустимости двойственных переменных

.

Таким образом, имеем условия 1) и 2) критерия. Критерий доказан.

 

В системе  уравнений (9) число уравнений на единицу меньше числа неизвестных (вершин на единицу больше, чем дуг), поэтому для расчета потенциалов одна из переменных может быть определена произвольным образом (удобно полагать ее равной нулю).