На главную   ::   Содержание



Транспортная задача и теоретические основы метода потенциалов

Задан граф $ G=\left(V,E\right)$. Вершины графа -- это географические пункты. Для каждого пункта $ i\in V$ задана величина $ b_i$ -- мощность узла $ i$. Выпуск продукции сосредоточен в пунктах производства, для которых $ b_i<0$. Остальные считаются пунктами потребления ($ b_i>0$). Также могут рассматриваться транзитивные пункты (развилки) -- где $ b_i=0$. Стоимость перевозки груза по дуге пропорциональна количеству груза. Требуется обеспечить потребителей необходимым количеством продукции с минимальными суммарными затратами на перевозки.

Сетевая постановка.

Построим математическую модель задачи. Пусть $ c_j$ -- стоимость перевозки единицы продукции, а $ x_j$ -- количество продукции, перевозимое по дуге $ j\in E$. Функционал задачи может быть записан в виде

$\displaystyle \sum_{j\in E} c_jx_j=cx\to min\eqno{(1)}
$

Ограничения задачи:

$\displaystyle \sum_{j\in N_i^+} x_j-\sum_{j\in N_i^-}x_j=b_i\quad i\in V\eqno{(2)}
$

Естественное ограничение -- условие неотрицательности

$\displaystyle x_j\geqslant 0\eqno{(3)}
$

Задача линейного программирования (1)-(3) называется транспортной задачей в сетевой постановке. Обозначим через $ A$ матрицу инцидентности графа. Тогда в матричной форме задача записывается так:

\begin{displaymath}
\begin{array}{c}
cx\to\min\\
Ax=b\\
x\geqslant \mathbb{O}\\
\end{array}
\end{displaymath}

Транспортная задача сбалансирована (имеет решение) тогда и только тогда, когда $ \sum b_i=0$. Если это не выполнено, положим $ \delta=\sum b_i$. Создадим новую вершину с мощностью $ -\delta$. Будем называть ее свалкой. Соединим все пункты со свалкой дугами обоих направлений. Если имеется избыток продукции, то лишнее свозится на свалку бесплатно, а забирается оттуда за бесконечную цену, если же недостаток, то забирается со свалки бесплатно, а возвращается туда за бесконечную цену.

Матричная постановка.

Теперь рассмотрим матричную постановку задачи. Пусть граф -- двудольный. Каждой дуге соответствует пара вершин $ i,j$, причем $ i$ -- производство, $ j$ -- потребление. Стоимость перевезти по дуге обозначим $ c_{ij}$. Пусть $ x_{ij}$ -- количество продукции, которую мы везем из $ i$ в $ j$. Целевая функция перепишется в виде

$\displaystyle \sum_i
\sum_j c_{ij} x_{ij}\to\min$

Ограничения задачи:

$\displaystyle \sum_i
x_{ij}\geqslant d_j$ (потребителю везем не меньше, чем ему надо)

$\displaystyle \sum_j
x_{ij}\leqslant b_i$ (у производителя берем не больше, чем может произвести)

$\displaystyle x_{ij}\geqslant 0
$

Если задачу сбалансировать, то неравенства превратятся в равенства. Балансировку нужно выполнить так, чтобы получилось $ \sum b_i=\sum
d_j$.

Метод решения.

Рассмотрим двойственную задачу:

\begin{displaymath}
\begin{array}{c}
vb\to\max\\
vA\leqslant c
\end{array}
\end{displaymath}

$ v_i,  i\in V$ -- переменные двойственной задачи, называемые потенциалами. Ограничения можно переписать в следующем виде:

$\displaystyle v_{j_u}-v_{i_u}\leqslant c_u.
$

Здесь $ i_u$ -- начало дуги, $ j_u$ -- конец дуги.

Заметим, что ранг матрицы инцидентности равен $ \vert V\vert-1$. Поэтому базисное множество дуг представляет собой множество дуг некоторого дерева в графе.

Для базисных дуг выполняется соотношение двойственности

$\displaystyle v_{j_u}-v_{i_u}= c_u.
$

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

Алгоритм решения задачи в сетевой постановке.

Шаг 0. Построение начального базисного плана.
Добавляем одну фиктивную вершину. Базисные дуги начального плана -- фиктивные дуги, объем перевозок по этим дугам равен модулю мощности узлов. Стоимости перевозок равны бесконечности. Направления дуг учитывают, что перевозка идет от производителя к потребителю.
Шаг 1. Вычисление потенциалов.
Выберем произвольную вершину, ее потенциал полагаем равным нулю. Потенциалы остальных вершин определяются последовательным просмотром базисных дуг. Если известен потенциал начала или конца дуги, то потенциал неизвестной вершины определяется из уравнения

$\displaystyle v_{j_u}-v_{i_u}= c_u.
$

Шаг 2. Проверка оптимальности текущего базисного плана.
Если для двойственной задачи ограничения выполняются у всех дуг сети, то текущее базисное решение оптимально. Иначе выберем дугу $ w$, для которой это соотношение нарушается.
Шаг 3. Пересчет базисного решения.
Включение в базисный план дуги $ w$ порождает цикл. Условно ориентируем все дуги в этом цикле в ту же сторону, что и дугу $ w$. При этом некоторые дуги в этом цикле условно повернутся (станут отрицательно ориентированы). Среди таких дуг выберем ту, перевозки по которой минимальны. Обозначим величину перевозки по этой дуге $ \lambda$. Ко всем положительно ориентированным дугам прибавим $ \lambda$, ко всем отрицательно ориентированным прибавим $ -\lambda$. При этом у выбранной дуги и, возможно, у некоторых других, перевозка станет равной нулю. Нужно удалить одну из этих дуг. С новым базисным планом выполняем переход на Шаг 1.


На главную   ::   Содержание