Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 67
Текст из файла (страница 67)
Следовательно, в полученный норматив уже включены все случайные колебания и нет необходимости вносить в него дополнительные поправки, не считая тех, которые соответствуют нормам времени на личные нужды и на усталость. Это дает возможность получить дисперсию нормативного времени, с помощью которой для него строятся доверительные интервалы. В заключение отметим, что, хотя для решения данного примера потребовались сложные и трудоемкие вычисления, все они могут быть выполнены на ЭВМ.
Для этого разработана специальная ГЕРТ-процедура, написанная на языке ФОРТРАН)Ч (см. [33]). Для обращения к ней необходимо пробить на стандартных картах данные о каждой непрерывной плотности распределения. ЧАСТЫП. МНОГОПРОДУКТОВЫЕ ПОТОКИ В СЕТЯХ Результаты получены при участии Дж. Эванса, Университет г. Цинциннати В гл. 3 было показано, каким мощным средством для решения ряда детерминированных потоковых задач является алгоритм дефекта. При рассмотрении каждого примера делалось одно важное предположение, согласно которому по дугам сети должен протекать однопродуктовый поток. Однако существует немало практических задач о перевозке нескольких различных продуктов, которые должны сохраняться при прохождении по дугам сети.
Необходимо иметь возможность различать продукты. Рассмотрим, например, упрощенную задачу транспортировки трех видов фруктов из садов, расположенных в Калифорнии, в магазины, ведущие оптовую торговлю. Предположим, что сады, принадлежащие частной компании, расположены в городах Санта-Барбара, Бейкерсфилд и Сакраменто. В период уборки урожая из этих садов поставляются в различных количествах Таблица б.б.
Производительность (антики в неделю) Новые воароеы 4!1 Таблица б.б. Величины спросе (ящики в неделю) таблица б.7. пропускная способность железных дорог (вцики в неделю) Таблица б.б. Транспортные затраты (центы не ящик) апельсины, лимоны и лаймы (табл.
5.5). По договорному соглашению требуется доставлять в оптовые магазины, расположенные в Денвере, Сиэтле и Канзас-Сити, такое количество фруктов, которое указано в табл. 5.6. Перевозка осуществляется по железной дороге, однако в каждом поезде для фруктов 412 Глаза Ю ЗЛЗ. ФОРМУЛИРОВКИ ЗАДАЧ О МНОГОПРОДУКТОВОМ ПОТОКЕ В ВИДЕ ЗАДАЧ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ Задачи о многопродуктовом потоке, так же как и задачи об однопродуктовом потоке, могут быть сформулированы в виде задач линейного' программирования. Задача о транспортировке фруктов является примером многопродуктовой транспортной задачи.
Обозначим через хьп поток й-го продукта из (-го источника в 1чй сток, а через с"и — стоимость транспортировки единицы этого продукта. Пусть далее ал и Ь|" — это соответственно предложение узла ( и спрос узла 11 для й-го продукта, а ип— пропускная способность дуги (ю', 1). Математическая постановка многопродуктовой транспортной задачи выглядит следующим образом: минимизировать "~~ ~~' ~~~~сзпх"ы ь 1 ~-1 _#_-~ (5.23) отведено ограниченное место.
Пропускные способности путей между различными пунктами отправления и пунктами назначения приведены в табл. 5.7. Независимо от вида фруктов данные величины задаются числом ящиков, перевозимых в неделю (предполагается, что все фрукты упакованы в ящики одинаковых размеров).
Вес каждого ящика, а следовательно, и соответствующие транспортные затраты зависят от вида упакованных в него фруктов. Затраты на транспортировку одного ящика приведены в табл. 5.8. Задача определения схемы перевозки фруктов, минимизирующей транспортные затраты, является задачей о многопродуктовом потоке. Отметим, что данная задача аналогична транспортной задаче, рассмотренной в разд. 2.10, в том отношении, что перевозки могут осуществляться только между пунктами отправления и пунктами назначения.
Характерная особенность задач о многопродуктовом потоке состоит в том, что по дугам сети протекает несколько неоднородных потоков. При этом суммарная величина потоков всех продуктов по дуге ограничена ее пропускной способностью. Если бы это было не так, то можно было бы для каждого продукта независимо решить минимизационную транспортную задачу, используя, например, алгоритм дефекта. Однако указанные выше ограничения на пропускные способности дуг существенно усложняют решение задачи.
аз Новые волроеы при условии, что ~ хз,/= Ьа/ для всех /, й, (5.24) 4 ха,/=аь/ для всех /,й, / ~~~ха//<и// для всех 1,/, (5.26) хам)~0 для всех /,/,й. (5.27) Как и в однопродуктовой транспортной задаче, предполагается, что для каждого продукта суммарное предложение равно сум- марному спросу, т. е. а', = ~~ (/а/ для всех й.
/ / Во многих задачах, называемых многопродуктовыми задача- ми о перевозках, вводятся промежуточные узлы, т. е. такие уз- лы, которым не приписывается ни предложение, ни спрос, а только требуется, чтобы для них выполнялось условие сохране- а, =/о 1 (5.25) (5.28) ьз/ =гз ь,' =2о аг =/5 1 а, '=2о Рпс. 5.25, Сеть в ывогопродуктовой задаче о перевозках. ния потока. В качестве одного из таких примеров рассмотрим сеть, изображенную на рис.
5.25. Узлы 1 и 2 являются источниками продукта 1, а узел 2 — источником продукта 2. Узел 5 является пунктом назначения для обоих продуктов, а узлы 3 н 4 — промежуточными. Многопродуктовая задача о перевозках может быть сформулирована в виде следующей задачи линейного программирования: г ми~и~некро~а~~ )' )~' с"цхь// (5.29) а / </,Пеа при условии, что чвч хаы — Ъ' х"/, аа„если Узел а является источ. (5.30) лы Г'Й ником продукта й Глава б 414 если узел у является проме- жуточным узлом, лт,' х" м — ~~~~~ хаи = О, 1 ! ~~» ха,! — ~~х"л = — Ьлу, ! (5.31) если узел у является стоком продукта а, (5.32) Таблица б.в Нецелочисленные решения возникают по той причине, что матрицы ограничений в задачах линейного программирования, вообще говоря, не являются унимодулярными. Напомним, что условие унимодулярности матрицы ограничений, введенное в гл.
2, является достаточным для существования целочисленных оптимальных решений. Поскольку в задачах об одиопродуктовом потоке данное условие выполнено, то для них можно разработать высокоэффективные алгоритмы, в которых по существу выполняются только две операции — сложение и вычитание, а такие операции, как, например, деление и обращение матрицы, не требуются. С вычислительной точки зрения арифметические операции, выполняемые с целыми числами, являются намного более быстрыми, чем операции, использующие числа (десятич- ~~)' х"м < и,! для всех (й у) ЕА, (5.33) х'!!) )О для всех й и (у,у) ЕА.
(5.34) Через А здесь обозначается множество дуг сети. Одна из трудностей решения задач о многопродуктовом потоке вызвана тем, что оптимальные решения могут быть нецелочисленными. В качестве примера рассмотрим двухпродуктовую транспортную задачу, сетевая формулировка которой задана на рис. 5.26. Дугам сети приписаны числа с'и, с'», ии. Оптимальное решение соответствующей задачи линейного программирования представлено в табл.
5.9. 415 Нова/е воароеи ные) с плавающей точкой. Благодаря этому создаются программы, позволяющие очень быстро решать задачи большой размерности. Для задач о многопродуктовом потоке были разработаны специальные алгоритмы, в которых используется специфика структуры и свойства данного класса задач. Было показано, а, в; 1 ь, ь (! 42) / / 2 2 2 2 2 2 2 2 Рнс. 5.26. Даухпродуктоаая транспортная задача. что эти алгоритмы являются более быстрыми, чем процедуры решения общей задачи линейного программирования, но значительно более медленными, чем соответствующие алгоритмы для задач об однопродуктовом потоке. Детальное изучение этих методов выходит за рамки нашей книги.
Однако в настоящей главе мы рассмотрим ряд специальных вопросов, связанных с задачами о многопродуктовом потоке и методами их решения. $.19. СПЕЦИАЛЬНЫП КЛАСС ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ О МНОГОПРОДУКТОВОМ ПОТОКЕ Как отмечалось выше, общая задача о многопродуктовом потоке может не иметь целочисленного оптимального решения. Однако существует несколько классов этих задач, в которых матрицы ограничений являются унимодулярными, и, следовательно, целочисленные оптимальные решения существуют. Интересно отметить, что многие из этих задач могут быть сведены к эквивалентным задачам об однопродуктовом потоке, которые несложно решаются с помощью алгоритма дефекта или любого другого алгоритма решения задачи о потоке минимальной стоимости.
Глава з 4|6 при условии, что ~~~~ ~х",| — — Ь"с для всех" 1', й, с (5.36) (5.37) для всех с,й, (5.38) для всех 1,/, х'„, зсс) 0 длЯ всех с,),И. (5.39) При т=2 данная задача сводится к следующей задаче линейного программирования: г в минимизировать ~~)' ~ [(с"вс — с",|) х",с+с",сбвс) (5.40) А-с|-с при условии, что ~~~ х'в|+ звс изс для всех 1, (5.41) — '~'х",|= — а," для всех й, — ~(з,| — — — ~~)'„ив|+ ~~~~ ~а,з (5А2) (5.43) Многопродуктовая транспортная задача была сформулирована в равд. 5.18. Для нее известен следующий результат. Матрица ограничений в многопродуктовой транспортной задаче является унимодулярной в том и только в том случае, когда число источников (т) илн число стеков (л) не превосходит 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
