Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

Г л а в а 6

ЦИФРОВЫЕ АНАЛОГИ ЗАДАЧ О ПОТОКАХ В СЕТЯХ

6.1. МОДЕЛЬ ЗАДАЧИ О МАКСИМАЛЬНОМ ПОТОКЕ

Задачу о максимальном потоке можно решить как задачу -о кратчайшем пути (см. § 1.7). При этом требуется преобразование

.исходной сети в двойственную, что не всегда удобно при подготовке задачи к решению.

Для определения максимального потока можно воспользоваться следующим методом. Предварительно на сети отыскивается какойнибудь путь и определяется величина минимальной пропускной •способности одной из дуг этого пути. Величина найденной минималь­ ной пропускной способности отнимается от пропускных способнос­ тей дуг пути и запоминается. Далее, на преобразованной таким

. образом сети отыскивается новый путь и дуга с минимальной пропуск­ ной способностью в этом пути. Вычитанием величины новой мини­ мальной пропускной способности в других дугах снова преобразовы­ вается сеть, величина минимальной пропускной способности скла­ дывается с аналогичной предыдущей величиной и запоминается и т. д. Процесс заканчивается тогда, когда не будет ни одного пути между начальным и конечным узлами сети.

Сумма величин минимальных пропускных способностей дуг

.в путях и определяет величину максимального потока сети. Подобный метод позволяет построить относительно простые

•цифровые аналоги для решения данной задачи.

При определении величины максимального потока в модели реализуется метод, подобный методу, описанному в работе [206]: при вычитании от величин пропускных способностей дуг некоторого пути величины минимальной пропускной способности дуги этого пути, эта величина минимальной пропускной способности дуги

..прибавляется к величинам пропускных способностей каждой дуги, включенной навстречу дугам этого пути.

Цифровой аналог представляет собой соединенные в соответст­ вии с топологией сети модели дуг (МВ) и устройство управления.

В модели нет как таковых моделей узлов, им соответствуют по-

.люсы электрических соединений отдельных моделей дуг. Устройство управления не сложное и его техническая реализация не имеет принципиального значения, поэтому такое устройство далее не рассматривается. Отметим только, что оно должно содержать счет­ чик импульсов соответствующей емкости для запоминания величин

.минимальных пропускных способностей дуг путей, тем самым для

.160

определения величины максимального потока, и некоторые вспомо­ гательные элементы.

Модель дуги в случае отрицательной логики изображена на рис. 99. В принципе она является объединением двух моделей дуг, которые способны определить кратчайший путь на сети и включенные навстречу друг другу.

Модели дуг соединяются между собой полюсами 19 и 20. Для каждой ориентированной дуги сети только в счетчик импульсов

Рис. 99

1 предварительно заносится число импульсов, которое дополняет величину пропускной способности этой дуги до полной емкости счет­ чика. Для неориентированной дуги число импульсов, которое до­ полняет величину пропускной способности дуги до полной емкости счетчика, заносится в счетчик импульсов 1 я Г.

Триггеры 3, 4, 3' и 4' вначале находятся в нулевом состоянии. Считая величины пропускных способностей дуг сети величинами их продолжительности, модель отыскивает на сети какой-либо крат­ чайший путь. Для этого устройство управления подает в начальный узел импульс пуска. Предположим, что в некоторый момент времени этот сигнал появится через дизъюнктор, который получается со­

(ГИ) через полюс 2 1 , конъюнктор 10 и дизъюнктор 18. Одновремен­ но запрещается пуск модели встречной дуги.

Сигнал переполнения счетчика 1 через конъюнктор 11 ставит триггер 4 в единичное состояние, т. е. сигнал пуска через диод Д пройдет на полюс 2 0 и произойдет пуск соединенных с ним моделей ветвей. Во всех моделях ветвей, в которых импульс переполнения счетчиков импульсов 1 (Г) появится на полюсе 2 0 позже этого мо­ мента, триггеры 4 не будут устанавливаться в единичное состояние, так как с полюса 20 через инвертор 5 и конъюнктор 11 этих моделей ветвей будет поступать запрещающий сигнал.

В процессе расширения сигналов пуска в сети теряется содержи­ мое счетчиков импульсов 1 (Г). Для обновления информации одно­ временно с пуском какого-нибудь счетчика импульсов ( 1 или Г) тактовые импульсы через дизъюнктор 17 попадают в регенерацион­ ный счетчик импульсов 2 , емкость которого равняется емкости счет­ чиков 1 я Г.

Когда сигнал пуска достигает последнего узла сети и совершится регенерация во всех моделях ветвей, устройство управления по­ дает запрещающий потенциал в конечный узел сети.

Таким образом находится какой-нибудь кратчайший путь; у моделей ветвей этого пути на выходе конъюнкторов 1 2 (1 2 ') будет разрешающий сигнал.

Для определения величины минимальной пропускной способнос­ ти некоторой дуги пути устройство управления подает разрешающий сигнал через полюс 22 на все конъюнкторы 14, 15 (14', 15'), импуль­ сы ГИ начинают поступать одновременно через конъюнкторы 14 (14') и дизъюнкторы 18 (18’) во все счетчики импульсов 1 (Г) только кратчайшего пути, потому что имеем разрешающий сигнал с конъюнктора 1 2 (1 2 ').

В модель дуги, которая имеет противоположное направление первой модели дуги, импульсы от генератора ГИ будут поступать через конъюнктор 15 (15') на реверсивный вход счетчика импульсов 1 (Г), так как приходит разрешающий сигнал с конъюнктора 1 2 (12'). Так осуществляется добавление величины минимальной пропускной способности дуги пути к величинам пропускных способ­ ностей дуг, которые включены навстречу дугам этого пути.

Одновременно эти импульсы поступают и в счетчики определе­ ния минимального потока устройства управления.

Импульс переполнения какого-нибудь счетчика импульсов 1

(Г) через конъюнкторы 16 (16') и полюс 23 поступает в устройство управления и прекращает поступление импульсов от ГИ ; так опре­ деляется величина минимальной пропускной способности дуги этого пути.

Затем модель аналогично отыскивает новый кратчайший путь на преобразованной сети и определяет величину минимальной про­ пускной способности дуги этого нового пути.

Процесс оканчивается,, когда в сети не будет больше путей между начальным и конечным узлами.

162

В счетчике определения максимального потока устройства управления будет записано число импульсов, пропорциональное величине искомого максимального потока.

6.2. ЦИФРОВОЙ АНАЛОГ ДЛЯ РЕШЕНИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ПОТОКЕ

Как известно, задача о минимальном потоке в сети состо­ ит в определении наименьшей величины потока между двумя узла­ ми в случае задания нижних границ потока через каждую ветвь, т. е. если поток через каждую ветвь не меньше заданного.

На рис. 100, а показана блок-схема устройства для определения минимального потока транспортной сети. Она состоит из генерато­ ра импульсов (ГИ), устройства управления (УУ), блока регист­ рации потока (БРП), блока эле­ ментарных процессоров (БЭП) и устройства ввода — вывода ин­ формации (УВВ).

Число элементарных процес­ соров БЭП соответствует количе­ ству ветвей транспортной сети. Каждый элементарный процес­ сор восполняет функции запо­ минания исходной информации о потоковом ограничении ветви и преобразования этого потоково­ го ограничения в процессе опре­ деления минимального потока. Функциональная схема элемен­ тарного процессора показана на рис. 100, б.

Элементарный процессор состоит из двух задатчиков потоковых ограничений (ЗПО-1 и ЗПО-2), двух формирователей потокового ограничения (ФПО-1 и ФПО-2) и блока выбора потокового ограниче­ ния (БВПО). Полюсами 1 и 2 элементарные процессоры соединяются между собой в соответствии с топологией транспортной сети.

Нижние границы пропускных способностей ветвей в виде про­ порционального количества импульсов заносятся устройством вво­ да — вывода через устройство управления в задатчики потоковых ог­ раничений элементарных процессоров (ЗПО-1). Задатчики ЗПО-1 служат для хранения информации о потоковых ограничениях со­ ответствующих ветвей в направлении от полюса 1 к полюсу 2, а в ЗПО-2 — в противоположном направлении.

Определение минимального потока транспортной сети осущест­ вляется следующим образом. Вначале отыскивается допустимый поток в сети. С этой целью устройство управления находит на сети

элементарных процессоров произвольный путь, соединяющий на­ чальный узел с конечным и содержащий хотя бы одну ветвь с нену­ левой нижней границей пропускной способности. После этого блоки выбора потокового ограничения ветвей, принадлежащих выбран­ ному пути, выдают сигнал в формирователи потокового ограничения ФПО-1 в случае, если в ветви ненулевая нижняя граница пропуск­ ной способности, и в ФПО-2 — если нулевая.

Формирователи потоковых ограничений ФПО-1 выдают сигна­ лы на вычитание импульсов в ЗПО-1, а формирователи потоко­ вых ограничений ФПО-2 — сигналы на сложение импульсов в ЗПО-2.

В элементарные процессоры выбранных ветвей после этого устройством управления посылаются импульсы, которые если в ветви ненулевая нижняя граница пропускной способности, вычитаются

вЗПО-1, если же нулевая пропускная способность, то складываются

вЗПО-2 и так до тех пор, пока нижние границы потоковых ограниче­ ний этих ветвей не станут равными нулю. Это соответствует пропус­ канию потока такой величины, что во всех ветвях выбранного пути удовлетворяются наложенные ограничения. Приход же импульсов

вЗПО-2 соответствует избытку потока через ветвь с нулевой нижней границей потокового ограничения. Если ветвь с нулевой нижней гра­

ницей потокового ограничения принадлежит нескольким путям, то в ЗПО-2 суммируются все избытки потока через эту ветвь.

Указанный процесс осуществляется в устройстве до тех пор, пока не станут нулевыми потоковые ограничения всех ветвей, которые первоначально были записаны в ЗПО-1.

Импульсы, соответствующие потоку через каждый выбранный путь, суммируются блоком регистрации потока.

Суммарное количество импульсов блока регистрации потока будет соответствовать допустимому потоку транспортной сети, так как нижние границы потоковых ограничений всех ветвей будут удовлетворены. При этом через некоторые ветки (а возможно и во всей сети из начального узла в конечный) будет протекать из­ быточный поток и, вычитая его из допустимого потока, найдем иско­ мый минимальный поток транспортной сети.

С целью минимизации найденного допустимого потока устройст­ вом управления отыскивается какой-либо путь из начального узла сети в конечный, проходящий только по ветвям с ненулевым избы­ точным потоком. Если такой путь существует, то подается сигнал на уменьшение потока в ветвях, составляющих этот путь (в задатчи­ ках ЗПО-2). Одновременно увеличиваются избытки потока в тех же ветвях в противоположном направлении (в задатчиках ЗПО-1). Как только в одной из ветвей выбранного пути величина избыточно­ го потока станет равной нулю (в задатчиках ЗПО-2), отсчет импуль­ сов прекращается и из начального узла в конечный отыскивается новый путь с учетом пропускных способностей ветвей, записанных в задатчики потоковых ограничений ЗПО-1. Одновременно с опре­ делением избыточного потока через сеть производится его вычита­

,1 6 4