Симплекс алгоритм. Процесс приближения к оптимуму (направленный перебор краевых вершин)

Пусть задача представлена в К В, соответственно сразу получаем некое исходное базисное решение.

Возникают следующие вопросы:

• Оптимально ли и единственно ли оно;
• Если не оптимально, а ранее мы показали, что поиск решения состоит в переборе краевых вершин, то возникает вопрос, как осуществить переход к следующему решению.

Вспоминая, что целевая функция выглядит следующим образом:

_n

Z=Σ С_jX_j

^j=1

Просуммируем соответствующие уравнения в системе (2) умножив их на коэффициент С_j.

C₁x₁ + a_1m+1x_m+1 + … + a_1nx_n = C₁B₁

…

C_mx_m + a_mm+1x_m+1 + … + a_mnx_n = C_mB_m

Имеем:

_{n n m}

∑ С_jX_j + ∑ С_jX_j = Z₀ + ∑ С_jX_j (3)

^{j=1 j=m+1 j=m+1}

Где C _j - коэффициент при свободных переменных и зависит от значения a_ij , В_i. По своему смыслу Z₀ есть значение целевой функции для исходного базисного решения.

Теорема:

Допустимое базисное решение x_i = В_i при i = 1…m, x_j = 0 при j = m+1…m, является оптимальным, если коэффициенты C_j в выражении (3) не отрицательны.

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

Если переменные C ≥ 0, то при любых значениях (не отрицательных) переменных x_j , разность Z и Z₀ неотрицательна и ее минимум есть 0, следовательно, Z не будет меньше Z₀, что говорит о том, что его нельзя уменьшить.

Следствия:

_n

1. Любое решение системы (1), которому соответствует нулевая сумма (Σ С_jX_j) при

^j=m+1

любых C_j ≥0 и x_j ≥0 будет оптимальным, соответственно при существовании C _j < 0, решение может быть улучшено.

1. Допустимое оптимальное базисное решение окажется единственным, если все C _j > 0 (строго больше).

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

Теперь рассмотрим, как осуществить переход к новому решению и сформулируем критерий оптимальности выбора направления перехода.

Пусть среди коэффициентов C _j есть отрицательные значения, это значит, что давая приращения, соответственным переменным, целевую функцию можно уменьшить, чтобы перейти к другому целевому решению (как следует из интерпретации) необходимо сделать положительной (ввести в базис) какую-то из переменных x_n+1 = … =x_n = 0, обратив в 0 одну из переменных x₁…x_n . соответственно в базис должно вводиться та переменная (ей дается положительное приращение), которая имеет в выражении для целевой функции отрицательный коэффициент.

Обозначим через S тот номер j из n+1,…,n величина коэффициента C _j для которого отрицательна и максимальна по модулю.

C_s=min[C _j <0]

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

Соответственно будем давать положительное приращение к переменной X_s . Давая данное приращение, из уравнений (2), получаем:

x₁ = B₁ - a_1s x_s

…

xm = Bm - a_ms x_s

Для Z имеем:

Z = Z₀ + С_s X_s (С_s < 0)

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

Это произойдет если хотя бы один коэффициент с индексом X_s положителен по условию и среди В_i нет отрицательных. Если все a_is положительны, то первая в 0 обратиться та базисная переменная, для которой будет выполняться:

X_s = min [В_i / a_is]

Это и есть формализованное условие перехода к последующей краевой вершине.

Симплекс метод.

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

Однако остается проблема, состоящая в том, как найти то первое допустимое решение (а это должна быть краевая точка), с которой начинать направленный перебор вершин (т.е. когда уже становится возможным применение СА). Для это цели и служит СМ, состоящий в двухэтапном решении задачи. На первом этапе требуется найти какое-либо решение задачи (исходную краевую точку), на втором – осуществить перебор вершин с целью поиска оптимального решения. При этом будем помнить, что краевая точка легко отыскивается, в случае представления задачи в КВ (см. выше).

С М предполагает в общем случае двухэтапного применения С А.

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

Исходная:

a₁₁x₁ + … + a_1nx_n = b₁

a_1mx₁ + … + a_mnx_n = b_m

К В:

a₁₁x₁ + … + a_1nx_n + x_n+1= B₁

a_1mx₁ + … + a_mnx_n + x_n+m= B_m

Однако этим мы изменили собственно задачу. В каком случае решение новой задачи и исходной задачи будут совпадать?

Если существует решение для первой задачи, то оно допустимо и для второй при условии x_n+1 = … =x_n+m = 0 (т.к. именно эти переменные были нами введены, ввиду их неотрицательности, при данном условии все переменные обращаются в 0).

Рассмотрим сумму (W= x_n+1 + …+ =x_n+m ) наименьшее значение которой есть 0 ввиду неотрицательности переменных при x_n+1 = … =x_n+m = 0. Таким образом, проверка условия minW=0 для второй системы ограничений, является условием совпадения решения для первой и второй задач.

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

_m

minW=Σ x_n+j .

^j=1

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

Для данной задачи, приведенной к К В (то есть может быть применен С М), легко находится первое решение. x_n+1 = В₁, …, x_n+m =B_m , а x₁ =…= x_n =0. После чего может быть использован С А с целью поиска оптимального решения. Если удается найти оптимальное решение, для которого W=0, это решение является исходным для основной задачи. В противном случае задача не разрешима.

Второй этап состоит в решении основной задачи, в использовании С А уже для решения основной задачи, при этом получим решение вспомогательной задачи рассмотренное как исходное для основной, проверяется на оптимальность при необходимости осуществления последовательного перебора решений (Замечание: здесь уже используется целевая функция Z).