Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ презентация

Содержание

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

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

Слайд 2хранение
5 тыс $
90 тыс $
90 тыс $
потом
сразу

n лет

Слайд 3решить задачу управления запасами процент 0,01(2b+d) 1/год,


расход=

цена заказа 40(c+6)р.
Оценить спрос

на деньги населения
N=(c+d)20*106

р./мес ,

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

на деньги.

Слайд 5Введение в управление запасами





Водопад
запас
S
S
S
S




Оптимальный размер заказа
T
T
T
Z
Q

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

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

Слайд 8T
T
T
T
S
S
S
S
S




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

Слайд 9Введение в управление запасами





Водопад
запас
S
S
S
S
T
T
T

Слайд 10Введение в управление запасами





Водопад
запас
S
S
S
S

T
T
T

Слайд 11решить задачу управления запасами процент 0,14 1/год,

расход 20 000

р/мес.

цена заказа 180р.

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




Оптимальный размер заказа

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

Слайд 14Уточнение..



Эффективный уровень запаса Q/2
Вместо этого можно считать b -> 0,5 b
решить

задачу управления запасами процент 0,1(2b+d) 1/год, расход

р./мес , цена зак.40(c+6)р. Указание

. Оценить спрос на деньги населения N=(c+d)20*106

Слайд 15решить задачу управления запасами процент 0,01(2b+d) 1/год,


расход=

цена заказа 40(c+6)р.
Оценить спрос

на деньги населения
N=(c+d)20*106

р./мес ,

Слайд 16решить задачу управления запасами процент 0,14 1/год,

расход 20 000

р/мес.

цена заказа 180р.

Ответ: индивидуальный спрос на деньги равен 20 тыс. рублей,

Слайд 17решить задачу управления запасами процент 0,14 1/год,

расход 20 000

р/мес.

цена заказа 180р.


















Население N=100 000 000 чел


Ответ: индивидуальный спрос на деньги равен 20 тыс. рублей,

Ответ №2 : спрос населения на деньги равен 2 трлн. рублей

b

Q

спрос на деньги населения







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

Слайд 20DH (20 км)

Слайд 21DH (20 км)

Минимальное остовное дерево
Шага и ребра

Слайд 22
150 км
34 км
2500 км
20 км
1500 км
A
D
H
C
DH (20 км)
DA (34 км)


Слайд 23
150 км
34 км
2500 км
20 км
1500 км
A
D
H
C
DH (20 км)
DA (34 км)
АС (1500

км)



Условная оптимизация

Слайд 24150 км
34 км
2500 км
20 км
1500 км
A
D
H
C
DH (20 км)
DA (34 км)
АС (1500

км)



Условная оптимизация

Суммарная длина … =1554 км

Ответ:

S

Слайд 25Построить мин. остовное дерево жадным алгоритмом

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Задание и пример

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)

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

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

проекта

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

Слайд 35
самый короткий маршрут между городами T и S


7
3
3
3
1
S
B
C
T
F
I
6
3
1
1
5
H
Z=0 км.
.

45
5
D

Слайд 36Задача





Слайд 37
Найти самый короткий маршрут


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








Слайд 38самый короткий маршрут между городами 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




Слайд 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 км.

Zc=min(Zh+3,
Zd+7)=
=3+3=6

D

.


45

Ответ:кратч.путь – SBCHT, полная длина 9 км.

5




Слайд 40самый короткий маршрут между городами 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





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

Ответ:кратч.путь –…

5




Слайд 42Найти самый короткий маршрут


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

Слайд 43Самый безопасный маршрут...
Вероятность не заплатить штраф
Вероятность не заплатить штраф на маршруте
→max
→max
минус

логарифмы

Монотонное преобразование

Инверсия

→min

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

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

Слайд 46Строительство дома.
Школа
фунд
Монол(несущие) стены
Кладка вн стен
крыша
остекление
Черн.
отделка

Подвод коммуникаций
Чистовая
отделка

S
F
В обычном проекте от

15 000 до 40 000 работ


Короткий вариант

d

Слайд 47Строительство дома.

Короткий вариант
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



Слайд 48Задача













Короткий вариант
d

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

Слайд 50Проект из 3х работ

Искать не можем
Ищем

Слайд 51Проект из 3х работ


Ищем

Слайд 52Проект из 3х работ


Слайд 53Проект из 3х работ


Слайд 54Проект из 3х работ


Слайд 55Проект из 3х работ


Слайд 56Проект из 3х работ



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

Слайд 58Рассчитать время и запасы

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


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



Слайд 61Рассчитать время и запасы

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

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

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

Слайд 65B
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 варианта

пример :

Слайд 66Поздние времена последовательно вычисляются. Например, на первом шаге позднее время может

быть вычислено для события В(и ни для какого другого), т.к. известно позднее время в точке 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 мес.

Слайд 67F
I
H
L
M
V
C
D
40
80
60
30
15
13
16
63
84
35
49
72

Тр=0
Крит. Путь.

Слайд 68F
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



Слайд 69Замена оборудования
Уст. Оборудование теряет в стоимости:
1й год стоимость 4000, послед года

2 р меньше
2й год – 2000р
3й год – 1000р
4й год -500 р
и т.д.
Издержки функ: 600р*число лет
(время 5 лет)


















Граничное условие

продажа оборудования

продажа

продажа

продажа

продажа

Ответ: эксплуатировать три года, потом заменить и не менять 2 года, прибыль 11 900 р .

Слайд 70Замена оборудования
Оборудование стоит 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

старение

эксплуатация

Слайд 71F
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

Слайд 72F
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

Слайд 73F
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

Слайд 74F
I
H
L
M
V
C
D
40
80
60
30
15
13
16
63
84
35
49
72

Тр=0
Крит. Путь.

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

Слайд 76Решение:


Слайд 77Пример:
Забега вперёд

Слайд 81ответ

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

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

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

Слайд 86Среднее время в системе - …

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

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

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

Слайд 93Переход по циклу

Слайд 102БАЗИСНЫЙ ПЛАН ПОСТРОЕН!!!

Слайд 104









столбцы
строки





















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

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

Слайд 106Транспортная задача
М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

Слайд 107Транспортная задача
x21= 120
x43= 160
x11=80
x33= 120
x32= 120
x12= 20
Метод Потенциалов

таможня
Вывозные пошлины
Ввозные пошлины
Новые тарифы





Слайд 108Транспортная задача
x21= 120 .
x43= 160
x11=80
x33= 120
x32= 120
x12= 20

.

Метод Потенциалов


таможня

Новые тарифы

Берём минимальный (отрицательный элемент)





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

типа проходящий через неё и базисные переменные.

Слайд 111Транспортная задача
x21= 100
x43= 160
x11=100
x33= 120
x32= 120
x22= 20
Метод

Потенциалов

таможня

Рассчитаем новые тарифы

Берём минимальный (отрицательный элемент)


Данный план оптимален
Отрицательных тарифов нет

Слайд 112Операционная стоимость

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

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

Выбираем небазисную переменную

Уменьшаем целевую функцию до

бесконечности?

Слайд 115Лучше возможно?!: Двойственная задача и метод потенциалов

Выбираем небазисную переменную
Уменьшаем целевую функцию

до бесконечности?

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

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

– не зависит от x и не меняет предпочтения задачи


Выбираем небазисную переменную





Слайд 118Лучше возможно?!: Двойственная задача и метод потенциалов

Выбираем небазисную переменную




Слайд 119Лучше возможно?!: Двойственная задача и метод потенциалов

Выбираем небазисную переменную



Слайд 120Лучше возможно?!: Двойственная задача и метод потенциалов

Выбираем небазисную переменную




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

Выбираем небазисную переменную




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

– не зависит от x и не меняет предпочтения задачи


Выбираем небазисную переменную





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

– не зависит от x и не меняет предпочтения задачи


Выбираем небазисную переменную





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

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

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

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


Слайд 130

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



Обратная пропускная

способность

Прямая пропускная способность

Сводим задачу к <аналогичной> предыдущей :

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

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

Слайд 132Алгоритм Дейкстры
Задача о построении минимального потока на графе
100
11
17
5
23
10
0
0
S
F
Дана сеть,

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

0

2

B

A

b

0

Слайд 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
12
21
0
11
S
F
Дана сеть,

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

11

2

B

A



Слайд 136Алгоритм Дейкстры
Задача о построении минимального потока на графе
89
0
17
5
02
21
0
11
S
F
Дана сеть,

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

11

2

B

A




Слайд 137Алгоритм Дейкстры
Задача о построении минимального потока на графе
89
0
17
5
12
21
0
11
S
F
Дана сеть,

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

11

2

B

A




Слайд 138Алгоритм Дейкстры
Задача о построении минимального потока на графе
84
0
17
0
12
21
5
11
S
F
Дана сеть,

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

16

2

B

A




Путей нет

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

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

Слайд 140Алгоритм Дейкстры
Задача о построении минимального потока на графе
84
0
17
0
02
21
5
11
S
F
Дана сеть,

cij – пропускные способности маршрутов в каждом направлении

Найти максимальный поток от источника S к стоку F на этом графе.

16

2

B

A


Слайд 141Алгоритм Дейкстры
Задача о построении минимального потока на графе
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:

Слайд 142

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





Обратная пропускная

способность

Прямая пропускная способность

Сводим задачу к <аналогичной> предыдущей :

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

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

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

Учитель как главная позиция в школе Неблагоприятная ситуация для одаренного ученика 80 % - конфликт с учителями и даже со школой ) Неблагоприятная ситуация для одаренного учителя 207
Обмотки машин переменного тока. Построение развернутой схемы трехфазной двухслойной статорной обмотки с укороченным шагом 369
План презентации: Презентация должна быть на светлом фоне без анимации. Переход слайдов по щелчку. Презентация диплом состоит из следующих частей: 1) титульный лист 2)объект, предмет, цель, задачи и методы исследования (т.е. ваше введение) 3) Гипотеза 4) 327
Сложение и вычитание в пределах 20 191
Развитие мелкой моторики 222
ВОЗМОЖНОСТИ ФИНАНСИРОВАНИЯ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЙ НА ФОНДОВОМ РЫНКЕ 177

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

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

Email: Нажмите что бы посмотреть 

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

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика