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

1) Исследование на вырожденность.

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

При этом, если N=m+n-1, тогда вариант не вырожденный, а если N<m+n-1, то вариант вырожденный. Если вариант окажется вырожденным, то для дальнейшего решения задачи необходимо из числа свободных клеток взять недостающее количество клеток, ставим туда 0 и условно считаем занятыми. Нули проставляются в такие клетки, чтобы вариант остался ациклическим. В каждой рабочей таблице все занятые клетки объединены между собой единой цепью. В этой цепи могут быть несколько ответвлений. От 1 занятой клетки до другой в цепи можно переходить или по строке или по столбцу, поворачивая под прямым углом. Если вариант вырожденный, то единая цепь разрывается, и 0 ставится в такую клетку, чтобы разрыв ликвидировать.

2) Исследование на оптимальность.

Теорема об оптимальности: вариант решения задачи будет оптимальным, если найдется такая система абстрактных чисел, называемая потенциалами поставщиков Ui и потенциалами потребителей Vj, при которой для занятых клеток таблицы будет выполняться условие

Vj – Ui Cij (Z min)

или

Vj – Ui Cij (Z max)

причем для занятых клеток Vj – Ui = Cij.

На основании этой теоремы исследование на оптимальность проводится в 2 этапа.

На первом этапе для каждой занятой клетки составляется уравнение Vj – Ui = Cij и получаем систему из ( таких уравнений. Далее решаем эту систему относительно потенциалов, то есть находим значения всех потенциалов. Для удобства расчетов присваиваем любому потенциалу любое числовое значение и в зависимости от него рассчитываем значения остальных. Это необходимо в связи с тем, что количество неизвестных на единицу больше количества уравнений. Чаще всего берут Ui =0 и от него считают все остальные.

На втором этапе для свободных клеток таблицы проверяется условие Vj – Ui Cij (Z min) или Vj – Ui Cij (Z max). Вариант будет оптимальным, если для всех свободных клеток это условие будет выполняться.

Для тех клеток, для которых условие не выполняется, рассчитывается их оценка:

= ǀ (Vj – Ui) - Cijǀ.

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

Смысл перераспределения заключается в том, чтобы в самую плохую клетку ( где наибольшая) перераспределить какое-то количество груза.

Перераспределение груза должно отвечать следующим требованиям:

1. должны выполняться требования системы ограничений модели;

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