Транспортная задача. Определение опорного решения.
Транспортная задача линейного программирования формулируется следующим образом. Необходимо минимизировать транспортные расходы
при ограничениях
,
где 
- стоимость перевозки единицы продукции из пункта i в пункт j; 
– планируемая величина перевозок из пункта i в пункт j (план перевозок 
– матрица размерности 
); 
- потребности в продукте в пункте j; 
- запасы в пункте i.
Предполагается, что модель закрытого типа, то есть 
.
Если модель открытого типа 
, то ее всегда можно привести к закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления:
Если 
, то 
, тогда 
, причем 
.
Если 
, то 
, 
и 
.
Транспортная задача представляет собой задачу линейного программирования и, естественно, ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточнения оценок. В этом случае основная трудность бывает связана с числом переменных задачи (m´n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгерский метод.
Алгоритм метода потенциалов, его называют еще модифицированным распределительным алгоритмом, начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла или метод минимального элемента.
Он позволяет найти некоторый допустимый план перевозок. Составим транспортную таблицу некоторой задачи.
 |
30 | 80 | 20 | 30 | 90 | |
 |
||||||
| 120 | 2
30 |
4
80 |
2
10 |
3 |
8 | |
| 30 | 3 |
5 |
6
10 |
6
20 |
2 | |
| 40 | 6 |
8 |
7 |
4
10 |
5
30 | |
| 60 | 3 |
4 |
2 |
1 |
4
60 | |
В данном случае, имеем задачу закрытого типа, т.к. 
.
При построении плана должны учитывать, что сумма перевозок в столбце должна оказаться равной потребностям в данном пункте, а сумма перевозок в строке запасу в пункте, соответствующем данной строке.
Заполнение начинается с верхнего левого угла таблицы. Величина перевозки устанавливается равной минимальной из величин: величины остатка запасов в пункте i или величины еще неудовлетворенного спроса в пункте j.
Если ресурс в данной строке исчерпан, то переходим к перевозке в следующей строке текущего столбца (на одну строку вниз).
Если потребности для данного пункта (столбца) удовлетворены, то переходим к следующей перевозке текущей строки в следующем столбце.
Затраты на перевозку по построенному плану равны:
.
Естественно, что найденный план далек от оптимального.
В таблице отыскивается 
и в первую очередь заполняется соответствующая клетка: 
. Затем вычеркивается остаток соответствующей строки, если 
, или столбца, если 
, и корректируем остатки запасов и неудовлетворенного спроса. В оставшихся клетках таблицы снова отыскивается минимальная стоимость перевозки и заполняется соответствующая клетка и т.д.
 |
30 | 80 | 20 | 30 | 90 | |
 |
||||||
| 120 | 2
30 |
4
80 |
2
|
3 |
8
10 | |
| 30 | 3 |
5 |
6
|
6
|
2
30 | |
| 40 | 6 |
8 |
7 |
4
|
5
40 | |
| 60 | 3 |
4 |
2
20 |
1
30 |
4
10 | |
Затраты на перевозку по построенному плану равны:
.
Этот план лучше, но утверждать, что он оптимален, нельзя.
Определение 1. Набором называется произвольная совокупность перевозок транспортной таблицы.
Определение 2. Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.
Определение 3. Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.
