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

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

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

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

Из следствия известно, что поиск оптимального решения зада­чи линейного программирования идет только среди базисных решений, число которых (C_n^m) достаточно велико. Симплекс метод вносит определенный порядок при нахождении оптимального решения.

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

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

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

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	0

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

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. В каких случаях решение стремится к бесконечности?