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

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

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

3.2 Сущность симплекс-метода. 52

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

3.2.2 Решение задачи в общем виде. Симплексная таблица. 58

3.3 Решение задачи производственного планирования симплекс-методом.. 68

3.4 Вопросы и упражнения. 70

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

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

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

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

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

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

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

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

 ,

где А_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) единичных независимых столбцов, будем называть базисными (х_Б), а остальные переменные - небазисными. Столбцы (вектора), соответствующие базисным переменным, также будем называть базисными. Совокупность этих переменных (или этих векторов) будем называть базисом. Если среди базисных переменных есть нулевые, базис называют вырожденным.

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

3.2 Сущность симплекс-метода