Cтраница 2
Сеточный поиск может окончиться и раньше, если величина пробных шагов станет слишком малой. Если сеточный поиск закончился, а в симплексном множестве не появились новые переменные, то задача считается решенной. В противном случае те переменные, которые при сеточном поиске покинули е-окрестности своих границ, переводятся из сеточного в симплексное множество. Затем выполняется следующий симплексный поиск. Напомним, что ограничения общего вида учитываются штрафами. Поэтому как в сеточной, так и в симплексной фазе алгоритм минимизирует функцию вида (7.8.1) при оставшихся простых ограничениях. [16]
При работе алгоритма каждый симплекс представлен в матричной форме. Столбцы матрицы соответствуют его вершинам, строки - номерам переменных из симплексного множества. Пусть некоторая переменная переходит из симплексного множества в сеточное. Тогда из матрицы исключаются столбец, соответствующий вершине, из-за которой произошел переход, и строка, соответствующая этой переменной. Когда происходит обратный переход, к матрице добавляется строка, все элементы которой равны значению новой симплексной переменной. Далее добавляется новый столбец, все элементы которого, кроме последнего, равны элементам столбца, соответствующего наилучшей вершине. Последние компоненты этих столбцов отличаются на величину пробного шага, используемого при сеточном поиске. В результате получается симплекс большей размерности, с которого можно начинать очередную симплексную фазу алгоритма. [17]