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

Симплекс-метод является аналитическим методом решения задач линейного программирования. Пусть система ограничений задается системой линейных уравнений среди неотрицательных решений этой системы надо найти такие, которые максимизировали (минимизировали) линейную функцию . Найдем ранг данной системы, пусть ранг равен . Выразим переменные через остальные переменные: где , , …, .

Переменные называются базисными, а остальные переменные называются свободными. Подставляя в целевую функцию вместо базисных переменных их выражения через свободные переменные получим . Пологая, что все свободные переменные равны нулю, найдем значения базисных переменных: , ,…., . Полученное решение является допустимым – оно называется базисным. Для полученного базисного решения значение целевой функции . От полученного базиса можно перейти к другому базису с таким расчетом, чтобы значение не увеличивалось.

Рассмотрим пример: решить задачу линейного программирования

,

.

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

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

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

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

Симплексные таблицы

Пусть система ограничений приведена к единичному базису: , целевая функция приведена к виду .

Представим эти данные в виде таблицы:

Базисные переменные	Свободные члены		…		…			…		…
			…		…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
			…		…			…		…
…	…	…	…	…	…	…	…	…	…	…	…
			…		…			…		…
			…		…			…		…

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

Если после проделанных действий:

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

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

3. все значения , тогда получено оптимальное решение.