Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. A) принятие решения о финансировании одного из них не влияет на принятие решения о финансировании другого;
  2. Gt; во-вторых, когнитивной оценкой (cognitive appraisal), которую человек дает событию, требующему разрешения.
  3. II. Пример решения.
  4. III. Алгоритм решения кинематических задач
  5. III. Когда выгодно рассматривать движение из движущейся системы отсчета (решения двух задач учителем)?
  6. III. Примеры решения задач.
  7. III. Примеры решения задач.
  8. III. Примеры решения задач.
  9. IV. Примеры решения задач.
  10. IV. Примеры решения задач.

Для системы из 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. Далее движенне не возможно, поскольку нет ребра, образующего острый угол с направлением антиградиента.


Дата добавления: 2015-04-16; просмотров: 15; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2022 год. (0.019 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты