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

задаётся системой линейных уравнений следовательно можно просто пере-
бирать решения системы линейных уравнений. Перебирать точки не как по-
пало, а следуя некоторому алгоритму. Все эти идей были заложены Хичко-
ком при создании универсального метода решения задач ЛП (симплекс-
метод).

     ПРИВЕДЕНИЕ ЗАДАЧИ К КАНОНИЧЕСКОМУ ВИДУ

      Прежде чем решать симплекс-методом их нужно привести к канониче-
скому виду. Для приведения задач к каноническому виду требуется проде-
лать:
      1) Привести все неравенства в уравнения введением дополнительных
переменных.
      2) Все свободные члены должны быть >0. (В случае необходимости
умножить на (-1))
      3) Все переменные должны быть >0.
      4) В матрице системы уравнений должна содержаться единственная
подматрица порядка m (m - количество уравнений в системе ограничений).
      5) Задача решается на максимум.
      Покажем на примере, как приводят задачу к каноническому виду.
     z = 2 x1 + 3 x2 − x3 → min
     w = − z = −2 x1 − 3 x2 + x3 → max
     ⎧              2 x1 + 3 x2 ≤ 3
     ⎪               x1 − 4 x2 ≤ 4
     ⎪
     ⎨
     ⎪ x1 + 3x3 ≥ −9            − x1..... − x3 ≤ 9
     ⎪⎩              x1 , x2 , x3 ≥ 0
      ⎧ 2 x1 + x2 + x4 = 3
      ⎪ x − 4x = 4                                 ⎛ 2  1  0 1 0 0⎞
      ⎪      1       2
                                                   ⎜              ⎟
      ⎨                                        A = ⎜ 1 − 4 0 0 1 0⎟
      ⎪− x1 ..... − x3 = 9                         ⎜ −1 0 −1 0 0 1⎟
      ⎪⎩ xj ≥ 0        j = 1, i                    ⎝              ⎠

      Заметим, что в матрице системы ограничений столбцы единичной под-
матрицы могут быть переставлены местами .
      В процессе приведения задачи к каноническому виду мы вместо z вве-
ли w=-z, там, где функция z достигает минимума функция w достигает мак-
симума. Также были введены дополнительные переменные x4,x5,x6. кроме то-
го, иногда при приведении задачи к каноническому виду приходится вводить
искусственные переменные.

     Основные определения и теоремы.

     Общая задача ЛП имеет несколько форм записи.
     1) Развёрнутая
     2) Векторная

                                              8