Симплекс-метод решения задач линейного программирования
Симплекс-метод является аналитическим методом решения задач линейного программирования. Пусть система ограничений задается системой линейных уравнений 
среди неотрицательных решений этой системы надо найти такие, которые максимизировали (минимизировали) линейную функцию 
. Найдем ранг данной системы, пусть ранг равен 
. Выразим переменные 
через остальные переменные: 
где 
, 
, …, 
.
Переменные называются базисными, а остальные переменные называются свободными. Подставляя в целевую функцию 
вместо базисных переменных их выражения через свободные переменные получим 
. Пологая, что все свободные переменные равны нулю, найдем значения базисных переменных: 
, 
,…., 
. Полученное решение 
является допустимым – оно называется базисным. Для полученного базисного решения значение целевой функции 
. От полученного базиса можно перейти к другому базису с таким расчетом, чтобы значение 
не увеличивалось.
Рассмотрим пример: решить задачу линейного программирования 
, 
.
Перепишем систему линейных ограничений в виде 
, введя новые балансовые переменные 
. Найдем ранги основной 
и расширенной матрицы системы 
. Ранги совпадают и равны двум, следовательно система совместна и две базисные переменные (например 
) можно выразить через три свободные ( 
): 
. Целевую функцию также выразим через свободные переменные 
, тогда при 
, 
, 
найдем значения базисных переменных 
, 
. Таким образом найдено допустимое решение системы 
. При данном допустимом решении целевая функция 
.
Выясним, можно ли увеличить значение ; увеличение 
приведет к уменьшению целевой функции т.к. перед переменной стоит знак минус, а увеличение 
приведет к увеличению целевой функции. Поэтому увеличим так, чтобы базисные переменные не стали отрицательными, оставив равными нулю. Из уравнения 
следует, что можно увеличить до двух, в результате получим новые значения переменных 
, , , 
, 
или 
.
Примем за свободные переменные 
и выразим через них 
. Из уравнения получим 
. Подставим это выражение для в уравнение 
, получим 
. Значение целевой функции при новом допустимом решении найдем подставив выражение для в , получим 
, при новом допустимом решении 
, т.е. оно увеличилось. Тогда
так как свободные переменные входят в целевую функцию с отрицательными знаками, дальнейшее увеличение невозможно. Значит, решение является оптимальным и 
.
Симплексные таблицы
Пусть система ограничений приведена к единичному базису: , целевая функция приведена к виду 
.
Представим эти данные в виде таблицы:
| Базисные переменные | Свободные члены | 
| … | 
| … | 
| 
| … | 
| … | 
|
|
| 
| … | … | 
| … | 
| … | 
| |||
| … | … | … | … | … | … | … | … | … | … | … | … |
|
| 
| … | … | 
| … | 
| … | 
| |||
| … | … | … | … | … | … | … | … | … | … | … | … |
|
| 
| … | … | 
| … | 
| … | 
| |||
| 
| … | … | 
| … | 
| … | 
|
Выберем разрешающий столбец 
из условия: 
и хотя бы один из элементов 
. Затем выберем разрешающую 
-ю строку из условия 
для . Произведем пересчет элементов разрешающей -й строки по формуле 
, где 
. Элементы всех остальных строк вычисляем по формуле 
, где 
.
Если после проделанных действий:
1. найдется хотя бы одно отрицательное значение 
и в каждом столбце с таким значением окажется хотя бы один положительный элемент, то можно улучшить решение, проделав еще одну итерацию;
2. найдется хотя бы одно отрицательное значение , столбец которого не содержит положительных элементов, тогда целевая функция не ограничена в области допустимых решений т.е. 
;
3. все значения 
, тогда получено оптимальное решение.