Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 9
Текст из файла (страница 9)
Кроме того, должны выполняться ограничения двух типов. Ограничения первого типа гарантируют, что поставки продукции не превысят предложения. Таким образом, мы имеем Т.Т ограничений вида хгт<В!! для всех г=1,2,...,Ь и 1=1,2,...,Т. (2.19) Второй тип огранвчений гарантирует удовлетворение спроса в каждом периоде. Мы имеем Т ограничений вида !. !в+~' ~~ ~хм — ~г(! > О для всех г=1,2,..., Т. (2.20) ! ! ! ! ! ! Остановимся на следующем примере.
Будем рассматривать три периода и предположим, что в каждом периоде продукция может производиться как в рабочее, так,и в сверхурочное время. Соответствующие значения приведены в табл. 2.3. Таблица 2,3. Пример задачи производственного планирования Для того чтобы свести данную задачу к потоковой задаче, следует определить компоненты сети.
Будем предполагать, что узлы сети соответствуют источникам снабжения продукции, периодам, в течение которых возникает необходимость в ее производстве, и спросу на продукцию в эти периоды. Можно указать семь возможных источников снабжения продукции. Она может быть: а) взята из начальных запасов; б) произведена в каждом из трех производственных периодов в рабочее время; в) произведена в каждом из трех производственных периодов в сверхурочное время.
Дуги сети будут иметь четыре 45 Детерминированньсе нотоки в сетях характеристики: 1) направление допустимого потока; 2) минимальную величину требуемого потока по дуге; 3) максимальную величину допустимого потока по дуге; 4) стоимость единицы потока по дуге. Дуга, которая соединит пару узлов ( и 1, графически будет обозначаться следующим образом: сд.,и,с> ~-, где Š— минимальная величина допустимого потока, У вЂ” максимально допуствмый поток, С вЂ” стоимость единицы потока.
Задача сетевой оптимизации заключается в нахождении потока минимальной стоимости, гарантирующего удовлетворение спроса в периодах 1, 2 и 3 ограниченным предложением источников снабжения. На рис. 2.9 изображена сеть для данной задачи. Рассмотрим дугу (х', Р~). Параметр (О, 15, 0) дугц указывает на то, что в первом периоде продукцию из начального запаса можно либо не использовать совсем (Ь=О), либо использовать не более 15 ее единиц (У= 15), причем стоимость продукции нулевая (С=О). Аналогично параметр дуги ('т', Ро) указывает на то, что во втором периоде начальный запас объемом !5 единиц также может быть не использован, однако стоимость единицы продукции, если она используется, равна 1 долл.
(С= 1). Аналогичный смысл имеют параметры всех дуг, ведущих из источников е, )сь 01, Ям Оь, Яв, Ов к узлам, представляющим периоды (Рь Рв, Рз). И наконец, благодаря введению дуг (Рь 11~). (Рь Рз) и (Рь 0з) предложение удовлетворяет спрос. Например, минимальная величина требуемого потока по дуге (Рь Ве) равна 80 единицам (1=80), максимально допустимый поток также равен 80 единицам ((х'=80), а стоимость единицы потока равна нулю (С=О).
Следовательно, по дуге (Рь Вв) в узел Оз поступает 80 единиц потока. Дуго (Рь В~) и (Рь Рв) накладывают аналогичные требования на объем продукции, выпускаемой в первом и третьем периодах соответственно. Данная задача может быть решена как задача нахождения потока минимальной стоимости с использованием алгоритма решенная транспортной задачи, описанного в равд. 2.10, или алгоритма дефекта, описанного в гл. 3.
Полное описание задач подобного класса содержится в гл. 3. 2.1.10. ЗАКЛЮЧЕНИЕ Мы остановились на рассмотренных выше моделях для того, чтобы показать, насколько разнообразными являются задачи, решение которых может быть получено с помощью сете- Детерминированные потоки в еетнх 47 ного моделирования. Основное внимание было уделено потоковым моделям. Такие модели могут быть как детерминированными, так и стохастическими, имеющими детерминированный аналог.
Используя статические модели, мы определили понятие работы. Динамические модели возникали главным образом в тех случаях, когда узлы соответствовали временным периодам или комбинациям момент времени-место,расположения, Модели подобного типа являются весьма общими и могут использоваться даже в том случае, когда размерность задачи не позволяет воспользоваться традиционными методами линейного программирования.
Особенность задач нахождения кратчайшей цепи и одно- продуктовых потоковых задач в том, что их решение сводится к легко осуществляемому поиску некоторых цепей сети. Несомненно, это способствовало тому, что данные модели получили широкое распространение. Рассмотрение поставленных выше задач имело'целью познакомить читателя с сетевыми моделями. Эти задачи значительно проще, чем те, которые реально возникают на практике.
Однако их изучение полезно по той причине, что они являются несложными для понимания и решаются просто. Кроме того, эти модели позволяют наглядно изобразить решение каждой задачи. В последующих разделах мы остановимся на методах решения этих и некоторых других задач. Будут также описаны соответствующие вычислительные алгоритмы. 2.2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ И ПОТОКИ В СЕТЯХ Основной результат данного, раздела заключается в следующем: показано, что большинство потоковых задач,,рассматриваемых в последующих разделах книги, могут быть сформулированы как задачи линейного программирования (ЛП).
Возникает естественный вопрос: почему мы не ограничиваемся сведением этих задач к задачам ЛП? Во-первых, специфика структуры потоковых моделей, описывающих реально существующие системы, позволяет находить более эффективные алгоритмы поиска решения, чем симплексный метод. Во-вторых, эти специальные алгоритмы часто позволяют решать задачи ЛП большой размерности за время, меньшее среднего времени решения подобных задач. В-третьих, .именно тот факт, что мы можем описать математические зависимости взаимосвязями узлов и дуг сети, нередко помогает нам при постановке и решении практических задач.
Особое внимание следует уделить изучению специфики потоковых задач, сформулированных в виде задач ЛП, поскольку знание особенностей структуры сети играет главную роль в Глава л при условии; что — 1 ~»; < а,, ЖЧа, (2.22) »» )' ~~» — ~~)" ~»~ — — О, »ЕЬ1,р, » / ~~~~~ ~п — ~" »,» > Ьп»~Из, » » О < ~~» < (/,», (», ») сА. (2.25) Данная задача состоит в минимизации стоимости потока в сети (см. (2.21)). Из неравенства (2.22) следует, что в нашем распоряжении находится не менее Хп; единиц продукта, а со» гласно неравенствам (2.24), в стоки должно быть доставлено не менее ХЬ» единиц.
Соотношения (2.25) указывают на то, что ь' (2.23) повышении эффективности алгоритмов. В частности, целесообразно заранее определить, в каких случаях при применении методов ЛП будут получены целочисленные оптимальные решения. При этом может быть использовано несколько важных теорем, приводимых в данном разделе. Если заранее известно, что решение целочисленное, то для его поиска можно воспользоваться одной из следуюших процедур: 1) специальным алгоритмом ЛП, позволяюшим находить целочисленное оптимальное решение; 2) итеративными процедурами, непосредственно использующими сетевую структуру модели.
Такие итеративные процедуры основаны на использовании аддитивной арифметики, а целочисленные решения, получаемые прн нх применении, соответствуют решениям задачи ЛП. Излагаемый в данном разделе материал основан на результатах, полученных Гарфинкелем и Немхаузером [191.. Рассмотрим сеть с а источниками, р стоками и ~р промежуточными узлами. Предположим, что однопродуктовый поток должен протекать из источников в стоки через промежуточные узлы. Каждая дуга сети характеризуется верхней границей с»»» потока ~п через нее и стоимостью сп единицы потока. Сеть может быть представлена в виде ориентированного графа 6=(й(, А), где М=йа(»й(ВЦщщ, а М, Хз н Хв — множества источников, стоков и промежуточных узлов соответственно.
Задача нахождения потока минимальной стоимости, поставленная в равд. 2.1.4, может быть переформулирована математически следующим образом: минимизировать ~~)' ~~~~~ с,»»»» Детерминнвовоннме потоки в сетях потоки по дугам ограничены. Равенства (2.23) представляют собой условия сохранения потока для каждого промежуточного узла (ом. гл. 1). Частным случаем общей задачи, описываемой выражениями (2.21) — (2.25), является каждая из следующих четырех важных задач, постановка которых приводилась в разд. 2.1: 1) транспортная задача (равд. 2.1.5), 2) задача о назначениях (равд. 2.1.5), 3) задача о максимальном потоке (равд.
21.4) и 4) задача о кратчайшей цепи (равд. 2.1.1). Случай 1. Транспортная задача. В случае когда поток течет непосредственно из источников в стоки, сеть ие содержит промежуточных узлов. Если требуется, чтобы фиксированное предложение удовлетворяло заданный спрос при минимальных затратах, то возникает классическая транспортная задача с ограничениями, которая формулируется следующим образом: минимизировать "~~ ~~)' с,»),» (2.25) е при условии, что (2.28) минимизировать ~~)' ~ с,.Д» с» (2.30) при условии, что ~)' )';» < 1 16" '~~ Ь1 >1 Ж~з » 7,»>0, (1,1)чА.
Отметим, что если число стоков равно ограничения (2.31), (2.32) записываются 4 — 1 654 (2.31) (2.32) (2.33) числу источников, то в виде равенств. Не- мт' 1';» < а;, (~Х„, (2.27) » ")~~)», ~ )Ьо (бааз, » 0 < 70 < (7и, (1 1) еА (2.29) Если на пропускные способности одной или нескольких дуг, соединяющих источники с источниками илн стоки со стоками, не накладываются ограничения сверху, то возникает задача о перевозках.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
