Исследование
<<  Проект – исследование Подарим мусору вторую жизнь Введение в исследование  >>
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Хранение
Хранение
Решить задачу управления запасами процент 0,01(2b+d) 1/год, расход=
Решить задачу управления запасами процент 0,01(2b+d) 1/год, расход=
Задача оценить Б) объём денежной массы в стране А) индив
Задача оценить Б) объём денежной массы в стране А) индив
Введение в управление запасами
Введение в управление запасами
Величина расхода
Величина расхода
Время между заказами
Время между заказами
V, b
V, b
Введение в управление запасами
Введение в управление запасами
Введение в управление запасами
Введение в управление запасами
Решить задачу управления запасами процент 0,14 1/год, расход 20 000
Решить задачу управления запасами процент 0,14 1/год, расход 20 000
Исследование ф-ии Z(Q)
Исследование ф-ии Z(Q)
Исследование ф-ии Z(Q)
Исследование ф-ии Z(Q)
Уточнение
Уточнение
Решить задачу управления запасами процент 0,01(2b+d) 1/год, расход=
Решить задачу управления запасами процент 0,01(2b+d) 1/год, расход=
Ответ: индивидуальный спрос на деньги равен 20 тыс
Ответ: индивидуальный спрос на деньги равен 20 тыс
b
b
Задача о построении минимального остовного дерева
Задача о построении минимального остовного дерева
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
DH (20 км)
DH (20 км)
Минимальное остовное дерево
Минимальное остовное дерево
H
H
Условная оптимизация
Условная оптимизация
S
S
Построить мин
Построить мин
Задание и пример
Задание и пример
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Сеть нефтепроводов на море…
Сеть нефтепроводов на море…
Планирование и моделирование проекта
Планирование и моделирование проекта
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Задача динамического программирования
Задача динамического программирования
Самый короткий маршрут между городами T и S
Самый короткий маршрут между городами T и S
Задача
Задача
Найти самый короткий маршрут
Найти самый короткий маршрут
Самый короткий маршрут между городами T и S
Самый короткий маршрут между городами T и S
Самый короткий маршрут между городами T и S
Самый короткий маршрут между городами T и S
Самый короткий маршрут между городами T и S
Самый короткий маршрут между городами T и S
Ответ:кратч
Ответ:кратч
Найти самый короткий маршрут
Найти самый короткий маршрут
Самый безопасный маршрут
Самый безопасный маршрут
Сетевое планирование
Сетевое планирование
Спу:
Спу:
Строительство дома
Строительство дома
Строительство дома
Строительство дома
Задача
Задача
Обсчитанный проект из 3х работ
Обсчитанный проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Проект из 3х работ
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Рассчитать время и запасы
Теперь обратный проход
Теперь обратный проход
Теперь обратный проход
Теперь обратный проход
Теперь обратный проход
Теперь обратный проход
A
A
Поздние времена последовательно вычисляются
Поздние времена последовательно вычисляются
Крит
Крит
Тп=130-72
Тп=130-72
Замена оборудования
Замена оборудования
Замена оборудования
Замена оборудования
Крит
Крит
Крит
Крит
Крит
Крит
Крит
Крит
Вероятностное дин
Вероятностное дин
Решение:
Решение:
Пример:
Пример:
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Ответ
Ответ
Система массового обслуживания
Система массового обслуживания
Система обслуживания с несколькими сервисами
Система обслуживания с несколькими сервисами
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Формула Литтла для связи объёма и скорости обновления людей
Формула Литтла для связи объёма и скорости обновления людей
Среднее время в системе - …
Среднее время в системе - …
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Задача управления ресурсами, двойственная задача
Задача управления ресурсами, двойственная задача
Транспортная задача
Транспортная задача
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Метод Северо-Западного угла
Метод Северо-Западного угла
Переход по циклу
Переход по циклу
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Тамбов 50(c+a)
Тамбов 50(c+a)
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Владивосток 25
Владивосток 25
Владивосток 25 (5)
Владивосток 25 (5)
Владивосток 25 (5) (0)
Владивосток 25 (5) (0)
Владивосток 25 (5) (0)
Владивосток 25 (5) (0)
Базисный план построен
Базисный план построен
Тамбов 200
Тамбов 200
Суммарные издержки
Суммарные издержки
Транспортная задача
Транспортная задача
Транспортная задача
Транспортная задача
Метод Потенциалов
Метод Потенциалов
Метод Потенциалов
Метод Потенциалов
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Для каждой базисной переменной существует ровно один означенный цикл
Для каждой базисной переменной существует ровно один означенный цикл
Рассчитаем новые тарифы
Рассчитаем новые тарифы
Операционная стоимость
Операционная стоимость
БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно
БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно
БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно
БАЗИСНЫЙ ПЛАН: значение ЦФ/ Лучше возможно
Лучше возможно
Лучше возможно
Т.к. уменьшающиеся поставки должны остаться положительными
Т.к. уменьшающиеся поставки должны остаться положительными
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Лучше возможно
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Задача определения кратчайшего пути
Задача определения кратчайшего пути
Задача о построении минимального потока на графе
Задача о построении минимального потока на графе
Алгоритм Дейкстры
Алгоритм Дейкстры
b
b
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Флойда
Алгоритм Флойда
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Транспортная задача
Транспортная задача
Задача коммивояжёра
Задача коммивояжёра
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Презентация на тему: «Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ». Автор: . Файл: «Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ.ppt». Размер zip-архива: 3546 КБ.

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

содержание презентации «Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ.ppt»
СлайдТекст
1 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

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

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

2 Хранение

Хранение

Потом

90 тыс $

90 тыс $

Сразу

5 тыс $

N лет

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

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

цена заказа 40(c+6)р.

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

Р./Мес ,

4 Задача оценить Б) объём денежной массы в стране А) индив

Задача оценить Б) объём денежной массы в стране А) индив

Спрос на деньги.

Величина расхода

Цена хранения

Стоимость транзакции

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

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

Водопад

S

S

S

S

Запас

Z

Q

T

T

T

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

6 Величина расхода

Величина расхода

Цена хранения

Стоимость транзакции

Объём заказа

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

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

8 V, b

V, b

Q

Q

Q

S

S

S

S

S

T

T

T

T

График: динамика запаса

Ежеквартальные платежи

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

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

Запас

Водопад

S

S

S

S

T

T

T

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

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

Запас

Водопад

S

S

S

S

T

T

T

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

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

р/мес. Цена заказа 180р.

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

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

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

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

Исследование ф-ии 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/год, расход=

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

цена заказа 40(c+6)р.

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

Р./Мес ,

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

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

рублей,

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

17 b

b

Q

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

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

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

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

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

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

Жадный алгоритм

19 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
20 DH (20 км)

DH (20 км)

21 Минимальное остовное дерево

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

DH (20 км)

Шага и ребра

22 H

H

150 км

A

20 км

34 км

D

1500 км

2500 км

C

DH (20 км) DA (34 км)

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

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

H

150 км

A

20 км

34 км

D

1500 км

2500 км

C

DH (20 км) DA (34 км) АС (1500 км)

24 S

S

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

H

150 км

A

20 км

34 км

D

1500 км

2500 км

C

DH (20 км) DA (34 км) АС (1500 км)

Ответ:

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

25 Построить мин

Построить мин

остовное дерево жадным алгоритмом

Ответ: минимальное остовное дерево

1. GE ( 1 км)

2. GI ( 2 км)

3. EO ( 4 км)

4. GС ( 5 км)

5. DН ( 7 км)

6. НС ( 7 км)

7. МС ( 8 км)

8. LA ( 11 км)

9. AM ( 14 км)

10. ВК ( 20 км)

11. МК ( 37 км)

Протяженность: 116 км

n=12

Число шагов =12-1 (n-1)

Е

I

G

D

О

Н

С

А

M

В

L

K

S

4

3

S

1

8.5

S

2

9

8

S

7

5

7

10

21

S

S

8

14

35

11

38

37

43

20

39

26 Задание и пример

Задание и пример

Ответ: минимальное остовное дерево

1. GE ( 1 км)

2. GI ( 2 км)

3. EO ( 4 км)

4. GС ( 5 км)

5. DН ( 7 км)

6. НС ( 7 км)

7. МС ( 8 км)

8. LA ( 11 км)

9. AM ( 14 км)

10. ВК ( 20 км)

11. МК ( 37 км)

Протяженность: 116 км

n=12

Число шагов =12-1 (n-1)

Е

I

G

D

О

Н

С

А

M

В

L

K

12-

12+

S

4

3

S

1

8.5

S

2

9

8

S

7

5

7

10

21

S

10-b

S

8

14

35

11

38

37

43

20

39

12+a

12-b

27 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
28 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
29 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
30 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
31 Сеть нефтепроводов на море…

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

32 Планирование и моделирование проекта

Планирование и моделирование проекта

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

33 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
34 Задача динамического программирования

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

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

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

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

D

B

7

C

1

3

5

3

T

1

S

Z=0 км.

6

45

.

1

3

5

F

3

I

H

36 Задача

Задача

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

Найти самый короткий маршрут

Z=7 км.

Z=1 км

Zc=6

7

1

B

C

D

1

3

T

3

5

Z=10 км.

S

Z=0 км

45

6

1

3

F

5

H

3

I

Z=3 км

Zi=2 км.

Z=3+2=5 км.

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

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

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

D

B

7

C

1

Z=0+1 км.

3

5

3

T

1

S

Z=0 км.

6

45

.

1

3

5

F

3

I

H

Z=0+3 км.

.

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

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

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

D

B

7

C

1

Z=0+1 км.

3

5

3

T

1

S

Z=0 км.

6

45

.

1

3

5

Zi= =min(5+zh,1+zd)= 1+1=2 км.

F

3

I

H

Z=0+3 км.

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

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

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

Z=3+3=6

Z=7 км.

D

B

7

C

1

Z=0+1 км.

3

5

3

T

1

S

Z=0 км.

6

45

.

1

3

5

F

3

I

H

Z=0+3 км.

Z=2+3=5 км.

Zi=min(5+zh,1+zd)=1+1=2 км.

41 Ответ:кратч

Ответ:кратч

путь –…

Найти самый короткий маршрут

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

Z=7 км.

D

B

7

C

1

Z=0+1 км.

3

5

3

T

1

S

Z=0 км.

6

45

Z=10 км.

1

3

5

F

3

I

H

Z=0+3 км.

Z=3+3=6 км.

Zi=min(5+zh,1+zd)=1+1=2 км.

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

Найти самый короткий маршрут

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

Z=7 км.

D

B

7

C

1

Z=0+1 км.

3

5

3

T

1

S

Z=0 км.

6

45

Z=10 км.

1

3

5

F

3

I

H

Z=0+3 км.

Z=3+3=6 км.

Zi=min(5+zh,1+zd)=1+1=2 км.

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

43 Самый безопасный маршрут

Самый безопасный маршрут

..

Вероятность не заплатить штраф

Вероятность не заплатить штраф на маршруте

?max

?max

?min

Минус логарифмы

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

Инверсия

44 Сетевое планирование

Сетевое планирование

Задача планирования проекта

Построение кратчайшего пути

45 Спу:

Спу:

Отделка

Стены

Котл

Фунд

Проект 1

Сарай

Проект 2

Дом

Баня

~«Душ»

46 Строительство дома

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

Остекление

Кладка вн стен

В обычном проекте от 15 000 до 40 000 работ

Черн. отделка

Монол(несущие) стены

Крыша

Чистовая отделка

Фунд

Подвод коммуникаций

F

S

Школа

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

d

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

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

Тп=193-16

Тп=130-72

Тп=177

H

L

Тр=40

58

Тр=93

30

72

13

40

16

Тп=193

Тп=0 Тп=60-60

D

F

Тр=80

I

Тр=193

Тр=109

80

15

84

Тп=109-15 =94

Тр=0

M

Тп=109

60

49

63

Тр=60

Тр=112

V

35

Тп=130

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

C

Тп=109-49 Тп=60

Ответ:

d

48 Задача

Задача

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

d

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

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

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

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

Ищем

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

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

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

Ищем

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

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

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

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

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

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

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

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

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

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

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

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

Итог в каждой вершине время и управление

Подробно:...

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

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

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

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

A

Тр=17

10 мес.

Тр=???

B

17 мес.

7 мес.

20 мес.

24 мес.

Тр

Тр=0

Тп=120

120 мес.

S

F

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

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

A

Тр=17

10 мес.

Тр=27

B

17 мес.

7 мес.

20 мес.

24 мес.

Тр

Тр=0

Тп=120

120 мес.

S

F

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

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

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

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

Критический путь: ST

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

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

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

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

65 A

A

B

TпН=96мес TрН=17мес

Rсоб=27-96-10=-79

Tпок=113мес tрок=27мес

Rпоз=113-96-10

Rполн=113-17-10

Rран=27-17-10

На каждой работе вычислить запасы

10 мес.

A

Тр=17

10 мес.

Тп=96

B

Тр=27

Тп=113

17 мес.

7 мес.

20 мес.

24 мес.

Тр=0

Тр=120

F

120 мес.

S

Тп=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 мес.

67 Крит

Крит

Путь.

H

L

30

72

13

40

16

D

F

I

80

15

84

Тр=0

M

60

49

63

V

35

C

68 Тп=130-72

Тп=130-72

58

Тп=193-16

Тп=177

H

L

Тр=40

Тр=93

30

72

13

40

16

Тп=193

Тп=0 Тп=60-60

D

F

Тр=80

I

Тр=109

80

15

84

Тр=193

Тп=109-15 =94

Тр=0

M

Тп=109

60

49

63

Тр=60

Тр=112

V

35

Тп=130

C

Тп=109-49 Тп=60

Ответ:

Критческий путь.

ICDF

Его длина 193 месяца

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*возраст

s,t

Возраст

s+1,0

s+1,t+1

S, время

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

t

600(t+1)

Старение

Продажа

600*1-4000*2t

+4000t

Покупкаt

71 Крит

Крит

Путь.

Тр=40+0

H

L

30

72

13

40

16

D

F

Тр=80+0

I

80

15

84

Тр=0

M

60

49

63

Тр=60+0

V

35

C

72 Крит

Крит

Путь.

Тр=80+13=max(TpM+ML;TpH+HL)

Тр=40

H

L

30

Тр=93

72

13

40

Тр=49+60=max(TpM+MD;TpC+CD)

16

D

F

Тр=80

I

80

15

84

Тр=109

Тр=193

Тр=0

M

60

49

63

Тр=60

Тр=112

V

35

C

Тр=40+72=max(TpH+HV;TpC+CV)

73 Крит

Крит

Путь.

Тр=93=max(TpM+ML;TpH+HL)

Тр=40+0

H

L

30

72

13

40

Тр=109=max(TpM+MD;TpC+CD)

16

D

F

Тр=80+0

I

Тр=109+84=193= =max (TpL+LF; TpD+DF; TpV+VF) Тр=193

80

15

84

Тр=0

M

60

49

63

Тр=60+0

V

35

C

Тр=40+72=max(TpH+HV;TpC+CV)

74 Крит

Крит

Путь.

H

L

30

72

13

40

16

D

F

I

80

15

84

Тр=0

M

60

49

63

V

35

C

75 Вероятностное дин

Вероятностное дин

программирование

76 Решение:

Решение:

77 Пример:

Пример:

Забега вперёд

78 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
79 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
80 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
81 Ответ

Ответ

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

Система массового обслуживания

Стационарные маркоские цепи.

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

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

84 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
85 Формула Литтла для связи объёма и скорости обновления людей

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

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

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

87 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
88 Задача управления ресурсами, двойственная задача

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

..

Симплекс и граф. Методы.

89 Транспортная задача

Транспортная задача

М-метод и

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

90 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
91 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
92 Метод Северо-Западного угла

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

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

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

94 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
95 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
96 Тамбов 50(c+a)

Тамбов 50(c+a)

Тверь 200a

Томск 140(c+b)

Мкв 100a

11a

10

60

СПб 140b

6d

20c

10a

Ввост 190c

5a

3b

8c

Ростов 150a

20

5(d+c)

5(a+c+d)

97 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
98 Владивосток 25

Владивосток 25

СПб 30

Москва 20

10 x11

0,5 x12

Хабаровск 35

4 x21

12 x22

99 Владивосток 25 (5)

Владивосток 25 (5)

СПб 30

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35

4 x21

12 x22

100 Владивосток 25 (5) (0)

Владивосток 25 (5) (0)

СПб 30

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)

4 x21=5

12 x22

101 Владивосток 25 (5) (0)

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22=30

102 Базисный план построен

Базисный план построен

!!

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22 =30

103 Тамбов 200

Тамбов 200

Тверь 300

Томск 120

М 100

11a

10

60

СПб 120

6d

20c

10a

Ввост 240

5a

3b

8c

Ростов 160

20

5(d+c)

5(a+c+d)

104 Суммарные издержки

Суммарные издержки

Терминалы //потребители

Тамбов 200

Тверь 300

Томск 120

М 100

СПб 120

Ввост 240

Ростов 160

Склады(поставщики)

Источник

Сток

Столбцы

Строки

Потребители

11a

10

60

6d

20c

10a

5a

3b

8c

20

5(d+c)

5(a+c+d)

105 Транспортная задача

Транспортная задача

Метод с.западного Угла

Тамбов 200

Тверь 300

Томск 120

М 100

Мin(100,200)=100

СПб 120

Мin(120,100)=100

Мin(20,300)=20

Мin(240,280)=240

ВлВосток 240

Мin(120,120)=120

Ростов 160

Мin(160,40)=240

106 Транспортная задача

Транспортная задача

Метод минимального элемента

Тамбов 200

Тверь 300

Томск 120

80

140

20

М 100

3

10

8

Мin(100,80)=80

Мin(20, 20)=20

20

СПб 120

1

5

9

Мin(120,200)=120

120

Мin(240,120)=120

ВлВосток 240

11

7

6

Мin(120,140)=120

Ростов 160

12

2

10

Мin(160,300)=160

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

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

Транспортная задача

Таможня

Вывозные пошлины

Новые тарифы

Ввозные пошлины

Тамбов 200

Тверь 300

Томск 120

М 100

3

10

8

x11=80

x12= 20

СПб 120

1

5

9

x21= 120

x33= 120

ВлВосток 240

11

7

6

x32= 120

Ростов 160

12

2

10

x43= 160

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

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

Транспортная задача

Таможня

Новые тарифы

Тамбов 200

Тверь 300

Томск 120

М 100

0

0

-1

x11=80

x12= 20 .

СПб 120

0

-2

3

x21= 120 .

x33= 120

ВлВосток 240

11

0

0

x32= 120

Ростов 160

17

0

9

x43= 160

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

109 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
110 Для каждой базисной переменной существует ровно один означенный цикл

Для каждой базисной переменной существует ровно один означенный цикл

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

«Теорема».

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

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

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

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

Транспортная задача

Таможня

Тамбов 200

Тверь 300

Томск 120

М 100

0

0

-1

x11=100

СПб 120

0

-2

3

x21= 100

x22= 20

x32= 120

x33= 120

ВлВосток 240

11

0

0

Ростов 160

17

0

9

x43= 160

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

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

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

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

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

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22

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

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

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22

Уменьшаем целевую функцию до бесконечности?

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

115 Лучше возможно

Лучше возможно

!: Двойственная задача и метод потенциалов

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22

Уменьшаем целевую функцию до бесконечности?

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

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

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

Уменьшаем целевую функцию до бесконечности?

117 Лучше возможно

Лучше возможно

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

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

0 x11=20

-11,5 X12

Хабаровск 35 (30)(0)

0 x21=5

0 x22=30

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

118 Лучше возможно

Лучше возможно

!: Двойственная задача и метод потенциалов

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22

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

119 Лучше возможно

Лучше возможно

!: Двойственная задача и метод потенциалов

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22

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

120 Лучше возможно

Лучше возможно

!: Двойственная задача и метод потенциалов

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22

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

121 Лучше возможно

Лучше возможно

!: потенциалы подобрали так v+u=0 на базисных переменных

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

10 x11=20

0,5 x12

Хабаровск 35 (30)(0)

4 x21=5

12 x22=30

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

122 Лучше возможно

Лучше возможно

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

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

0 x11=20

0,5-(8+4) X12

Хабаровск 35 (30)(0)

0 x21=5

0 x22=30

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

123 Лучше возможно

Лучше возможно

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

Владивосток 25 (5) (0)

СПб 30 (0)

Москва 20 (0)

0 x11=20

-11,5 X12

Хабаровск 35 (30)(0)

0 x21=5

0 x22=30

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

124 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
125 Задача определения кратчайшего пути

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

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

7

2

4

1

6

3

5

17

5

15

6

6

3

4

2

4

4

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

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

Алгоритм Дейкстры

127 Алгоритм Дейкстры

Алгоритм Дейкстры

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

128 b

b

0

129 Алгоритм Дейкстры

Алгоритм Дейкстры

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

130 Алгоритм Флойда

Алгоритм Флойда

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

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

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

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

131 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

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

132 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

5

0

23

0

100

S

F

0

17

10

2

11

A

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

b

0

133 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

5

11

12

0

89

S

F

11

17

21

2

0

A

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

134 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

5

11

12

0

89

S

F

11

17

21

2

0

A

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

135 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

5

11

12

0

89

S

F

11

17

21

2

0

A

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

136 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

5

11

02

0

89

S

F

11

17

21

2

0

A

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

137 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

5

11

12

0

89

S

F

11

17

21

2

0

A

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

138 Алгоритм Дейкстры

Алгоритм Дейкстры

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

Путей нет

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

B

16

0

12

5

84

S

F

11

17

21

2

0

A

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

139 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

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

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

B

5

0

23

0

100

F

S

0

17

10

2

11

A

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

Матрица потков

Ответ:

B

0

5-0

23-12

0

100-84

S

F

11

0

0

Fmax=16

0

11-0

A

b

Максимальная пропускная способность сети

0

140 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

B

16

0

02

5

84

S

F

11

17

21

2

0

A

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

141 Алгоритм Дейкстры

Алгоритм Дейкстры

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

fSB=16= 11+5 Fsa=0 fBS=11+0 fBF=5 +0 fAF=11 +0

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

Вариант2:

B

16

0

12

5

84

S

F

11

17

21

2

0

A

F.=F1+f2=5+11=16 =поток

142 Алгоритм Дейкстры

Алгоритм Дейкстры

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

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

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

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

143 Транспортная задача

Транспортная задача

М-метод и

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

144 Задача коммивояжёра

Задача коммивояжёра

Ветвей и границ или поиск с усечением

145 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
146 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
147 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
148 Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
«Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ»
http://900igr.net/prezentacija/pedagogika/vvedenie-v-issledovanie-operatsij-173505.html
cсылка на страницу
Урок

Педагогика

135 тем
Слайды
900igr.net > Презентации по педагогике > Исследование > Введение в ИССЛЕДОВАНИЕ ОПЕРАЦИЙ