Идея аналитического решения ЗЛП
Ясно, что геометрический подход к решению ЗЛП годится только в случае, когда ОДР можно изобразить на плоскости. В общем случае такой подход не годится. В дальнейшем мы рассмотрим аналитический, так называемый симплекс-метод решения ЗЛП. А в этом разделе мы рассмотрим решение задачи, так сказать, «подручными» средствами, которые ярко демонстрируют идею симплекс-метода.
Решим наш предыдущий пример, одновременно проводя параллель с введёнными выше понятиями:
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. Это значение уже увеличить невозможно, так как коэффициенты при переменных отрицательны, и любое изменение (увеличение) значений свободных переменных ведёт к уменьшению значения целевой функции.
Как видим, мы получили то же решение. что и в геометрическом методе.