Симплекс-метод решения ЗЛП.

В основе геометрической интерпретации решения системы m линейных уравнений с n неизвестными (m<n) лежит теорема: каждому допустимому базисному решению системы ограничений ЗЛП соответствует угловая точка многоугольника решений. Справедлива и обратная теорема: каждой угловой точке множества допустимых решений системы ограничений (многоугольника решений) соответствует допустимое базисное решение. Обобщая упомянутые в этом параграфе теоремы можно сформулировать следствия: если существуют, и при том единственное оптимальное решение задачи линейного программирования, то оно совпадает с одним из допустимых базисных решений системы ограничений.

Очевидно, число допустимых базисных решений конечно и не превышает . Следовательно, для случая, когда число переменных не позволяет решить задачу графически, или это решение представляет технические сложности, можно решить задачу так: найти все допустимые базисные решения системы ограничений, вычислить значение целевой функции выбрать наибольшее и наименьшее. Однако, практическое осуществление столь «прозрачного» метода связано с большими вычислительными трудностями.

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

Впервые симлексный метод решения был предложен американским ученым Дж.Данцигом в 1949 году, хотя еще в 1939 году его идеи были разработаны советским ученым Л.В. Канторовичем. На основе симплекс метода создан пакет прикладных программ 1рх88, обладающий достаточно большими вычислительными возможностями. Однако, студентом необходимо ознакомиться с сутью этого метода, которую мы изложим на примере.

Симплекс-метод изложим для ЗЛП, поставленной в канонической форме: f→min, ограничения в виде системы уравнений, число переменных любое.

Пример. Решить симплекс-методом задачу:

F=4-x₂+x₅→min;

1. Проверим, является ли система уравнений совместной. Для этого найдем ранг матрицы и ранг расширенной матрицы:

; r( )=r( )=3.

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

1 этап: х₁,х₃,х₄ – базисные, х₂,х₅ – свободные;

Проверим, является ли построенное базисное решение допустимым, то есть выполняются ли неравенства X_j≥0. Если решения не является допустимым, в качестве базисных выбираем три другие переменные, при которых определитель не равен нулю.

3. Поставим вопрос – можно ли каким либо образом «улучшить» решение? Легко понять, что функцию можно уменьшить за счёт увеличения любой свободной переменной, входящей в выражение целевой функции с отрицательным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная станет базисной и примет не нулевое, а положительное значение. Формальным признаком выбором такой переменной является знак «минус» перед свободной переменной в выражении целевой функции. В нашем случае это переменная х_2.

Однако, базисных переменных должно быть на каждом этапе решения задачи ровно 3, т.к. r=3. Чем больше будет значение переменной, тем меньше будет значение целевой функции, но система ограничений накладывает условия на рост переменной x₂.

Поскольку необходимо сохранить допустимость решений, т.е. все переменные должны остаться неотрицательными, то должны выполняться следующие неравенства (x₅=0 как свободная переменная):

Формально оценочные отношения для x₂ можно получить, составляя для каждого уравнения системы ограничения отношение свободного члена к коэффициенту при меняемой переменной, если меняемая переменная входит в выражение целевой функции со знаком « - »; если меняемая переменная не входит в уравнение или входит с положительным кооэффициентом, то это отношение заменяем символом ~. Очевидно, что сохранение неотрицательности всех переменных решения возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной x₂ определяется как x₂=min{5,~,3}=3. При x₂= 3 переменная x₄ обращается в нуль и переходит в свободные.

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

4. Решая последнее разрешающее уравнение, находим меняемую переменную х₂ и подставляем ее в оставшиеся ограничения и в выра­жение целевой функции. Находим тем самым новое допустимое базис­ное решение.

2 этап: X₁ , х₂, х₃ - базисные, х₄, х₅ - свободные;

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

Ответ: f_min = 1, .

Блок-схема симплекс-метода.

1. Постановка задачи в канонической форме. Построение исходного допустимого базисного решения.

2. Проверка критерия оптимальности. Если все свободные пере­менные входят в выражение целевой функции с положительными коэф­фициентами, то построенное решение оптимально, переходим к пункту
5; если критерий оптимальности не выполнен, то переходим к пункту
4.

3. Построение нового допустимого базисного решения.

4. Конец.

Доказано, что за конечное число шагов можно получить оптимальное решение.

Частный случай 1. Если на каком-то этапе решения ЗЛП в выра­жении целевой функции имеется свободная переменная с отрицатель­ным коэффициентом, а во все уравнения системы ограничений она ли­бо не входит, либо входит с положительным коэффициентом, то целевая функция не ограничена при данной системе ограничений. Опти­мального решения нет.

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

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