Задача линейного программирования. Горячев Л.В. - 3 стр.

                                                                                           3

   Задача линейного программирования (ЛП) является наиболее простой среди экстремальных
задач с ограничениями. Студент, прослушавший курс "Методы оптимизации", должен хорошо знать
свойства таких задач и уверенно владеть методами численного решения.
   Однако практические занятия по второму курсу учебной программой не предусмотрены, а те
один-два примера, рассмотренные на лекции, вряд ли могут быть достаточными для выработки у
студентов твердых навыков. Поэтому необходимость в методическом руководстве для более деталь-
ного знакомства с численным методом (симплекс-методом) решения задач ЛП очевидна.
                                   Общие свойства ЛП
   К рассмотрению темы "Линейное программирование"мы приступаем после знакомства с общей
теорией задач выпуклого программирования. поэтому предполагается, что теорема Куна-Таккера и
свойства пары двойственных задач выпуклого программирования студентам известны, нам остается
лишь кратко напомнить основные свойства задач линейного программирования, доказательства
которых легко вытекают из общей теории.
   Задача ЛП в достаточно общем виде может быть записана так:
                                            (c, x) − max
                                               Ax = b
где
       c = (c1 , c2 , . . . , cn )T — мерный вектор-столбец коэффициетов
       x = (x1 , x2 , . . . , xn )T — мерный вектор-столбец неизвестных
       A = (aij ), m × n            — матрица коэффициентов
       B = (b1 , b2 , . . . , bm )  — вектор-столбец коэффициентов
      Однако при решении удобно пользоваться канонической формой задачи:
                                         (c, x) − max                                     (1)
                                               Ax = b                                     (2)
                                                x≥0                                       (3)
где A = (aij ) — (m × n)–матрица коэффициентов, m < n, ранг A = m.
   В этом случае мы имеем дело с неотрицательными решениями системы уравнений.
   Любая задача ЛП с помощью элементарных преобразований может быть приведена к канони-
ческому виду.
   Рассмотрим задачу ЛП в следующем виде:
                                            (c, x) − max                                  (4)
                                Ax ≤ b – ограничеия-неравенства                           (5)
                             x ≥ 0 – ограничения неотрицательности                        (6)
Задачу (4)–(6) можно рассматривать как задачу выпуклого программирования, то есть целевая
функция является выпуклой, а многогранное множество допустимых планов выпукло.
   Согласно общей теории задача (4)–(6) может быть записана с помощью функций Лагранжа
                                   max min [(c, x) + (y, b − Ax)]
                                   x≥0 y≥0

двойственная к ней имеет вид             
                      
                                  min max (y, b) + (c − AT y, x)
                                  y≥0 x≥0

В эквивалентной форме мы можем записать
                                             (y, b) − min                                 (7)
                                                T
                                              A y≥c                                       (8)
                                                y≥0                                       (9)
Задача (7)–(9) называется двойственной (сопряженной) к задаче (4)–(6), обе они образуют пару
двойственных или сопряженных задач в симметричной форме.
   Другая пара двойственных задач в симметричной форме может быть получена аналогично.