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

ние из допустимого потока, который был записан в блоке регистра­ ции потока.

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

6.3. МОДЕЛИРОВАНИЕ ЗАДАЧИ О ПОТОКЕ ЗАДАННЫХ ЗНАЧЕНИЙ НА ГРАФЕ

С ПОМ ОЩ ЬЮ КОМБИНИРОВАННОЙ МОДЕЛИ

Близкой к задаче о нахождении оптимальной связываю­ щей цепи является задача о потоке заданных значений, которая состоит в следующем [8].

165

6.4. МОДЕЛИРОВАНИЕ ЗАДАЧИ СИНТЕЗА СЕТИ, ОПТИМАЛЬНОЙ ПО ПРОПУСКНЫМ СПОСОБНОСТЯМ

Суть этой задачи, возникающей при проектировании се­ тей связи, транспортных, информационных систем, электронных и других цепей, состоит в следующем [171]. Заданы требования на возможные величины потоков между парами узлов синтезируемой сети. Необходимо построить сеть на заданном множестве узлов, допускающую заданные величины потоков, сумма пропускных спо­ собностей ветвей которой была бы минимальной. Таким образом, задана функция, определенная на множестве пар узлов г (х, у), имеющая смысл требований на величины потоков между узлами х и у. Необходимо определить пропускные способности ветвей С (х, у) таким образом, чтобы выполнялись ограничения

при этом

р = 2 с (х, у)

х.у

достигала бы возможного минимума. В этой постановке видно, что задача является в каком-то смысле обратной множеству задач о максимальном потоке, где по пропускным способностям С (х, у) определяют величины максимальных потоков между возможными парами узлов V (х , у). Эту задачу формально можно свести к задаче линейного программирования, так как условия (6.1) образуют

2п~ 1— 1 линейных неравенств, соответствующих всем возможным разрезам сети. Однако иметь дело с задачей таких размеров очень затруднительно даже при сравнительно небольшом числе узлов сети. Гомори и Ху [171] предложили комбинаторный метод решения этой задачи, не требующий перебора всех ограничений. Здесь мы построим схему цифровой модели этой задачи, реализующую несколько иной комбинаторный метод, приводящий, однако, к более простым схем­ ным решениям.

Метод реализуется в два этапа. На первом этапе определяется максимум требований на поток в ветвях, относящихся к каждому узлу

Проиллюстрируем это на простом примере, рассмотренном Фордом и Фалкерсоном [171] (рис. 103).

На рис. 103, а изображена сеть из пяти узлов, где около ветвей проставлены величины г (х, у). В кружках узлов в числителе дроби обозначены номера узлов, а в знаменателе — величины узловых доминант (6.2).

На втором этапе осуществляется синтез искомой сети. С этой целью через узлы, доминанты которых не равны нулю, проводят гамильтонов цикл произвольного вида (например, цикл 1—2—3—4—

167

5—1). Всем ветвям этого цикла приписывают пропускные способ­ ности, равные минимуму из доминант узлов (в нашем случае R2 = = 6), и уменьшают на эту величину все доминанты (рис. 103, б). Далее проводят новый гамильтонов цикл через оставшиеся узлы

Рис. 103

(например, цикл 1—3—4—5— 1). Часть ветвей этого цикла ранее могла принадлежать первому циклу. К пропускным способностям этих ветвей прибавляют минимум из измененных доминант узлов (в нашем случае R4 = R&= 1), а новым ветвям приписывают эту величину. Уменьшают, как и ранее, доминанты узлов (рис. 103, в).

168

При этом множество узлов с ненулевыми доминантами уменьшится по крайней мере на единицу (в нашем случае выпадут из рассмотре­ ния узлы № 4 и 5).

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

Рис. 104

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

1 6 9

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

Рис. 105

по соответствующим ветвям. В счетчики Сч2 моделей узлов, имею­ щие одинаковую емкость со счетчиками моделей ветвей, импульсы предварительно не заносятся. Триггеры Тх и Т2 моделей ветвей и узлов устанавливаются в единичное состояние. Из схемы управле­ ния от специального генератора импульсов в модели ветвей и узлов подается серия импульсов с количеством, равным емкости счетчи­ ков. В модели ветвей эта серия проходит через полюса 1, а в модели узлов — через полюса 5. При переполнении счетчиков Счх моделей ветвей соответствующие триггеры 7\ устанавливаются в нулевое состояние и через полюса і и j запрещают поступление импульсов через схему И 3 в счетчики Сч2 модели узлов, связанных с моделью рассматриваемой ветви. После окончания этой серии в счетчиках моделей узлов будут записаны количества импульсов, равные М —

— R[, где М — максимальная емкость счетчиков, a R t — максимум требования на поток по ветвям, связанным с узлом і.

170

На этом заканчивается первый этап работы модели. Второй

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

Сигналы принадлежности ветвей выбранному гамильтонову циклу установят триггеры 7\ этих моделей ветвей в единичное со­ стояние. Импульсы генератора начнут одновременно заполнять счетчики Сч2 моделей узлов и моделей ветвей, вошедших в гамиль­ тонов цикл. Как только переполнится один или несколько счетчи­ ков Сч2 моделей узлов, обладающих минимальной доминантой, триг­ геры Т2 этих моделей установятся в нулевые состояния и запретят поступление импульсов в счетчики моделей ветвей, связанных с этими узлами. Упомянутые узлы выпадут из рассмотрения, и фор­ мирователь гамильтоновых циклов образует новый цикл, не вклю­ чающий выпавших узлов, и так далее, пока не исчерпается содержи­ мое всех счетчиков моделей узлов.

Опрос счетчиков моделей ветвей позволит определить пропуск­ ные способности ветвей искомой сети.

6.5. МОДЕЛИРОВАНИЕ СТОИМОСТНО-РЕСУРСНЫХ РАЗНОВИДНОСТЕЙ ЗАДАЧ СПУ

При проведении оптимизации сетевых графиков по ре­ сурсам, что является основным содержанием задач 2 и 3 (см. § 1.6), необходимо располагать информацией о суммарных величинах ре­ сурсов каждого типа, потребляемых в каждый момент выполнения сетевого графика. Если предположить, что интенсивность потреб­ ления ресурса какой-либо работы не меняется в течение времени ее выполнения, то суммарные ресурсы можно выразить следующей зависимостью:

k-TQ вида, необходимого для выполнения работы (і, /); а (т) — функ­ ция единичного скачка, равная нулю при х < 0 и единице при т > 0.

Как нетрудно видеть, произведение двух функций единичного скачка (6.3) образует функцию единичного импульса (рис. 106, а), а функция RW (t) представляет собой сумму ресурсов одновременно выполняемых работ.

Выбор единицы ресурсов произволен (за единицу ресурса может быть принят один человек или два станка и т. д.). Одним из важных понятий в сетевом планировании и управлении является понятие

171