Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
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)
31
Сеть нефтепроводов на море…
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
45
СПУ: фунд стены отделка котл проект 2 проект 1 Сарай дом баня ~«душ»
46
Строительство дома. Школа фунд Монол(несущие) стены Кладка вн стен крыша остекление Черн. отделка Подвод коммуникаций Чистовая отделка S F В обычном проекте от до работ Найти критический(максимальный) путь(на основе ранних времен наступления событий), при обратном проходе найти поздние времена наступления событий и запасы времени в каждом событии-вершине (как разность позднего и раннего времен). Для 1-2х не касающихся критиического пути (полностью некритических) работ выписать все запасы времени(полный, собственный, I и II рода). (а также коэффициенты напряженности работ). Изобразить линейную диаграмму проекта. b a+1 1K S BC AE T F G H I J L b 4 (b+d)/2 Короткий вариант d
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 F I H L M V C D Тр=0 Ответ: Тр=40 Тр=80 Тр=60 Тр=93 Тр=109 Тр=112 Тр=193 Тп=193 Тп=177 Тп= Тп=130 Тп=109 Тп= Тп= =94 Тп= Тп=60 Тп=0 Тп=60-60
48
Найти критический(максимальный) путь(на основе ранних времен наступления событий), при обратном проходе найти поздние времена наступления событий и запасы времени в каждом событии-вершине (как разность позднего и раннего времен). Для 1-2х не касающихся критиического пути (полностью некритических) работ выписать все запасы времени(полный, собственный, I и II рода). (а также коэффициенты напряженности работ). Изобразить линейную диаграмму проекта. b a+1 1K S BC AE T F G H I J L b 4 (b+d)/2 Задача Короткий вариант d
49
50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп=30 Тп=0 S F B Обсчитанный проект из 3х работ
50
50 мес. 17 мес.20 мес. Тр=0 Тр=??? Тр=? Тп=0 S F B Проект из 3х работ Искать не можем Ищем
51
50 мес. 17 мес.20 мес. Тр=0 Тр=17 Тп=0 S F B Проект из 3х работ Ищем
52
50 мес. 17 мес.20 мес. Тр=0 Тр=17 Тр=50 Тп= S F B Проект из 3х работ
53
50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп= 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 Тп=??? S F B Проект из 3х работ
56
50 мес. 17 мес.20 мес. Тр=0 Тп=50 Тр=17 Тр=50 Тп=30 Тп=0 S F B Проект из 3х работ
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 Тр=27 Тр=120 SF B A Рассчитать время и запасы
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
120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 SF B A Рассчитать время и запасы
62
120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=? Тп=?? F Теперь обратный проход Критический путь: ST
63
120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=113 Тп=? F Теперь обратный проход
64
120 мес. 17 мес. 20 мес. 10 мес. 24 мес. 7 мес. Тр=0 Тп=120 Тр=17 Тр=27 Тр=120 B A S Тп=113 Тп=96 F Теперь обратный проход
65
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 варианта пример :
66
Поздние времена последовательно вычисляются. Например, на первом шаге позднее время может быть вычислено для события В(и ни для какого другого), т.к. известно позднее время в точке 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 мес.
67
F I H L M V C D Тр=0 Крит. Путь.
68
F I H L M V C D Тр=0 Критческий путь. Ответ: ICDF Его длина 193 месяца Тр=40 Тр=80 Тр=60 Тр=93 Тр=109 Тр=112 Тр=193 Тп=193 Тп=177 Тп= Тп=130 Тп=109 Тп= Тп= =94 Тп= Тп=60 Тп=0 Тп=60-60
69
Замена оборудования Уст. Оборудование теряет в стоимости: 1й год стоимость 4000, послед года 2 р меньше 2й год – 2000р 3й год – 1000р 4й год -500 р и т.д. Издержки функ: 600р*число лет (время 5 лет) Граничное условие продажа оборудования продажа Ответ: эксплуатировать три года, потом заменить и не менять 2 года, прибыль р.
70
Замена оборудования Оборудование стоит 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 старение эксплуатация
71
F I H L M V C D Тр=0 Крит. Путь. Тр=40+0 Тр=80+0 Тр=60+0
72
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
73
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
74
F I H L M V C D Тр=0 Крит. Путь.
75
Вероятностное дин. программирование
76
Решение:
77
Пример: Забега вперёд
81
ответ
83
Система обслуживания с несколькими сервисами
85
Формула Литтла для связи объёма и скорости обновления людей
86
Среднее время в системе - …
92
Метод Северо-Западного угла
93
Переход по циклу
96
Тамбов 50(c+a) Тверь 200aТомск 140(c+b) Мкв 100a11a1060 СПб 140b 6d 20c10a Ввост 190c5a3b8c Ростов 150a 205(d+c)5(a+c+d)
98
Владивост ок 25 СПб 30 Москва x11 0,5 x12 Хабаровск 35 4 x21 12 x22
99
Владивост ок 25 (5) СПб 30 Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 4 x21 12 x22
100
Владивост ок 25 (5) (0) СПб 30 Москва 20 (0) 10 x11=20 0,5 x12 Хабаровск 35 (30) 4 x21=5 12 x22
101
Владивост ок 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Тверь 300Томск 120 М 10011a1060 СПб 1206d20c10a Ввост 2405a3b8c Ростов (d+c)5(a+c+d)
104
Тамбов 200Тверь 300Томск 120 М a1060 СПб 120 6d20c10a Ввост 240 5a3b8c Ростов (d+c)5(a+c+d) столбцы строки Склады(поставщики) Терминалы //потребители Суммарные издержки источник потребители сток
105
Транспортная задача Тамбов 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 Метод с.западного Угла
106
Транспортная задача Тамбов 200Тверь 300Томск 120 М СПб ВлВосток Ростов Мin(120,200)= 120 Мin(160,300)= 160 Мin(100,80)= 80 Мin(240,120)= 120 Мin(120,140)= 120 Мin(20, 20)= 20 Метод минимального элемента
107
Транспортная задача Тамбов 200Тверь 300Томск 120 М СПб ВлВосток Ростов x21= 120 x43= 160 x11=80 x33= 120 x32= 120 x12= 20 Метод Потенциалов таможня Вывозные пошлины Ввозные пошлины Новые тарифы
108
Транспортная задача Тамбов 200Тверь 300Томск 120 М СПб ВлВосток Ростов x21= 120. x43= 160 x11=80 x33= 120 x32= 120 x12= 20. Метод Потенциалов таможня Новые тарифы Берём минимальный (отрицательный элемент)
110
«Теорема». неё базисные переменные. Для каждой базисной переменной существует ровно один означенный цикл данного типа проходящий через неё и базисные переменные.
111
Транспортная задача Тамбов 200Тверь 300Томск 120 М СПб ВлВосток Ростов x21= 100 x43= 160 x11=100 x33= 120x32= 120 x22= 20 Метод Потенциалов таможня Рассчитаем новые тарифы Берём минимальный (отрицательный элемент) Данный план оптимален Отрицательных тарифов нет
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
Владивост ок 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 и не меняет предпочтения задачи Выбираем небазисную переменную
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
Владивост ок 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 на базисных переменных Выбираем небазисную переменную
122
Владивост ок 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 и не меняет предпочтения задачи Выбираем небазисную переменную
123
Владивост ок 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 и не меняет предпочтения задачи Выбираем небазисную переменную
125
Задача определения кратчайшего пути
128
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
130
Обратная пропускная способность Прямая пропускная способность Сводим задачу к предыдущей :
131
Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе SF 0 2 B A
132
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 Сводим задачу к предыдущей :
133
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A
134
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A
135
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A
136
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A
137
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A
138
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A Путей нет
139
Дана сеть, 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
140
SF Дана сеть, cij – пропускные способности маршрутов в каждом направлении Найти максимальный поток от источника S к стоку F на этом графе B A
141
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:
142
Обратная пропускная способность Прямая пропускная способность Сводим задачу к предыдущей :
Еще похожие презентации в нашем архиве:
