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

Симплекс-метод основан на следующих свойствах ЗЛП:

1. Множество всех планов задачи линейного программиро­вания выпукло.

2. Не существует локального экстремума, отличного от глобального. Другими словами, если целевая функция принимает экстремальное значение, то данное значение будет единственным.

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

4. Каждой угловой точке многогранника решений отвечает опорный план задача линейной оптимизации.

Представим математическую модель задачи линейного программирования в виде целевой функции (1)

И системы ограничений в виде системы неравенств (2)

Для приведения системы неравенств к системе уравнений добавим в левую часть неравенств дополнительные переменные (Xn+1, Xn+2... X_m). Первое базисное решение получим, полагая X₁=X'₂=...=Хn= 0. Изобразим это решение в виде специальной симплекс таблицы.

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

	-Х1	-Х2	-Х3	-Хj	-Xn	В
Xn+1	A11	A12	A13	A1j	A1n	B1
Xn+2	A21	A22	A23	A2j	A2n	B2
Xi	Ai1	Ai2	Ai3	Aij	Ain	Bi
Xm	Am1	Am2	Am3	Amj	Amn	Bm
F	-c1	-c2	-c3	-cj	-cn

Переходить от одного опорного решения к другому будем только после проверки условия оптимальности найденного решения. Разобьем поиск оптимального решения на шаги:

1. Условие оптимальности:

Если коэффициенты F – строки неотрицательны, то полученное опорное решение оптимально для задачи на максимум.

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

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

min(b_i/a_ij>=0) (2.4)

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

4. Далее производим, так называемые, модифицированные Жордановы преобразования (формируем новый вид симплекс-таблицы):

4.1. Меняем местами переменные X, стоящие на разрешающей строке и на разрешающем столбце. (новое базисное решение)

4.2. Разрешающий элемент заменяем единицей.

4.3. Остальные элементы разрешающей строки остаются без изменения.

4.4. Остальные элементы разрешающего столбца меняют свои знаки на противоположные.

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

a_ij=a_ija_rs-a_isa_rj (2.5)

где а_rs- разрешающий элемент

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

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

П р и м е ч а н и я к симплекс-методу.

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

2. Несовместимость системы ограничений (в канонической форме) обнаруживается при построении начального д.б.р. (оно не существует).

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

4. Симплекс-метод за конечное число итераций либо приводит к оптимальному решению, либо устанавливает неразрешимость задачи (см. пп. 1.2,3).

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

6. На каждой итерации целевая функция убывает (в задаче на минимум) или возрастает (в задаче на максимум); это свойство нарушается только в случае зацикливания (см. примечания 11,12).

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

8. Слабые переменные со знаком "+" (вводимые для канонизации неравенств вида “≤”) можно использовать в качестве базисных переменных, и слабые переменные со знаком “-” (вводимые для канонизации неравенств вида “≥”) - нет.

9. Структуру симплекс-таблицы можно упростить, если на каждой итерации исключать из таблицы столбики для базисных переменных. При этом сокращается объем вычислений.

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

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

12. Для выхода из зацикливания: в критерии определения ведущей строки вместо элементов 0-го столбика применяют элементы 1-го столбика; если и здесь ведущая строка неоднозначна, то применяют элементы 2-го столбика и так далее, пока ведущая строка не будет определена однозначно.

Что Вы должны знать:

(вопросы для самоконтроля)

1. Какие задачи линейного программирования можно решить симплексным методом?
2. Как строится первый опорный план?
3. Каков признак оптимальности?
4. Как определяется разрешающий столбец и разрешающая строка?
5. Как осуществляется перерасчет элементов симплекс-таблицы?
6. В каких случаях решение стремится к бесконечности?