Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 10 стр.

                           ⎧8 x1 + 5 x2 + x3 = 40
                           ⎪
                           ⎨5 x1 + 6 x2 + x4 = 30 .
                           ⎪⎩2 x1 + 5 x2 + x5 = 20
    При этом в далее получаемом решении переменные x3 и x4 будут соответ-
ствовать объемам неиспользованного сырья S1 и S2 , а x5 – неиспользованному
машинному времени.

                      1.4. Методы решения задач ЛП
     Методы решения задач ЛП делятся на два типа: точные и приближенные.
Точные или конечные методы представляют собой симплексные методы опти-
мизации, среди которых можно выделить:
        • непосредственно симплексный метод, называемый также методом
          последовательного улучшения плана;
        • модифицированный симплексный метод;
        • двойственный симплексный метод, называемый также методом по-
          следовательного уточнения оценок;
        • метод одновременного решения прямой и двойственной задач, на-
          зываемый также методом последовательного сокращения невязок.
      К приближенным методам оптимизации относят различные варианты
градиентных схем оптимизации, методы случайного поиска и т.д.
      Наибольшее распространение получили симплексные методы решения
задачи ЛП, по существу представляющие собой последовательный перебор уг-
ловых точек, при котором значение целевой функции улучшается от итерации к
итерации (от одной угловой точки к другой).
      Поясним общую суть этих методов. Для задачи ЛП в канонической форме
с n переменными, подчиненными m ограничениям (m < n), можно получить ре-
шение (хотя и не всегда допустимое), придавая каким либо из (n – m) перемен-
ным произвольные значения и разрешая систему m уравнений относительно ос-
тавшихся m переменных. Особенно интересны решения такого типа, когда
(n – m) переменных приравниваются нулю. Такое решение называют базисным
решением системы из m уравнений с n неизвестными. Переменные, прирав-
ненные к нулю, называются свободными, остальные – базисными и образуют
базис.
      Если полученное решение содержит только положительные компоненты,
то оно называется базисным допустимым или опорным планом.
      Особенность допустимых базисных решений состоит в том, что они яв-
ляются крайними точками ОДР расширенной задачи, т.е. угловой точкой мно-
гогранника решений.
     Опорное решение называется невырожденным, если оно содержит m
положительных компонент (по числу ограничений).
      Невырожденный опорный план образуется пересечением n гиперплоско-
стей из образующих допустимую область. В случае вырожденности в угловой
точке многогранника решений пересекается более n гиперплоскостей.
10