Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 55


Оказывается, аналогичное правило справедливо и в случае n - m = k > 2 (только геометрическая интерпретация теряет в этом случае свою наглядность). Обойдемся без доказательства, просто сформулируем это правило.

Оптимальное решение ОЗЛП (если оно существует) достигается при такой совокупности значений переменных х1, х2,..., хn, где по крайней мере k из них обращаются в нуль, а остальные неотрицательны.

При k = 2 такая совокупность значений изображается точкой на плоскости, лежащей в одной из вершин многоугольника допустимых решений (ОДР). При k =

3 ОДР представляет собой уже не многоугольник, а многогранник, и оптимальное решение достигается в одной из его вершин. При k

> 3 геометрическая интерпретация теряет наглядность, но все же геометрическая терминология остается удобной. Мы будем продолжать говорить о «многограннике допустимых решений» в k-мерном пространстве, а оптимальное решение (если оно существует) будет достигаться в одной из вершин этого многогранника, где, по крайней мере, k

переменных равны нулю, а остальные — неотрицательны. Будем для краткости называть такую вершину «опорной точкой», а вытекающее из нее решение — «опорным решением».

Отсюда вытекает идея, лежащая в основе большинства рабочих методов решения ОЗЛП,— идея «последовательных проб». Действительно, попробуем разрешить уравнения (9.1) относительно каких-нибудь m

базисных переменных и выразим их через остальные k свободных. Попробуем положить эти свободные переменные равными нулю — авось повезет, наткнемся на опорную точку. Вычислим базисные переменные при нулевых значениях свободных. Если все они оказались неотрицательными, значит, нам повезло, мы сразу же получим допустимое (опорное) решение, и его остается только оптимизировать. А если нет? Значит, данный выбор свободных и базисных переменных допустимого решения не дает; точка лежит не на границе, а вне ОДР. Что делать? Надо «переразрешить» уравнения относительно каких-то других базисных переменных, но не как попало, а так, чтобы это приближало нас к области допустимых решений (для этого в линейном программировании существуют специальные приемы, на которых мы останавливаться не будем).


Содержание  Назад  Вперед