Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 42
Текст из файла (страница 42)
3.1$. ЗАДАЧА О ПЕРЕВОЗКАХ Рассмотрим систему, в которой имеется гп складов и и магазинов. Предложение 1-го склада равно аг (1 1, 2, ..., лг), а спрос 1'-го магазина равен Ь| (1=1, 2, ..., п). Из каждого склада товар может быть перевезен в любой магазин либо непосредственно, либо по дополнительным маршрутам, включающим промежуточные склады. Кроме того, товар можно перевозить вначале нз одного склада в другой, а затем — в магазин.
На первый взгляд может показаться, что данная задача решается непосредственно с помощью алгоритма решения транспортной задачи. Однако е этом случае величины «предложения» и «опроса» каждого магазина были бы равны нулю и, следовательно, никакие перевозки не были бы возможны 161. Кроме того, возможно, что стоимость транспортировки 1 единицы товара из 1-го источника в /-й магазин ие равна стоимости транспортировки 1 единицы товцра из )чго магазина в (-й источник, что имеет место, например, прн перевозках по улицам с односторонним движением. Для решения первой задачи выберем достаточно большое число О, которое превосходило бы объем всех возможных перевозок, и прибавим его ко всем величинам первоначальных цредложений и спросов. Как было показано в разд. 2.11, наиболее ш л разумно выбрать в качестве 0 величину тп)п(Е аь Е ЬД. Соотг-~ 1-~ ветствующие затраты на транспортировку должны определяться мз существующих условий экономического характера и постановки задачи.
17 — 1654 Глава 8 Рассмотрим задачу о перевозках с двумя источниками снабжения и двумя магазинами. Матрица стоимостей задается следующим образом: о! в! Я! в2 Спрос О2 Предложение В матрице О=ш(и[Ха!, ХЬ!1 =пни[9, 91 =9. Данная задача о перевозках свелась к классической транспортной задаче, которая может быть решена с помощью алгоритма дефекта так, как описывалось выше. Следует отметить„ Ш л что в рассмотренном примере (а) л!=а и (б) Е а!= Е Ьь одна- ! ! ! ко в общем случае это не так. Если не выполнено условие (а), то это просто означает, что матрица стоимостей не будет квадратной.
Если не выполнено условие (б), то для существования О$ е решения должно выполняться нера!венство Е а!) Е Ьь Отме- ! ! ! тим, что вводить фиктивный пункт назначения нет необходимости. Нужно только приписать возвратной дуге метку (Х[Ь7+Е~, Х[Ь,+91, О). ! ! 3.!7. НЕЛИНЕЙНЪ|Е СТОИМОСТИ Некоторые задачи с нелинейными стоимостями дуг могут быть решены с помощью алгоритма дефекта посредством кусочно-линейной аппроксимации. На рис. 3.14 изображена выпуклая нелинейная функция стоимости дуги (х, у) и аппроксимирующая ее кусочно-линейная функция.
Линеаризованной функции стоимости в сети соответствуют три дуги (1), (2), (3) (рис. 3.15), ведущие из х в у. Поскольку исходная функция стоимости выпуклая, то величины наклонов отрезков прямых удовлетворяют соотношению а!(ав(а,. Таким образом, при увеличении потока, протекающего из х в у. вначале он приписывается дуге (1). После насыщения дуги (1~ Алеорнтм де енто поток прнннсывается дуге (2). А после насыщения дуги (2) поток прнпнсывается дуге (3). Результирующей кривой стоимости потока является ломаная линия, изображенная на рнс. 3.14.
Если функция стонмостн потока является вогнутой (рнс. 3.16), то исходная сеть не может быть аппрокснмнрована О, ое ое Суммарный поток по дуге Рнс. 3.14. Нелинейные стоимости. лннейной сетью н, следовательно, в этом случае нельзя воспользоваться алгоритмом дефекта. Это является основным ограниченнем алгоритма дефекта. Для изучения моделей с вогнутыми 1и,.О.и,) Суммарный поток по дне Рис. 3.15. Сетевая интерпретация Рис. 3.16.
Вогнутая нелинейная функнусочно-линейной аппроксимация. пвя стоимости. функцнямн стоимостей потоков читателю предлагается обратнться к работе йенсена н Барнеса.[51. В качестве последнего примера, иллюстрирующего применение алгоритма дефекта, будет рассмотрена н решена следую щая задача производственного вланнровання [8).
1т Ю л ик о с *м Х о Ь о и о о я и о л с м ит Ю и о а о 'л л о с о о с с Ю т а о о с '" о Ебб Глава 3 3.18. ЗАДАЧА ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ (ФИЛЛИПС И ВЕНСЕН) Компания, изготавливающая стулья, владеет четырьмя фабриками, расположенными в различных городах страны. Стоимость изготовления одного стула, не считая стоимости древесины, а также минимальная и максимальная месячные выработки даны в табл. 3.6. Для изготовления одного стула требуется 20 фунтов древесины.
Компания получает древесину у двух поста~вщиков, каждый из которых может продавать ее в любом количестве. Однако по условию контракта фирма должна закупать Таблица З.б. Стоимости продукции и уровни производства Фабрика Стоимость производ- Максимальная Минимальная стев одного ступа производительность производитель. (вопло ность 500 750 1000 250 0 400 '500 250 5 7 3 .4 1 2 3 4 у каждого поставщика не менее 8 т древесины. Стоимости древесины следующие: Поставщик 1: 10 цент/фунт, Поставщик 2: 7,6 цент/фунт. Затраты (в центах) на транспортировку одного фунта древесины от поставщиков на фабрики задаются следующей таблицейс Фабрика 1 2 3 4 Источник поставки 1 1 2 4 4 древесины 2 4 3 2 2 Стулья продаются главным образом в четырех городах: Нью-Р)орке, Чикаго, Саи-Франциско и Остине.
Затраты (в долларах на стул) на транспортировку стульев с фабрики в.зти города приводятся в следующей таблице: Город. н-Й о с.Ф ч Фабрика 2 3 2Е| Алгоритм дефакто Таблица 8.7. Ланпае о цепах и спросе Максимапьныа с и рос Минимапьныи спрос Продажная цена(депп) город 2000 400 1500 1500 500 100 500 500 Нью.йорк Остин Сан.Франциско Чикаго 20 15 20 18 В табл. 3.7 приводятся максимальный и минимальный спрос, а также цена одного стула в указанных городах. С помощью алгоритма дефекта мы определим: 1. где следует закупать древесину каждой фабрике; 2.
сколько стульев следует изготавливать каждой фабрике; 3. сколько стульев следует продавать в каждом городе; 4. куда следует каждой фабрике отправлять свою продукцию. На рис. 3.17 изображена сеть для данной задачи, предназначенная для работы алгоритма дефекта. Метки, приписанные дугам сети, выписаны в табл. 3.8. Отметим, что все стоимости задаются в центах на стул, а верхние и нижние границы— в стульях.
Оптимальное (имеющее минимальную стоимость) решение данной задачи, полученное с помощью алгоритма дефекта, дается в табл. 3.9. Теперь на поставленные выше вопросы можно дать ответы в терминах искомых переменных )н. 1, Где следует закупать древесину каждой фабрике? а. Фабрика 1 должна закупать древесину для 500 стульев (т. е. 10000 фунтов) у гпоставщика 1 и для 0 стульев (т.
е. 0 фунтов) у поставщика 2. б. Фабрика 2 должна закупать древесину для 300 стульев (т. е. 6000 фунтов) у гпоставщика 1 и для 450 стульев (т. е. 9000 фунтов) у поставщика 2. в. Фабрика 3 должна закупать древесину для 0 стульев (т. е. 0 фунтов) у поставщика 1 и для 1000 стульев (т. е. 20000 фунтов) у поставщика 2. г. Фабрика 4 должна закупать древесину для 0 стульев (т. е. 0 фунтов) у поставщика 1 и для 250 стульев (т. е. 5000 фунтов) у поставщика 2. 2. Сколько стульев следует изготавливать каждой фабрике? а.
Фабрика 1 должна изготавливать 500 стульев. б. Фабрика 2 должна изготавливать 750 стульев. в. Фабрика 3 должна изготавливать 1000 стульев. г. Фабрика 4 должна изготавливать 250 стульев. 3. Сколько стульев следует продавать в каждом городе? 'о о о о о о о О~ / о 00 л с е Ц о е а е е о о о е а Х х о. о Б л о *к Я л х оо Г оо р. о о, о оо о о г Ол О 0' о О О О 1 О О О О „о о О Е ООО о -,0" Ф Ъ ОО Л О. ч' 0. д 0 о У 00' 00' 0. 0' 0.
00' О О О О О О й е х с о. о е в О О и О СЧ О О х О \ в о л л Ц Х о ц х о е о Й Я С~ о % х х 2 х' х а с е ц л е о е о е с а ~о, о о у оо ~00 500 ,000. О б~ О. Ф 0. ОО 00 ' 4 0 „со~ 0"" ~ч С .~00 'оо о оо Ц О х д в О О о о 'о о, О. ~оо о., " о г О д О О О. о о О ~о ., о. О ОО4 оо, с~с 'о оу. х СЧ <,Р Е Д' Х е З ф 000' 500' С а о 3с Б о л о. Ф о х е олх л д с с о о с Ц Ц О с е Ф О 'л О л О Ц О о е е с о О Ц е е е л с х л е х л е с е е о 263. Алгоритм дгФгита Таблица 3.8. Характеристики дуг сети ерхняя В узел граница Нижняя граница Стоимость Из узла Дуга Число узлов равно 18 Число дуг равно 36 В рассматриваемом примере потоки по дугам 1 — 10 и 38 не ограничены сверху. Дле удобства соответствуюцие верхние границы полагаются равными произвольному д, статочио Оольиому числу.
Теоретически зти величины равны + и. 1 2 3 4 5 6 7 8 9 1О 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 1 1 2 2 2 2 3 3 3 3 4 5 б 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 13 14 15 16 2 3 4 5 б 7 4 5 6 7 8 9 10 11 '12 13 14 15 12 13 14 15 12 13 14 15 12 13 14 15 16 16 16 16 1 2500 2500 2500 2500 2500 2500 2500 2500 2500 2500 500 750 1000 250 500 500 500 500 750 750 750 750 1000 1000 1000 1000 250 250 250 250 2000 400 1500 1500 5400 800 800 0 0 0 0 0 О 0 0 0 400 500 250 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 500 100 500 500 1600 0 0 220 240 280 ,280 230 210 190 190 500 700 300 400 100 100 200 0 300 600 700 300 300 100 500 300 800 200 100 400 -2000 -1500 2000 1800 0 264 Глааа 8 Таблица 8.9. Оптимальное решение дуга (01) Дуга Р 7) а. В Нью-йорке надо продавать 1400 стульев. б.
В Остине надо продавать 100 стульев. в. В Сан-Франциско надо продавать 500 стульев. г. В Чикаго надо продавать 500 стульев. 4. Куда следует каждой фабрике отправлять свою продукцию? а. Фабрика 1 отправляет 500 стульев в Чикаго. б. Фабрика 2 отправляет 750 стульев в Нью-йорк.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
