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

Двумерные задачи линейного программирования решаются графически. Для случая n=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

В общем виде, когда в задаче участвуют n-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более трех, весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.

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

Этот метод является универсальным, применимым к любой задаче линейного программирования, которая с помощью элементарных преобразований может быть приведена к каноническому виду.

f(x) = c₁x₁+c₂x₂+…+c_nx_n max (min).

a₁₁x₁+a₁₂x₂+…+a_1nx_n +х _{n +1} = b₁,.

a₂₁x₁+a₂₂x₂+…+a_2nx_n+х _{n +2} = b₂,.

_.…

a_m1x₁+a_m2x₂+…+a_mnx_n+х _{n +т} = b_m,.

x_i?0 i = .

Сущность симплекс-метода заключается в том, что если число неизвестных больше числа уравнений, то данная система неопределенная с бесчисленным множеством решений. Для решения системы все неизвестные произвольно подразделяют на базисные и свободные. Число базисных переменных определяется числом линейно-независимых уравнений. Остальные неизвестные свободные.

Выразим в системе ограничений базисные неизвестные через небазисные, т. е. разрешим систему относительно базисных неизвестных:

х _{n +1} = a₁₁(-x₁)+a₁₂(-x₂)+…+a_1n(-x_n) +b₁,.

х _{n +2} = a₂₁(-x₁)+a₂₂(-x₂)+…+a_2n(-x_n) + b₂,.

_.…

х _{n +т} = a_m1(-x₁)+a_m2(-x₂)+…+a_mn(-x_n)+b_m.

Свободным неизвестным придают произвольные значения и подставляют в систему. Любому набору свободных неизвестных можно придать бесчисленное множество произвольных значений, которые дадут бесчисленное множество решений. Если все свободные неизвестные приравнять к нулю, то решение будет состоять из значений базисных неизвестных. Такое решение называется базисным.

В теории линейного программирования существует теорема, которая утверждает, что среди базисных решений системы можно найти оптимальное, а в некоторых случаях и несколько оптимальных решений, но все они обеспечат экстремум целевой функции. Таким образом, если найти какой-либо базисный план, а затем улучшить его, то получится оптимальное решение. На этом принципе и построен симплекс-метод.