Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 10

Полезно отметить, что в геометрической интерпретации переход от одного опорного плана к другому в симплекс-методе соответствует перемещению одной из крайних точек к другой вдоль ребра выпуклого многогранника. (Другими словами, в задаче ЛП “движение” осуществляется по соседним вершинам многогранника) [4…6].

Рассмотрим далее вопрос о применимости симплекс-метода для решении задач ЛП, первоначально заданных в канонической форме, не имеющей  базисных переменных.

В этом случае для нахождения исходного опорного плана используется   метод искусственного базиса. В этом методе вместо исходной канонической задачи  (2.4) рассматривается расширенная задача с n+m переменными, полученная введением в систему ограничений AX=B  задачи (2.4)  искусственных переменных x_n+i  ³ 0 (i =1, …, m ).

Эти переменные включаются в целевую функцию с одинаковыми отрицательными коэффициентами  – M, где M – сколь угодно большое положительное  число:

                   max z =c_jx_j – M                          (2.21)

                   a_ijx_j  + x_n+i = b_i ,       i = 1, …, m;                (2.22)

                           x_j ³ 0,     j = 1, …, n+m.                             (2.23)

Расширенная задача  (2.21) – (2.23) иногда называется M- задачей, а метод искусственного базиса –  M- методом. Единичные векторы-столбцы A_n+1, A_n+2, …, A_n+m матрицы условий M-задачи, соответствующие искусственным переменным, составляют искусственный единичный базис. Ему соответствуют очевидный начальный опорный план X = (0, 0, …, 0, b₁, b₂, …, b_m ), имеющий n+m компонент, аналогичный (2.16), где нулевыми являются первые n координат, и значение целевой функции

                                    z = – M 

Числа  – M , по абсолютной величине значительно превосходящие остальные коэффициенты целевой функции, позволяют выводитьиз базиса искусственные переменные и  вводить  в базис переменные исходной задачи.

З а м е ч а н и е  2.16. Возможен случай, когда часть переменных в исходной канонической задаче ЛП уже являются базисными. В этом случае соответствующие им столбцы включаются в базис, а число вводимых искусственных переменных уменьшается на число таких переменных.

Таким образом, имея начальный опорный план, можно применить симплекс-метод для отыскания оптимального плана расширенной задачи (2.21) – (2.23).

При этом для обратного перехода от  расширенной задачи к исходной канонической задаче используется теорема [4], основное содержание которой состоит в следующем: если в оптимальном плане M-задачи

X_опт = (x₁, x₂,…, x_n, 0, … ,0) все искусственные переменные равны нулю, т.е. x_n+i = 0, (i=1, …, m), то первые n координат этого плана дают оптимальный план исходной задачи.

З а м е ч а н и е  2.17. Переход от решения расширенной задачи к исходной задаче в М - методе аналогичен переходу от решения задачи в канонической форме к задаче в стандартной форме, рассмотренному  на этапе 2.

Отметим также, что метод искусственного базиса используется для решения задач ЛП, в которых ряд неравенств имеют знак «больше или равно» [4] .

Рассмотрим далее вычислительную схему симплекс-метода. Как указывалось ранее, рассматриваемый метод применим к задаче ЛП, имеющей каноническую базисную форму, характеризующуюся системой ограничений вида (2.5) с неотрицательными коэффициентами вектора ограничений  b_i  ³ 0. 

Условия такой задачи удобно задать в виде так называемой симплекс-таблицы (таблица 2.1).

Таблица 2.1