next up previous contents
След: Задача о максимальном потоке Нзд: Примеры задач линейного программирования Пред: Задача о раскрое   Содержание

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

В транспортной задаче требуется найти оптимальный план перевозок некоторого продукта от заданного множества производителей, также занумерованных числами \( 1, 2, \ldots, M \), к множеству потребителей, также занумерованных числами \( 1, 2, \ldots, N \).

Производственные возможности \(i\)-го производителя заданы объемом производимого продукта - \( a_i \). Спрос \(j\)-го потребителя на этот продукт задается числом \(b_j\).

Обозначим планируемый объем перевозок от \(i\)-го производителя к \(j\)-ому потребителю как \(x_{ij}\). В этих условиях должны быть выполнены балансовые соотношения:

\begin{displaymath}
\begin{array}{l}
\sum_{j=1}^N x_{ij} = a_i, i = 1, 2, \ldots, M \\
\sum_{i=n}^M x_{ij} = b_j, j = 1, 2, \ldots, N
\end{array}\end{displaymath} (6)

Для существования допустимого плана перевозок должен выполнятся общий баланс между спросом и потреблением:

\begin{displaymath}
\sum\limits{_{i=1}^{M}} a_i = \sum\limits{_{j=1}^{N}} b_j = D
\end{displaymath}

При этом транспортную задачу называют сбалансированной.

Можно убедиться, например, что в сбалансированной транспортной задаче

\begin{displaymath}
x_{ij} = a_i b_j/D
\end{displaymath} (7)

являются допустимым вариантом перевозок, то есть удовлетворяющим ограничениям (6).

Целью решения транспортной задачи является минимизация суммарных транспортных расходов. Если предположить, что стоимость перевозки продукта линейно зависит от объема перевозки и характеризуется числами \( c_{ij} \), где \( c_{ij} \) - стоимость перевозки единицы продукта от \(i\)-го производителя к \(j\)-му потребителю, а \(x_{ij}\) -- обьемы перевозок, то целевая функция в транспортной задаче принимает вид:

\begin{displaymath}
T(x) = \sum\limits{_{i=1}^{M}} \sum\limits{_{j=1}^{N}} c_{ij} x_{ij}
\end{displaymath} (8)

и задача заключается в минимизации (8) при выполнении ограничений (6) и условия неотрицательности переменных \(x_{ij}\).

Переменные \(x_{ij}\) можно представить в виде матрицы (см. табл. 1).

Таблица: Матрица объемов перевозок.
Потребители
Поставщики
1 2 ... \(N\)
1 \(x_{11}\) \(x_{12}\) ... \(x_{1N} \)
2 \(x_{21}\) \(x_{22}\) ... \(x_{2N} \)
... ... ... ... ...
M \(x_{M1}\) \(x_{M2}\) ... \(x_{MN} \)

или, более традиционную, в виде вектора \( x_k , k = 1, 2, \ldots, M N \) развернув в этот вектор вышеприведенную таблицу. При естественном обходе таблицы (1) (скажем по столбцам) матрица ограничений (6) примет специфический вид, приведеный в табл. 2.

Таблица: Матрица ограничений транспортной задачи.
1 1 ... 1                    
        1 1 ... 1            
                ...          
                  1 1 ... 1  
1       1       ... 1        
  1       1     ...   1      
    $\ddots$       $\ddots$   ...     $\ddots$    
      1       1 ...       1  

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

Для характеризации разреженности ипользуют две меры -- количество ненулевых элементов в матрице ограничений и их отношение к общему числу элементов матрицы. Последняя характеристика называется плотностью. Для транспортной задачи плотность \( d \) равна \( 3/(M + N) \) и падает с ростом размерности задачи, что вообще типично для задач линейного программирования.

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

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

Таблица: Список транспортных связей
¡ Поставщик Потребитель Стоимость перевозки
1 Владивосток Москва 134
2 Хабаровск Владивосток 27
... ... ... ...
127 Якутск Магадан 98

С \(i\)-ой связью можно ассоциировать соответствующую переменную \(x_i\), которая имеет смысл объема перевозок по этому направлению.

Если множество связей, ведущих к потребителю \(i\), обозначить через \(S(i)\), а множество связей, ведущих к поставщику \(j\), обозначить через \(D(j)\), то балансовые уравнения запишутся как

\begin{displaymath}
\sum_{k\in S(i)} x_k = a_i,
\quad
\sum_{k \in D(j)} x_k = b_j;
i = 1,2, \dots, M;\ j = 1,2, \dots, N.
\end{displaymath}

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


next up previous contents
След: Задача о максимальном потоке Нзд: Примеры задач линейного программирования Пред: Задача о раскрое   Содержание
Evgeni A. Nurminski 2000-08-19