Задачи линейного программирования канонического вида метод симплекса


,Алгоритм решения ЗЛП симплекс- методом



бет5/6
Дата11.06.2022
өлшемі489.26 Kb.
#268043
түріСамостоятельная работа
1   2   3   4   5   6
4,Алгоритм решения ЗЛП симплекс- методом
Пусть необходимо решить задачу о планировании производства . Ранее было показано, как эта задача представляется в каноническом виде:

Решение данной задачи также ранее было получено графическим методом. Для
наглядности будем соотносить алгебраический способ решения данной задачи (симплекс- метод) с графическим
1 шаг. Получаем первое опорное решение, используя остаточные переменные (x3,x4,x5) как базисные. Выразим через базисные свободные переменные (x1,x2) из (5.17-5.19):




Если обратиться к графической интерпретации решения ЗЛП (см. Рис. 5.2), то
первому опорному плану соответствует угловая точка А.
Для сравнения дополним геометрическую интерпретацию задачи информацией о
том, какие переменные обращаются в ноль в каждой угловой точке согласно системе
ограничений (5.21-5.23) и условию неотрицательности (5.20).

2 шаг. Анализируем выражение (5.24). Так как среди коэффициентов целевой функции
есть отрицательные, то полученное опорное решение не является оптимальным. В
соответствии с идеей симплекс-метода нужно осуществить переход к следующей угловой точке, то есть найти новый опорный план, но так, чтобы значение целевой функции (5.24) улучшилось (уменьшилось). Согласно выражению (5.24) значение целевой функции можно уменьшить с помощью увеличения переменной х1, либо увеличением переменной х2. Так как коэффициент при переменной х1 по абсолютной величине больше, чем коэффициент при переменной х2, то следует ввести в базис переменную х1. Следовательно, можно сформулировать правило ввода новой переменной в базис: вводить в базис следует ту переменную, у которой коэффициент максимальный по абсолютной величине.
3 шаг. Необходимо определить, вместо какой базисной переменной следует ввести новую переменную (в данном случае х1). Как было отмечено ранее, ввод новой переменной в базис означает вывод некоторой переменной из базиса, то есть выводимая переменная должна обратиться в ноль. Проанализируем уравнения (5.21-5.23):
• из (5.21) видно, что ни при каких значениях х1 переменная х3 не обратится в ноль,
так как коэффициент при х1 положительный и равенство нулю возможно при х1=-4,
а это противоречит условию неотрицательности переменных в ЗЛП;
• из (5.22) следует, что переменная х4 обратится в ноль при х1 =12;
• из (5.23) получаем, что переменная х5 обратится в ноль при х1 = 3.
Если обратиться к графическому представлению (см. Рис. 5.2), то видно, что
пересечение линий уравнений x2=0 и x1 −3x2 = 3 соответствует угловой точке Е, в
которой переменные x2 и х5 обращаются в ноль. Значит, переменную х1 следует ввести в базис вместо переменной х5. Так как, при решении ЗЛП, зависящей от более, чем двух
неизвестных, графическое представление фактически невозможно, то алгебраически
выбор переменной, выводимой из базиса, соответствует следующему правилу вывода:
выводить из базиса следует ту переменную, у которой отношение правой части
ограничений к соответствующим отрицательным значениям при переменной, вводимой в базис, является минимальным по абсолютной величине.
Для данного примера должно выполняться условие:

подтверждается, что в базис следует ввести х1 переменную вместо переменной х5.
Таким образом, новый базис - (x3,x4,x1), свободные переменные - (x2,x5).
4 шаг. Выражаем свободные переменные через базисные. Для этого из выражения (5.23)
выразим переменную х1:

Таким образом, получаем новый опорный план – x2 =(3,0,35,18,0), а соответствующее ему значение целевой функции F2=-9. Так как F2 отрицательный коэффициент при х2 только в уравнении (5.27), то следует ввести в базис
переменную х2 вместо переменной х4. Таким образом, если вновь обратится к
графическому представлению (Рис. 5.2), то произошел переход из угловой точки E в
угловую точку D. В этой точке в ноль обращаются переменные х4 и х5. Итак, новый базис – (x3,x2,x1), а свободные переменные - (x4,x5). 6 шаг. Снова выражаем свободные переменные через базисные. Для этого из выражения (5.27) выразим переменную х2:

Подставляя (5.29)- в (5.28), получаем:
Таким образом, получаем новый опорный план – x3 =(9,2,57,0,0), а
соответствующее ему значение целевой функции F3=-31. Так как F3опорный план улучшает значение целевой функции и он оптимальный, так как все
коэффициенты целевой функции положительны. Значит, задача (5.16-5.20) решена, оптимальный план х1=9, х2=2, а соответствующее ему максимальное значение целевой функции равно – 31 (согласно графическому представлению – это угловая точка D)



Достарыңызбен бөлісу:
1   2   3   4   5   6




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
рсетілетін қызмет
Жалпы ережелер
жиынтық бағалаудың
республикасы білім
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
Қазақстан республикасының
мерзімді жоспар
арналған жиынтық
қызмет стандарты
болып табылады
арналған әдістемелік
жалпы білім
бағалаудың тапсырмалары
Мектепке дейінгі
оқыту әдістемесі
Қазақ әдебиеті
пәнінен тоқсанға
нтізбелік тақырыптық
Зертханалық жұмыс
Инклюзивті білім
Әдістемелік кешені
республикасының білім
білім берудің
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
қазақ тілінде
туралы хабарландыру
қазіргі заман
атындағы жалпы