Линейное программирование. Филькин Г.В. - 10 стр.

     3) Матричная
     4) С помощью знаков суммирования.
     z = c * x - векторная
     A1 X 1 + A2 X 2 + ... + An X n = A0 (Д)
     c = (c1 , c2 ....cn ) x = ( x1 , x2 ....xn ) x j > 0
           ⎛ a11 ⎞        ⎛ a12 ⎞          ⎛ b1 ⎞
           ⎜ ⎟            ⎜     ⎟          ⎜ ⎟
           ⎜a ⎟           ⎜ a22 ⎟          ⎜b ⎟
      A1 = ⎜ 21 ⎟    A2 = ⎜           A0 = ⎜ 2 ⎟
             ...            ... ⎟            ...
           ⎜ ⎟            ⎜     ⎟          ⎜ ⎟
           ⎜a ⎟           ⎜a ⎟             ⎜b ⎟
           ⎝ m1 ⎠         ⎝ m2 ⎠           ⎝ m⎠
      Определение 1. Планом или допустимым решением задачи ЛП назы-
вается набор переменных (х) удовлетворяющий условию (Д)
      Определение 2. План х называется опорным, если векторы АJ входя-
щие в разложение (Д) с положительными коэффициентами являются линейно
независимыми.
      Определение 3. Оптимальным решением задачи ЛП называется набор
переменных, в котором достигается max или min.
      Замечание: В спорный план может входить не более чем m векторов.
      Определение 5. Множество называется выпуклым, если вместе с лю-
быми 2мя точками оно содержит отрезок их соединяющий.
      В задачах ЛП область допустимых решений всегда выпукла.
      Определение 6. Непустое множество решений канонической задачи
называется многогранником решений, а всякая опорная точка является угло-
вой, т.е. вершиной многогранника.
      Справедлива теорема: Если каноническая задача ЛП имеет оптималь-
ное решение, то max значение целевой функции принимает в одной из вер-
шин. Если оптимальное решение принимается более чем в одной точке, то
множество оптимальных решений бесконечно и состоит из точек являющих-
ся выпуклой линейной комбинацией нескольких вершин.
      Теорема: Если система векторов в разложении (1) линейно независима
и такова: X1A1+X2A2+….+XiAi=A0          Xi>0, то точка с координатами (Х1,
Х2…..Хi, 0, 0,….,0) является опорным планом многогранника решений.
      Выводы:
      1. Непустое множество решений канонической задачи ЛП образует
выпуклый многогранник;
      2. Каждая вершина этого многогранника определяет опорный план;
      3. В одной из вершин значение целевой функции является оптималь-
ным (максимальным, если функция ограничена сверху на множестве допус-
тимых решений);
      4. Если максимальное значение функция Z принимает более чем од-
ной точке, то она принимает это значение на выпуклой линейной комбина-
ции данных точек.

     Симплексный метод.


                                                       9