I этап. Определение начального допустимого решения

Для сбалансированной транспортной задачи существует только m + n − 1 независимых уравнений. Таким образом, как и в симплекс-методе, начальное базисное допустимое решение должно иметь m+n-1 базисных переменных.

Начальное базисное решение транспортной задачи по- лучают непосредственно из транспортной таблицы. Для этого можно использовать три процедуры.

1. Правило “северо-западного угла”

При нахождении опорного плана транспортной зада- чи методом “северо-западного угла” на каждом шаге рас- сматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной X11 приписывают максимальное значение, допускаемое ограни- чениями на спрос и запасы.

После этого вычеркивают соответствующий столбец или строку, фиксируя этим, что остальные переменные вычеркну- того столбца (строки) полагаются равными нулю. Если ограни- чения выполняются одновременно, то можно вычеркнуть либо

строку, либо столбец. Процесс завершается тогда, когда будет присвоено значение переменной xmn.

Исходный опорный план, построенный по правилу “севе-

ро-западного угла”, обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина cij). Более совершенным прави- лом является правило “минимального элемента”.

2. Правило “минимального элемента”

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

Правило “минимального элемента” заключается в том, чтобы перевозить максимально возможные объемы из пунк- тов отправления маршрутами минимальной стоимости. За- полнение таблицы начинаем с клетки, которой соответствует наименьшая стоимость перевозки (элемент cij) из всей табли- цы. Переменной этой клетки xij присваивается максимально возможное значение с учетом ограничений. Затем остаток по столбцу или строке помещается в клетку того же столбца или строки, которой соответствует следующее по величине зна- чение cij и т. д. Иными словами, последовательность заполне- ния клеток определяется по величине cij, а помещаемая в этих клетках величина xij такая же, как и в правиле “северо-запад- ного угла”.

Нахождение опорного плана по этим двум процедурам бу-

дет выполнено в подразд. 10.3.

3. Метод аппроксимации Фогеля

При определении оптимального плана транспортной задачи методом аппроксимации Фогеля на каждой итера-

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

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

Алгоритм решения транспортной задачи методом аппрок- симации Фогеля следующий:

I этап. Определение начального допустимого плана.

1. Для каждой строки таблицы необходимо упорядочить элементы стоимости перевозок cij по возрастанию. Определить величину “штрафа” строки как разность значений второго и первого элемента в ранжированном ряду.

2. Для каждого столбца таблицы необходимо упорядочить элементы стоимости перевозок cij по возрастанию. Далее необ- ходимо определить величину штрафа столбца.

3. Определить строку (или столбец), имеющую (имеющий) наибольший штраф по всем штрафам строк и столбцов, а в ней (в нем) — элемент с минимальной величиной стоимости перево- зок cij. Зафиксировать индексы (i, j) этого элемента.

4. Присвоить наибольшее значение из допустимых (с уче-

том ограничений) переменной xij, индексы которой соответс- твуют шагу 3.

5. Скорректировать величины ai и bj и вычеркнуть строку i, если ai = 0, или столбец j, если bj = 0.

6. Проверить, все ли величины ai и bj равны нулю, если

да, то окончить вычисления; в противном случае взять в качестве исходной оставшуюся часть таблицы и перейти к шагу 3.

Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптималь- ному, либо сам оптимальный план.