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

пункт при отсутствии ограничении на величину потока по ветвям, т. е.

1-1 = 2 2 С[,хц

Схема, иллюстрирующая пост­ роение электронной модели зада­ чи о кратчайшем пути, приведена на рис. 23. В отличие от модели за­ дачи о максимальном потоке здесь вместо источника напряжения Е между начальным 1 и конечным N полюсами сети включен идеаль­ ный источник тока / . В соответ­ ствии с экстремальным принципом для цепей распределение токов и напряжений в схеме модели такое, что мощность, поставляемая в мог дель источником тока P j = JU, максимальна среди возможных значений, совместимых с ограниче­ ниями (3.25) и (3.26). Поскольку J = const, а в соответствии со вторым законом Кирхгофа

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

чину кратчайшего пути в сети, а совокупность ветвей модели, по которым будет протекать ток J ,— изображать форму этого крат­ чайшего пути.

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

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

иконтуров, подробно рассматривается в § 3.4 гл, 3.

59

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

К нелинейным транспортным задачам мы приходим, когда целевая функция (і становится нелинейной. Общая математическая постановка этих задач имеет вид:

Наиболее частым является случай сепарабельности функции ц:

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

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

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

’и

Дифференцируя обе части (3.32) по верхнему пределу Іц, получим

!И

Введя масштабные соотношения hi — Уіха и произведя необ­ ходимые преобразования, придем к искомому выражению для вольтамперной характеристики:

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

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

£0

полюсные функциональные преобразователи с соответствующим ви­ дом вольт-амперной характеристики.

Частными, но весьма важными нелинейными транспортными за­ дачами являются задачи оптимального распределения ограничен­ ных ресурсов. С целью иллюстрации методов построения электрон­ ных моделей нелинейных транспортных задач рассмотрим две разновидности задачи оптимального распределения ограниченных однородных ресурсов [168].

Предположим, что следует рас­ пределить N поисковых единиц по п районам поиска. Каждый район ха­ рактеризуется различными вероятно­ стями Р,- нахождения в нем искомого объекта и вероятностями Wj, с кото­ рыми единица распределяемых ре­ сурсов (средств) может обнаружить объект в у'-м районе. Если принять предположение о независимости дей­ ствия поисковых единиц, то они мо­ гут обнаружить цель (объект) с ве­ роятностью

/=I

Необходимо определить такое рас­ пределение единиц по районам поиска X/, при котором (3.35) достигнет мак­ симума при выполнении таких огра­ ничений:

(3.36) определяет ограничение на общее число поисковых единиц,

(3.37) ограничивает максимально возможное число единиц, которое можно направить в у-й район.

В известном смысле обратной к этой задаче является следующая. Найти минимальное количество однородных средств и их распре­ деление по районам поиска х/, при которых вероятность обнаруже­ ния объекта была бы не меньше некоторого наперед заданного зна­ чения [|л]:

61

Схема электронной модели прямой задачи (3.35) — (3.37) изобра­ жена на рис. 24, а.

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

Решение обратной задачи на модели рис. 24, а можно осущест­ вить путем регулировки величины тока I N д о тех пор, пока произ­ ведение на величину напряжения U не достигнет величины, соот­ ветствующей необходимому значению вероятности [р].

Задачи распределения ограниченных ресурсов настолько много­ образны, что вопросы их моделирования могли бы составить пред­ мет самостоятельного исследования. Сюда относятся модификации

3.4. ПРИНЦИПЫ ПОСТРОЕНИЯ МОДЕЛЕЙ ЗАДАЧ СПУ НА ОСНОВЕ АНАЛОГИИ ДЕННИСА

Так как временная разновидность задачи расчета сете­ вого графика (задача 1 ) является частным случаем задачи об экстре­ мальных путях на графе без петель и контуров, то для ее модели­ рования может быть использована диодная аналогия Денниса, суть которой рассматривалась выше. Моделью работы сетевого графика, таким образом, будет двухполюсник, содержащий последовательное соединение идеальных диода и источника напряжения, величина напряжения которого пропорциональна продолжительности выпол­ нения работы (рис. 25, а). Модели работ для получения сетевого гра­ фика должны быть электрически соединены между собой в соответ­ ствии с его топологией. К полюсам образовавшейся электронной цепи, изображающим начальное 5 Ни конечное SK события графика, необходимо подключить источник тока I (рис. 25, б). В соответст­ вии с минимальными свойствами цепей постоянного тока ток этого источника потечет по моделям работ, находящимся на критическом пути, а напряжение на полюсах источника тока будет пропорцио­ нально длине критического пути сетевого графика. Схема модели сетевого графика рис. 6 приведена на рис. 25, б.

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

62