![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Геометрическая интерпретация решения СЗЛПДля системы из m уравнений с n неизвестными существует бесконечное множество решений, зависящее от r = n – m параметров. Любой элемент такого множества может быть представлен точкой в пространстве независимых переменных. Для рассмотренного примера пространство независимых переменных представляет собой плоскость с осями координат Условие неотрицательности зависимых переменных может быть представлено выбором полуплоскоси Для идентификации полуплоскостей целесообразно проанализировать, в какой области лежит точка Если построен начальный базис (как в нашем случае), то точка, где независимые переменные равны нулю должна удовлетворять ОДЗ. Отсюда точка В силу линейности целевой функции ее градиент
![]() В рассматриваемом примере m = 3, n = 5. Отсюда максимальное число базисных решений
Однако допустимых (удовлетворяющих условию Как было отмечено, направлением движения к оптимальному решению является антиградиент перпендикулярен линии равного уровня Однако алгоритмически движение не может осуществляться строго по направлению антиградиента, поскольку в этом направлении возможен выход за пределы ОДЗ. В симплекс-алгоритме движение осуществляется только по ребрам многогранника. При этом на каждом шаге выбирается ребро, наиболее близкое к антиградиенту (наименьший по модулю острый угол между направлениями ребра и антиградиента). Шаг оканчивается в следующей вершине, служащей основанием нового симплекса. Наконец в точке В рассматриваемом примере движение из начальной вершины А осуществляется по ребру АЕ (х5=0, х4=var) до пересечения с линией х3=0 (вершина Е), где производится замена базиса (х4
|