Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 45
Текст из файла (страница 45)
Дуга, ведущая из узла 1 в узел 2, соответствует периоду, в котором радиоприемники были приобретены. Дуги (2, 3), (3, 4) и (4, 5) соответствуют хранению радиоприемников на складе в месяцы 1, 2 и 3 соответственно. Дуги (2, 6), (3, 6), (4, 6) и (5, 6) соответствуют продаже радиоприемников в месяцы 1, 2, 3 и 4 соответственно. Как видно из исходных данных, рассматриваемая задача не является линейной и поэтому нельзя ожидать, что ее решение окажется простым.
Однако эта задача, так же как и аналогичные ей задачи, имеет отличительную особенность, заключающуюся в том, что оптимальный поток протекает по одной един.ственной цепи, т. е. все радиоприемники следует продать в один и тот же период, а до этого времени они должны храниться на складе. Таким образом, задача свелась к определению месяца, подходящего для продажи радиоприемников. Зная эту особен- Алгоритм дефекта 27Ь ность задачи, можно, использовать алгоритм дефекта для поиска оптимальной («максимальной») цепи в сети.
Оптимальное решение задачи следующее: все радиоприемники следует хранить. до 3-го месяца и затем продать их. Прибыль (в долл.) при этом составит 840= (40 — 20 — 1,2 — 2,0)50. Рис. 3.21. Сеть в задаче о продаже радиоприемников. 3.23. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ АЛГОРИТМ ДЕФЕКТА Назначение: нахождение оптимальных решений в различных потоковых задачах с сетями, имеющими ограниченную пропускную способность.
Могут быть решены следующие задачи: 1) транспортная задача; 2) задача о назначениях; 3) задача о максимальном аотоке; 4) задача о дереве кратчайших цепей;. 5) задача о перевозках; 6) задача о максимальном потоке минимальной стоимости. Локализация: под~программа ОКА(.О в пакете сетевой оптимизации. Ограничения: программа обрабатывает сети, содержащие до 500 узлов и 500 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме ОКА1.О и основной программе. Входные данные: Набор 1.
Одна карта с именем алгоритма ОКА(. в формате (А4). Набор 2. Одна карта с числом узлов н числом дуг в сети в формате (2110). Набор 3. Общее число карт в данном наборе равно числу дуг в сети. С каждой карты считываются следующие величины: 1) номер начального узла дуги; 2) номер конечного узла дуги; 3) верхняя граница потока по дуге; 4) нижняя граница потока по дуге; 5) стоимость прохождения единицы потока из начального узла дуги в конечный узел. Формат (215, 3Р10.2). Набор 4.
Данный набор состоит из одной карты, содержащей слово 'РЕ)ч11' в формате (А4), которая указывает конец задачи. Набор 5. Данный набор состоит нз одной карты, содержащей 13' слово 'ЕХ1Т' в формате (А4), которая указывает конец входных данных. Составные части программы. Программа состоит из следующих подпрограмм: ОКА(.О (ввод, вывод и вычисления); БЕТг10% (процедура расстановки пометок). Используемые переменные: 1 — начальный узел дуги, 3 — конечный узел дуги, Н1 — верхняя пропускная способность этой дуги, 1.0 — нижняя пропускная способность этой дуги, г1.0% — поток по этой дуге, Р1 †значен двойственных переменных, СОЗТ вЂ” стоимость прохождения единицы потока по этой дуге.
Используемый метод: данный алгоритм основан на методе, описанном в равд. 3.3 — 3.5. Литература; 161. .3.24. РЕКТИФИКАКИЯ И РАСПРЕДЕЛЕНИЕ НЕФТИ Три нефтеочистительных завода могут получать неочищенную нефть из двух месторождений, первое из которых расположено в заливе Аляска, а второе †Персидском заливе. Стоимость одного барреля нефти в этих месторождениях составляет 16,80 и 12,60 долл. соответственно (стоимость галлона — 0,40 и 0,30 долл.).
Из обоих месторождений нефть может поставляться в неогра|ниченном количестве, но не менее 300000 галлонов в .день. Производственная мощность и затраты .на ректнфикацию "одного галлона нефти для каждого из заводов указаны в табл. 3.13. Топливо 8.13. Стоимость ректификакии и производительность заводов Эти заводы должны снабжать нефтью четыре района.
В табл. 3.14 указаны затраты (в долл.) на транспортировку одного галлона ~нефти. В табл. 3.15 даны суточная потребность .в нефти каждого из районов и продажная цена одного галлона. Для максимизации своей прибыли нефтяная компания долж г о 4, о О. Я ! а О г ~Ь,. о О о ~У о- 3 У" о о о" Р~ 4. о о, 0 О о /~ л о о оо л о. о о о о о о о а а а .41 0 ф 'р' о~ % О о в' Б 8 о о Ю о с\ о 4'4 о Ъ \ 4 о о \ Ъ 'о о х К а к 4 о .р О Ф х.
с С 4- О Ф 4 с а Х 'Е 44 с Ф 4- 4М К О Ф а а у а О Ф Ф х г~ ф 4', О' 'Ъ) ~ Ф444 ~ОС'0 ,о, о. ф 'о. 44 % 44. с а Ф ' 4Е К Ф О 4С й а а а О а Ф с а 63 ой оа а \- Фа О О хс оа а а 4 а К 4 Х а Ь о ~ аа а Ф о Ф с й а 4 О о с Ф а с о о Х 4в О Ф й а о о ол о а и а Ф Ф О а а 44 Ф а Ф х Ф 4 о х О Ф Р Е 278 Глава 8 Таблица д14. Затраты на транспортировку на поставлять в указанные районы наиболее дешевую нефть при минимальных затратах на транспортировку.
Сетевая диаграмма изображена на рис. 3.22. Решение задачи, найденное с помощью программы, описанной в равд. 3.23, дается ниже. Решение, попученное с помощью алгоритма дефекта Краткии отчет Число уапоа = 14 щиспо дуг = 28 Н1 1.0 'Лчоток Стоимость, 9999999 300' 300 0 9999999 300 650 0 9999999 0 0 40 9999999 0 0 40 9999999 0 300 40 9999999 0 350 30 9999999 0 300 30. 9999999 0 0 ЗО 1250 200 350 3 1500 300 300 4- 1350 300 300 5 1250 0 200 5 1250 0 0 б 1250 0 150 б 1250 0 0 7 1500 0 50 6 1500 0 175 7 1500 0 25 7 1500 0 50 б !350 0 0 7 1350 0 0 б 1350 О 0 б 1350 0 300 5 250 200 250 — 84 175 90 175 — 69 175 100 175 — 64 350 200 350 — 74 9999999 О 950 0 М 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 1 1 1 2 1 3 2 4 2 5 2 6 3 4 3 5 3 б 4 7 5 8 б 9 7 10 7 11 7 12 7 13 8 10 8 11 8 12 8 13 9 10 9 11 9 12 9 13 ТО 14 11 14 12 14 13 14 14 1 Алгоритм дефекта Суммарные затраты на осуществление проекта = †295,00 Дуга 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 26 27 28 Узел 1 2 3 4 5 б 7 8 9 1О 11 12 13 14 Поток по дуге 300 650 0 О 300 350 300 0 350 300 300 200 0 150 0 50 175 25 50 0 .0 0 300 250 175 175 350 950 Узловое число Р! 47 37 47 77 77 77 80 79 80 85 86 86 85 47 Глава 3 Проверка точности м Н1 7.0 Поток Стоимость Отметим, что оптимальное решение имеет отрицательную стоимость.
Это означает, что при оптимальной организации процесса производства и распределения капитал будет увеличиваться (получение прибыли), поскольку затраты обозначались положительными числами, а продажные цены — отрицательными. Соответствующая 'оптимальная структура производства и распределения легко определяется из найденных потоков по дугам.
Таблица 815. Суточная потребность УПРАЖНЕНИЯ 1. Сформулировать перечисленные ниже задачи н построить для каждой из инх цнрпуляпионную модель: а1 транспортная задача (пять источников и четыре стока); 1 1 2 2 1 3 5 2 б 6 3 4 7 3 5 9 4 7 10 5 8 11 б 9 12 7 10 14 7 12 16 8 10 17 8 11 18 8 12 19 8 13 23 9 13 24 10 14 25 11 14 26 12 14 27 13 14 .
28 14 1 9999999 300 9999999 300 9999999 0 9999999 0 9999999 0 1250 200 1500 300 1350 300 1250 0 1250 0 1500 0 1500 0 1500 0 1500 0 1350 0 250 200 175 90 175 100 350 20( 9999999 0 300 650 300 350 300 350 300 300 200 150 50 175 25 50 300 250 175 175 350 950 0 0 40 30 30 3 4 5 5 6 6 7 7 б 5 — 84 — 69 — 64 — 74 0 Алгоритм дг екта б) задача о назначениях (трн источника и три стока); в) задача о максимальном потоке (в общем виде); г) задача о кратчайшей цепи (в общем виде); д) задача о дереве кратчайших цепей (сеть состоит из четырех узлов, каждый из которых соединен со всеми другими); е) задача о перевозках (четыре источника и четыре стока).
8. Модель производственного планирования. Фирма должна удовлетворять спрос на продукцию в течение трех периодов. В каждом периоде продукции может выпускаться в рабочее и в сверхурочное время. Заданы следуюпзие исходные данные: Стоимость производства единицы пРодукции Производительность (в единицах1 Ожидаемый Рабочее Сверхурочное Рабочее Сверхурочное спрос Период время время время время (в единицах) 100 20 14 18 60 100 1О 17' 22 80 60 20 17 22 140 Стоимость хранения единицы продукции на складе в течение одного периода равна 1 долл.
Уровень запасов в начале первого периода составляет !5 едшпш, Сформулировать данную задачу как цнркуляцнонную н решить бе, используя алгоритм дефекта. Сформулировать данную задачу как транспортную и решить ее, используя алгоритм дефекта. 8.
В следующей циркуляционной задаче найти максимальный поток нз узла 1 в узел 5. В качестве начального решения взять нулевой поток и нулевые значения для всех двойственных переменных и. Каждой дуге прнансана тройка (гту,,(Утп Сту). (1, 4,8) Оптовая база 3 Спрос = б единиц ииип вп4вр вол е дол зхлопязЕДИНИЦа ед»» ла Че Промыяленная компания 2' Товарные запасы = З единиц 4 доллцединица ело~ в а р иииц ери Оптовая база 4 Спрос = 4 единиц Промыяленная компания 3 .Товарные запасы =.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
