Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 7
Текст из файла (страница 7)
Если прибыль рассматривать как отрицательные затраты, то для ориентированного 2 -2,1 цикла с минимальным значением (Хси)/(Хги) величина средней при- Рвс. 2.4. сеть, опясываяппая были в единицу времени будет мак- графики прибытия судна в снмальной. порты. Оптимальное расписание движения судна задается контуром (1, 3), (3, 4), (4, 1) (рнс. 2.4).
При этом величина (Есн)/(Х/и) равна (3+2 — 4)/(1+2+3) = ='/е. Числа, приписанные дугам, указывают затраты си и времена Ги. Если все /и неотрицательные, то поставленная задача решается с помощью методов, аналогичных тем, которые используются при поиске кратчайшей цепи. 3 — 1654 Глава л 2дль ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ И ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ при услови~и, что У, 1=1, — О, (чь 1, (Фп, / / — У, (=п, (2.2) О < /'// < (///, (/, /) 6А. (2.3) В уравнениях (2.2) суммирование производится по всем узлам, для которых функция /// определена.
При целочисленных дуговых параметрах (/у рассматриваемая модель является абсолютно унимодулярной и поэтому оптимальное решение 5 также является целочисленным. Хотя данная задача может быть решена с помощью методов линейного программирования, более эффективным решением оказывается метод расстановки пометок, состоящий в построении возрастающей последова- Предыдущие примеры были сведены к задаче поиска цепи или контура, на которых достигается оптимальное значение специальным образом подобранной целевой функции.
В этих задачах дуги можно рассматривать как устройства, в результате работы которых от источника к стоку через узлы сети протекает 1 единица потока. Параметром дуги, или расстоянием, является обобщенная стоимость использования дуги. Обычно такие модели называют сетями с расстояниями. В более общей интерпретации дуга представляется как звено в механизме, предназначенном для транспортмрования многих единиц потока. В этом случае параметр дуги соответствует максимальной величине потока, который может протекать по дуге в единицу времени.
Этот параметр называется пропускной способностью дуги, а сеть — сетью с ограниченной пропускной способностью. Пусть 0= (Ы, А) — ориентированная сеть, где в!= (1, 2,... ...,и) — множество узлов, А — множество дуг, и пусть (/и— пропускная способность дуги (й /). Для удобства будем предполагать, что узел 1 является источником, а узел и — стоком. Согласно определению, данному в равд. !.3, целочисленная функция (;;, определенная на множестве А, называется потоком в сети О, если она удовлетворяет ограничениям (1.1)— (1.3).
Значение Х/„=л.///=У называется величиной потока. За- / I дача о максимальном потоке заключается в определении максимально допустимой величины У и может быть сформулирована следующим образом: максимизировать У Детериинироеаннтне потони в сетях 35 минимизировать ~~)' ~~)~~ с~Д~ (2.4) при условии, что (2.5) l Ент< ~ы(У», (1,)) ~А. (2.6) Хотя данная задача может быть решена с помощью симплекс- ного метода, более эффективным решением является процедура, основанная на использовании сетевой структуры рассматриваемой модели и условии дополняющей лежесткости, формулируемом в линейном программировании. Данная процедура известна под названием метода дефекта [151 (см. гл.
3). 2.1.5. ТРАНСПОРТНАЯ ЗАДАЧА Транспортная задача является одной из первых потоковых задач. Впервые она была решена в 1941 г, Хитчкоком 129] и с тех пор применяется при,решении многих задач перевозки и распределения. Несомненно, данная модель является наиболее широко используемой моделью, Постановка транспортной задачи, а также методы ее решения содержатся в,равд. 2.10.
Наиболее наглядной данная модель является при описании способов перевозки груза с заводов на склады. Предположим, что имеются ш заводов и л складов. Предложение Ого завода равно зь 1=1, 2, ..., лт, а спрос на )ьм складе равен с(ь 1=1,2,...,п. Задача минимизации общих затрат на перевозку 3 тельности потоков, последним членом которой является максимальный поток. Метод расстановки пометок описан в,равд.2.14.
0пределение понятия унимодулярности дается в,равд. 2.2. Для того чтобы создать более общую теоретическую основу, необходимую для понимания .рассматриваемых ниже прикладных задач, введем несколько дополнительных понятий. Для каждой дуги (1, /) определим линейный коэффициент стоимости сш а помимо верхней границы Уи введем нижнюю границу Ец. Для каждого узла 1 будет определено предложение Ь;~0.
При этом будем предполагать, что отрицательное значение Ь; соответствует спросу в узле й В описанной модели цри Ь;)О узел 1 можно рассматривать как источник, при Ь;=0— как промежуточный узел, а при Ьс(0 — как сток. После проведенного обобщения задача поиска потока минимальной стоимости может быть сведена к поиску таких целочисленных дуговых потоков ~;ь которые являются решением следующей задачи: Глава 2 груза эквивалентна определению величин хпь являющихся решением следующей задачи: минимизировать ~~~~~ '~ ~сыхы (2.7) при условии, что (2.8) 2.1.6.
ЗАДАЧА О ПОСТАВШИКЕ Владелец кафе должен иметь с(1 салфеток на каждый из п последовательных дней. Он может покупать новые салфетки стоимостью а центов каждая или отдавать грязные салфетки в стирку, причем в прачечной имеются два вида обслуживания— обычное и срочное. Для простоты будем предполагать, что салфетка, отданная в обычную стирку, бывает готова через хи — — зо 1=1,2,.,т, Х Ф ~~)' хм = 0,, 1= 1,2,...,п, (2.9) Ф хп)~0, 1=1,2...,т, 1=1,2,...,п. (2.!О) Для того чтобы система уравнений (2.8), (2.9), была совместной, предполагается, что Хз~=Хс(ь Данная модель может быть / описана с помощью сети, если предположить, что узлами являются заводы и склады, а дугами — имеющиеся дороги для перевозки груза.
Тогда дорога, сосо едвняющая 1-й завод с 1'-м скла- О дом, представляется ориентированной дугой 1'1, О. На рис. 2.5 ивов~ 1 бражена сеть, построенная для вп т=2, п=З. Следует отметить, что транспортная задача является частным случаем задачи поиска потока минимальной стоимости, сфорвв 2 мулированной в разд. 2.1.4, и сво- дится к последней при Ь|= — с(ЬЬ;= 3 дв Частным случаем транспортной задачи (при ги =,и, з; = 1, Н; = 1) является задача о назначениях, которая называется так потому, что типичная ее постановка связана с оптимальным назначением рабочих на рабочие места. Задача о назначениях и методы ее решения рассматриваются в равд. 2.12.
37 Детерминированные потока в сетях Чистые салфетки Грязные салфетки Магазин Рис. 2.6. Сеть в задаче о поставщике. ных в обычную стирку в )-й день; д; — число салфеток, отданных в ~рочную стирку в ~-й день; йг — число грязных салфеток, отложенных до следующего дня. На рис. 2.6 изображена соответствующая сеть при п=З.
Каждой дуге приписана одна из введенных выше переменных, а каждому узлу — соответствующее предложение. Пунктирная дуга используется для того, чтобы уравновесить спрос и предложение. Единственной особенностью данной задачи является то, что требуемое число чистых салфеток 0т равно числу салфеток, использованных к концу дня. После некоторых преобразований решение данной задачи может быть сведено к решению транспортной задачи. Хотя зта формулировка задачи выглядит несколько фривольной, впервые ее решение было использовано при планировании работы по ремонту оборудования, производимому на военных заводах.
В данном случае каждая величина спроса Ну известна либо соответствует предполагаемому количеству единиц оборудования специального типа, которое должно быть от- 2 дня, а плата при этом, равна Ь центам; для салфетки, отданной в срочную стирку, соответствующие величины равны ! дню н с центам, причем с)Ь. Задача заключается в выборе такого плана покупки и стирки салфеток, при котором спрос удовлетворяется при минимальных затратах.
Данная задача может быть сформулирована в виде сетевой задачи. Для этого введем следующие обозначения: р; — число салфеток, купленных для пользования в 1-й день; з; — число салфеток, отдан- 38 Глава 2 ремонтировано к заданному сроку. Обычному и срочному обслуживанию соответствует выполнение ремонта в местной мастерской и отправка оборудования в центральную мастерскую.
2.1.7. КАЛЕНДАРНОЕ ПЛАНИРОВАНИЕ ТРУГ!ОВЫХ РЕСУРСОВ « †! и Х Х"" в 1! в+! (2.11) при условя~и, что 1 а х„— зт —— Р;, .-! 1=!+! 1=1,,п — 1, (2.12) з,) О, хп) О. (2.13), (2.14) Данная постановка не допускает достаточно простую сетевую интерпретацию; это становится возможным лишь после некоторых преобразований. Предлагаемая ниже процедура описана для случая п=4. Ограничения (2.12) задаются уравнения- ми х„+х„+х„ — в! = Р, (2.! 5) х!в+х!в+ х,в+ хм — а, = Р„(2.16) х„ Хяв+ Хвф — з, = Р,. (2.17) Рассматриваемая ниже модель может быть использована для выработки политики в области занятости, позволяющей надлежащим образом сбалансировать затраты, связанные с наймом и увольнением рабочих, и затраты на содержание людей, не имеющих работу в течение непродолжительного периода времени. Предполагается, что спрос на рабочую силу является детерминированным, но не постоянным на протяжении заданного периода планирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
