Глава II. Транспортная задача

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

2.1. Замкнутая модель транспортной задачи.

Пусть в пунктах A₁,…,A_m производится некоторый продукт в количествах a₁,…,a_m > 0. Этот продукт перевозится в пункты B₁,…,B_n, где он полностью потребляется в количествах b₁,…,b_n > 0. Для каждой пары индексов i,j задана стоимость c_ij 0 перевозок единицы продукта из пункта производства A_i в пункт потребления B_j. Необходимо перевезти весь произведенный продукт из пунктов A₁,…,A_m в пункты потребления B₁,…,B_n. При этом требуется, чтобы потребности каждого из пунктов B₁,…,B_n полностью удовлетворялись.

Сформулируем эту задачу как задачу линейного программирования.

Назовем планом перевозок неотрицательную матрицу X = (x_ij) размера m×n, в которой число x_ij ≥ 0 указывает количество продукта, перевозимого из пункта A_i в пункт B_j, 1 ≤ i ≤ m, 1 ≤ j ≤ n.

Стоимость z(X) перевозок является линейной функцией от X, именно, z(X) = ∑_i,j c_ijx_ij, x_ij ≥ 0.

В задаче требуется найти такой план перевозок X, чтобы его стоимость была бы минимальной, причем весь продукт был бы вывезен из пунктов производства, доставлен в пункты потребления, и все потребности были бы полностью удовлетворены. Отсюда следует, что транспортная задача является задачей линейного программирования. Действительно то, что весь продукт, производимый в A_i вывозится записывается в виде уравнения

∑_j x_ij = a_i , ( i = 1, …, m )

Аналогично, условие того, что потребности пункта B_j полностью удовлетворены, записывается в виде уравнения

∑_i x_ij = b_j, ( j = 1, …, n ).

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

(1)

x_ij ≥ 0;

z(X) = ∑_i,j c_ijx_ij → min.

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

Другие модели транспортной задачи будут рассмотрены позднее.

Назовем план перевозок X допустимым, если выполнены все ограничения из (1). Укажем способ построения допустимого решения методом минимального элемента.

Этот способ возможен, если ∑_i a_i = ∑_j b_j. Для этого выберем клетку с индексами (i,j), в которой стоит минимальное из чисел c_ij. В эту клетку помещаем число x_ij = min(a_i ,b_j ). Если a_i < b_j, то все остальные элементы i-ой строки полагаем равными нулю, число b_j заменяем на b_j – a_i, а a_i на 0. Если же a_i ≥ b_j, то все остальные элементы j-ого столбца полагаем равными нулю, число a_i заменяем на a_i – b_j, а b_j на 0. В результате число пустых строк или столбцов уменьшается на единицу. Продолжая этот процесс, получаем первоначальный план.

Продемонстрируем этот метод на конкретном примере. Пусть a₁ = 18, a₂ = 10, a₃ = 12, b₁ = 16, b₂ = 9, b₃ = 15, а матрица C имеет вид

Построим вспомогательную таблицу

	b1 = 16		b2 = 9		b3 = 15
a1 = 18		с11=1		с12=3		с13=4
a3 = 10		с21=2		с22=5		с23=3
a3 = 12		c31=6		c32=7		c33=5

Минимальный элемент с₁₁=1. В клетку (1,1) помещаем min(18,16)=16. В соответствии с изложенным правилом получаем таблицу

	b1 = 0		b2 = 9		b3 = 15
a1 = 2	16	с11=1		с12=3		с13=4
a3 = 10	0	с21=2		с22=5		с23=3
a3 = 12	0	c31=6		c32=7		c33=5

Далее из всех незаполненных клеток, находящихся в двух последних столбцах выбираем ту, в которой число c_ij минимально. Это, например, с₂₃=3. Применяя общее правило, получаем новую таблицу

	b1 = 0		b2 = 9		b3 = 5
a1 = 2	16	с11=1		с12=3		с13=4
a3 = 0	0	с21=2	0	с22=5	10	с23=3
a3 = 12	0	c31=6		c32=7		c33=5

Далее выбираем клетку (1,2) с с₁₂=3. Получаем новую таблицу

	b1 = 0		b2 = 7		b3 = 5
A1 = 0	16	с11=1	2	с12=3	0	с13=4
A3 = 0	0	с21=2	0	с22=5	10	с23=3
A3 = 12	0	c31=6		c32=7		c33=5

Наконец завершаем процесс и получаем первоначальный план. При этом можно отбросить первую строку и первый столбец. Получаем

16	с11=1	2	с12=3	0	с13=4
0	с21=2	0	с22=5	10	с23=3
0	c31=6	7	c32=7	5	c33=5

Теорема 1. Транспортная задача (1) имеет решение тогда и только тогда, когда

∑_i a_i = ∑_j b_j.

Доказательство. Пусть решение X существует. Тогда из (1) вытекает, что

∑_i a_i = ∑_i ∑_j x_ij = ∑_j ∑_i x_ij = ∑_j b_j.

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

Из ограничений видно, что все элементы допустимой матрицы неотрицательны и потому ограничены. Следовательно, функция z(X) достигает минимума на некотором допустимом плане, т.е. транспортная задача всегда имеет решение.

Рассмотрим двойственную задачу линейного программирования к транспортной задаче (1). В соответствии с общим правилом запишем (1) в виде

∑_j x_ij ≤ a_i , i = 1, …, m;

- ∑_j x_ij ≤ - a_i , i = 1, …, m;

∑_i x_ij ≤ b_j, j = 1, …, n; (2)

- ∑_i x_ij ≤ - b_j, j = 1, …, n

x_ij ≥ 0;

- z(X) = - ∑_i,j c_ijx_ij → max.

Тогда двойственная задача имеет вид

_i’ - _i’’ + β_j’ - β_j’’ ≥ - c_ij , i = 1, …, m, j = 1, …, n;

_i’,_i’’,β_j’, β_j’’ ≥ 0, i = 1, …, m, j = 1, …, n; (3)

T’= ₁’a₁ – ₁’’a₁ + … + _m’a_m – _m’’a_m + β₁’b₁ – β₁’’b₁ + … + β_m’b_m – β_m’’b_m → min

Положим T = -T’ и _i = _i’’ - _i’, β_j = β_j’’ - β_j’, i = 1, …, m, j = 1, …, n.

Тогда (3) имеет вид

_i + β_j ≤ c_ij , i = 1, …, m, j = 1, …, n; (4)

T = ₁a₁ + … + _ma_m + β₁b₁ + … + β_mb_m → max.

Теорема 2. Для того, чтобы допустимый план перевозок X был оптимальным необходимо и достаточно, чтобы существовали такие числа (потенциалы) ₁, … , _m,β₁, … , β_n, для которых

1) _i + β_j ≤ c_ij при всех i,j;

2) _i + β_j = c_ij, если x_ij > 0.

Доказательство. Проверим достаточность. Пусть задан допустимый план X = (x_ij), и ₁, … , _m,β₁, … , β_n из условий теоремы. Предположим, что Y = (y_ij) - произвольный допустимый план. В силу ограничений (1) и свойств 1), 2) из условия теоремы получаем

z(Y) = ∑_i,j c_ijy_ij ≥ ∑_i,j (_i + β_j)y_ij = ∑_i _i ∑_j y_ij + ∑_j β_j ∑_i y_ij = ∑_i _i a_i + ∑_j β_j b_j = ∑_i _i ∑_j x_ij + ∑_j β_j ∑_i x_ij = ∑_i,j (_i + β_j)x_ij = ∑_i,j c_ijx_ij = z(X).

Проверим теперь необходимость. Пусть X ⁰= (x_ij⁰) – оптимальный план и ₁, … , _m,β₁, … , β_n – оптимальное решение двойственной задачи. По (4) выполнено неравенство 1) из условия теоремы. Кроме того, по теореме о равновесии получаем (_i+ β_j - c_ij) x_ij⁰ = 0. Поэтому если x_ij⁰ > 0, то выполнено равенство 2) из условия теоремы.

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

G  {1, … ,m }, H  {1, … ,n},

что одно из них собственное и

_{i  G} a_i = _{j  H} b_j

Другими словами, суммарный запас продукта в пунктах A_i, i  G, совпадает с потреблением в пунктах B_j, j  H.

Далее мы будет предполагать, что рассматриваемая транспортная задача невырождена. Изложим метод потенциалов решения невырожденной транспортной задачи, опирающийся на теорему 2. Мы уже имеем допустимый первоначальный план, построенный методом минимального элемента. Из этого построения видно, что число ненулевых элементов в первоначальном плане равно n + m – 1. Найдем первоначальную систему потенциалов. Для этого в соответствии с условием 2) из теоремы 2 составим систему из n + m – 1 линейного уравнения

_i + β_j = c_ij.

В этой системе число неизвестных _i,β_j равно n + m. Можно показать, что ранг этой матрицы равен n + m – 1. Поэтому одно из неизвестных является свободным. Полагаем его равным нулю и далее находим частное решение системы. Продемонстрируем этот шаг на рассмотренном выше примере. Имеем системы линейных уравнений

Положим ₁ = 0. Тогда β₁ = 1, β₂ = 3. Далее ₃ = 4, β₃ = 1, ₂ = 2.

Для полученной системы потенциалов проверяем выполняется ли условие 1) из теоремы 2. Для этого составляем вспомогательную матрицу D, в которой на месте (i,j) стоит d_ij = _i + β_j . Если d_ij  c_ij для всех (i,j), то построенный план по теореме 2 является оптимальным. Далее вычисляем значение целевой функции z(X) для этого плана. В нашем примере

Мы видим, что условие 1) нарушается в клетке (1,2).

Опишем основной шаг алгоритма, состоящий в улучшении плана. Выберем клетку (p,q), в которой _p + β_q > c_pq. По построению x_pq = 0. Нам потребуется

Предложение. Пусть план X = (x_ij) допустим, и x_pq = 0 для некоторой пары индексов (p,q). Тогда существует и единственная такая последовательность различных строк p = i(0), i(1), … , i(k) и различных столбцов j(1), … , j(k-1), j(k) = q в матрице X, что элементы этой матрицы, стоящие в клетках (i(0), j(1)), (i(1), j(1)), (i(1), j(2)), (i(2), j(2)), … , (i(k), j(k-1)), (i(k), j(k)), отличны от нуля.

Заметим, что если мы начнем движение по матрице X с клетки (p,q), двигаясь далее по клеткам (i(0), j(1)), (i(1), j(1)), (i(1), j(2)), (i(2), j(2)), … , (i(k), j(k-1)), (i(k), j(k)) из предложения, то мы сначала идем по строке, далее по столбцу, затем снова по строке и т. д. На последнем шаге мы идем по строке и попадаем в исходный столбец с номером q.

Расставим во всех выбранных клетках чередующиеся метки +, - , начиная с + в начальной выбранной клетке (p,q). Пусть  - минимальный среди элементов x_ij, стоящих в выбранных клетках с меткой -. В клетках с меткой + число x_ij увеличиваем на , а в клетках с меткой - уменьшаем на . Все остальные элементы матрицы X не меняем. Получаем новый допустимый план X’ = (x_ij’). Сравним значения целевых функций для планов X и X’. Имеем

z(X') - z(X) = _i,j c_ij(x'_ij - x_ij) = _s=0^k-1 c_i(s)j(s)(x'_i(s)j(s) - x_i(s)j(s) ) +

_s=0^k c_i(s)j(s+1)(x'_i(s)j(s+1) - x_i(s)j(s+1) ) = _s=0^k-1 c_i(s)j(s) - _s=0^k c_i(s)j(s+1) = [ c_i(0)j(0) + (_i(1) + _j(1)) +  + (_i(k-1) + _j(k-1)) - (_i(0) + _j(1)) - … - (_i(k-1) + _j(k))] = [ c_i(0)j(0) - (_i(0 + _j(k))] < 0.

Итак, план улучшился. Для нового плана снова находим систему потенциалов и с помощью теоремы 2 проверяем его оптимальность и т. д. В результате через конечное число шагов в результате работы этого алгоритма получаем оптимальный план.

Продемонстрируем работу этого алгоритма на рассмотренному выше примере. Мы выбрали клетку (2,1). Выбираем путь (2,3), (3,4), (3,2), (1,2), (1,1). Расставляем метки + для клеток (2,1), (3,4), (1,2), и метки – для клеток (2,3), (3,2), (1,1). Минимальный элемент  стоящий в клетках с меткой – равен 7. Изменяем матрицу и получаем новую таблицу

9	с11=1	9	с12=3	0	с13=4
7	с21=2	0	с22=5	3	с23=3
0	c31=6	0	c32=7	12	c33=5

Для новой таблицы пишем систему уравнений для нахождения потенциалов:

Полагаем ₁ = 0. Тогда β₁ = 1, и поэтому β₂ = 3, ₂ = 1. Далее β₃ = 2, ₃ = 3. Таким образом, матрица D имеет вид

В соответствии с теоремой 2 построенный план

оптимален. Поэтому ответом является

z(X) = 91 + 93 + 72 + 33 + 125 = 9 + 27 + 14 + 9 + 60 =119.