1.7.2. Обоснование целенаправленности перебора допустимых базисных решений

Определим, как изменяется значение целевой функции ЗЛП при переходе от одного допустимого базисного решения к другому в соответствии с изложенной выше процедурой.

Значения целевой функции для соседних базисных решений определяются следующим образом:

, (1.70)

, (1.71)

где соотношение (1.71) записано с учетом (1.65).

Тогда изменение целевой функции определяется следующим соотношением:

, (1.72)

где величина, заключенная в фигурные скобки, является симплекс-разностью, вычисленной для l-го столбца матрицы А (см. соотношения 1.43, 1.44):

. (1.73)

Нетрудно заметить, что ∆с_l, представляет собой скалярное произведение вектора градиента целевой функции и направляющего вектора S:

. (1.74)

Известно также, что знак скалярного произведения определяется знаком косинуса угла между векторами, входящими в произведение. Сам же косинус положителен только для углов, меньших π/2, то есть для острых углов.

Симплекс-разности могут быть вычислены для всех j=1,2,...,n. При этом с учетом (1.43 и 1.73) вектор-строка симплекс-разностей определяется следующим соотношением:

. (1.75)

Нетрудно также установить, что

для jN(B). (1.76)

Действительно на основе (1.73) и (1.41)

.

Возвратимся к анализу соотношения (1.72), которое можно теперь записать в виде

. (1.77)

Из (1.77) видно, что симплекс-разность определяет скорость изменения целевой функции при перемещении в выбранном направлении.

Чтобы обеспечить положительное приращение целевой функции ∆z0 (напомним, что рассматривается ЗЛП с направлением оптимизации на max) при положительном значении λ(В)0 (по условию всегда λ(В)≥0) необходимо выполнение условия ∆c_l0.

На основе этого из анализа величин симплекс-разностей могут быть сделаны следующие выводы по решению всей ЗЛП:

- сформулированы условия оптимальности найденного допустимого базисного решения;

- определено правило выбора направления дальнейшего перемещения в пространстве оптимизационных переменных, если условие оптимальности не выполняется;

- определено условие реализации такого исхода решения ЗЛП, при котором целевая функция задачи неограниченна на заданном множестве допустимых решений ( ).

Условие оптимальности

Если для заданного В

∆c≤0, (1.78)

то В является оптимальным базисом (В⁰=В), а соответствующее базисное решение – оптимальным решением ЗЛП:

(1.79)

. (1.80)

Необходимо отметить, что условия (1.78) с учетом (1.76) могут быть определены еще и в следующем виде:

для всех . (1.81)

Правило выбора направления дальнейшего перемещения в пространстве оптимизационных переменных (выбора номера столбца l, вводимого в базис).

При выборе очередного направления перемещения хотелось бы обеспечить более быстрый переход к оптимальному решению ЗЛП (если, конечно, оно существует). При решении конкретной ЗЛП, начиная с фиксированного допустимого базисного решения, быстрота поиска ее оптимального решения определяется числом шагов, которые сделает алгоритм при переборе допустимых базисных решений. Рассчитать число шагов заранее невозможно. Интуитивно ясно, что чем быстрее будет возрастать целевая функция на каждом шаге, тем число шагов будет меньше.

Из (1.77) видно, что приращение целевой функции на каждом шаге определяется как величиной симплекс-разности ∆с_l, так и величиной шага λ(В) в выбранном направлении. С учетом необходимости проведения множества шагов задача выбора оптимального маршрута движения в пространстве оптимизационных переменных (маршрута с наименьшим числом шагов) является чрезвычайно сложной. Решать ее строго с целью уменьшения вычислительной сложности работы алгоритма не имеет смысла. Поэтому в большинстве алгоритмов руководствуются следующим простым эвристическим правилом:

на каждом шаге выбор направления движения (выбор столбца l матрицы А, вводимого в базис) осуществляют по максимальной положительной симплекс-разности ∆с_l. Если несколько симплекс-разностей соответствуют максимальному значению, то для определенности среди соответствующих столбцов матрицы А выбирается столбец с наименьшим номером.

Формально это правило записывается в виде следующих соотношений:

, (1.82)

где .

Это правило определяет выбор направления движения по наибольшей скорости роста целевой функции при перемещении от одного допустимого базисного решения к другому и не гарантирует максимальное приращение ∆z даже на одном шаге (рис.1.15).

Можно придумать и более эффективные с точки зрения уменьшения числа шагов (но, соответственно, и более сложные) правила выбора направления движения. Однако исследования показали, что с учетом вычислительной сложности самого этого правила вычислительная сложность всего алгоритма поиска оптимального решения ЗЛП оказывается наименьшей в среднем (для широкого круга практических ЗЛП и вариаций их параметров) именно при применении правила (1.82).

Проверка условия .

Как уже говорилось, указанное условие будет выполняться при выходе на образующую, направляющий вектор которой образует острый угол с градиентом целевой функции.

Формально с учетом (1.68, 1.69, 1.77) это соответствует выполнению следующего условия:

. (1.83)