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

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

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

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

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

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

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

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

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

1.2.10. Дельта-метод

Дельта-метод может использоваться только в том случае, если все   значения   элементов   матрицы   стоимости неотрицательные.

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

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

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

Коэффициенты вектора вычитаний по строкам попарно умножаются на значения вектора ресурсов. Коэффициенты вектора вычитаний по столбцам попарно умножаются на значения вектора потребностей. Полученное произведение берётся со знаком плюс, если операция «зануления» была «полезной». Для «вредной» операции полученное произведение берётся со знаком минус.

На первом этапе в дельта-методе используется процедура метода добротностей по преобразованию строк и столбцов с целью получения разрежённой матрицы [3,5,6].

Алгоритм дельта-метода

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

2.  На последующих шагах выполняют одну процедуру вредную (уменьшают количество нулей и уменьшают дельта-оценку), а вторую процедуру – полезную (увеличивают дельта-оценку), но суммарная дельта-оценка от двух процедур должна быть меньше дельта-оценки предыдущего шага. Пара процедур (вредная и полезная) выполняется для одной строки и одного столбца разрежённой матрицы.