Цель работы:
При решении ЗЛП симплексным методом необходимо пользоваться критериями оптимальности целевой функции.
Критерий оптимальности решения при отыскании максимума линейной функции: если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение оптимально.
Критерий оптимальности решения при отыскании минимума линейной функции: если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.
Пример 3.1.
Решить симплексным методом ЗЛП:
Решение. Переходим от системы неравенств к системе уравнений, вводя новые переменные x3, x4, x5:
I шаг.
Основные переменные: x3, x4, x5.
Неосновные переменные: x1, x2.
Выразим основные переменные через неосновные:
Полагая, что x1=0 и x2=0, получим X1=(0;0;2;10;5),
F=x1+2x2=0. Так как все xi≥0, то значение функции F можно увеличить за счет перевода переменной x2 в основные. Оценим рост переменной x2:
x2=min{2;5}=2.
Данное значение получается из оценки переменной x3, и при этом значении переменной x2 переменная x3=0, тем самым переходя в неосновные и уравнение становится разрешающим.
II шаг.
Основные переменные: x2, x4, x5.
Неосновные переменные: x1, x3.
Выразим основные переменные через неосновные, начиная с разрешающего уравнения:
Полагая, что x1=0 и x3=0, получим X2=(0;2;0;6;9),
F=x1+2x2=x1+2(2+x1-x3)=x1+4+2x1-2x1=4+3x1-2x3=4. Так как все xi≥0, то значение функции Fможно увеличить за счет перевода переменной x1 в основные. Оценим рост переменной x1:
x1=min{6/7;3}=6/7.
Данное значение получается из оценки переменной x4, и при этом значении переменной x1 переменная x4=0, тем самым переходя в неосновные и уравнение становится разрешающим.
III шаг.
Основные переменные: x1, x2, x5.
Неосновные переменные: x3, x4.
Выразим основные переменные через неосновные, начиная с разрешающего уравнения:
Полагая, что x3=0 и x4=0, получим X3=(6/7;20/7;0;0;46/7),
F=x1+2x2= =46/7. Так как все xi≥0, то значение функции F увеличить нельзя – выполняется критерий оптимальности функции при решении задач на максимум. Данное значение функции и есть максимальное Fmax=46/7.
Ответ. Fmax=46/7.
Пример 3.2.
Решить симплексным методом ЗЛП:
Решение. Переходим от системы неравенств к системе уравнений, вводя новые переменные x3, x4:
I шаг.
Основные переменные: x3, x4.
Неосновные переменные: x1, x2.
Выразим основные переменные через неосновные:
Полагая, что x1=0 и x2=0, получим X1=(0;0;3;5), F=x1-3x2=0. Так как все xi≥0, то значение функции F можно уменьшить за счет перевода переменной x2в основные. Оценим рост переменной x2:
x2=min{3;2,5}=2,5.
Данное значение получается из оценки переменной x4, и при этом значении переменной x2 переменная x3=0, тем самым переходя в неосновные и уравнение становится разрешающим.
II шаг.
Основные переменные: x2, x3.
Неосновные переменные: x1, x4.
Выразим основные переменные через неосновные, начиная с разрешающего уравнения:
Полагая, что x1=0 и x4=0, получим X2=(0;5/2;1/2;0),
F=x1-3x2=x1-3(5/2+1/2x1-1/2x4)=-15/2-1/2x1+3/2x4=-15/2. Так как все xi≥0, то значение функции Fможно уменьшить за счет перевода переменной x1 в основные. Оценим рост переменной x1:
x1= 1/3. Данное значение получается из оценки переменной x3, и при этом значении переменной x1переменная x3=0, тем самым переходя в неосновные и уравнение становится разрешающим.
III шаг.
Основные переменные: x1, x2.
Неосновные переменные: x3, x4.
Выразим основные переменные через неосновные, начиная с разрешающего уравнения:
Полагая, что x3=0 и x4=0, получим X3=(1/3;16/6;0;0),
F=x1-3x2= =-23/3. Так как все xi≥0, то значение функции F уменьшить нельзя – выполняется критерий оптимальности функции при решении задач на минимум. Данное значение функции и есть минимальное Fmin=-23/3.
Ответ. Fmin=-23/3.