Читайте также:
|
В этом методе оценивается потенциал пустых клеток таблицы транспортной задачи. Этот потенциал показывает можно ли, перемещая потоки в эту клетку улучшить план. Существует теорема о потенциалах:
Если к коэффициентам затрат сразу всего столбца или сразу всей строки прибавить фиксированное число, то потенциал свободных клеток не изменится.
правило нахождения оценки для свободных клеток:
1) для каждого столбца и для каждой строки нужно ввести фиксированные потенциалы: 
; если они прибавляются к затратам и имеют отрицательные значения, чтобы эти коэффициенты стали равны нулю, то мы можем посмотреть какие при этом получатся величины в свободных клетках. Если получатся отрицательные величины, то ее потенциал меньше, чем у заданной клетке, если положительные, то больше.
Если менять по циклу данную клетку с клеткой с большим потенциалом, то план улучшится, и наоборот.
Мы получаем систему уравнений: 
(эти клетки не подходят для циклов)
(эти клетки подходят для улучшения плана)
2) обычно количество потенциалов больше, чем количество этих уравнений, в результате часть потенциалов оказывается неопределенными, тогда их либо обнуляют, либо подбирают так, чтобы количество отрицательных клеток было - минимальное значение.
В результате мы определяем все клетки, где затраты меньше суммы потенциалов, и пытаемся для этих клеток построить циклы. Если этот процесс будет происходить многократно, но на каком-то этапе клеток не окажется вообще, это значит, что мы нашли минимум издержек – оптимальный план.
Замечание: Следует учитывать, что оптимальное решение находится как базисное при котором количество ненулевых клеток фиксировано и минимально, при построении начального плана, план может быть не базисным. Иногда полученный план приводят к базисному не важно лучше это или хуже для общих затрат, тогда метод потенциалов работает наиболее эффективно, а циклы строятся так, чтобы клетки очищать полностью.
Дата добавления: 2015-07-11; просмотров: 98 | Нарушение авторских прав