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

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

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

при ограничениях Пример отыскания максимума линейной функции - student2.ru (1)

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

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

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

где Пример отыскания максимума линейной функции - student2.ru

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

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

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

Пример отыскания максимума линейной функции - student2.ru (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 . Это можно осуществить, перейдя к такому новому допустимому решению, в котором эта переменная будет базисной.

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

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

Пример отыскания максимума линейной функции - student2.ru Откуда Пример отыскания максимума линейной функции - student2.ru (5)

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

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

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

Пример отыскания максимума линейной функции - student2.ru или Пример отыскания максимума линейной функции - student2.ru (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) определяет оценочное отношение Пример отыскания максимума линейной функции - student2.ru откуда Пример отыскания максимума линейной функции - student2.ru Следовательно, наибольшее возможное значение для х1: х1=min{µ;3/1;11/2; µ}=3. Второе уравнение является разрешающим.

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

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

Третий опорный план Х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 как свободная переменная).

Пример отыскания максимума линейной функции - student2.ru Откуда Пример отыскания максимума линейной функции - student2.ru

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

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

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

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

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

Наши рекомендации