3.4. Идея аналитического решения злп
Ясно, что геометрический подход к решению ЗЛП годится только в случае, когда ОДР можно изобразить на плоскости. В общем случае такой подход не годится. В дальнейшем мы рассмотрим аналитический, так называемый симплекс-метод решения ЗЛП. А в этом разделе мы рассмотрим решение задачи, так сказать, «подручными» средствами, которые ярко демонстрируют идею симплекс-метода.
Решим наш предыдущий пример, одновременно проводя параллель с введёнными выше понятиями:
4x1+x2 max
Приведём задачу к каноническому виду:
4x1+x2 max
Так
как определитель матрицы
,
составленной из коэффициентов при
переменных x3,
x4,
x5
не равны нулю, то эти переменные
базисные, а переменные x1
и x2
свободные. Положив x1=x2=0,
получим базисное решение X1=(0;
0; 24; 24; 12). Оно является допустимым: xj≥0
при всех j=1,
2, …, 5. Оно также является базисным, и
даже опорным. Число отличных от нуля
координат этого решения равно r=3.
Значит, оно является невырожденным.
Базисом опорного решения являются
векторы
A3=
,
A4=
,
A5=
.
Согласно 3.1.4 любое опорное решение ЗЛП является угловой точкой ОДР, а согласно 3.1.2 целевая функция достигает экстремума в угловой точке. Поэтому мы можем проверить, не является ли это опорное решение решением задачи. Целевая функция в данном опорном решении принимает значение ноль. Коэффициенты целевой функции при свободных переменных положительны. Это означает, что стоит только начать менять хотя бы одну свободную переменную (так как x1≥0 и x2≥0, то они при изменении непременно принимают положительные значения), то значение функции сразу начнёт увеличиваться. Следовательно, опорное решение X1 не является оптимальным, и переводом одной из свободных переменных x1 или x2 в базисные мы добьёмся увеличения значения целевой функции.
Мы заинтересованы не только в росте значения целевой функции, но и в том, чтобы этот рост происходил как можно быстрее. Поэтому будем менять (увеличивать) значение x1, коэффициент при котором больше коэффициента при x2. Другими словами, переведём x1 из свободных в базисные.
В свою очередь, какая-то из базисных переменных должна перейти в число свободных. Какая?
Для того, чтобы определить, какая, выразим в системе ограничений-уравнений базисные переменные через свободные:
Из
первого выражения (
)
вытекает, что x1
мы можем увеличивать до
=12.
Как только x1
станет больше 12, так сразу x3<0,
что недопустимо. Вообще, ясно, что x1
мы можем менять (увеличивать) до min
,
,
=6
(здесь
означает, что во втором выражении x1
можем увеличивать сколько угодно, и x4
будет оставаться больше 0). Как только
x1=6,
так сразу (при x2=0)
x5=0.
А это означает, что x5
и x1
примут значения в том опорном решении,
где x1,
x3,
x4
базисные, а x2
и x5
свободные. Поэтому x1
переводим из свободных в базисные, а x5
из базисных в свободные. Поэтому из
последнего выражения выразим x1
через x2
и x5,
и подставим его выражение в остальные
и в целевую функцию:
.
Теперь подставляем выражения для x1 в выражение для x3, x4 и целевой функции:
=
,
то есть x3= .
=
,
то есть x4= .
=
=
,
то
есть
.
Таким образом, наша задача принимает вид
max
При
x2=x5=0
получаем новое опорное решение (опорный
план) X2=(6;
0; 12; 72; 0), при котором F=24.
Так как в
коэффициент при x2
положителен, то, меняя (то есть по сути
увеличивая) x2,
добьёмся дальнейшего увеличения значения
целевой функции
.
Поэтому переведём x2
из свободных в базисные. Так как min
,
,
=2
достигается в выражении для x3,
то x2
вводим в число базисных вместо x3.
Выражаем x3
через x3,
x5
и подставляем его выражение в выражения
для x1,
x4
и в целевую функцию:
.
=
,
то есть x1= .
=
,
то есть x4= .
=
=
,
то есть .
Таким образом, наша задача принимает вид
max
При x3=x5=0 получаем опорное решение X2=(9; 2; 0; 90; 0), в котором целевая функция принимает значение F=38. Это значение уже увеличить невозможно, так как коэффициенты при переменных отрицательны, и любое изменение (увеличение) значений свободных переменных ведёт к уменьшению значения целевой функции.
Как видим, мы получили то же решение, что и в геометрическом методе.