Кривошеев О.И. МЭСИ, каф. Прикладной математики. 5 тыс $ 90 тыс $ потом сразу n лет. - презентация

1 Кривошеев О.И. МЭСИ, каф. Прикладной математики

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

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

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

5 Введение в управление запасами Водопад запас S S S S Оптимальный размер заказа T TT Z Q Стоимость транзакции Цена хранения Величина расхода Объём заказа

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

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

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

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

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

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

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

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

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

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

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

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

18 150 км 34 км 2500 км 20 км 1500 км A D H C

19 150 км 34 км 2500 км 20 км 1500 км A D H C

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

21 150 км 34 км 2500 км 20 км 1500 км A D H C 1. DH (20 км) Минимальное остов ное дерево Шага и ребра

22 150 км 34 км 2500 км 20 км 1500 км A D H C 1. DH (20 км) 2. DA (34 км)

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

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

25 Построить мин. остов ное дерево жадным алгоритмом 13-b13-b 12+a |7-d| d-1 10-b c+5 Рига Москва Одесса Aстрахань Екатеринбург СПб GE ( 1 км) А В С D Е Н I G K L M 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 МК ( 37 км) S Ответ: минимальное остов ное дерево протяженность: 116 км n=12 Число шагов =12-1 (n-1)

26 Задание и пример |7-d| d с+5 Рига Москва Одесса Aстрахань Екатеринбург СПб Уренгой 12+с 23-а-b b 12+a 12-b GE ( 1 км) А В С D Е Н I G K L M 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 МК ( 37 км) S Ответ: минимальное остов ное дерево протяженность: 116 км n=12 Число шагов =12-1 (n-1)

27

28

29

30

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

32

33

34

35 S самый короткий маршрут между городами T и S S B C T FI H Z=0 км D

36 Задача b a+1 1 S B C AE T FI 6+b d d c 2 c (b+d)/2 a 1+а Найти кратчайший путь из S до T. На каждом шаге в очередном слое расставляются наименьшие возможные расстояния до Т на основе длин путей до предыдущего слоя (указаны возле стрелок) и ранее вычисленных расстояний предыдущего слоя. Результаты вычислений должны быть записаны рядом с вершинами, в против ном случае в процессе проверки не возможно установить факт использования алгоритма. Кроме того, напротив каждой вершины одна из исходящих стрелок должна быть помечена как решение оптимизационной задачи поиска кратчайшего пути в этой вершине. При обратном проходе это даст возможность восстановить оптимальный путь. L H G D

37 Найти самый короткий маршрут S B C T F I H Z=0 км Zi=2 км. Z=1 км Z=3 км Zc=6 D Z=3+2=5 км. Z=10 км. Z=7 км. 45 Ответ:кратч.путь – SBCHT, полная длина 10 км. 5 b a+1 1 S B C AE T FI 6+b d d c 2 c (b+d)/2 a 1+а Найти кратчайший путь из S до T. На каждом шаге в очередном слое расставляются наименьшие возможные расстояния до Т на основе длин путей до предыдущего слоя (указаны возле стрелок) и ранее вычисленных расстояний предыдущего слоя. Результаты вычислений должны быть записаны рядом с вершинами, в против ном случае в процессе проверки не возможно установить факт использования алгоритма. Кроме того, напротив каждой вершины одна из исходящих стрелок должна быть помечена как решение оптимизационной задачи поиска кратчайшего пути в этой вершине. При обратном проходе это даст возможность восстановить оптимальный путь. L H G D

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

39 S самый короткий маршрут между городами T и S S B C T FI 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

40 S самый короткий маршрут между городами T и S S B C T FI 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

41 Найти самый короткий маршрут S B C T FI 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

42 Найти самый короткий маршрут S B C T FI 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

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

44

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

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

47 Найти критический(максимальный) путь(на основе ранних времен наступления событий), при обратном проходе найти поздние времена наступления событий и запасы времени в каждом событии-вершине (как разность позднего и раннего времен). Для 1-2 х не касающихся критического пути (полностью некритических) работ выписать все запасы времени(полный, собственный, I и II рода). (а также коэффициенты напряженности работ). Изобразить линейную диаграмму проекта. b a+1 1K S BC AE T F G H I J L b 4 (b+d)/2 Задача Короткий вариант d

48 50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп=30 Тп=0 S F B Обсчитанный проект из 3 х работ

49 50 мес. 17 мес.20 мес. Тр=0 Тр=??? Тр=? Тп=0 S F B Проект из 3 х работ Искать не можем Ищем

50 50 мес. 17 мес.20 мес. Тр=0 Тр=17 Тп=0 S F B Проект из 3 х работ Ищем

51 50 мес. 17 мес.20 мес. Тр=0 Тр=17 Тр=50 Тп= S F B Проект из 3 х работ

52 50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп= S F B Проект из 3 х работ

53 50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп=30 Тп= S F B Проект из 3 х работ

54 50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп=30 Тп=??? S F B Проект из 3 х работ

55 50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп=30 Тп=0 S F B Проект из 3 х работ

56 120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 SF B A Рассчитать время и запасы Итог в каждой вершине время и управление Подробно:...

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

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 120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 SF B A Рассчитать время и запасы

61 120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=? Тп=?? F Теперь обратный проход Критический путь: ST

62 120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=113 Тп=? F Теперь обратный проход

63 120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=113 Тп=96 F Теперь обратный проход

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

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

66 F I H L M V C D Тр=0 Крит. Путь.

67 F I H L M V C D Тр=0 Критческий путь. Ответ: ICDF Его длина 193 месяца Тр=40 Тр=80 Тр=60 Тр=93 Тр=109 Тр=112 Тр=193 Тп=193 Тп=177 Тп= Тп=120 Тп=109 Тп= Тп= =94 Тп= Тп=60 Тп=0 Тп=60-60

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

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

70 F I H L M V C D Тр=0 Крит. Путь. Тр=40+0 Тр=80+0 Тр=60+0

71 F I H L M V C D Тр=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 Тр=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 Тр=0 Крит. Путь.

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

75 Решение:

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

77

78

79

80 ответ

81

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

83

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

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

86

87

88

89

90

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

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

93

94

95

96 Транспортная задача Тамбов 200Тверь 300Томск 120 М 100 СПб 120 Ввост 240 Ростов 160 Мin(100,200)= 100 Мin(120,100)= 100 Мin(20,300)= 20 Мin(240,280)= 240 Мin(160,40)= 240 Мin(120,120)= 120

97 Транспортная задача Тамбов 200Тверь 300Томск 120 М 100 СПб 120 Ввост 240 Ростов 160

98

99

100 Владивост ок 25 СПб 30 Москва x11 0,5 x12 Хабаровск 35 4 x21 12 x22

101 Владивост ок 25 (5) СПб 30 Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 4 x21 12 x22

102 Владивост ок 25 (5) (0) СПб 30 Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30) 4 x21=5 12 x22

103 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22=30

104 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 =30 БАЗИСНЫЙ ПЛАН ПОСТРОЕН!!!

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

106 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно?!

107 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно?! Выбираем небазисную переменную Уменьшаем целевую функцию до бесконечности?

108 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную Уменьшаем целевую функцию до бесконечности?

109 Т.к. уменьшающиеся поставки должны остаться положительными

110 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную

111 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную

112 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22 Лучше возможно?!: Двойственная задача и метод потенциалов Выбираем небазисную переменную

113 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30)(0) 4 x21=5 12 x22=30 Лучше возможно?!: потенциалы подобрали так v+u=0 на базисных переменных Выбираем небазисную переменную

114 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 0 x11=20 0,5-(8+4) X12 Хабаровск 35 (30)(0) 0 x21=5 0 x22=30 Лучше возможно?!: v+u=0 потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи Выбираем небазисную переменную

115 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 0 x11=20 -11,5 X12 Хабаровск 35 (30)(0) 0 x21=5 0 x22=30 Лучше возможно?!: v+u=0 потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи Выбираем небазисную переменную

116 Владивост ок 25 (5) (0) СПб 30 (0) Москва 20 (0) 0 x11=20 -11,5 X12 Хабаровск 35 (30)(0) 0 x21=5 0 x22=30 Лучше возможно?!: v+u=0 потенциалы есть +- пошлина производителя и импортера – не зависит от x и не меняет предпочтения задачи Выбираем небазисную переменную

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

118 Задача определения кратчайшего пути

119

120

121 S F K D C 17(a+c+d) 45a c+a+b+d 5 a 10+b 11(b+c) 5b 120 5b+1 a b 0

122

123 Обратная пропускная способность Прямая пропускная способность Сводим задачу к предыдущей :

124 Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе SF 0 2 B A

125 SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе. 0 2 B A S F K D C 17(a+c+d) 45a c+a+b+d 5 a 10+b 11(b+c) 5b 120 5b+1 a b 0 Сводим задачу к предыдущей :

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

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

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

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

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

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

132 Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе SF 16 2 B A S F 0 2 B A SF 0 0 B A Обрат ная пропу скная спосо бность Пряма я пропу скная спосо бность S F K D C 17(a+c+d) 45a c+a+b+d 5 a 10+b 11(b+c) 5b 120 5b+1 a b 0 Ответ: Матрица потков Максимальная пропускная способность сети F max= 16

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

134 SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении F.=f1+f2=5+11=16 =поток 16 2 B A f SB =16= 11+5 Fsa=0 f BS =11+0 f BF =5 +0 f AF =11 +0 Вариант 2:

135 Обратная пропускная способность Прямая пропускная способность Сводим задачу к предыдущей :

136

137

138

139

140

141