Разбор задачи
Условие и материал
Проверка найденного опорного решения
транспортной задачи 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 и ... Смотреть решение »