Алгоритм решения транспортной задачи с нарушенным балансом, страница 5

3.  Если нельзя указать пару процедур (вредную или полезную), которая уменьшает дельта-оценку по сравнению с предыдущим шагом, то найдено оптимальное решение. Оптимальный план перевозок определяют по следующему алгоритму:

- ненулевые элементы плана перевозок размещаются на нулевых позициях разреженной матрицы стоимости;

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

- из рассмотрения удаляется соответствующий столбец или строка;

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

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

       1.2.1.1 Алгоритм решения поставленной задачи был разработан на основе метода потенциалов.

Алгоритм метода потенциалов

Имея опорный план перевозок, в методе потенциалов выполняют анализ клеток матрицы плана перевозок. Все заполненные клетки матрицы перевозок называются базисными, все незаполненные клетки - свободными.

Для каждой свободной клетки, аналогично распределительному методу, можно построить замкнутый контур  (цикл) и перераспределить ресурсы между поставщиками и потребителями. Отличие этого метода состоит в том, что определяется потенциал каждой клетки и, в зависимости от значения потенциала,  выполняется  перемещение только  по  одному контуру (циклу).

План перевозок будет оптимальным, если он содержит m+n

положительных чисел u и v, которые называются потенциалами строк и столбцов соответственно. Для вычисления потенциалов в матрицу плана перевозок добавляют одну строку сверху и один столбец слева.

Для определения  потенциалов строк и столбцов используют формулу u+v=c, подставляя в нее значения из базисных клеток.

Для начала выполнения расчетов надо потенциал одной строки или одного столбца приравнять нулю. Затем, используя указанную формулу выполнить остальные вычисления. Примем за ноль потенциал первой строки u = 0.

Тогда v=c-u. Далее выбираем те базисные клетки, для которых уже имеется один потенциал (или строки или столбца), и определяем следующий потенциал. Для базисной клетки a известен потенциал первой строки u. Поэтому можем определить потенциал второго столбца: v=c-u. И так далее.

Для свободных клеток вычисляются оценки по формуле u+v-c0. Если оценки всех свободных клеток отрицательны или равны нулю, то опорный план - оптимальный. Если хотя бы одна оценка больше нуля, то относительно этой свободной клетки строят замкнутый контур и выполняют перераспределение ресурсов (аналогично распределительному методу). Если несколько свободных клеток имеют оценки, большие нуля, то замкнутый контур строят для свободной клетки с наибольшим значением оценки.

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

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

Метод добротностей и распределительный метод также указали оптимальный план перевозок, но это были другие планы. Таким образом, рассмотренный пример содержит несколько альтернативных оптимальных планов перевозок.

Метод потенциалов предоставляет сведения, имеет ли транспортная задача альтернативные оптимальные планы перевозок.

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