§1.3 Симплекс-метод. Понятие о методе искусственного базиса.

Симплексный метод – метод последовательного улучшения решения (плана) и нахождения оптимального решения (плана).

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

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

Последнюю строку, которую назовем индексной, заполняем коэффициентами целевой функции, представленной в виде уравнения

,

где – свободный член L(X). Вместо записываем в первом блоке только , а в последующих блоках – результаты вычислений.

Каждая итерация, т.е. переход от одного блока таблицы к другому осуществляется известными элементарными преобразованиями Жордана – Гаусса для строк. Они сводятся к следующим действиям:

1. Выбирают p-й разрешающий столбец из условия, что (в задаче на максимум) и хотя бы один элемент в нем ;
2. Выбирают q-ю разрешающую строку из условия , для .
3. На пересечении разрешающей строки и разрешающего столбца выбирается разрешающий коэффициент .
4. Разрешающая строка делится на .
5. Все остальные элементы таблицы пересчитываются по формулам

,

,

, , .

Теорема 1. (Основная теорема симплекс-метода) Если после выполнения очередной итерации:

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

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

Число отличных от нуля координат опорного решения не может быть больше ранга r системы векторов условий (числа линейно независимых уравнений системы ограничений). Будем в дальнейшем считать, что система ограничений состоит из линейно независимых уравнений, т.е. r=m.

Если число отличных от нуля координат опорного решения равно mто решение называется невырожденным, в противном случае (меньше m) – вырожденным.

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

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

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

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

1. Получить нулевое уравнение. Для этого функцию цели выразить через свободные переменные имеющегося опорного решения и перенести все переменные в левую часть. Присоединить нулевое уравнение к системе ограничений как дополнительное уравнение.
2. Рассмотреть оценки свободных переменных. Если все оценки неотрицательны (неположительны), то имеющееся решение доставляет максимум (минимум) функции цели. Если в задаче требуется найти максимум (минимум), то выписать найденное оптимальное решение и соответствующее максимальное (минимальное) значение функции цели. В противном случае в качестве разрешающего выбрать столбец p, которому соответствует отрицательная (положительная) оценка.
3. Найти соотношения для всех , В качестве разрешающей выбрать строку, которой соответствует наименьшее из найденных соотношений.
4. Выполнить одну итерацию метода Жордано-Гауса. Перейти к пункту 2.

Особые случаи решения задач симплекс-алгоритмом.

1. После выбора разрешающего столбца может оказаться, что что разрешающую строку выбрать невозможно. Это может быть только тогда, когда среди коэффициентов разрешающего столбца нет положительных элементов. В этом случае задача линейного программирования решений не имеет.
2. После отыскания оптимального решения оценки некоторых свободных переменных равны нулю. Это значит, что имеет место альтернативный оптимум. Действительно, если ввести в базис переменную, имеющую нулевую оценку, то получится другое, также оптимальное решение.
3. После выбора разрешающего столбца и нахождения отношений вида имеет несколько таких минимальных отношений.
   Если выбор разрешающей строки производить бессистемно, то может произойти «зацикливание», т.е. ситуация, когда циклически находится некоторая группа одних и тех же опорных решений. В этом случае для предотвращения зацикливания в качестве разрешающей следует всегда выбирать строку с наименьшим номером в системе ограничений.

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

Решение.

1. Ранг матрицы системы уравнений

равен 4. Ранг расширенной матрицы также равен 4, следовательно, четыре переменные (базисные) можно выразить через две (свободные), т.е.

.

Причем целевая функция выражена через эти же свободные переменные.

Составим следующую таблицу.

В индексной строке два отрицательных элемента: -7 и -5. Например, выбираем -5.

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

2. Далее все рассуждения повторяются для второй таблицы. Новый разрешающий элемент есть 2.

       3)Те же рассуждения применяем к третьей таблице.

4)Далее получим

Поскольку в индексной строке нет отрицательных оценок мы получили оптимальный план (5, 3, 0, 0, 6, 3) и наибольшее значение целевой функции .

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

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

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

, (j=1,2,…,l, l).

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

Искусственными переменными называют неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом +1 и в целевую функцию в задаче на минимум с коэффициентом +М, а в задаче на максимум с коэффициентом –М. число М сколь угодно большое по сравнению с единицей.

В общем случае расширенная задача на максимум имеет вид:

,

(j=1,2,…,l, l).

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

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

Если расширенная задача не имеет решения, ввиду неограниченности целевой функции, то исходная задача не имеет решения по той же причине (признак отсутствия решения ввиду неограниченности).