Плана перевозок

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

 

1. Осуществляется выбор перспективной клетки с наибольшей по модулю отрицательной оценкой:

– перспективная клетка.

2. Строится цикл, исходная вершина которого находится в перспективной клетке, а остальные – в занятых клетках.

Правило построения цикла заключается в следующем.

Перемещаясь от перспективной клетки по строке или столбцу, проводим линию до любой занятой клетки и, делая поворот на 90° , снова проводим ее до следующей занятой клетки. Эта процедура продолжается до тех пор, пока цикл не замкнется в перспективной клетке.

3. В вершинах цикла расставляются чередующиеся знаки «+» и «–», начиная с перспективной, в которой ставится знак «+».

4. Определяется число α как минимальный объем груза среди клеток цикла с отрицательными вершинами (в отрицательной полуцепи цикла).

Величина α определяет количество груза, который можно перераспределить в рассматриваемом цикле.

5. В перспективную клетку (i, j)^* вписывается значение α; в цикле осуществляется перераспределение на эту величину.

Число α прибавляется к перевозкам, если они соответствуют положительно отмеченным клеткам цикла, и вычитается в противном случае.

В результате преобразования перспективная клетка становится занятой, а клетка, которая определила число α – свободной.

6. Строится новая распределительная таблица, вычисляются потенциалы и характеристики, проверяется оптимальность плана.

 

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

 

1) Построение первоначального опорного плана (методом северо-западного угла или методом наилучшего элемента).

2) Вычисление потенциалов поставщиков и потребителей, а также вычисление оценок (характеристик) свободных клеток.

3) Проверка условия оптимальности.

4) Последовательное улучшение опорного плана до получения оптимального.