Экономико-математические методы и модели

Содержание

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

Главная
Разное
Экономико-математические методы и модели

Слайды и текст этой презентации

Слайд 1 Экономико-математические методы и модели

к.э.н., доц. Косухина М.А.

Слайд 2Учебные вопросы
Решение ЗЛП симплекс-методом:
Метод искусственного базиса ( М-метод);
Примеры.
Лекция 4

ЭМММ
27.02.2020

Слайд 3Метод искусственного базиса
Последняя трудность, которую осталось преодолеть - это

определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются

все итерации.
За счет чего мы так легко составили исходную симплекс-таблицу в предыдущем примере из лекции 3 ? Легко видеть, что это произошло потому, что среди переменных были такие, что входили лишь в одно уравнение системы ограничений и не входили в другие.
На искусственном введении таких переменных и основан метод искусственного базиса.

27.02.2020

Лекция 4 ЭМММ

Метод искусственного базиса Последняя трудность, которую осталось преодолеть - это определение исходного опорного плана и исходной симплекс-таблицы,

Слайд 4Метод искусственного базиса
Итак, пусть мы имеем задачу линейного программирования в

канонической форме

Можно считать, что все bi≥0, так как умножением соответствующего

ограничения на -1 всегда можно сменить знак.
Возьмем ну очень большое число M и будем решать следующую вспомогательную задачу.

27.02.2020

Лекция 4 ЭМММ

Метод искусственного базисаИтак, пусть мы имеем задачу линейного программирования в канонической формеМожно считать, что все bi≥0, так

Слайд 5Вспомогательная задача

В этой задаче сразу ясен исходный базис - в

качестве него надо взять переменные xn+1,…,xn+m.
В качестве исходного опорного плана

надо взять план

27.02.2020

Лекция 4 ЭМММ

Вспомогательная задачаВ этой задаче сразу ясен исходный базис - в качестве него надо взять переменные xn+1,…,xn+m.В качестве

Слайд 6Решение симплекс-таблицы
А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса

дополнительные переменные.
Заметим, что если какая-то дополнительная переменная выведена из базиса,

то соответствующий столбец симплекс-таблицы можно просто вычеркнуть и больше к нему не возвращаться.
В конце концов возможны два варианта:

27.02.2020

Лекция 4 ЭМММ

Решение симплекс-таблицыА теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса дополнительные переменные.Заметим, что если какая-то дополнительная переменная

Слайд 7Решение симплекс-таблицы
Вариант 1
Все векторы, соответствующие введенным дополнительным переменным, будут выведены

из базиса.
В этом случае мы просто вернемся к исходной

задаче, попав в какую-то вершину допустимой области.
Все столбцы симплекс-таблицы, соответствующие дополнительным переменным, тогда исчезнут и дальше будет решаться исходная задача.

27.02.2020

Лекция 4 ЭМММ

Решение симплекс-таблицыВариант 1Все векторы, соответствующие введенным дополнительным переменным, будут выведены из базиса. В этом случае мы просто

Слайд 8Решение симплекс-таблицы
Вариант 2
Несмотря на то, что M очень велико, получающийся

оптимальный план будет все-таки содержать какую-то из дополнительных переменных.
Это

означает, что допустимая область исходной задачи пуста, то есть ограничения исходной задачи противоречивы и поэтому исходная задача вообще не имеет решений.
Заметим в заключение, что величина M вообще не конкретизируется и так и остается в виде буквы M.
При решении учебных задач в дополнительную строку пишут алгебраические выражения, содержащие M, а при счете на ПК вводится еще одна дополнительная строка, куда пишутся коэффициенты при M.

27.02.2020

Лекция 4 ЭМММ

Решение симплекс-таблицыВариант 2Несмотря на то, что M очень велико, получающийся оптимальный план будет все-таки содержать какую-то из

Слайд 9Введем дополнительные переменные:
Пример 1
27.02.2020
Лекция 4 ЭМММ

Слайд 10Строим симплекс-таблицу
Разрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец

x3.
Разрешающую строку найдем по минимуму отношения:
Min {15/3; 20/5;10/1}=10 – строка

х6

27.02.2020

Лекция 4 ЭМММ

Строим симплекс-таблицуРазрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец x3.Разрешающую строку найдем по минимуму отношения:Min {15/3;

Слайд 11Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка

= 7/5М+16/5 - столбец x2 .
Разрешающую строку найдем по минимуму

отношения: Min {15/7; 20;30/9}=15/7– строка х5

27.02.2020

Лекция 4 ЭМММ

Переходим к новой симплекс-таблице методом Жордана-Гаусса.Разрешающему столбцу соответствует наибольшая оценка = 7/5М+16/5 - столбец x2 .Разрешающую строку

Слайд 12Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка

= 6/7 - столбец x1 .
Разрешающую строку найдем по минимуму

отношения: Min {-15; 25/3;15/6}=21/7– строка х4

27.02.2020

Лекция 4 ЭМММ

Переходим к новой симплекс-таблице методом Жордана-Гаусса.Разрешающему столбцу соответствует наибольшая оценка = 6/7 - столбец x1 .Разрешающую строку

Слайд 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 ЭМММ
Введем дополнительные переменные:

Пример 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Строим симплекс-таблицу
Разрешающему столбцу соответствует наименьшая оценка = -2M-2 – столбец

x1.
Разрешающую строку найдем по минимуму отношения:
Min {8/2; 6/1;}=4– строка х4

27.02.2020
Лекция

4 ЭМММ

Строим симплекс-таблицуРазрешающему столбцу соответствует наименьшая оценка = -2M-2 – столбец x1.Разрешающую строку найдем по минимуму отношения:Min {8/2;

Слайд 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 ЭМММ

Письменно ответить на вопросыРешить методом искусственного базиса ЗЛП:max f(xi)=x1+2x2+2x3x1+2x2=6x1+3x2+x3=12х1,2,3>=0Не забудьте указать ФИО и № группы! 27.02.2020Лекция 4

Скачать презентацию

Разделы презентаций

Экономико-математические методы и модели

Содержание

Слайды и текст этой презентации

Слайд 1 Экономико-математические методы и модели

к.э.н., доц. Косухина М.А.

Слайд 2Учебные вопросы
Решение ЗЛП симплекс-методом:
Метод искусственного базиса ( М-метод);
Примеры.
Лекция 4

ЭМММ
27.02.2020

Слайд 3Метод искусственного базиса
Последняя трудность, которую осталось преодолеть - это

определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются

Слайд 4Метод искусственного базиса
Итак, пусть мы имеем задачу линейного программирования в

канонической форме

Можно считать, что все bi≥0, так как умножением соответствующего

Слайд 5Вспомогательная задача

В этой задаче сразу ясен исходный базис - в

качестве него надо взять переменные xn+1,…,xn+m.
В качестве исходного опорного плана

Слайд 6Решение симплекс-таблицы
А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса

дополнительные переменные.
Заметим, что если какая-то дополнительная переменная выведена из базиса,

Слайд 7Решение симплекс-таблицы
Вариант 1
Все векторы, соответствующие введенным дополнительным переменным, будут выведены

из базиса.
В этом случае мы просто вернемся к исходной

Слайд 8Решение симплекс-таблицы
Вариант 2
Несмотря на то, что M очень велико, получающийся

оптимальный план будет все-таки содержать какую-то из дополнительных переменных.
Это

Слайд 9Введем дополнительные переменные:
Пример 1
27.02.2020
Лекция 4 ЭМММ

Слайд 10Строим симплекс-таблицу
Разрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец

x3.
Разрешающую строку найдем по минимуму отношения:
Min {15/3; 20/5;10/1}=10 – строка

Слайд 11Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка

= 7/5М+16/5 - столбец x2 .
Разрешающую строку найдем по минимуму

Слайд 12Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка

= 6/7 - столбец x1 .
Разрешающую строку найдем по минимуму

Слайд 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
Лекция

Слайд 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 ЭМММ

Обратная связь

Что такое TheSlide.ru?

Разделы презентаций

Экономико-математические методы и модели

Содержание

Слайды и текст этой презентации

Слайд 1 Экономико-математические методы и моделик.э.н., доц. Косухина М.А.

Слайд 2Учебные вопросы Решение ЗЛП симплекс-методом:Метод искусственного базиса ( М-метод);Примеры.Лекция 4

ЭМММ27.02.2020

Слайд 3Метод искусственного базиса Последняя трудность, которую осталось преодолеть - это

определение исходного опорного плана и исходной симплекс-таблицы, с которой начинаются

Слайд 4Метод искусственного базисаИтак, пусть мы имеем задачу линейного программирования в

канонической формеМожно считать, что все bi≥0, так как умножением соответствующего

Слайд 5Вспомогательная задачаВ этой задаче сразу ясен исходный базис - в

качестве него надо взять переменные xn+1,…,xn+m.В качестве исходного опорного плана

Слайд 6Решение симплекс-таблицыА теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса

дополнительные переменные.Заметим, что если какая-то дополнительная переменная выведена из базиса,

Слайд 7Решение симплекс-таблицыВариант 1Все векторы, соответствующие введенным дополнительным переменным, будут выведены

из базиса. В этом случае мы просто вернемся к исходной

Слайд 8Решение симплекс-таблицыВариант 2Несмотря на то, что M очень велико, получающийся

оптимальный план будет все-таки содержать какую-то из дополнительных переменных. Это

Слайд 9Введем дополнительные переменные:Пример 127.02.2020Лекция 4 ЭМММ

Слайд 10Строим симплекс-таблицуРазрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец

x3.Разрешающую строку найдем по минимуму отношения:Min {15/3; 20/5;10/1}=10 – строка

Слайд 11Переходим к новой симплекс-таблице методом Жордана-Гаусса.Разрешающему столбцу соответствует наибольшая оценка

= 7/5М+16/5 - столбец x2 .Разрешающую строку найдем по минимуму

Слайд 12Переходим к новой симплекс-таблице методом Жордана-Гаусса.Разрешающему столбцу соответствует наибольшая оценка

= 6/7 - столбец x1 .Разрешающую строку найдем по минимуму

Слайд 13Переходим к новой симплекс-таблице методом Жордана-Гаусса.Полученный план оптимален.Х* = (х1=5/2

; x2=5/2 ; х3=5/2), F(x*)=-1527.02.2020Лекция 4 ЭМММ

Слайд 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Строим симплекс-таблицуРазрешающему столбцу соответствует наименьшая оценка = -2M-2 – столбец

x1.Разрешающую строку найдем по минимуму отношения:Min {8/2; 6/1;}=4– строка х427.02.2020Лекция

Слайд 16Строим симплекс-таблицуПолученный план оптимален.Х* = (х1=4 ; x2=0 ; х3=2),

F(x*)=1427.02.2020Лекция 4 ЭМММ

Слайд 17Письменно ответить на вопросыРешить методом искусственного базиса ЗЛП:max f(xi)=x1+2x2+2x3x1+2x2=6x1+3x2+x3=12х1,2,3>=0Не забудьте

указать ФИО и № группы! 27.02.2020Лекция 4 ЭМММ

Похожие презентации

Обратная связь

Что такое TheSlide.ru?

Слайд 1 Экономико-математические методы и модели

к.э.н., доц. Косухина М.А.

Слайд 2Учебные вопросы
Решение ЗЛП симплекс-методом:
Метод искусственного базиса ( М-метод);
Примеры.
Лекция 4

ЭМММ
27.02.2020

Слайд 3Метод искусственного базиса
Последняя трудность, которую осталось преодолеть - это

Слайд 4Метод искусственного базиса
Итак, пусть мы имеем задачу линейного программирования в

канонической форме

Можно считать, что все bi≥0, так как умножением соответствующего

Слайд 5Вспомогательная задача

В этой задаче сразу ясен исходный базис - в

качестве него надо взять переменные xn+1,…,xn+m.
В качестве исходного опорного плана

Слайд 6Решение симплекс-таблицы
А теперь начнем преобразования симплекс-таблицы, стараясь выводить из базиса

дополнительные переменные.
Заметим, что если какая-то дополнительная переменная выведена из базиса,

Слайд 7Решение симплекс-таблицы
Вариант 1
Все векторы, соответствующие введенным дополнительным переменным, будут выведены

из базиса.
В этом случае мы просто вернемся к исходной

Слайд 8Решение симплекс-таблицы
Вариант 2
Несмотря на то, что M очень велико, получающийся

оптимальный план будет все-таки содержать какую-то из дополнительных переменных.
Это

Слайд 9Введем дополнительные переменные:
Пример 1
27.02.2020
Лекция 4 ЭМММ

Слайд 10Строим симплекс-таблицу
Разрешающему столбцу соответствует наибольшая оценка = 8M+4 – столбец

x3.
Разрешающую строку найдем по минимуму отношения:
Min {15/3; 20/5;10/1}=10 – строка

Слайд 11Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка

= 7/5М+16/5 - столбец x2 .
Разрешающую строку найдем по минимуму

Слайд 12Переходим к новой симплекс-таблице методом Жордана-Гаусса.
Разрешающему столбцу соответствует наибольшая оценка

= 6/7 - столбец x1 .
Разрешающую строку найдем по минимуму

Слайд 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
Лекция

Слайд 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 ЭМММ