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

 

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

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

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

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

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

(3) А1x1 + А2x2 + А3x3 + А4x4 + A5 x5+ A6 x6 =A0,

где

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

Или, пользуясь терминами линейных векторных пространств, получим: векторы A3,A4,A5,A6 - линейно независимые единичные век­торы 6-мерного пространства. Они и образуют базис этого простран­ства. Поэтому в разложении (3) за базисные переменные выбираем x3,x4, x5,x6, свободные переменные x1,x2.

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

(4)

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

Z(X1)= 2x1+3x2=0.

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

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

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

Откуда (5)

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

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

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

или (6)

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

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

Z=2x1+3x2=2x1+3(5-x5)=15+2x1-3x5.

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

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

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

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

Z=2x1+3x2=2(3-x3+3х5)+3(5-x5)=21-2x3+3x5. Значение Z(X3)=21.

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

Откуда

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

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

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

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