Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 46
Текст из файла (страница 46)
б единиц б долл.',е еч»»» Оптовая база б Спрос = З единиц 4. Следукицую транспортную задачу сформулировать и решить как ыиркуляцнонную. 282 Глава 8 б. Для изображенной ниже сети сформулировать прямую и двойствеи: иую задачи и записать условия дополняющей нежесткости. Исходные данные Переменные Стоимость = с; У;" >0 Нижняя граница = А(1 Верхняя граница = у, 6.
Рассмотреть заданную ниже сеть. Используя программу, реализую. щую алгоритм дефекта, решить следующие задачи: Нижняя Стоимость единицы граница потока, долл. Верхняя граница Дуга а. Найти цепь из узла 1 в увел 11, имеющую минимальную стоимость. б. Найти потоки по дугам, обеспечивающие доставку 50 единиц потока в узел 11. в. Найти максимальный поток, который может протекать из узлов 1 и 2 в узел 11. (1, 3) (1, 4) (2, 4) (2, 5) (3, 4) (3, 7) (4, б) (4, 7) (4, 8) (5, 4) (5, 8) (б, 9) (б, 10) (7, 10) (8, 10) (9,11) . (10, 11) 20 15 17 32 41 27 1б 19 23 29 31 14 19 28 34 29 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12 8 13 9 1О 15' 0 7 9 11 5 7 10 8 14 12 11 ййз Алгоритм дефекта 7.
Используя алгоритм дефекта, найти кратчайший остов нзображеяной анже неорнентнрованной сети, Параметр каждой дугя равен стоимости едшшцы потока. 3. Для нзображенной ниже сети найти кратчайший древовидный остов с корнем в узле 1 (см. определения, данные в гл. 1). й. Рассмотреть заданную ниже сеть Используя программу, реалваую- ацую алгоритм дефекта, решить следующие задачи: Глава 3 Стоимость ед. потока долл. Верхняя граница Нижняя граница Дуга Нижняя граница Стоимость единицы потока Верхняя граница Дуга а. Найти циркуляцию мнннмальной стонмостн нз узлов 1 я 3 в узел У.
б. Найти величину максямального потока минимальной стоимости нв. узлов 1, 2 н 3 в узел 9. (1, 4) (1, 5) (2, 4) (2, 5) (3, 4) (3, 5) (4, 5) (5, 4) (4, 6) (4, 7) (4, 8) (5, 6) (5, 7) (5, 8) (б, 7) (7, 6) (7, 8) (8, 7) (6, 9) (7, 9) (8, 9) 95 86 91 78 98 77 81 86 90 79 96 77 95 84 82 79 91 85 84 80 93 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 29 37 31 46 29 31 47 45 53 29 37 41 36 .30 29 43 27 31 30 29 43 69 68 64 Алгоритм дефекта 1О. Какой результат будет получен при использовании алгоритма дефекта, если стоимости дуг отрицательны? 11. При работе алгоритма дефекта в качестве начального можно выбирать любое (допустимое или недопустимое) решение, удовлетворяющее условию сохранения потока.
Какой выигрыш будет получен, если в качестве начального использовать допустимое решение? Сформулировать все условия дополняющей нежесткости. 12. В чем различие между кратчайшим остовом и деревом кратчайших цепей? Между деревом кратчайших цепей н кратчайшим древовидным остовом? !8. В изображенной ниже сети найти дерево кратчайших цепей и сравнить его с кратчашнм остовом. Грузовики, принадпежвщие фирме А!ато 1 2 3 4 Грузоподьемность 15 12 13 16 Для выполнения заказа фирма А!апю может арендовать у фирмы П!!бег !!еп(-А-Тгпсй еще три грузовика, имеющие следующую грузоподьемпость (в т) . Грузовики, при— надлежащие фирме 6йбег Веп! — А — ТгасН ! 2 3 Грузоподьвмность Т 8 6 Эксплуатационные расходы для каждого грузовика следующие 1 2 3 4 25 3! 22 30 44 48 4! А!ашо а!)бвг 14. Сформулировать задачу о поставщике (равд.
2.!6) как (а) обычную потоковую задачу и (б) транспортную задачу, для решения которой может быть использован алгоритм дефекта. 15. Решить упражнение 51 гл. 2, яспользуя алгоритм дефекта. 18. Решить упражнение 52 гл. 2, используя алгоритм дефекта. 17. Фирма А!ашо получила заказ на кирпич, производимый на ее заводе в Сан-Антонио, шт. Техас. Заказ должен быть выполнен в ближайшяе 24 ч, а время на выполнение одного рейса до заказчика н обратно составляет 8 ч Фирма располагает четырьмя грузовиками, имеющнмн следующую грузоподь емность (в т)л Глава 8 Всего было заказано 200 т кирпича.
а. Определять допустпмую схему перевозкн, мнннмнзнрующую суммарные расходы. б, Чему равно максимальное количество кирпича, которое можно перевезтн за 3 дня? в. Заказчик потребовал доставить ему не 200, а 300 т кнрпнча. Фирма .А!алло может приобрести кирпич стоимостью 52 долл. за 10 т у завода Е!о Огапйе Вг!с!г Гас!огу. Определить для данного случая схему перевозки, .имеющую мнннмальную стоимость. 18. Тап8!ей %еЬ Ргойос!!оп Соглрапу владеет тремя компаниями, каждая вз которых может поставлять товар в четыре различных пункта сбыта. Издержкн производства нелннейные, но могут быть вычнслены.
Макснмальпая производительность каждого нз трех пунктов производства равна 25 еднннцам. В табл. 1 даны предельные н общие переменные нздержкн пронзводства. В табл. 2 даны затраты на транспортировку еднннцы товара нз каждо- Таблица!. ПРЕДЕЛЬНЫЕ ИЗДЕРЖКИ ПРОИЗВОДСТВА Пункт производства ! Пункт производства И Пункт производства ЕЛ уровень Предель- Общие Предель- Общие Предель- Общие лроизвод- ные перемен. ные перемен. ные перемен.
,ства издержки издержки издержки издержки издержки издержки 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 50 51 51 52 52 53 54 55 57 58 60 61 62 .64 65 66 67 68 69 70 72 75 80 100 120 50 101 152 204 256 304 363 418 475 533 593 654 716 780 845 911 978 1046 1115 1185 1257 1352 1412 1512 1632 60 60 60 60 61 61 62 62 62 63 63 64 64 64 64 65 65 66 66 67 67 67 69 70 80 60 120 180 240 301 362 424 486 548 611 674 738 802 866 930 995 1060 1126 1192 1259 1326 1393 1462 1532 1612 54 54 55 55 56 56 57 57 58 58 58 59 60 61 62 63 63 64 64 65 65 66 66 67 70 54 108 163 2!8 274 330 387 444 502 560 618 677 737 798 860 923 986 1050 11!4 1179 1244 1310 1376 1443 1513 Алгоритм дефекта Таблица 2. МАТРИЦА ЗАТРАТ НА ТРАНСПОРТИРОВКУ Таблица 3. СПРОС ПУНКТОВ СБЫТА го пункта производства в каждый пункт сбыта.
В табл. 3 даны величины спроса каждого из четырех секторов потребления. Найти оптимальный (минимизирующий общие затраты) план производства и перевозок. 19. АВС Сошрп1ег Сошрапу располагает 1О программамн, с помощью которых может быть решена задача.
Требуется получить выход программы 10, на вход которой может поступать выход программы 8 или программы 9. В первом случае время работы программы 1О равно 3 с, в во втором — 8 с. Точно так же на вход программ 8 и 9 и всех остальных программ поступает выход некоторой другой программы.
Задача заключается в определении набора программ, в результате работы которых будут получены требуемые результаты за минимальное время. На изображенной ниже сетевой диаграмме указаны отношения предшествования и время работы каждой программы, на вход которой должен поступать выход любой иъ предшествующих ей программ. Найти последовательность выполнения программ, минимизирующую общее время выполнения.
29. Решить упражнение 51 гл. 2, предполагая, что возможны следующим перевозки. Элементы таблицы равны затратам в сотнях долл. Глава 3 21. Решить упражнение 35 гл. 2, используя программу, реалнзуюспую алгоритм дефекта, и сравнить время ее работы со временем работы прохраммы, реализующей алгоритм Дейкстры. 22. Решить упражнення 28а, б гл. 2, используя алгоритм дефекта. 23. Решить упражнение 29а гл. 2, используя алгоритм дефекта. 24. Решить упражнение 21а гл.
2, используя алгоритм дефекта, н сравнять полученный результат с результатом работы алгорнтма, данного в гл. 2. Смоглн бы вы еще решить задачи б н в? ЛИТЕРАТУРА 1. $?игЫп Е. Р., ТЬе ОШ-о1-КРИег А!яогИЬсп: А Рг!щег, $(апб СогрогаПоп, 8ап!а Моп!св, Са1Иогп!а, $?есещЬег 1967. .2. Рогб 1.. К., Рийсегзоп О. К., Махйпа! Р1окг !ЬгоиПЬ а Ме!мог1с, Салос(сал Гоигла! о) МаЯепииссз (Аннов! 1956). ;3.
Рогб 1.. И., Рийсегвоп О. Е., Р1омз !п Хе!мог1св, Рппсе1оп ОпгчехвИу Ргевв, Рппсе!оп, Х. 3., 1962, [Имеется перевод: Форд Л. Р., Фалкерсон Д. Потоки в сетях. — Мл Мир, 1966.) 4. Рпйсегвоп О. И., ТЬе ОШ-о1-ХсИег Ме!Ьод 1ог М!пипа! Соз1 Р!ом РгоЫещз, уоигла! о( Арруеа Ма!бегло!сев, 9 (1) (Магсп!961). 5. депвеп Р. А., Вагпев сч'., Хе!могй Р1очг Ргойгащщ!пй, Тч'Псу, 1пс., Хеиг Уог1сс 1979. 6. РЬП!!рв О. Т., 3епвеп Р.
А., Ме!счог1с Р1ои Ор1ипйа1!оп чЛй 1Ье Ои(-о1-КП1ег А(Пот!!Ьщ, Раг1 1 — ТЬеогу, Иевеагсй Мепзогапбшп 71-2, РеЬгиагу 1971. 7. РЫИ!рв $?. Т., Лепвеп Р. А., Хе) жог1с Р!осч Ор!ппйаПоп тН!Ь йе ОЫ-о(-КП1ег А!йопйщ, Раж П вЂ” АррПса!!опв, $?езеагсЬ Мещогапбшп 71-3, Ригдие $)п!чегвйу, РеЬгиагу 1971. '8. РЬРП1рз О. Т., Зепзеп Р. А., Хее!мог)с Р1осч Апа!уюв: ТЬе С)и1-о$-КП!ег А!йог!йщ !лбов!г(а! Епй!пееппй (РеЬгиагу 1974). РогПопв гергобисеб Ьу регппвыоп о1 !Ье аи1Ьогз апб йе Ащег!сап 1пв!ИЫе о1 1пдиз!г!а! Епй!пеегв. '9. РЫП!рв О.
Т., Иач!пдгап А,, 8о!Ьегй 3. 3., ОрегаИопв ИевеагсЬ: Рг!пс!р!ев апд Ргас11се, %Псу, 1пс., Месч с'ог)с, 1977. 30. 8аЬа 3. 1., Ап А!Пот!0ип 1ог Виз 8сЬебиПпй РгоЫешв, ОрегаМола! Яевеагсй Яиаггег!у, 2! (4) (ОесешЬег 1970). .'11. 8игапвоп Н. 8., %оо!веу И. Е. О., НППв Н., Ов!пй !Ье ОШ-о$-К(Иег А!йопПип, $лс(аз?гса! Елу!леег(лу (МагсЬ 1974). РогПопв гергобисед Ьу регпиввшп о$ йе аийогв апб !Ье Апсегкап 1пз!ИЫе о1 1пбив!г!а1 Епй!песта. '12.
8мапзоп Н. 8., Ъоо!веу П. Е. Е., Ап Ои1-о1-К1Иег Ме(счог1с Ти1опа1, 8?ОМАР (чеьчв(е?$ег (Запиагу 1973). 33. 'ча1ба, МайегпаПса! Ргойгаппп!пя, Абб!воп-Жев1еу РиЫ. Со., 1пс., Ееаб!пй, Маза., 1961. Глава 4 МЕТОДЫ УПРАВЛЕНИЯ ПРОЕКТАМИ Я был бы рад стать лучше, — сказал он, — но не знаю, как этого добиться.
Что ыне нужно делать? К. Джексон, Б. Джексон. Толстый неуклюжий слоненок Нам, находясь в положении «толстого неуклюжего слоненка», стоит задуматься, как существенно повысить эффективность вычислений, используя специфику определенного класса задач о потоках в сетях. Такое повышение эффективности может быть достигнуто атри использовании сетевых моделей для изображения крупных строительных или конструкторских проектов и управления ими. При управлении проектами с помощью МКП (метод критического пути) или ПЕРТ (метод оценки и пересмотра планов) и при календарном, планировании работ применяются специальные способы, изображения сетей. В частности, при этом используются ориентированные дуги и бесконтурные сети.
Благодаря такой специальной структуре были разработаны очень эффективные и простые процедуры вычислений для получения важной информации о состоянии проекта. Эти специальные методы и связанные с ними задачи управления затратами и ресурсами и составляют основное содержание этой главы, которая посвящена не только тому, «как этого добиться», но и, когда определен класс задач, тому, «что нужно делать». Глава разбита на три части. Часть 1 посвящена схематическому изображению, построению сетевых моделей и процедурам вычислений, используемым при анализе с помощью МКП и ПЕРТ. В части П обсуждаются вопросы управления ресурсами и затратами с помощью сетевых методов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
