Библиографическое описание:

Маркелова И. В., Данилов А. М. Сетевые модели в приложениях // Молодой ученый. — 2014. — №7. — С. 149-152.

Сетевые модели используются при решении различных технико-экономических задач [1…4]; имеют многочисленные приложения во всех отраслях индустриального и экономического планирования (распределение потоков товаров, газа, нефти, воды, людей и т. д.; задача о перегрузке товаров). Ограничимся рассмотрением двух наиболее важных приложений.

Рис.1

1.                  Задача о максимальном потоке. Исходные параметры задачи указаны на рис.1. Готовая продукция распределяется с минимальными расходами по складам, а оттуда попадает потребителям (источники, склады и потребители — узлы сети, пути между ними — дуги). На каждой дуге указана ее максимальная пропускная способность. Задача состоит в получении максимально возможного потока от источника (узел 1)к стоку (узел 6). Направления потоков могут быть изменены; расходы на перевозку также не учитываются. Это частный случай сетевой задачи. Неизвестными величинами являются потоки  из узла  в узел ; , - верхние пределы (пропускные способности) дуг. Из условия равновесия следует:

;

- суммарный поток, поступающий в узел  по всем ; - суммарный поток из -го узла по всем . Это справедливо также для источника и стока (вводится фиктивная труба с бесконечно большой пропускной способностью (пунктир на рисунке от стока к источнику)).

Матрица инцидентности (матрица коэффициентов последнего уравнения; имеет специальную структуру):

А=

(A).

Каждому из шести узлов соответствует строка, и каждой из девяти дуг соответствует столбец матрицы; числа +1 и -1 полностью описывают связи между узлами и дугами. Задача определения максимального потока (сделать  наибольшим) превращается в обычную задачу линейного программирования (возможно использование симплекс- метода).

Укажем и другой подход (укороченный вариант). Разделим все узлы на две группы  и  с источником в группе  и стоком в  (разрез сети). Сумма пропускных способностей по всем дугам, идущим из  в , определит пропускную способность разреза (например, если  содержит первый и третий узлы, то пропускная способность этого разреза равна ; поток, превышающий 11, невозможен, так как не может пройти через разрез). Известно, максимальный поток в сети равняется пропускной способности минимального разреза (теорема о максимальном потоке и минимальном разрезе). Неравенство в одну сторону очевидно: поток не превосходит пропускной способности разреза (для произвольных значений потока и разреза). Никакой поток не в состоянии сделать больше, чем просто насытить все дуги, пересекающие разрез, и их общая пропускная способность является верхней гранью для потока (аналогично «слабой двойственности», простому неравенству , , ). Определение достижимости равенства — более сложная задача, как и в теореме двойственности.

Пусть некоторый поток является максимальным. Рассмотрим все дуги, которые не достигли предела пропускной способности, и пусть  содержит источник, а также все узлы, которые можно от него достичь по этим дугам. Остальные узлы образуют группу . Тогда сток будет находиться в ; в противном случае поток не будет максимальным. Более того, каждая дуга, соединяющая  с , является заполненной. Иначе узел, в который она входит, принадлежал бы , а не . Следовательно, поток действительно наполняет разрез, и равенство достигается. Это дает возможность проверить, что заданный поток является максимальным (нужно лишь найти соответствующий разрез). В рассматриваемом примере максимальный поток равен 6 (максимальный поток и минимальный разрез указываются на рис.2). Указанная теорема дает и алгоритм решения: для любого потока нужно вычислить неиспользованную пропускную способность каждой дуги. Если сток может быть достигнут по какому-то недозаполненному пути, то следует увеличить результат. Постепенно будет достигнут максимальный поток (в случае целочисленных пропускных способностей целочисленным будет и поток — задача целочисленного программирования).

Рис. 2

2.                  Задача о простом назначении. В выполнении n работ участвуют m человек, каждый из которых может выполнять лишь определенные работы из указанных. Требуется распределить работы, исходя из их специальностей, не допуская при этом выполнение одной и той же работы разными людьми. Укажем необходимые условия, при которых возможно такое назначение. Каждый должен иметь, по крайней мере, одну специальность; каждая пара должна иметь две различные специальности. Каждая группа из трех (или k) человек должна быть в состоянии выполнять, по меньшей мере, три (или k) различных работ. Иначе цель не может быть достигнута. Справедливо утверждение: назначение возможно тогда и только тогда, когда каждая группа в состоянии выполнять достаточное число работ; если группа состоит из k человек, то вместе они должны быть в состоянии выполнять, по меньшей мере, k работ.

На первый взгляд условие выглядит слабым: один квалифицированный человек в состоянии помочь всей группе выполнить k работ. Однако это условие относится к каждой группе, включая и те, в которых этот человек не состоит. Если распределение работ невозможно, то всегда можно найти группу, для которой это условие выполняется. Начнем с конструирования сети, имеющей пропускную способность m между каждым человеком и работами, которые он может выполнять (исполнители подключаются к источнику, а работы — к стоку при помощи дуг с пропускной способностью ; рис.3).

Рис.3

Если суммарный поток станет m, то все дуги от источника будут заполнены, и все будут иметь работу. Если максимальный поток окажется меньше m, то существует разрез с пропускной способностью меньше m, например, такой, что в группе S содержатся источник и узлы J1,…,Jk. j1,…jn. Ни один из этих k человек не в состоянии выполнять другие работы. Иначе нашлась бы дуга с пропускной способностью m, пересекающая разрез. Так что пропускная способность разреза равняется m-k (от источника к оставшимся людям) плюс l (от этих работ к стоку), что в сумме даст m-k+l; это величина будет меньше m при . Следовательно, определится группа из k человек, которая может выполнять лишь  работ. Если назначение окажется невозможным (поток оказался меньше m), то какая-то группа людей сдерживает его.

Приведенные сетевые модели эффективно использовались при разработке информационных моделей человека-оператора эргатической системы (как многоканальной системы управления; [5…7]).

Литература:

1.         Данилов А. М., Гарькина И. А., Домке Э. Р. Математическое и компьютерное моделирование сложных систем. — Пенза: ПГУАС. — 2011. — 296 с.

2.         Данилов А. М., Домке Э. Р., Гарькина И. А. Формализация оценки оператором характеристик объекта управления / Информационные системы и технологии. — 2012. — № 2. — С. 5–10.

3.         Будылина Е. А., Гарькина И. А., Данилов А. М. Декомпозиция динамических систем в приложениях / Региональная архитектура и строительство. — 2013. — № 3. — С. 95–100.

4.         Будылина Е. А., Гарькина И. А., Данилов А. М., Махонин А. С. Основные принципы проектирования сложных технических систем в приложениях / Молодой ученый. — 2013. — № 5. — С. 42–45.

5.         Гарькина И.А, Данилов А. М., Пылайкин С. А. Транспортные эргатические системы: информационные модели и управление / Мир транспорта и технологических машин.– 2013. — № 1(40). — С.115–122.

6.         Andreev A. N., Danilov A. M., Klyuev B. V., Lapshin E. V., Blinov A. V., Yurkov N. K. Information models for designing conceptual broad-profile flight simulators / Measurement Techniques. August 2000. — Vol.43. Issue 8. — P.667–672.

7.         Гарькина И. А., Данилов А. М., Домке Э. Р. Математическое моделирование управляющих воздействий оператора в эргатической системе / Вестник Московского автомобильно-дорожного государственного технического университета (МАДИ). — 2011. — № 2. — С. 18–23.

Обсуждение

Социальные комментарии Cackle