димая переменная имеет положительный коэффициент. В этом случае граница обозначается символом оо.
Все возможные случаи, которые возникают при оценке переменной, перечислены далее.
Очевидно, что сохранение неотрицательности возможно, если не нарушена ни одна из границ. Следовательно, в рассматриваемом случае
X2=min{ 18/3,16,5,00} = 5.
При 2 = 5 переменная обращается в нуль и переходит в неосновные. Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна), называется разрешающим. В данном случае - это третье уравнение.
Шаг 2. Основные переменные Х2, хз, Х4, хв» Неосновные переменные
На этом шаге вьфазим новые неосновные переменные, начиная с разрешающего уравнения (оно используется при выражении записи для 2)
Х2=5-Х5
Хз=18-Х1-3(5-Х5) (3.4)
Х4 =16-2xi --(5-Х5) Х5 =21-3xi. Преобразуя систему, получим:
Х2=5-Х5
Хз=18-х,-3(5X5) Х4 =16-2xi -(5-Х5) Х5 =21-3xi.
Второе базисное решение Х2 = (0; 5; 3; 11; 0; 21) является допустимым.
Выразив линейную функцию через неосновные переменные, получим: F = 2xi + ЗХ2 = 2xi + 3(5 - Х5) = 15 + 2xi - ЗХ5.
Значение целевой функции (2) = 15.
Изменение значения линейной целевой функции можно определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для целевой функции. В рассматриваемом примере
Ai =5.3=15,F(X2) = F(Xi) + AF, =0+15 =15.
Далее, как легко видеть, значение (з) не является максимальным, поскольку оно может быть улучшено за счет переменной , входящей в выражение для F с положительным коэффициентом. Как и ранее предположив, что правые части уравнений (3.4) неотрицательны, получим, что наибольшее значение х, определяется из выражения
= min { 00,3,5,5,00} = 3. Второе уравнение является разрешающим, переменная переходит в неосновные при этом AF2 =32 = 6.
Шаг 3. Основные переменные х,Х2,х,х. Неосновные переменные Х3, Х5
Повторяя процедуру шага 2, выражаем новые основные переменные через неосновные, начиная с разрешающего уравнения. Проведя необходимые преобразования, получим:
Xj = 3 - Хз + ЗХ5 Х2 = 5 - Х5
Х4 =5 + 2x3-5x5
Хб =12 + 3x3-9x5.
Базисное решение = (3; 5; 0; 5; 0; 12) соответствует вершине, у которой Xj = 3; Х2 = 5 . Выражаем линейную функцию через неосновные переменные:
F = 2xi +3x2 =2(3-Хз +Зх5) + 3(5-Х5) = 21-2хз +ЗХ5 з=(Хз)=21.
Проверяем (Хз)-(Х2) = 21-15=6=А2.
Третье допустимое базисное решение не является оптимальным, так как при неосновной переменной Х5 в выражении целевой функции через неосновные переменные содержится положительный коэффициент. Переводим Х5 в основную переменную. При определении наибольшего возможного значения для Х5 получаем, рассмотрев все че-
тыре уравнения системы (3.5), лг; =min{ оо,5,1,12/9} = 1. Третье уравнение является разрешающим, и переменная переходит в неосновные Дз =1-3 = 3.
Шаг 4. Основные переменные x,X2,X},x. Неосновные переменные х,х.
После преобразований получим
Xi=6 + -X--X
. 2 1 3 9
6=3-3 + 54-
Базисное решение = (6; 4; 0; 0; 1,3).
Целевая функция, выраженная через неосновные переменные, имеет вид F = 24-x,-x,.(3.6)
Это выражение не содержит положительных коэффициентов при неосновных переменных, следовательно, улучшить решение нельзя и поэтому значение целевой функции F(X) = 24 максимальное.
На основе изучения рассмотренного выше примера критерий оптимальности решения при отыскании максимума линейной функции может быть сформулирован так:
V если в выражении целевой функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных пере-менньос, то решение оптимально.
При решении задачи определения минимума линейной целевой функции можно использовать один из следующих путей:
1)если необходимо отыскать минимум F, то решается задача максимизации функции -F, и это решение принимается за решение исходной задачи;
2)на каждом шаге симплексного метода уменьшать целевую функцию за счет той неосновной переменной, которая входит в выражение линейной функции с отрицательным коэффициентом.