Симплексный метод решения задач линейного программирования
Симплексный метод – это метод последовательного улучшения плана. Этим методом можно решать задачи линейного программирования с любым количеством переменных и ограничений.
Этот метод включает в себя три основные этапа:
- Построение начального опорного плана.
- Правило перехода к лучшему (точнее, нехудшему) решению.
- Критерий проверки найденного решения на оптимальность.
1) Построение начального опорного плана.
Данную задачу линейного программирования необходимо сначала привести к каноническому виду; при этом правые части ограничений должны быть неотрицательными. Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной. Базисной называют плановую переменную, которая входит только в одно уравнение (а в другие не входит), и при этом имеет коэффициент, равный единице. Пусть задача линейного программирования приведена к каноническому виду, и все уравнения системы ограничений имеют свою базисную переменную. Приравняв базисные переменные к соответствующим правым частям ограничений, а остальные переменные к нулю, получим опорное или базисное решение задачи. Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение). 
max 
Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой: В каждом ограничении слева добавим положительную переменную 
, соответственно запишем канонический вид задачи: 
max 
. Переменные 
базисные. Приравниваем их к правым частям ограничений:
Все остальные переменные – свободные, приравниваем их к нулю: 
Запишем теперь начальный опорный план 
(0; 0; 0; 0; 16; 4; 0).
2) Составление симплексных таблиц. Критерий оптимальности.
Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:
| Базис |  | В |  |  | … |  |  |
 |  | … |  | ||||
 |  |  |  |  | … |  | |
 |  |  |  |  | … |  | |
| … | … | … | … | … | … | … | |
 |  |  |  |  | … |  | |
 |  |  |  | … |  | ||
Здесь приняты следующие обозначения. Столбец «Базис» – это базисные переменные. Столбец «
» – это коэффициенты при базисных переменных в целевой функции. Столбец «В» – правые части ограничений; 
–коэффициенты при переменных в ограничениях; 
–коэффициенты при переменных в целевой функции. Последняя строка в таблице (
) – это проверочная или оценочная строка. 
–значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца 
умножают на соответствующий элемент столбца В и произведения складывают, т.е. 
. 
–называют оценками или симплексными разностями и находят так: элементы столбца 
умножают на соответствующие элементы столбца
, складывают результаты и вычитают
. Например, 
. Оценки (
) базисных переменных всегда равны нулю. Признак оптимальности опорного плана состоит в следующем: Опорный план будет оптимальным тогда и только тогда, когда все оценки 
для задачи на max и 
для задачи на min. Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных. Переменная, которую нужно ввести в базис, соответствует той оценке 
, которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называютразрешающим. Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения 
. Выбирают из
наименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называетсяразрешающей. На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент. Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере. Пример. Решить симплексным методом задачу линейного программирования. 
max 
Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства. 
max 
2) Определяем базисные переменные – это 
. 3
) Заполняем первую таблицу
| Базис |  | В | 2 | 3 | 0 | 0 | 0 | 0 |  |
 |  |  |  |  |  | ||||
 | 0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 |  |
 | 0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 |  |
 | 0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 |  |
 | 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
 |  0 |  –2 |   –3 |  0 |  0 |  0 |  0 | ||
Здесь 
и
не удовлетворяют условию оптимальности, т. к. они меньше нуля. Выбираем среди них большее по модулю. Это
. Следовательно, столбец переменной
– разрешающий. Значит, в новый базис нужно ввести переменную
. Находим 
:
;
; 
Наименьшее из этих чисел – это число 5, что соответствует строке базисной переменной 
. Значит, строка базисной переменной
– разрешающая, следовательно, из базиса нужно вывести переменную
. Элемент
=1 – разрешающий. Новый базис:
. Заполнение следующей таблицы начинаем со столбцов «Базис» и «
». Потом заполняем разрешающую строку, разделив каждый ее элемент на разрешающий, т.е. на 1. Все элементы разрешающего столбца будут нулями, кроме разрешающего, который всегда равен 1. Столбцы под
переписываем без изменения, т. к. эти переменные остались в базисе. Остальные элементы новой таблицы находим по правилу прямоугольника. Например, элемент
найдем из прямоугольника 
= 
Или элемент 
=
из прямоугольника Оценки 
для новой таблицы можно находить по этому же правилу. В
целом, решение данной задачи симплексным методом в виде таблиц будет иметь вид
| Базис |  | В | 2 | 3 | 0 | 0 | 0 | 0 |  |
 |  |  |  |  |  | ||||
 | 0 | 18 | 1 | 3 | 1 | 0 | 0 | 0 | 6 |
 | 0 | 16 | 2 | 1 | 0 | 1 | 0 | 0 | 16 |
 | 0 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
 | 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | – |
 | 0 | –2 | –3 | 0 | 0 | 0 | 0 | таб. 1 | |
 | 0 | 3 | 1 | 0 | 1 | 0 | –3 | 0 | 3 |
 | 0 | 11 | 2 | 0 | 0 | 1 | –1 | 0 | 5,5 |
 | 3 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | – |
 | 0 | 21 | 3 | 0 | 0 | 0 | 0 | 1 | 7 |
 | 15 | –2 | 0 | 0 | 0 | 3 | 0 | таб. 2 | |
| Базис |  | В | 2 | 3 | 0 | 0 | 0 | 0 |  |
 |  |  |  |  |  | ||||
 | 2 | 3 | 1 | 0 | 1 | 0 | –3 | 0 | – |
 | 0 | 5 | 0 | 0 | –2 | 1 | 5 | 0 | 1 |
  | 3 | 5 | 0 | 1 | 0 | 0 | 1 | 0 | 5 |
 | 0 | 12 | 0 | 0 | –3 | 0 | 9 | 1 |  |
 | 21 | 0 | 0 | 2 | 0 | –3 | 0 | таб. 3 | |
 | 2 | 6 | 1 | 0 | –0,2 | 0,6 | 0 | 0 | |
 | 0 | 1 | 0 | 0 | –0,4 | 0,2 | 1 | 0 | |
 | 3 | 4 | 0 | 1 | 0,4 | –0,2 | 0 | 0 | |
 | 0 | 3 | 0 | 0 | 0,6 | –1,8 | 0 | 1 | |
 | 24 | 0 | 0 | 0,8 | 0,6 | 0 | 0 | таб. 4 | |
О
ценочная строка четвертой таблицы показывает, что получен оптимальный план, так как все
. 
–это значения 
из столбца В, т.е.
,
,
,
. Свободные (небазисные) переменные 
. Итак, 
= (6; 4; 0; 0; 1; 3), 
= 
= 24. Примечание: При переходе от таблицы к таблице для контроля сравнивают 
, которое должно быть не меньше предыдущего для задачи на максимум и не больше предыдущего – для задачи на минимум. При использовании симплексного метода возможны следующие случаи. 1) Если в оценочной строке симплекс-таблицы оценка 
= 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план. 2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует. Задания для самостоятельной работы. Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:
| а) |  max   | б) |  min   |
3.2. Симплекс-метод решения задач линейного программирования
Поскольку, как было показано в п. 3.1 решение задачи линейного программирования находится в одной из крайних (угловых) точек ОДЗ, важным вопросом является изучение не системы неравенств (4), а соответствующей системы уравнений AX = B, решение которой дает угловые точки ОДЗ.
Если уравнения системы АX = B линейно независимы, то система имеет множество решений при n > m и единственное решение при n = m. При решении задачи линейного программирования симплекс-методом всегда будет выполняться n > m, поэтому для получения некоторого одного решения, «лишние» n – m переменных приравниваются нулю.
Если приравнять к нулю n – m произвольных переменных (например, переменные xm+1, xm+2, …, xn) и, решив систему, найти значения оставшихся m переменных (x1, x2, …, xm), то такое решение называется базисным.
Если нулю приравнять некоторые другие n – m переменных – получим другое базисное решение. Любое базисное решение, у которого все переменные неотрицательные называется допустимым базисным решением.
Переменные, которые были приравнены нулю, называются небазисными. Оставшиеся т переменных, значение которых получены из решения системы, называются базисными.
Допустимое базисное решение представляет собой угловую вершину ОДЗ.
Решение задачи симплекс-методом сводится к направленному перебору смежных друг с другом угловых точек, которые представляют собой допустимые базисные решения.
Сформулируем в общем виде алгоритм симплекс-метода:
1: Приведение задачи к стандартной форме. Стандартной формой задачи линейного программирования будем называть задачу, у которой все ограничения записаны как равенства и при этом правые части ограничений неотрицательны.
2: Выделение исходного базисного решения (по возможности из стандартной формы). То есть определение тех переменных n – m переменных, которые приравниваются нулю и нахождение значений оставшихся базисных переменных.
3: Определение, является ли полученное базисное решение оптимальным, если да, то решение окончено, иначе переходим к шагу 4.
4: Определение переменной, которая войдет в базис и переменной, которая из базиса выйдет таким образом, чтобы новое решение было лучше предыдущего. То есть, если текущее базисное решение неоптимально, необходимо определить, какую из базисных переменных приравнять нулю, и какую из небазисных переменных вместо нее включить в базис.
5: Использование эквивалентных преобразований методом Жордана-Гаусса для нахождения нового допустимого базисного решения. Переход к шагу 3.
Чтобы привести задачу линейного программирования к стандартной форме необходимо:
1. Убедиться, что во всех ограничениях правые части bi неотрицательны. Если есть отрицательные правые части ограничений, такие ограничения нужно умножить на –1 (при этом учесть, что в ограничениях типа или знак ограничения изменится на противоположный).
2. К левой части ограничений типа нужно прибавить новую, дополняющую переменную S, которая уравнивала бы левую и правую часть и показывала бы насколько левая часть ограничения меньше правой.
в стандартном виде будет выглядеть так:
3. Из левой части ограничений типа нужно вычесть новую, избыточную переменную e, которая уравнивала бы левую и правую часть и показывала бы насколько левая часть ограничения больше правой.
в стандартном виде будет выглядеть так:
Дополняющие переменные S и избыточные e будем называть вспомогательными, в то время, как переменные x – основными.
Чтобы из стандартной формы сразу выделить базисное решение, необходимо в качестве базисных переменных выбрать те m переменных, каждая из которых встречается только в одном из уравнений и включена в него с коэффициентом, равным единице.
В качестве исходных базисных переменных в задачах с ограничениями удобно брать переменные S1, …, Sn.
Реализацию алгоритма симплекс-метода проиллюстрируем на следующем примере.
Пример 3.2. Мебельная фабрика может производить шкафы, столы, стулья. При изготовлении мебели используются древесина, труд рабочих на столярном и отделочном участках. Необходимое количество ресурсов для изготовления шкафов, столов и стульев приведено в таблице:
Таблица 3.1 – Исходные данные к примеру 3.2