Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

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

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

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

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

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

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

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

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

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

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

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

- метод минимального элемента;

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

В процессе решения после каждой итерации (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение следующего условия:

N = m + n -1 (11.7)

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

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

Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство:

U_i + V_J = C_ij (11.8)

где U_i - потенциал i -й строки;

V_j - потенциал j -го столбца.

Вычисляя потенциалы по выражению (9.8), принимаем для первой строки U₁ = 0.

Проверяем план на оптимальность по незагруженным клеткам,

S_ij = C_ij – (U_i + V_j) (11.9)

используя следующее неравенство:

U_i + V_j ≤ C_ij (11.10)

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

Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы соединений между которыми равны 90°.

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