Симплекс-метод решения задачи линейного программирования

Графический способ решения задачи линейного программирования целесообразно использовать для задач небольшой размерности (с двумя переменными) или задач, которые могут быть сведены к задачам с двумя переменными. Можно строить и трехмерные графики, хотя это уже несколько сложнее. Достоинствами этого метода являются его простота и наглядность. Однако на практике при построении экономико-математических моделей обычно вводится большее количество переменных, что делает необходимым использование более сложных методов.

Симплекс-метод представляет собой общий аналитический метод решения задачи линейного программирования*.

Так же, как и при использовании графического способа решения, идея симплекс-метода состоит в рассмотрении вершин области допустимых планов (ОДП) в многомерном пространстве и в определении на основании некоторого критерия, является ли рассматриваемый план оптимальным.

При этом симплекс-метод предлагает алгоритм такого направленного перебора этих вершин, при котором нет необходимости рассматривать их все, поскольку при переходе от одного плана к другому происходит приближение к искомому решению (или установление неразрешимости).

Однако, если при использовании графического метода вершины ОДП можно было определить визуально, то в симплекс-методе это уже можно сделать только аналитически. Поэтому для описания алгоритма рассматриваемого метода необходимо ввести некоторые понятия.

Векторная запись задачи линейного программирования. Опорный план

Система ограничений задачи линейного программирования, приведенной к канонической или стандартной форме, может быть записана в векторной форме следующим образом:

,

где А_j = - векторные коэффициенты; B= , X= , R Î {£;³;=}.

Будем считать, что система ограничений задачи в канонической форме представляет собой линейно независимую систему уравнений (в противном случае часть уравнений можно просто вычеркнуть).

Опорным планом задачи линейного программирования в канонической форме называется такой допустимый план, совокупность векторных коэффициентов при ненулевых компонентах которого представляет собой систему линейно независимых векторов*.

Например, представим систему ограничений задачи, записанной в канонической форме, в векторной форме:

2х₁ + 3х₂ - х₃ + х₄ = 5

4х₁ + 6х₂ + 2х₃ + х₅ = 10

х_1-5 ³ 0

А₁ = , А₂ = , А₃ = , А₄ = , А₅ = , В = , Х = ;

.

Рассмотрим план Х⁽¹⁾ = (0; 0; 0; 5; 10). Этот план является допустимым, в чем легко убедиться, подставив его в систему ограничений:

2*0 + 3*0 - 0 + 5 = 5

4*0 + 6*0 + 2*0 + 10 = 10

0 ³ 0

5 ³ 0

10 ³ 0

Отличными от нуля являются переменные х₄ и х₅. Векторные коэффициенты при этих переменных А₄ = и А₅ = являются линейно независимыми. В самом деле, . Следовательно, план Х⁽¹⁾ является опорным.

Убедимся в том, что отнюдь не любой допустимый план является опорным. Для этого рассмотрим другой план Х⁽²⁾ = (1; 1; 0; 0; 0). Здесь ненулевыми компонентами плана являются переменные х₁ и х₂. Этот план тоже является допустимым:

2*1 + 3*1 - 0 + 0 = 5

4*1 + 6*1 + 2*0 + 0 = 10

1 ³ 0

0 ³ 0

Однако этот план не является опорным, так как можно подобрать отличные от нуля числа d₁ и d₂, при которых d₁А₁+ d₂А₂ = d₁ +d₂ = . Таких чисел бесконечно много, например, d₁ = 3, d₂ = -2.

Можно доказать [6], что каждой вершине ОДП задачи линейного программирования соответствует опорный план. Поэтому, чтобы найти оптимальный план в одной из вершин, симплекс-метод перебирает именно опорные планы задачи линейного программирования.

Очевидно, что ненулевых компонент в опорном плане может быть не больше, чем ограничений в задаче (в рассмотренном примере невозможно построить три двумерных линейно независимых вектора, поэтому ненулевых компонент не может быть больше двух). Для реализации симплекс-метода необходимо, чтобы в опорном плане присутствовало ровно m линейно независимых векторов, т.е. базис m–мерного пространства. В случае, если ненулевых компонент в опорном плане меньше, чем m, один или несколько из этих векторов могут соответствовать и нулевым переменным. Переменные, столбцы коэффициентов при которых образуют полную систему (m) единичных независимых столбцов, будем называть базисными (х_Б), а остальные переменные - небазисными. Столбцы (вектора), соответствующие базисным переменным, также будем называть базисными. Совокупность этих переменных (или этих векторов) будем называть базисом. Если среди базисных переменных есть нулевые, базис называют вырожденным.

Например, в плане Х⁽¹⁾ в базис входили переменные х₄ и х₅, и базис был невырожденным.