Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 60
Текст из файла (страница 60)
367 Новые вопросы Сети, прн прохождении через дуги которых возможно увеличение или уменьшение потока, будем называть обобщенными сетями. Более точно потоки, протекающие по дугам обобщенной сети, изменяются коэффициентами выигрыша (или проигрыша) таким образом, что поток, входящий в дугу, может отличаться от потока, выходящего из нее. Фактически для получения величины выходного потока величину входного потока следует домножить на коэффициент выигрыша (проигрыша). Рассмотрим ориентированную сеть, состоящую из дуг ((, 1), причем из узла 1 в узел 1 протекает поток величины ~п, а стоимость единицы потока равна сп. Допустимая величина потока по дуге (1, 1) должна быть не меньше величины Сп и не должна превосходить величину Уп.
Дуговой коэффициент будем обозначать через Ап. Графически эти параметры дуг будем обозначать следующим образом: Отметим, что при Ап=1 мм приходим к традиционной сетевой постановке, при Ап->1 поток увеличивается (выигрыш), при Ап(1 поток уменьшается (проигрыш). Поскольку изменение потока происходит при ег47 прохождении по дугам, то принцип сохранения потока по-прежнему имеет силу. Однако очевидно, что величины потока теперь могут принимать не только целые, ио и любые положительные вещественные значения. Несмотря на то, что обобщенные сетевые задачи являются достаточно общими и имеют широкую область применения, ранее им не уделяли должного внимания. Лишь недавно были предприняты попытки разработки эффективных алгоритмов решения этих задач и написания соответствующих машинных программ для широкого пользования.
6Л. ПРИМЕНЕНИЕ ОБОБЩЕННЫХ СЕТЕЙ Как уже отмечалось, с помощью обобщенных сетей могут быть решены многие задачи, не допускающие обычную сетевую интерпретацию. Это становится возможным благодаря тому, что дуговые множители имеют двоякий физический смысл. Вопервых, они могут отражать количественное изменение потока некоторого однородного продукта. Например, обобщенные сети позволяют моделировать такие процессы, как испарение, фильтрация, износ, расширенное воспроизводство, процентный прирост капитала, очистка сточных вод, ректификация с различной эффективностью, работа станков с различной производи- Глава в тельностью, проектирование силовых конструкций.
Во-вторых, дуговые множители могут отражать превращение одного типа продукта в другой. Это позволяет моделировать такие процессы, как обработка продукции, производство, превращение топлива в энергию, смешение, а также решать задачи, связанные с составлением расписания работы бригад, определением потребности в рабочей силе и обменом валюты. (Более подробно см. [4, 8, 9, 13].) Следующие примеры показывают практическое значение обобщенных сетей. С помощью обобщенной сетевой модели Бомик [1] описал полную систему распределения водных запасов с учетом возможных потерь. В основном эта модель отражает процесс движения воды по каналам к различным резервуарам.
Но при этом также рассматривается возможность задержания воды на некоторое время. Множители в данном случае учитывают уменьшение количества воды вследствие испарения и фильтрации. Ким [19] использовал обобщенные сети для описания процесса очистки меди. Процедура электролитической очистки меди моделируется сложной сетью, дуги которой соответствуют линиям постоянного тока, а множители в величинам сопротивлений. С помощью такой модели можно исследовать влияние короткого замыкания на процесс очистки.
Чарнес и Купер [4] нашли применение обобщенным сетям как в изучении модели предела пластичности, так и в потоковой модели склад-фонды. В первом случае сеть строится с помощью уравнений равновесия для горизонтального и вертикального направлений с учетом перекрестного взаимодействия. Потоковая модель склад-фонды фактически является многопериодной моделью. Дуги здесь используются для описания производства н продажи продукции, пополнения ее запасов, а также осуществления денежных вкладов. Множители вводятся для того, чтобы учесть взаимозаменяемость товара и денег. Крам [5] с помощью обобщенной сети описал модель конт-' роля и регулирования денежных операций, которая позволяет многонациональной корпорации суммировать изменение цен, дебиторские задолженности, счета к оплате, денежные сборы, выплаты девидендов, уплаты процентов, лицензионные платежи и сборы на управление.
Дуги представляют собой возможные варианты потока денег, а коэффициенты соответствуют затратам, накоплению, превращению в наличные деньги и обменному курсу. Кроме того, обобщенные сети находят применение при решении задач загрузки оборудования [4, 6, 28], различных задач о смешивании [4, 28], задач о поставщике [6, 28] и задач составления расписаний (например, задач о производстве и распределении, составлении расписания работы бригад, движения самолетов и задач подготовки кадров [4, 6, 28]),.
Новые вовпоеы 5.2. ОБОБЩЕННАЯ СЕТЕВАЯ ЗАДАЧА КАК ЗАДАЧА Л ИНЕИНОГО ПРОГРАММИРОВАНИЯ при условии, что ~~)' ~,1 — ~~)' А~Д, < Р, ! 1 ~~)' ~м — '~))'Ал)п = О, 1Ф з, Т, (5.2) (5.3) (5.4) 1 / О< ~1~< УО для всех (е,у). (5.5) Отметим несколько предположений, касающихся данной постановки. 1. Все дуговые множители являются положительными вещественными числами. 2. Нижние границы потоков по всем дугам равны нулю. Данное предположение не ограничивает общности рассматриваемой задачи, поскольку для дуг с положительными нижними границами можно произвести замену )О=Ц вЂ” Ан. 3. Источники и стоки объединяются таким образом, что сеть содержит только один источник и один сток.
Этого можно достигнуть, вводя главный источник и главный сток (см. описание метода дефекта). 4. В отличие от традиционных постановок входной поток Р может отличаться от выходного потока г". Это происходит в силу того, что потоки по дугам изменяются в соответствии с дуговыми множителями. Таким образом, требуемый поток г будет определен для стока.
Входные потоки не известны до тех пор, пока не найдено окончательное решение, однако на них можно наложить ограничение, при котором они не будут превосходить 24 †16 Обобщенную сетевую задачу можно рассматривать как задачу о потоке минимальной стоимости в сети с выигрышами и проигрышами. Цель — добиться, чтобы в сток втекал поток величины г, имеющий минимальную стоимость, или чтобы из источника вытекал поток величины Р, имеющий минимальную стоимость. Мы опишем алгоритм, который позволяет решать обе эти задачи, однако для простоты изложения будем рассматривать первую из них. Задача о потоке минимальной стоимости в сети с выигрышами и проигрышами может быть сформулирована следующим образом: минимизировать ~~~~ ~)~~ с,.ДГ 1 Глава о величины г".
Отметим, что при данном предположении для входного потока г" может не существовать выходного потока г. Для решения данной задачи будут предложены два различных алгоритма. Первый из них используется для решения обобщенных сетевых задач частного вида, в то время как второй представляет нам общую схему решения.
Перед тем как перейти к описанию этих алгоритмов, остановимся на некоторых основных свойствах обобщенных сетей. 5.з. хАРАКтеРистики сети Напомним, что множество ориентированных дуг, соединяющих источник и сток, называется цепью, или ориентированной цепью'1. Произведение всех дуговых множителей цепи Е будем называть изменением цепи и обозначать символом Сп= П Ам (5.6) сс пап Отметим, что если начальный и конечный узлы цепи совпадают, то она называется циклом.
Произведение (5.6) дуговых множителей цикла будем называть изменением цикла. Ап = Рис. 5.1. Сеть с аыигрышамн и проигрышами. Рассмотрим сеть, изображенную на рис. 5.1, вне связи с обобщенными сетевыми задачами. Цепь, соединяющая узлы 1 и 4, задается множеством дуг Е=((1, 2), (2, 3), (3, 4)), а изменение цепи равно Сп=1 2 6=12. Отметим, что если в дугу (1, 2) входит 1 единица потока, то в узел 2 также входит 1 единица; если входной поток по дуге (2, 3) равен 1„то в узел 3 поступают 2 единицы потока; если в дугу (3, 4) входят 3 едини- о Более точное определение цепи дано п гл. 1.— Прил.
перев. Новые вопросы цы потока, то в узел 4 — 12 единиц. Такое изменение потока по цепи называется евшгрышем цепи, поскольку в результате прохождения по ней поток увеличивается. С другой стороны, величина потока, выходящего из узла 1 и протекающего по цепи Е=((1, 2), (2, 4)), в узле 4 уменьшится в 4 раза. Следовательно, изменение цепи Се=1.Че='/,. Величина Се в данном случае называется проигрышем цепи. Таким образом, Изменение цепи = 1 †н изменений, Се= П Ам > 1 — выигрыш цепи, и.
век ( 1 — проигрыш цепи. Отметим далее, что последовательность дуг Е=((1, 2), (2, 3), (3, 1)) образует цикл, для которого величина Се=1 2.1(з=з(з. Такой цикл называется поглощающим циклом. Если Е=((1, 2), (2, 3), (3, 5), (5, 1)), то Се=1.2 з(з 1=1,5. Такой цикл называется генерирующим цикзом. Очевидно, что любой поток, входящий в узел 1 и проходящий по этому генерирующему циклу, увеличивается в 1,5 раза.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
