2.7. Симплексный метод Идея симплекс-метода.

Решение основной задачи линейного программи-рования геометрическим методом является наглядным в случае двух и даже трех переменных. Для случая же большего числа переменных этот метод становится невозможным.

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

Его суть в следующем. Если известны какая-нибудь крайняя точка и значение целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведмо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей). Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея наиболее широко применяемого симплексного метода ( метода последовательного улучшения плана) для решения ЗЛП. Итак, симплексный метод предполагает : 1) умение находить начальный опорный план; 2) наличие признака оптимальности опорного плана; 3) умение переходить к нехудшему опорному плану.

На рис. 2.12 дана геометрическая интерпретация идеи симплексного метода в случае двух переменных.

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

Любую ЗЛП можно представить в эквивалентном предпчтительном виде:

max(min) , (2.58)

(2.59)

(2.60)

Выразим базисные переменные х₁, х₂, ..., x_m из равенств (2.59) через свободные х_m+1, х_m+2, ..., x_n и подставим их в целевую функцию. После группировки подобных членов получим

Z=(c₁b₁+c₂b₂+...+c_mb_m)–((c₁a_1,m+1+c₂a_2,m+1+...+c_ma_m,m+1)–c_m+1)x_m+1+(( c₁a_1,m+2+

+c₂a_2,m+2+ ... +c_ma_m,m+2)–c_m+2)x_m+2+...+((c₁a_1n+c₂a_2n+ ... +c_ma_mn)–c_n)x_n (2.61)

Введем обозначения:

₀= c₁b₁+c₂b₂+...+c_mb_m=с_бА₀ , (2.62)

_j=(c₁a_1j+c₂a_2j+...+c_ma_mj)–c_j= с_бА_j–c_j , (2.63)

где с_б=(c₁, c₂, ..., c_m) — вектор коэффициентов целевой функции при базисных переменных; А₀=(b₁, b₂, ..., b_m)^T —  вектор-столбец свободных членов; А_j=(a_1j, a_2j, ..., a_mj)^T — вектор-столбец коэффициентов при переменных х_j.

С учетом равенств (2.61)—(2.63) задача (2.58)—(2.60) примет вид:

max(min)Z= _{0 –} (2.64)

(2.65)

(2.66)

где ₀= с_бА₀ ; _j=с_бА_j–c_j

Задачу (2.64)—(2.66) записывают в таблицу, которая называется симплексной (табл.1). Последнюю строку называют индексной строкой (строкой целевой функции), число ₀= с_бА₀ — значение целевой функции для начального опорного плана х₀, т. е. ₀=Z(х₀). Числа _j=с_бА_jc_jназываются оценками свободных переменных.

Т е о р е м а 1. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки _j неотрицательны, то такой план оптимален.

Доказательство. Так как Z= ₀ — и по условию _j0 , то Z достигает максимального значения при =0. Это возможно лишь при x_m+1=0, x_m+2=0, ..., x_n=0, т. е. опорный план (b₁, b₂, ..., b_m,) оптимален.

Т е о р е м а 2. Если исходная задача решается на минимум и для некоторого опорного плана все оценки _jнеположительны, то такой план оптимален.

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