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

Наиболее распространенным методом решения транспортных! задач является метод потенциалов.

Решение задачи методом потенциалов включает следующие этапы.

1. разработку начального плана (опорного решения);

2. расчет потенциалов;

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

4. поиск максимального звена неоптимальности (если условие п. 3 не было достигнуто);

5. составление контура перераспределения ресурсов;

1. определение минимального элемента в контуре перераспре­деления и перераспределение ресурсов по контуру;

2. получение нового плана.

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

Для транспортной задачи существует несколько методов отыс­кания начального плана (опорного решения):

• метод северо-западного угла;

• метод минимальной стоимости;

• метод двойного предпочтения и т. д.

Вычислительный алгоритм метода потенциалов рассмотрим на примере решения конкретной задачи прикрепления пунктов от­правления к пунктам назначения . В соответствии с принятыми в п. 8.1 обозначениями исходные данные задачи при­ведены в табл. 9.2.

Таблица 9.2