Геометрическая интерпретация симплексного метода

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

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т. е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума , уменьшение – при отыскании минимума).

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

Пусть область допустимых решений изображается многоугольником ABCDEGH (рис). Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать семь допустимых базисных решений, соответствующих семи угловым точкам многоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем к оптимальной точке С.

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

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования- симплексного метода (лат. Simplex – простой, простейший выпуклый многогранник в П-мерном пространстве с n+1 вершиной, например, тетраэдр в 3-мерном пространстве).

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

Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л. В. Канторовичем.

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

Для реализации симплексного метода – последовательного улучшения решения – необходимо освоить три основных элемента:

· способ определения какого-либо первоначально допустимого базисного решения задачи;

· правило перехода к лучшему (точнее не худшему) решению;

· критерий проверки оптимальности найденного решения.

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

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

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

Считаем, что матрица А размера , m<n, имеет ранг, равный m. Тогда система уравнений (2) совместна и имеет бесчисленное множество решений.

Из курса линейной алгебры известна процедура получения общего решения системы (2) методом последовательных исключений Жордана – Гаусса.

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

Выполним элементарные преобразования строк расширенной матрицы системы (А/b) так, чтобы в первых m столбцах располагалась единичная матрица. В результате получим следующую систему уравнений, эквивалентную исходной:

тогда общее решение системы уравнений (2) запишется следующим образом:

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

Положив их равными нулю, получим частное решение:

или

,

которое называется базисным решением этой системы.

Если все компоненты базисного решения (6) удовлетворяют условию неотрицательности, т.е. если , то такое решение называют допустимым базисным решением системы (2) или угловой точкой допустимого множества Е задачи линейного программирования (1)…(3). Если среди неотрицательных чисел в (6) есть равные нулю (), то допустимое базисное решение называется вырожденным (вырожденной угловой точкой), а соответствующая задача линейного программирования также называется вырожденной, а в противном случае () – невырожденной.

В основе симплекс – метода лежит следующий факт: если задача линейного программирования (1)…(3) разрешима, то минимум целевой функции из (1) достигается хотя бы в одной из угловых точек допустимого множества Е этой задачи.

Каждому выбору m базисных переменных системы (2) соответствует свое базисное решение. Поэтому число базисных решений (угловых точек) равно числу всевозможных базисных миноров матрицы А, т.е. не превосходит .

Предположим что задача линейного программирования (1)…(3) является невырожденной, а базисное решение (6) – допустимым.

Выразим целевую функцию задачи (1)…(2) через свободные переменные решения (6). Для этого подставим выражения базисных переменных через свободные из (5) в равенство (1):

,

где

Задача линейного программирования

имеет канонический вид, соответствующий допустимому базисному решению . Ее можно записать компактно, с помощью так называемой симплекс - таблицы (табл. 1)

симплекс – таблица. Табл.1

. . . . . .	. . . . . .	. . . . . .
	……

Строке с номером i таблицы 1 соответствует i-ое уравнение системы (9): , а в последней строке записаны коэффициенты из выражения (8) и значение , взятое со знаком минус.

Пример . Записать одну из симплекс – таблиц для задачи:

q Для того, чтобы перейти к каноническому виду рассматриваемой задачи, прибавим к левым частям соответствующих ограничений – неравенств дополнительные переменные :

В качестве базисных переменных удобно выбрать , тогда переменные x₁ и x₂ будут свободными. Выпишем общее решение системы уравнений из (11):

Полагая свободные переменные x₁ и x₂ равными нулю, получаем базисное решение . Очевидно, оно является допустимым базисным решением или угловой точкой множества Е. Так как целевая функция задачи (11) зависит лишь от свободных переменных, то выражения (11) представляют собой канонический вид задачи линейного программирования, соответствующий допустимому базисному решению . Таким образом искомая симплекс – таблица имеет вид (табл. 2):