Пример отыскания максимума линейной функции

 

Реализацию симплексного метода рассмотрим на примерах.

Пример. Решить симплексным методом задачу: Z=2x₁+3x₂®max

при ограничениях (1)

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений: (2)

Запишем систему (2) в векторной форме:

(3) А₁x₁ + А₂x₂ + А₃x₃ + А₄x₄ + A₅ x₅+ A₆ x₆ =A₀,

где

Для нахождения первоначального базисного решения (опорного плана) разобьем переменные на базисные и свободные. Данная система совместна. Ее ранг r=2, значит число базисных переменных k=6-2=4. Т.к. определитель, составленный из коэффициентов при дополнительных переменных х₃, х₄, х₅, х₆ отличен от 0, то их можно взять в качестве базисных переменных.

Или, пользуясь терминами линейных векторных пространств, получим: векторы A₃,A₄,A₅,A₆ - линейно независимые единичные век­торы 6-мерного пространства. Они и образуют базис этого простран­ства. Поэтому в разложении (3) за базисные переменные выбираем x₃,x₄, x₅,x₆, свободные переменные x₁,x₂.

1 шаг. Выразим базисные переменные через свободные:

(4)

Функция Z=2x₁+3x₂ уже выражена через свободные. Т.к. все величины х_i должны быть неотрицательны, то наименьшие возможные значения свободных переменных- это значения, равные нулю: x₁=0, x₂=0. Тогда получим базисное решение (первоначальный план) Х₁=(0;0;18;16;5;21), которое является допустимым и соответствует вершине О(0;0) многоугольника. При найденном решении

Z(X₁)= 2x₁+3x₂=0.

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

В данном примере для увеличения Z можно переводить в свободные либо х₁, либо х₂ , т.к. они обе со знаком ‘’+”. Выберем переменную х₂, имеющую больший коэффициент.

Система (4) накладывает ограничения на рост переменной х₂. Т.к. необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х₁=0 как свободная переменная):

Откуда (5)

Каждое уравнение (4), кроме последнего, определяет оценочное отношение – границу роста переменной х₂, сохраняющую неотрицательность соответствующей переменной.

В данном примере наибольшее возможное значение для переменной х₂ определяется как х₂=min{18/3;16/1;5/1;µ}=5. При х₂ =5 переменная х₅ обращается в 0 и переходит в свободные.

2 шаг. Выразим новые базисные переменные через новые свободные, начиная с разрешающего:

или (6)

Второй опорный план Х₂=(0;5;3;11;0;21) и соответствует вершине А(0;5), т.е. перешли к новой вершине.

Выразим линейную функцию через базисные переменные:

Z=2x₁+3x₂=2x₁+3(5-x₅)=15+2x₁-3x₅.

Значение Z(X₂)=15. Однако оно не является максимальным, т.к. возможно увеличение функции за счет переменной х₁, входящей в выражение для Z c положительным коэффициентом. Система уравнений (6) определяет оценочное отношение откуда Следовательно, наибольшее возможное значение для х₁: х₁=min{µ;3/1;11/2; µ}=3. Второе уравнение является разрешающим.

3 шаг. Выразим новые базисные переменные через новые свободные, начиная с разрешающего:

Третий опорный план Х₃=(3;5;0;5;0;12) и соответствует вершине В(3;5), т.е. перешли к новой вершине.

Выразим линейную функцию через базисные переменные:

Z=2x₁+3x₂=2(3-x₃+3х₅)+3(5-x₅)=21-2x₃+3x₅. Значение Z(X₃)=21.

Третье допустимое решение тоже не является оптимальным, т.к. при свободной переменной х₅ в выражении линейной функции через свободные переменные содержится положительный коэффициент. Переводим х₅ в базисную переменную. Определим наибольшее возможное значение для х₅ (при этом х₃=0 как свободная переменная).

Откуда

Следует обратить внимание на 1-ое уравнение, которое не дает ограничений на рост х₅, т.к. b₁=3 и коэффициент при х₅ имеют одинаковые знаки. Поэтому х₅=min{µ;5;1;12/9}. 3-е уравнение является разрешающим, и переменная х₄ переходит в свободные.

4 шаг. Выразим новые базисные переменные через новые свободные, начиная с разрешающего:

Четвертый опорный план Х₄=(6;4;0;0;1;3) и соответствует вершине С(6;4), т.е. перешли к новой вершине.

Выразим функцию Z через базисные переменные: Z=2x₁+3x₂=24-4/5x₃-3/5x₄. Это выражение не содержит положительных коэффициентов при свободных переменных, функцию Z невозможно еще увеличить, переходя к другому допустимому базисному решению поэтому значение Z(X₄)=24 максимальное., т.е. решение Х₄ оптимальное.