2015-02-27
344
«методом потенциалов».
Метод потенциалов - одна из разновидностей симплекс-метода, проводимого непосредственно в распределительной таблице: здесь так же вначале ведётся поиск начального опорного решения, а затем после поиска полезной свободной клетки проводят направленные итерации по получению решений с всё меньшим и меньшим значением целевой функции, вплоть до нахождения оптимального решения.
Отличие в рассматриваемом методе заключается только в том, что вместо «оценок клеток» (как известно, рекомендуется выполнять построение циклов со свободными клетками, имеющими отрицательные оценки) будут фигурировать нарушения потенциалов в некоторых свободных клетках.
Нарушения потенциала со знаком плюс в некоторой свободной клетке будет свидетельствовать о том, что с ней можно организовать цикл однократного замещения, ведущий к уменьшению значения целевой функции.
Попутно замётим, что численное значение нарушения потенциала (но с противоположным знаком) в точности равно отрицательной оценке той же самой свободной клетки.
Потенциалы клеток, занятых базисными переменными, в точности равны сумме потенциалов i -ой строки и j -го столбца, поскольку это является исходным условием для понятия потенциалов:
Пijбаз = ui + vj(11.1)
Нарушение потенциала для свободной клетки констатируется в том случае, если:Пijсв. > с ijсв(11.2.)
с ijсв – значение единичной стоимости, записанное в клетке
Численное значение нарушения потенциалов ΔПij равно:
ΔПij = Пijсв. - с ijсв = - о ijсв
Опорное решение в данном алгоритме рекомендуем определять методом минимального элемента (табл. 11.1.).
Таблица 11.1
Z0 = 970. Исходное опорное решение
Стрелками показан “маршрут» прохождения клеток с минимальными элементами, начиная с клетки (5 - 3) с минимальным значением единичной стоимости. Метод минимального элемента обеспечил меньшее значение целевой функции, чем метод северо-западного угла в исходной таблице.
Рассмотрим теперь порядок определения потенциалов и нарушения потенциалов ΔZij по свободным клеткам (табл. 11.2.).
Таблица 11.2
