Учебный материал
По теме
Проверка найденного опорного решения
транспортной задачи 245 на оптимальность
Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система m+ п действительных чисел ui и vj, удовлетворяющих условиям ui + vj = cij для занятых клеток и ui + vj - сij ≤ 0 для свободных клеток.транспортной задачи 245 на оптимальность
Числа ui и vj называют потенциалами.
В распределительную таблицу добавляют строку vj и столбец ui.
Потенциалы ui и vj находят из равенства ui + vj = cij, справедливого для занятых клеток. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно.
Так, если известен потенциал ui, то vj = сij — ui; если известен потенциал vj, то ui = cij – vj. Обозначим Δij = ui + vj - cij.
Эту оценку называют оценкой свободных клеток.
Если Δij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок Δij > 0, то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.
Проверим найденное опорное решение на оптимальность, добавив в распределительную табл. 23.3 столбец ui и строку vj.
Полагая u1 = 0, запишем это значение в последнем столбце таблицы.
Рассмотрим занятую клетку (3,1): u3 + v1 = 3, v1 = 2, откуда u3 = 1.
Для клетки (3,3): u3 + v3 = 8, u3 = 1, v3 = 7.
Для клетки (2,3): u2 + v3 = 5, v3 = 7, u2 = -2.
Для клетки (2,2): u2 + v2 = 1, u2 = -2, v2 = 3.
Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
