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

4. Вычисление линейной комбинации величин у =

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

k

где Е — величина напряжения, соответствующего единичному со­ стоянию триггеров на полюсах т,; [(У] — пороговое значение выход­ ного напряжения интегрирующего сумматора, при котором происхо­ дит разряд интегрирующей емкости.

Счетчик результата за время Nif получит количество импульсов

ным коэффициентом, с которым реализуется операция. Реализация единичных функций а (т, — і) обеспечивается тем, что первоначаль­

85

но проводимости £л, gk интегрирующего сумматора подключены к выходным напряжениям триггеров Е, а в моменты времени t = = т£ триггеры изменяют свои состояния и соответствующие про­ водимости подключаются к нулевому напряжению. Схема И обес­ печивает синхронизацию схемы сброса.

Таким образом, схема интегрирующего сумматора с обратной связью по сбросу обеспечивает управляемое преобразование частоты импульсов, питающих счетчик результата так, что в любой момент времени эта частота пропорциональна сумме коэффициентов при аргументах х1г временные интервалы т( которых еще не окончены.

56

Г л а в а 5

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

СТРУКТУР

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

Анализ характеристик электронных моделей задач об экстремальных путях и потоках, построенных с использованием ана­ логии Денниса, позволяет сформулировать следующие их недо­ статки:

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

2)при решении задач об экстремальных путях разрешающая спо­ собность схемы к различению близких по длине путей или их от­ резков оказывается невысокой из-за указанной неидеальности пря­ мой ветви вольт-амперной характеристики диодов;

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

4)суммирование напряжений вдоль экстремальных путей при­ водит к появлению в схемах моделей напряжений порядка сотен

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

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

ляется рядом схемных и методических приемов. Так, автоматизиро­ вать ввод исходной информации можно, применив динамический метод моделирования [117, 151]; разрешающая способность схем по­ вышается, если применить схемы операционных усилителей с дио­ дами в цепи обратной связи [178], эквиваленты отрицательных со­ противлений [57], метод зондирующего источника [167], схемы идеализированных диодов [49]. Уменьшить уровень напряжений, моделирующих искомые переменные, можно, использовав метод сдвига начала координат [44], и т. д.

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

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

8S

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

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

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

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

Одной из задач на сетях является задача о кратчайшем пути, по­ становка которой дана в § 1.2.

В задаче о кратчайшем пути в каждый узел входит несколько ветвей. Из этих ветвей необходимо выбрать ветвь, принадлежащую кратчайшему пути из начального узла сети к данному, и только после этого осуществить просмотр всех ветвей, выходящих из это­ го узла, прибавляя их к кратчайшему пути. Такая модель по прин­ ципу действия реализует алгоритм [191]. Поэтому содержание узла (рис. 48) в терминах булевой алгебры можно записать импликацией, в правой части которой конъюнкция, а в левой части дизъ­ юнкция: