Разработка алгоритма решения исследуемой транспортной задачи

Решение задачи основано на известном методе потенциалов, алгоритм которого имеет следующий вид:

1) определение опорного решения одним из существующих методов.

2) проверка на оптимальность: для базисных клеток, в которых записываются уравнения

Количество этих уравнений равно n+m-1. Решение этих уравнений позволяет определить значения неизвестных

После того, как будут определены значения этих неизвестных, проверяем выполнение следующих условий для свободных клеток . Для этого, проверяем выполнение следующих неравенств:

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

3) переход к другому решению. Вначале выбирается клетка, для которой имеет наибольшее отрицательное по абсолютной величине значение. В эту клетку записывают возможное большое значение, затем вводится изменение в таблицу. Следует обратить внимание, что должны выполнятся условие (2) – (4).