'

Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Понравилась презентация – покажи это...





Слайд 0

Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ Кривошеев О.И. МЭСИ, каф. Прикладной математики


Слайд 1

хранение 5 тыс $ 90 тыс $ 90 тыс $ потом сразу n лет


Слайд 2

решить задачу управления запасами процент 0,01(2b+d) 1/год, расход= цена заказа 40(c+6)р. Оценить спрос на деньги населения N=(c+d)20*106 р./мес ,


Слайд 3

Стоимость транзакции Цена хранения Величина расхода Задача оценить Б) объём денежной массы в стране А) индив. Спрос на деньги.


Слайд 4

Введение в управление запасами Водопад запас S S S S Оптимальный размер заказа T T T Z Q


Слайд 5

Стоимость транзакции Цена хранения Величина расхода Объём заказа


Слайд 6

Время между заказами


Слайд 7

T T T T S S S S S Q Q Q V, b График: динамика запаса Ежеквартальные платежи


Слайд 8

Введение в управление запасами Водопад запас S S S S T T T


Слайд 9

Введение в управление запасами Водопад запас S S S S T T T


Слайд 10

решить задачу управления запасами процент 0,14 1/год, расход 20 000 р/мес. цена заказа 180р.


Слайд 11

исследование ф-ии Z(Q). Оптимальный размер заказа


Слайд 12

исследование ф-ии Z(Q).


Слайд 13

Уточнение.. Эффективный уровень запаса Q/2 Вместо этого можно считать b -> 0,5 b решить задачу управления запасами процент 0,1(2b+d) 1/год, расход р./мес , цена зак.40(c+6)р. Указание . Оценить спрос на деньги населения N=(c+d)20*106


Слайд 14

решить задачу управления запасами процент 0,01(2b+d) 1/год, расход= цена заказа 40(c+6)р. Оценить спрос на деньги населения N=(c+d)20*106 р./мес ,


Слайд 15

решить задачу управления запасами процент 0,14 1/год, расход 20 000 р/мес. цена заказа 180р. Ответ: индивидуальный спрос на деньги равен 20 тыс. рублей,


Слайд 16

решить задачу управления запасами процент 0,14 1/год, расход 20 000 р/мес. цена заказа 180р. Население N=100 000 000 чел Ответ: индивидуальный спрос на деньги равен 20 тыс. рублей, Ответ №2 : спрос населения на деньги равен 2 трлн. рублей b Q спрос на деньги населения


Слайд 17

Жадный алгоритм Задача о построении минимального остовного дерева


Слайд 18


Слайд 19

DH (20 км)


Слайд 20

DH (20 км) Минимальное остовное дерево Шага и ребра


Слайд 21

150 км 34 км 2500 км 20 км 1500 км A D H C DH (20 км) DA (34 км)


Слайд 22

150 км 34 км 2500 км 20 км 1500 км A D H C DH (20 км) DA (34 км) АС (1500 км) Условная оптимизация


Слайд 23

150 км 34 км 2500 км 20 км 1500 км A D H C DH (20 км) DA (34 км) АС (1500 км) Условная оптимизация Суммарная длина … =1554 км Ответ: S


Слайд 24

Построить мин. остовное дерево жадным алгоритмом 1 2 4 3 5 8.5 7 8 21 10 11 35 14 37 43 39 20 1. GE ( 1 км) А В С D Е Н I G K L M 7 9 2. GI ( 2 км) 3. EO ( 4 км) О S S 4. GС ( 5 км) 5. DН ( 7 км) 6. НС ( 7 км) S S 7. МС ( 8 км) 8 8. LA ( 11 км) 9. AM ( 14 км) 10. ВК ( 20 км) S 38 11. МК ( 37 км) S Ответ: минимальное остовное дерево протяженность: 116 км n=12 Число шагов =12-1 (n-1)


Слайд 25

Задание и пример 12- 12+ 10-b 12+a 12-b 1 2 4 3 5 8.5 7 8 21 10 11 35 14 37 43 39 20 1. GE ( 1 км) А В С D Е Н I G K L M 7 9 2. GI ( 2 км) 3. EO ( 4 км) О S S 4. GС ( 5 км) 5. DН ( 7 км) 6. НС ( 7 км) S S 7. МС ( 8 км) 8 8. LA ( 11 км) 9. AM ( 14 км) 10. ВК ( 20 км) S 38 11. МК ( 37 км) S Ответ: минимальное остовное дерево протяженность: 116 км n=12 Число шагов =12-1 (n-1)


Слайд 26


Слайд 27


Слайд 28


Слайд 29


Слайд 30

Сеть нефтепроводов на море…


Слайд 31

Самый длинный - критический - путь в графе Планирование и моделирование проекта


Слайд 32


Слайд 33

Метод и примеры практического применения . Задача динамического программирования


Слайд 34

самый короткий маршрут между городами T и S 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км. . 45 5 D


Слайд 35

Задача


Слайд 36

Найти самый короткий маршрут 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км Zi=2 км. Z=1 км Z=3 км Zc=6 D Z=3+2=5 км. Z=10 км. Z=7 км. 45 Ответ:кратч.путь – SBCHT, полная длина 10 км. 5


Слайд 37

самый короткий маршрут между городами T и S 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км. . Z=0+1 км. Z=0+3 км. D . 45 5


Слайд 38

самый короткий маршрут между городами T и S 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км. Zi= =min(5+Zh,1+Zd)= 1+1=2 км. Z=0+1 км. Z=0+3 км. Zc=min(Zh+3, Zd+7)= =3+3=6 D . 45 Ответ:кратч.путь – SBCHT, полная длина 9 км. 5


Слайд 39

самый короткий маршрут между городами T и S 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км. Zi=min(5+Zh,1+Zd)=1+1=2 км. Z=0+1 км. Z=0+3 км. Z=3+3=6 D Z=2+3=5 км. . Z=7 км. 45 5


Слайд 40

Найти самый короткий маршрут 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км. Zi=min(5+Zh,1+Zd)=1+1=2 км. Z=0+1 км. Z=0+3 км. Zc=min(Zh+3, Zd+7)=3+3=6 D Z=3+3=6 км. Z=10 км. Z=7 км. 45 Ответ:кратч.путь –… 5


Слайд 41

Найти самый короткий маршрут 7 3 3 3 1 S B C T F I 6 3 1 1 5 H Z=0 км. Zi=min(5+Zh,1+Zd)=1+1=2 км. Z=0+1 км. Z=0+3 км. Zc=min(Zh+3, Zd+7)=3+3=6 D Z=3+3=6 км. Z=10 км. Z=7 км. 45 Ответ:кратч.путь – SBCHT, полная длина 10 км. 5


Слайд 42

Самый безопасный маршрут... Вероятность не заплатить штраф Вероятность не заплатить штраф на маршруте >max >max минус логарифмы Монотонное преобразование Инверсия >min


Слайд 43

Задача планирования проекта Сетевое планирование Построение кратчайшего пути


Слайд 44

СПУ: фунд стены отделка котл проект 2 проект 1 Сарай дом баня ~«душ»


Слайд 45

Строительство дома. Школа фунд Монол(несущие) стены Кладка вн стен крыша остекление Черн. отделка Подвод коммуникаций Чистовая отделка S F В обычном проекте от 15 000 до 40 000 работ Короткий вариант d


Слайд 46

Строительство дома. Короткий вариант d F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Ответ: Тр=40 Тр=80 Тр=60 Тр=93 Тр=109 Тр=112 Тр=193 Тп=193 Тп=177 Тп=193-16 Тп=130 Тп=109 Тп=130-72 58 Тп=109-15 =94 Тп=109-49 Тп=60 Тп=0 Тп=60-60


Слайд 47

Задача Короткий вариант d


Слайд 48

Обсчитанный проект из 3х работ


Слайд 49

Проект из 3х работ Искать не можем Ищем


Слайд 50

Проект из 3х работ Ищем


Слайд 51

Проект из 3х работ


Слайд 52

Проект из 3х работ


Слайд 53

Проект из 3х работ


Слайд 54

Проект из 3х работ


Слайд 55

Проект из 3х работ


Слайд 56

Рассчитать время и запасы Итог в каждой вершине время и управление Подробно:...


Слайд 57

Рассчитать время и запасы


Слайд 58

120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=??? Тр S F B A Рассчитать время и запасы


Слайд 59

120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр S F B A Рассчитать время и запасы


Слайд 60

Рассчитать время и запасы


Слайд 61

Теперь обратный проход Критический путь: ST


Слайд 62

Теперь обратный проход


Слайд 63

Теперь обратный проход


Слайд 64

B A TпН=96мес TрН=17мес Tпок=113мес Tрок=27мес Rран=27-17-10 10 мес. Rполн=113-17-10 Rсоб=27-96-10=-79 Rпоз=113-96-10 На каждой работе вычислить запасы 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=113 Тп=96 F 120 мес. окончание начало сама работа окончание начало работа 2 варианта 2 варианта пример :


Слайд 65

Поздние времена последовательно вычисляются. Например, на первом шаге позднее время может быть вычислено для события В(и ни для какого другого), т.к. известно позднее время в точке F . чтобы успеть к позднему времени события события F и не совать график всего проекта необходимо чтобы событие В состоялось не позднее чем через Тп=120-7=113 месяцев после старта проекта. После этого можно переходить к расчету позднего времени в точке A: нужно успеть за 10 месяцев к сроку 113(В) и за 24 месяца к F (120) – итого в А Тп=min(120-24, 113-10)=96. аналогично минимизируя позднее время для S (по трём вариантам) получим 0. (Вы можете догадаться, что совпадение обоих времен на критическом пути является общей закономерностью). Решение 2) работа AB не затрагивает критический путь FS. Рассчитаем для AB все запасы времени. В каждом событии есть два времени. Работа зависит от двух событий – значит для каждой работы имеется 4 комбинации Собственный запас Rc=-10+27-96=-69мес.(т.е. собственного запаса нет) Запас не претендующий на резервы предыдущих работ Rп=113-96-10=7 Запас не претендующий на резервы следующих работ Rр=27-17-10=0 мес Наконец максимальный (полный) запас времени на работу: Rм=113-10-17=86 мес.


Слайд 66

F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Крит. Путь.


Слайд 67

F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Критческий путь. Ответ: ICDF Его длина 193 месяца Тр=40 Тр=80 Тр=60 Тр=93 Тр=109 Тр=112 Тр=193 Тп=193 Тп=177 Тп=193-16 Тп=130 Тп=109 Тп=130-72 58 Тп=109-15 =94 Тп=109-49 Тп=60 Тп=0 Тп=60-60


Слайд 68

Замена оборудования Уст. Оборудование теряет в стоимости: 1й год стоимость 4000, послед года 2 р меньше 2й год – 2000р 3й год – 1000р 4й год -500 р и т.д. Издержки функ: 600р*число лет (время 5 лет) Граничное условие продажа оборудования продажа продажа продажа продажа Ответ: эксплуатировать три года, потом заменить и не менять 2 года, прибыль 11 900 р .


Слайд 69

Замена оборудования Оборудование стоит 4000 р. Уст. Оборудование теряет в стоимости: 1й год стоимость 4000, след года 2 р меньше 2й год – 2000р 3й год – 1000р 4й год -500 р (время 5 лет) и т.д. эксплуатация: 600*возраст возраст продажа 600(t+1) 600*1-4000*2t +4000t покупкаt t s, время s,t s+1,t+1 s+1,0 старение эксплуатация


Слайд 70

F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Крит. Путь. Тр=40+0 Тр=80+0 Тр=60+0


Слайд 71

F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Крит. Путь. Тр=40 Тр=80 Тр=60 Тр=80+13=max(TpM+ML;TpH+HL) Тр=49+60=max(TpM+MD;TpC+CD) Тр=40+72=max(TpH+HV;TpC+CV) Тр=93 Тр=109 Тр=112 Тр=193


Слайд 72

F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Крит. Путь. Тр=40+0 Тр=80+0 Тр=60+0 Тр=93=max(TpM+ML;TpH+HL) Тр=109=max(TpM+MD;TpC+CD) Тр=40+72=max(TpH+HV;TpC+CV) Тр=109+84=193= =max (TpL+LF; TpD+DF; TpV+VF) Тр=193


Слайд 73

F I H L M V C D 40 80 60 30 15 13 16 63 84 35 49 72 Тр=0 Крит. Путь.


Слайд 74

Вероятностное дин. программирование


Слайд 75

Решение:


Слайд 76

Пример: Забега вперёд


Слайд 77


Слайд 78


Слайд 79


Слайд 80

ответ


Слайд 81

Стационарные маркоские цепи. Система массового обслуживания.


Слайд 82

Система обслуживания с несколькими сервисами


Слайд 83


Слайд 84

Формула Литтла для связи объёма и скорости обновления людей


Слайд 85

Среднее время в системе - …


Слайд 86


Слайд 87

симплекс и граф. методы. Задача управления ресурсами, двойственная задача...


Слайд 88

метод потенциалов транспортная задача М-метод и


Слайд 89


Слайд 90


Слайд 91

Метод Северо-Западного угла


Слайд 92

Переход по циклу


Слайд 93


Слайд 94


Слайд 95


Слайд 96


Слайд 97


Слайд 98


Слайд 99


Слайд 100


Слайд 101

БАЗИСНЫЙ ПЛАН ПОСТРОЕН!!!


Слайд 102


Слайд 103

столбцы строки Склады(поставщики) Терминалы //потребители Суммарные издержки источник потребители сток


Слайд 104

Транспортная задача Мin(100,200)=100 Мin(120,100)=100 Мin(20,300)=20 Мin(240,280)=240 Мin(160,40)=240 Мin(120,120)=120 Метод с.западного Угла


Слайд 105

Транспортная задача Мin(120,200)=120 Мin(160,300)=160 Мin(100,80)=80 Мin(240,120)=120 Мin(120,140)=120 Мin(20, 20)=20 Метод минимального элемента 80 140 20 120 20


Слайд 106

Транспортная задача x21= 120 x43= 160 x11=80 x33= 120 x32= 120 x12= 20 Метод Потенциалов таможня Вывозные пошлины Ввозные пошлины Новые тарифы


Слайд 107

Транспортная задача x21= 120 . x43= 160 x11=80 x33= 120 x32= 120 x12= 20 . Метод Потенциалов таможня Новые тарифы Берём минимальный (отрицательный элемент)


Слайд 108


Слайд 109

«Теорема». Для каждой базисной переменной существует ровно один означенный цикл данного типа проходящий через неё и базисные переменные.


Слайд 110

Транспортная задача x21= 100 x43= 160 x11=100 x33= 120 x32= 120 x22= 20 Метод Потенциалов таможня Рассчитаем новые тарифы Берём минимальный (отрицательный элемент) Данный план оптимален Отрицательных тарифов нет


Слайд 111

Операционная стоимость


Слайд 112

БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно?!


Слайд 113

БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно?! Выбираем небазисную переменную Уменьшаем целевую функцию до бесконечности?


Слайд 114

Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную Уменьшаем целевую функцию до бесконечности?


Слайд 115

Уменьшаем целевую функцию до бесконечности? Т.к. уменьшающиеся поставки должны остаться положительными


Слайд 116

Лучше возможно?!: v+u=0 потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи Выбираем небазисную переменную


Слайд 117

Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную


Слайд 118

Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную


Слайд 119

Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную


Слайд 120

Лучше возможно?!: потенциалы подобрали так v+u=0 на базисных переменных Выбираем небазисную переменную


Слайд 121

Лучше возможно?!: v+u=0 потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи Выбираем небазисную переменную


Слайд 122

Лучше возможно?!: v+u=0 потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи Выбираем небазисную переменную


Слайд 123


Слайд 124

Задача определения кратчайшего пути Задача определения кратчайшего пути 1 3 2 5 4 6 7 2 4 6 5 4 4 6 15 17 3


Слайд 125

Алгоритм Дейкстры Задача о построении минимального потока на графе


Слайд 126

Алгоритм Дейкстры Задача о построении минимального потока на графе


Слайд 127

b 0


Слайд 128

Алгоритм Дейкстры Задача о построении минимального потока на графе


Слайд 129

Алгоритм Флойда Задача о построении минимального потока на графе Обратная пропускная способность Прямая пропускная способность Сводим задачу к <аналогичной> предыдущей :


Слайд 130

Алгоритм Дейкстры Задача о построении минимального потока на графе Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе.


Слайд 131

Алгоритм Дейкстры Задача о построении минимального потока на графе 100 11 17 5 23 10 0 0 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 0 2 B A b 0


Слайд 132

Алгоритм Дейкстры Задача о построении минимального потока на графе 89 0 17 5 12 21 0 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 11 2 B A


Слайд 133

Алгоритм Дейкстры Задача о построении минимального потока на графе 89 0 17 5 12 21 0 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 11 2 B A


Слайд 134

Алгоритм Дейкстры Задача о построении минимального потока на графе 89 0 17 5 12 21 0 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 11 2 B A


Слайд 135

Алгоритм Дейкстры Задача о построении минимального потока на графе 89 0 17 5 02 21 0 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 11 2 B A


Слайд 136

Алгоритм Дейкстры Задача о построении минимального потока на графе 89 0 17 5 12 21 0 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 11 2 B A


Слайд 137

Алгоритм Дейкстры Задача о построении минимального потока на графе 84 0 17 0 12 21 5 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 16 2 B A Путей нет


Слайд 138

Алгоритм Дейкстры Задача о построении максимального потока на графе Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 100 11 17 5 23 10 0 0 S F 0 2 B A 100-84 11-0 0 5-0 23-12 0 0 11 S F 0 0 B A Обратная пропускная способность Прямая пропускная способность b 0 Ответ: Матрица потков Максимальная пропускная способность сети Fmax=16


Слайд 139

Алгоритм Дейкстры Задача о построении минимального потока на графе 84 0 17 0 02 21 5 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 16 2 B A


Слайд 140

Алгоритм Дейкстры Задача о построении минимального потока на графе 84 0 17 0 12 21 5 11 S F Дана сеть, cij – пропускные способности маршрутов в каждом направлении F.=f1+f2=5+11=16 =поток 16 2 B A fSB=16= 11+5 Fsa=0 fBS=11+0 fBF=5 +0 fAF=11 +0 Вариант2:


Слайд 141

Алгоритм Дейкстры Задача о построении минимального потока на графе Обратная пропускная способность Прямая пропускная способность Сводим задачу к <аналогичной> предыдущей :


Слайд 142

метод потенциалов транспортная задача М-метод и


Слайд 143

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


Слайд 144


Слайд 145


Слайд 146


Слайд 147


×

HTML:





Ссылка: