СКАЧАТЬ:  zadacha-11.zip [27,4 Kb] (cкачиваний: 72)

Алгоритм симплекс- метода

В задачах линейного программирования критерий оптимальности определяется, как y = ∑ C_jx_j называемый линейной формой.

Решение основной задачи линейного программирования геометрическим методом является наглядным в случае двух и даже трех переменных. Для слу­чая большего числа переменных геометрический метод становится невозмож­ным. Для большего числа переменных применяется аналитический метод, который называется симплекс-методом или «методом последовательного улучшения плана». На любой процесс накладываются ограничения в виде равенств, неравенств или в смешанном виде. Систему ограничений можно записать следующим образом:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≥b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂                                                                                                                       (1)

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

a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_m

Среди неотрицательных решений системы (1) необходимо найти такое, которое бы максимизировали или минимизировали линейную функцию следующего вида:

l = c₀ + c₁x₁ + c₂x₂ + ... + c_nx_n, где xj ≥ 0, j = 1...n, n- число аргументов.

Если ограничительные условия заданы не­равенствами, то их нужно преобразовать в равенства путем введения новых не­отрицательных переменных x_n+1, так называемых балансовых (выравнивающих). Так, например, в неравенстве a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≤ b₂ достаточно добавить x_n+1 >0, и получится равенство a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n + x_n+1 = b`_2.

Алгоритм решения состоит из следующих этапов:

1. Необходимо убедиться в совместности системы линейных ал­гебраических уравнений. Для этого определяется ранг матрицы системы и ранг расширенной матрицы. В случае равенства двух рангов система имеет общее решение.

 Работа симплекс-метода начинается с выбора опорного решения, содер­жащего r базисных переменных и n-r свободных переменных. Число базисных переменных определяется по рангу.

2. Необходимо выразить базисные переменные  x₁,x₂...x_n через свободные. В результате система (1) может быть записана следующим образом:

x₁ = a`<sub>1,r+1</sub>x<sub>r+1</sub> + ... + a`_1nx_n + b`₁

x₁ = a`<sub>2,r+1</sub>x<sub>r+1</sub> + ... + a`_2nx_n + b`₂                                                                                                                                    (2)

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

x₁ = a`<sub>r,r+1</sub>x<sub>r+1</sub> + ... + a`_rnx_n + b`_r 

где b`_j ≥ 0, j = 1...n 

Систему (2) называют системой, приведенной к единому базису. Подставляя теперь в линейную форму l вместо базисных переменных их выра­жения через свободные из системы (2), получим

                             l = g₀ + g_r+1x_r+1 + ... + g_nx_n                                                       (3)

3. Принимая все свободные равными нулю,  найдем значения базисных переменных: x₁ = b`<sub>1</sub>, x<sub>2</sub> = b`₂,...,x_r = b`<sub>r</sub>. Таким образом, первое решение системы (b`₁, b`<sub>2</sub> ,...,b`_r ,0,...,0) является  допустимым – оно называется базисным. Подставляя в линейную форму  l значения базисных переменных, получим первое базисное значение линейной формы l_B = g₀.

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

Таким образом, далее меняем одну из свободных переменных с таким расчётом, чтобы значение l_B уменьшалось, или, по крайней мере, не увеличи­валось, если нами решается задача на нахождение min l, т.е. переходим к но­вому базису B` такому, что l<sub>B`</sub> < l_B. Процесс продолжается итеративно до тех пор, пока все коэффициенты в уравнении (3) не станут положительными.

Если ищется max l, то переход к новому базису B` осуществляется так, чтобы выполнялось неравенство: l<sub>B`</sub> > l_B . Соответственно процесс продолжается до тех пор, пока все коэффициенты в уравнении (3) не станут отрицательными.

Задача №11.  

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

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

Определим имеет ли система общее решение, для этого определим ранг расширенной и обычной системы:

Так как ранги равны, следовательно система совместна, так как ранг равен трем, то число базисных переменных также равно трем. Примем за базисные переменные , за свободные .

Найдем первое допустимое решение (0,0,0,3,4,2) в этом случае R=0, так как коэффициент в целевой функции для  не отрицательный, то данное решение не является оптимальным. Определим до какого значения можно увеличить :

 увеличиваем до трех, так как при этом переменные будут неотрицательны, но при этом =0, следовательно примем за базисную, а  за свободную и переходим к новому решению:

Второе допустимое решение (0,0,3,0,1,5); . Видим, что значение целевой функции увеличилось, коэффициенты в целевой функции отрицательны, следовательно дальнейшее увеличение целевой функции невозможно. Таким образом являются оптимальными значениями обеспечивающие максимум целевой функции.