Обобщённый алгоритм решения ЗЛП с помощью симплекс-таблиц.

Обобщённый алгоритм решения задачи линейной оптимизации (линейного программирования) с помощью симплекс-методасостоит в следующем.

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

Так, если в системе ограничений присутствует неравенство, у которого левая часть меньше правой, т.е. неравенство вида

a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n ≤ b_i,

то к его левой части необходимо прибавить неотрицательную величину x_n+i. В таком случае данное неравенство преобразуется в уравнение

a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n + x_n+i= b_i.

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

a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n ≥ b_i,

то из его левой части необходимо вычесть неотрицательную величину x_n+i . В таком случае данное неравенство преобразуется в уравнение

a_i1x₁ + a_i2x₂ + … + a_ijx_j +… + a_inx_n – x_n+i= b_i.

Во-вторых, целевая функция должна быть устремлена к минимуму (иными словами, ищется минимум целевой функции). Если в исходной постановке задачи оптими-зации предусматривается отыскание максимума целевой функции, то для отыскания её минимума необходимо умножить целевую функцию на –1.

Тогда задачу линейного программирования в канонической форме можно сформулировать так: найти такие неотрицательные значения переменных x₁, x₂, …, x_n, которые удовлетворяют ограничениям

 

a₁₁x₁ + a₁₂x₂ + … + a_1jx_j +… + a_1nx_n = b₁;

a₂₁x₁ + a₂₂x₂ + … + a_2jx_j + … + a_2nx_n = b₂;

…………………………………………

a_j1x₁ + a_j2x₂ + … + a_ijx_j + … + a_inx_n = b_i;

…. ……………………………………. (1)

a_m1x₁ + a_m2x₂ + … + a_mjx_j + … + a_mnx_n = b_m

 

и обращают в минимум целевую функцию

 

L() = c₁x₁ + c₂x₂ + … + c_jx_j + … + c_nx_n. (2)

 

При этом коэффициенты a_ijв системе ограничений и коэффициенты c_jцелевой функции могут принимать как положительные, так и отрицательные значения.

В такой постановке задача линейной оптимизации называется основной задачей линейного программирования (ОЗЛП).

Следует отметить, что при m = n данная задача имеет единственное решение и с точки зрения выбора решения не имеет смысла (т.е. по сути, не является оптимизационной). При m<n задача имеет множество решений и, следовательно, существует возможность выбора наилучшего (оптимального) решения.

Совокупность неотрицательных значений переменных x₁, x₂, …, x_n, удовлетворяющих ограничениям (2), называется допустимым решением ОЗЛП, а совокупность всех допустимых решений представляет собой подмножество допустимых решений ОЗЛП. Допустимое решение ОЗЛП в виде совокупности значений переменных, обеспечивающих минимальное значение целевой функции L(), называется оптимальным решением ОЗЛП.

Ввиду того, что m<n, все множество переменных x₁, x₂, …, x_n можно представить в виде двух подмножеств: базисных и свободных переменных. При этом число базисных переменных равно m, а число свободных – соответственно – k = n – m. В качестве свободных обычно принимают переменные x₁, x₂,…, x_k, а в качестве базисных – x_k+1, x_k+2, …, x_k+l, …, x_k+m.

Вторым шагом для решения ЗЛП с помощью симплекс-метода является её представление в стандартной форме.

Для этого, во-первых, в системе уравнений-ограничений (1) базисные переменные выражаются через свободные. В результате получается система уравнений вида

;

;

............................................................................

; (3)

……………………………………………… ,

где коэффициенты являются комбинациями коэффициентов a_ijиb_i.

Целевая функция вида (2) также выражается через свободные переменные и в результате принимает вид

, (4)

где коэффициенты являются комбинациями коэффициентов c_j.

Затем система уравнений (3) и выражение для целевой функции (4) преобразуются к виду

;

…………………………………………………

; (5)

…………………………………………………

,

, (6)

где ; .

Третьим шагом является построение исходной симплекс-таблицы на основании соотношений (5) и (6). Данная таблица имеет вид (табл. 1)

 

Таблица 1

БП\СП	СЧ			…
				…
				…
				…
…	…	…	…	…	…
				…

 

Четвёртым шагом является проверка допустимости решения ЗЛП на основе заполненной симплекс-таблицы. В качестве признака допустимости решения ЗЛП выступает требование неотрицательности всех элементов второго столбца (коэффициентов ) симплекс-таблицы (коэффициент в расчёт не принимается).

Если данное требование не выполняется (т.е. среди коэффициентов имеется хотя бы один отрицательный), то осуществляется замена базисных переменных на свободные в соответствии с алгоритмом, описанным в приложении 4 лабораторной работы №5. При этом если в ходе поиска допустимого решения возникнет ситуация, когда в симплекс-таблице один или несколько элементов второго столбца отрицательны, и хотя бы в одной строке, соответствующей одному из этих элементов, остальные элементы положительны, то это свидетельствует об отсутствии у ЗЛП допустимого решения.

После того какполучено допустимое решение ЗЛП, пятым шагом является проверка данного допустимого решения на оптимальность. Признаком оптимальности решения ЗЛП является требование отрицательности всех элементов второй строки (коэффициентов r_j) симплекс-таблицы (коэффициент в расчёт не принимается). Если данное требование не выполняется (т.е. среди коэффициентов r_j имеется хотя бы один положительный), то осуществляется замена базисных переменных на свободные в соответствии с алгоритмом, описанным в приложении 3 лабораторной работы №5, до тех пор, пока не будет получено единственное оптимальное решение. При этом искомыми оптимальными значениями переменных будут значения базисных переменных второго столбца конечной симплекс-таблицы, а минимальным значением целевой функции – значение . В принципе, можно решать задачу получения оптимального решения и добиваясь положительности всех элементов второй строки, но в таком случае минимальным значением целевой функции будет значение , взятое с отрицательным знаком.

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

Например, если коэффициент r₂ = 0, то имеет место выражение для целевой функции , где переменная x₂, а, следовательно, и сама целевая функция могут принимать произвольное значение.

 

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