Симплекс – алгоритм (2-й этап симплекс – метода)

Основная теорема симплекс-метода.

Симплекс – метод состоит из двух этапов:

1)нахождение исходного опорного решения ЗЛП;

Нахождение оптимального решения. Этот этап носит название симплекс - алгоритм.

Нахождение исходного опорного решения (1-й этап симплекс-метода).

Рассмотрим ЗЛП в стандартной форме, при этом неизвестные в целевой функции перенесем влево и рассмотрим следующую задачу.

Найти значения

xj ≥ 0, j = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru и max Z, (1.1)

удовлетворяющие условиям:

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru (1.2)

(1.3)

Замечание.Свободный член в уравнении целевой функции равен нулю, но он может быть, и отличен от нуля.

Будем считать, что система (1.1) ,(1.2) совместна, система уравнений (1.2) – линейно независима и все Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru .

Найдем опорное решение системы (1.2), совершив последовательность симплексных преобразований, и пусть при этом i-е уравнение системы (1.2) оказалось разрешенным относительно переменнойxi (i = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru ):

xi + aim+1xm+1 + aim+2xm+2 + ... + aisxs + ... + ainxn = bi (i = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru ), (1.4)

где все bi >0(i = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru ).

Базисными переменными являются переменные x1, x2, ... , xm, а свободными: xm+1, xm+2, ... , xs , ... , xn(базисными могут быть и не обязательно первые m переменных). Исходное невырожденное опорное решение системы (4.4) имеет вид:

X0 =(b1, b2, ... , bm, 0, 0, ... , 0).

Будем говорить, что система уравнений (4.4) приведена к опорному решению. Исключим из уравнения (4.3) базисные переменные. Для этого каждое i-е уравнение системы (1.4) умножим на сi и затем все полученные уравнения сложим, получим:

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru (1.5)

Уравнение (4.3) запишем следующим образом:

Z– Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru – cm+1xm+1 – ... – csxs – ... – cnxn = 0.

Складывая это уравнение с (4.5), получим:

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru

Обозначим: Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru

Тогда уравнение целевой функции будет иметь вид

Z+ Δm+1xm+1 + ... + Δsxs + ...+ Δnxn = Zo.(1.6)

Уравнение (4.6) будем называть уравнением целевой функции, приведенным к свободным переменным, а коэффициенты Δj (j = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru ) – оценками свободных переменных, где

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru (1.7)

В результате этих преобразований ЗЛП (1.1) - (1.3) приведена к следующей эквивалентной задаче: найти значения

xj ≥ 0, j = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru и max Z,(1.1)

удовлетворяющие условиям.

(1.4) Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru

(1.6)

Задачу (1.1), (1.4), (1.6) будем называть ЗЛП в канонической форме или в каноническом виде.

Система ограничений этой задачи приведена к опорному решению:

X0 =(b1, b2, ... , bm, 0, 0, ... , 0) и Z(X0) = Z0.

Уравнение целевой функции приведено к свободным переменным.

Замечание.Уравнение (1.6) добавим к системе уравнений (1.4) и рассмотрим систему из (m + 1) уравнений, при этом в уравнении (1.6) базисной является свободная

переменная Z.

Симплекс – алгоритм (2-й этап симплекс – метода).

В задаче (1.1), (1.4), (1.6) полагаем равными нулю свободные переменные и получаем исходное опорное невырожденное решение (невырожденный план):

X0= (b1, b2, ... , bm,0, 0, ... , 0) и Z(X0)= Z0.

Теперь от этого решения (плана) надо перейти к другому опорному решению (плану) X1с бóльшим значением целевой функции, чем z0, т.е. Z(Х1) > Z(Х0) = Z0.

Допустим, что для этого мы хотим ввести в базис свободную переменную xs = 0, т.е. хотим увеличить значение xs. При этом в s-м столбце обязательно должен быть хотя бы один коэффициент ais > 0. Выбираем s-й столбец разрешающим.

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

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru

т.е. в качестве разрешающей будет строка r, а в качеству разрешающего элемента: ars.

С разрешающим элементом ars выполним преобразование системы уравнений (1.4) и (1.6) по формулам полного исключения неизвестных (метода Жордана – Гаусса) и найдем новое опорное невырожденное решение Х1 со значением целевой функции:

Z(Х1) = Z0 – Δsxs.(1.8)

Если Δs < 0, то « – Δsxs» > 0и новое значениеZ(X1), будет больше, чем z0 на величину « – Δsxs» > 0.

Теперь сформулируем правила выбора разрешающего элемента в симплекс – алгоритме:

1. В базис вводим свободную переменную xsс отрицательной оценкой Δs < 0, если среди коэффициентов ais есть хотя бы один положительный, т.е.ais > 0. Это правило выбора разрешающего столбца s.

2. Из базиса выводим переменную xr по правилу

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru

Это правило выбора разрешающей строки r.

3. С разрешающим элементом ars выполним преобразование системы (1.4), (1.6).

Коэффициенты при неизвестных a΄ij, Δ΄j и значения b΄j, z΄0 в новой системе уравнений вычисляются по формулам:

Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru (1.9)

где введены обозначения:

i = a΄i0,Δ΄j = a΄0j, Z΄0 = a΄00.

Действия, выполненные в пп. 1-3 составляют одну операцию симплекс – алгоритма, выполнив которую, мы перейдем от опорного решения Х0к Х1, при этом Z(Х1)>Z(Х0) = Z0.

Вычислим ΔZ= Z(Х1)– Z(Х0) = – Δsxs > 0,откуда Δs = – Δz/xs.

Таким образом, коэффициент Δs характеризует изменение целевой функции Z, приходящееся на каждую единицу изменения переменной xs, т.е. он оценивает изменение целевой функции Z. Поэтому коэффициенты Δj и называются оценками свободных переменных.

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

Формулировка: Если после выполнения очередной итерации:

1) найдется хотя бы одна отрицательная оценка Δs < 0 и в каждом столбце с такой оценкой будет хотя бы один положительный элемент ais > 0, то можно улучшить решение, выполнив следующую итерацию;

2) найдется хотя бы одна отрицательная оценка Δs < 0, столбец которой не содержит положительных элементов, т.е. все ais ≤ 0 (i = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru ), то целевая функция z неограниченна в области допустимых решений, т.е. Zmax → ∞;

3) все оценки Δj ≥ 0 (j = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru ), то получено оптимальное решение.

Решение конкретных ЗЛП будем проводить в таблицах, аналогичных таблицам Гаусса, которые называются симплексными (сокращенно симплекс – таблицами).

Доказательство:

1) Выберем разрешающий элемент согласно пунктам 1 – 3 и перейдем к новому опорному решению Х1, для которого значение Z(Х1) больше, чем z0 на величину «– Δsxs»>0. Следовательно, новое опорное решение будет лучше предыдущего.

2) Пусть Δs<0 и все ais ≤ 0, i = Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru , тогда если переменную Xs ввести в базис, то функция Z увеличится на величину ΔZ = – Δsxs >0.

При наличии ais>0 величина Xs ограничивается минимумом отношений Симплекс – алгоритм (2-й этап симплекс – метода) - student2.ru для ais>0. Если же все ais≤0 , то значение Xs можно не ограничивать, т.к. при любом сколь угодно большом значении Xs, значения всех остальных базисных переменных Xi всегда будут неотрицательными, т.к Xi = bi – aisXs и при ais ≤ 0, Xi всегда положительны.

Таким образом, переменной Xs можно придавать сколь угодно большое значение и при этом целевая функция z будет достигать тоже сколь угодно большого значения, т.е. Zmax → ∞.

3) Если все оценки Δj ≥ 0, то т. к. Z(Х1) = Z0 – Δsxs, следует, что увеличивая любую свободную переменную мы будем уменьшать значение целевой функции Z. Отсюда следует, что ни при каком другом допустимом решении функция Z не может быть увеличена, т.е. найденное решение является оптимальным. Теорема доказана.

Наши рекомендации