Геометрическая интерпретация решения СЗЛП


Для системы из m уравнений с n неизвестными существует бесконечное множество решений, зависящее от r = n – m параметров. Любой элемент такого множества может быть представлен точкой в пространстве независимых переменных. Для рассмотренного примера пространство независимых переменных представляет собой плоскость с осями координат и . Область допустимых значений задачи ЛП ограничивается требованиями неотрицательности всех переменных, в том числе и независимых . Отсюда ОДЗ ограничивается первым квадрантом плоскости .

Условие неотрицательности зависимых переменных может быть представлено выбором полуплоскоси

Для идентификации полуплоскостей целесообразно проанализировать, в какой области лежит точка . Так для первого уравнения точке соответствует . Отсюда эта точка лежит в допустимой области.

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

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

В многомерной геометрии точку пересечения r плоскостей вместе с выходящими из этой точки лучами называют симплексом порядка r. Этим и объясняется название базового метода решения СЗЛП– симплекс-метод.

Ф=-10
В результате построения подобластей формируется многоугольник (ABCDE на рис. 8.4) , все внутренние точки которого представляют собой допустимые сочетания зависимых переменных.

В рассматриваемом примере m = 3, n = 5. Отсюда максимальное число базисных решений

Рис. 8.4. Геометрическая интерпретация

Однако допустимых (удовлетворяющих условию ) базисных решений только 5 (5 базисных решений являются недопустимыми, например вершина, соответствующая х1=0, х5=0. поскольку здесь х4<0).Именно допустимые базисные решения образуют множество вершин многогранника ОДЗ.

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

перпендикулярен линии равного уровня . Наиболее удаленная в направлении антиградиента вершина многогранника ABCDE это точка D (х2=0, х3=0), которая и является решением СЗЛП.

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

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

В рассматриваемом примере движение из начальной вершины А осуществляется по ребру АЕ (х5=0, х4=var) до пересечения с линией х3=0 (вершина Е), где производится замена базиса (х4 х3). Далее движение выполняется по ребру ED (х5=var, х3=0) до пересечения в точке D с линией х2=0. Далее движенне не возможно, поскольку нет ребра, образующего острый угол с направлением антиградиента.



Дата добавления: 2020-07-18; просмотров: 328;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.