Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Экономико-математические методы и модели
Содержание
- 1. Экономико-математические методы и модели
- 2. Учебные вопросы Решение ЗЛП симплекс-методом:Метод искусственного базиса ( М-метод);Примеры.Лекция 4 ЭМММ27.02.2020
- 3. Метод искусственного базиса Последняя трудность, которую осталось
- 4. Метод искусственного базисаИтак, пусть мы имеем задачу
- 5. Вспомогательная задачаВ этой задаче сразу ясен исходный
- 6. Решение симплекс-таблицыА теперь начнем преобразования симплекс-таблицы, стараясь
- 7. Решение симплекс-таблицыВариант 1Все векторы, соответствующие введенным дополнительным
- 8. Решение симплекс-таблицыВариант 2Несмотря на то, что M
- 9. Введем дополнительные переменные:Пример 127.02.2020Лекция 4 ЭМММ
- 10. Строим симплекс-таблицуРазрешающему столбцу соответствует наибольшая оценка =
- 11. Переходим к новой симплекс-таблице методом Жордана-Гаусса.Разрешающему столбцу
- 12. Переходим к новой симплекс-таблице методом Жордана-Гаусса.Разрешающему столбцу
- 13. Переходим к новой симплекс-таблице методом Жордана-Гаусса.Полученный план
- 14. Пример 2max f(xi)=3x1+2x2+x32x1+x2=8x1+x2+x3=6X1,2,3>=0max f(xi)=3x1+2x2+x3-Mx42x1+x2+x4=8x1+x2+x3=6X1,2,3>=027.02.2020Лекция 4 ЭМММВведем дополнительные переменные:
- 15. Строим симплекс-таблицуРазрешающему столбцу соответствует наименьшая оценка =
- 16. Строим симплекс-таблицуПолученный план оптимален.Х* = (х1=4 ; x2=0 ; х3=2), F(x*)=1427.02.2020Лекция 4 ЭМММ
- 17. Письменно ответить на вопросыРешить методом искусственного базиса
- 18. Скачать презентанцию
Учебные вопросы Решение ЗЛП симплекс-методом:Метод искусственного базиса ( М-метод);Примеры.Лекция 4 ЭМММ27.02.2020
Слайды и текст этой презентации
Слайд 2Учебные вопросы
Решение ЗЛП симплекс-методом:
Метод искусственного базиса ( М-метод);
Примеры.
Лекция 4
ЭМММ
Слайд 3Метод искусственного базиса
Последняя трудность, которую осталось преодолеть - это
определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются
все итерации.За счет чего мы так легко составили исходную симплекс-таблицу в предыдущем примере из лекции 3 ? Легко видеть, что это произошло потому, что среди переменных были такие, что входили лишь в одно уравнение системы ограничений и не входили в другие.
На искусственном введении таких переменных и основан метод искусственного базиса.
27.02.2020
Лекция 4 ЭМММ
Слайд 4Метод искусственного базиса
Итак, пусть мы имеем задачу линейного программирования в
канонической форме
Можно считать, что все bi≥0, так как умножением соответствующего
ограничения на -1 всегда можно сменить знак. Возьмем ну очень большое число M и будем решать следующую вспомогательную задачу.
27.02.2020
Лекция 4 ЭМММ
Слайд 5Вспомогательная задача
В этой задаче сразу ясен исходный базис - в
качестве него надо взять переменные xn+1,…,xn+m.
В качестве исходного опорного плана
надо взять план27.02.2020
Лекция 4 ЭМММ
Слайд 6Решение симплекс-таблицы
А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса
дополнительные переменные.
Заметим, что если какая-то дополнительная переменная выведена из базиса,
то соответствующий столбец симплекс-таблицы можно просто вычеркнуть и больше к нему не возвращаться.В конце концов возможны два варианта:
27.02.2020
Лекция 4 ЭМММ
Слайд 7Решение симплекс-таблицы
Вариант 1
Все векторы, соответствующие введенным дополнительным переменным, будут выведены
из базиса.
В этом случае мы просто вернемся к исходной
задаче, попав в какую-то вершину допустимой области. Все столбцы симплекс-таблицы, соответствующие дополнительным переменным, тогда исчезнут и дальше будет решаться исходная задача.
27.02.2020
Лекция 4 ЭМММ
Слайд 8Решение симплекс-таблицы
Вариант 2
Несмотря на то, что M очень велико, получающийся
оптимальный план будет все-таки содержать какую-то из дополнительных переменных.
Это
означает, что допустимая область исходной задачи пуста, то есть ограничения исходной задачи противоречивы и поэтому исходная задача вообще не имеет решений.Заметим в заключение, что величина M вообще не конкретизируется и так и остается в виде буквы M.
При решении учебных задач в дополнительную строку пишут алгебраические выражения, содержащие M, а при счете на ПК вводится еще одна дополнительная строка, куда пишутся коэффициенты при M.
27.02.2020
Лекция 4 ЭМММ
Слайд 10Строим симплекс-таблицу
Разрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец
x3.
Разрешающую строку найдем по минимуму отношения:
Min {15/3; 20/5;10/1}=10 – строка
х627.02.2020
Лекция 4 ЭМММ
Слайд 11Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка
= 7/5М+16/5 - столбец x2 .
Разрешающую строку найдем по минимуму
отношения: Min {15/7; 20;30/9}=15/7– строка х527.02.2020
Лекция 4 ЭМММ
Слайд 12Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка
= 6/7 - столбец x1 .
Разрешающую строку найдем по минимуму
отношения: Min {-15; 25/3;15/6}=21/7– строка х427.02.2020
Лекция 4 ЭМММ
Слайд 13Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Полученный план оптимален.
Х* = (х1=5/2
; x2=5/2 ; х3=5/2), F(x*)=-15
27.02.2020
Лекция 4 ЭМММ
Слайд 14Пример 2
max f(xi)=3x1+2x2+x3
2x1+x2=8
x1+x2+x3=6
X1,2,3>=0
max f(xi)=3x1+2x2+x3-Mx4
2x1+x2+x4=8
x1+x2+x3=6
X1,2,3>=0
27.02.2020
Лекция 4 ЭМММ
Введем дополнительные переменные:
Слайд 15Строим симплекс-таблицу
Разрешающему столбцу соответствует наименьшая оценка = -2M-2 – столбец
x1.
Разрешающую строку найдем по минимуму отношения:
Min {8/2; 6/1;}=4– строка х4
27.02.2020
Лекция
4 ЭМММ
Слайд 16Строим симплекс-таблицу
Полученный план оптимален.
Х* = (х1=4 ; x2=0 ; х3=2),
F(x*)=14
27.02.2020
Лекция 4 ЭМММ
Слайд 17Письменно ответить на вопросы
Решить методом искусственного базиса ЗЛП:
max f(xi)=x1+2x2+2x3
x1+2x2=6
x1+3x2+x3=12
х1,2,3>=0
Не забудьте
указать ФИО и № группы!
27.02.2020
Лекция 4 ЭМММ
