 |
 |
 |
 |
|
 |
 |
61
Транспортная задача является представителем класса задач линейного программирования и поэтому
обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд
дополнительных полезных свойств, которые позволили разработать специальные методы ее решения.
Если привести условия транспортной задачи к канонической форме задачи линейного
программирования, то матрица задачи будет иметь размерность (m+n) х mn. Матрицы систем уравнений
в ограничениях (3.2) и (3.3) имеют ранги, равные соответственно m и n. Однако, если, с одной стороны,
просуммировать уравнения (3.2) по m, а с другой — уравнения (3.3) по n, то в силу (3.5) получим одно и
то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной
комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n-1, и ее
невырожденный базисный план должен содержать m+n-1 ненулевых компонент.
Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц,
структура которых представлена на рис.3.1.
Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой
строки указан объем запаса продукта а
i
), а столбцы — пунктам потребления (последняя клетка каждого
столбца содержит значение потребности b
j
). Все клетки таблицы (кроме тех, которые расположены в
нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом
верхнем углу находится
цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для
данных пунктов. Клетки, которые содержат нулевые перевозки (х
i,j
= 0), называют свободными, а
ненулевые — занятыми (x
i,j
>0).
3.1.2. Построение исходного допустимого плана в транспортной задаче. По аналогии с другими
задачами линейного программирования решение транспортной задачи начинается с построения
допустимого базисного плана. Наиболее простой способ его нахождения основывается на так
называемом методе северо-западного угла. Суть метода состоит в последовательном распределении
всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д.
пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в
очередном пункте производства или к попытке полного, удовлетворения потребностей в очередном
пункте потребления. На каждом шаге
q величины текущих нераспределенных запасов обозначаются
а
i
(q)
, а текущих неудовлетворенных потребностей —
b
j
(q)
. Построение допустимого начального плана,
согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при
этом полагаем а
i
(0)
=
а
i
, b
j
(0)
= b
j
. Для очередной клетки, расположенной в строке
i и столбце j,
рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной
потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема
перевозки между данными пунктами: x
i,j
= min{а
i
(q)
, b
j
(q)
}. После этого значения нераспределенного
запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную