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

(1.3)

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

Будем считать, что система (1.1) ,(1.2) совместна, система уравнений (1.2) – линейно независима и все .

Найдем опорное решение системы (1.2), совершив последовательность симплексных преобразований, и пусть при этом i-е уравнение системы (1.2) оказалось разрешенным относительно переменнойx_i (i = ):

x_i + a_im+1x_m+1 + a_im+2x_m+2 + ... + a_isx_s + ... + a_inx_n = b_i (i = ), (1.4)

где все b_i >0(i = ).

Базисными переменными являются переменные x₁, x₂, ... , x_m, а свободными: x_m+1, x_m+2, ... , x_s , ... , x_n(базисными могут быть и не обязательно первые m переменных). Исходное невырожденное опорное решение системы (4.4) имеет вид:

X₀ =(b₁, b₂, ... , b_m, 0, 0, ... , 0).

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

(1.5)

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

Z– – c_m+1x_m+1 – ... – c_sx_s – ... – c_nx_n = 0.

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

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

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

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

(1.9)

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

b΄_i = a΄_i0,Δ΄_j = a΄_0j, Z΄₀ = a΄_00.

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

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

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

2) найдется хотя бы одна отрицательная оценка Δ_s < 0, столбец которой не содержит положительных элементов, т.е. все a_is ≤ 0 (i = ), то целевая функция z неограниченна в области допустимых решений, т.е. Z_max → ∞;

3) все оценки Δ_j ≥ 0 (j = ), то получено оптимальное решение.

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

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

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

2) Пусть Δ_s<0 и все a_is ≤ 0, i = , тогда если переменную X_s ввести в базис, то функция Z увеличится на величину ΔZ = – Δ_sx_s >0.

При наличии a_is>0 величина X_s ограничивается минимумом отношений для a_is>0. Если же все a_is≤0 , то значение X_s можно не ограничивать, т.к. при любом сколь угодно большом значении X_s, значения всех остальных базисных переменных X_i всегда будут неотрицательными, т.к X_i = b_i – a_isX_s и при a_is ≤ 0, X_i всегда положительны.

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

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