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

КАЗАНСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ и ОРДЕНА ДРУЖБЫ НАРОДОВ АВИАЦИОННЫЙ ИНСТИТУТ им. А. Н. ТУПОЛЕВА

На правах рукописи

Трегубов Владимир Михайлович

Разработка математического и программного обеспечения оптимизации проектных решений на имитационных моделях

Специальность 05.13.12 — Системы автоматизированного проектирования в промышленности

Автореферат диссертации на соискание ученой степени кандидата технических наук

Казань - 1991

КАЗАНСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ И ОРДЕНА ДРУЖИ НАРОДОВ АВИАЦИОННЫЙ ИНСТИТУТ ян.Л.И.ТУПОЛЕВА

На права;; рукописи

ТРЕГУБОВ ВЛАДИМИР МИХАЙЛОВИЧ

РАЗРАБОТКА .МАТЕМАТИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ОПТИМИЗАЦИИ ПРОЕКТНЫХ РЕШЕНИЙ НА ИМИТАЦИОННЫХ МОДЕЛЯХ

Специальность 05.13.12 - Систеш автоматизированного проектирования з промдиеппости

"Автореферат диссертация па соискания ученой степени кандидата тонтпескнх паук

Казань - 1991

"Работа выполнена на кафедре прикладной математики Казанского Ордена Трудового Красного,. Знамени химико-технологического института им.С.М.Кирова

Научный руководитель:

д.т.н., профессор Б.В,Скворцов

Официальные оппоненты:

д. т. н. , профессор И.1!.Дорохов (¡'.Москва) к.т.н., доц. М.М.Бер;геев (г.Казань)

Ведущая организация:

Казанский филиал Института проблей инфориатики АН СССР (г.Казань)

Зацита диссертации состоится 192^^.

в ^^ часов на заседании специализированного Совета К 063.43.03 в Казанском авиационном институте им.А.Н.Туполева по адресу.420111, г.Казань, ул.К.Маркса,10, зал заседаний. ^

С диссертацией мокно ознакомиться в библиотеке института.

Автореферат развезен "0,0" 4 ШСйЬ/, *>> 19Э1г

Ученые секретарь

.-нециализкросашюго Ссьетс , '

Общая характеристика работы

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

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

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

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

В соответствии с этой целью задачами диссертационной работы являются:

- постановка задачи оптимизации проектных решений на имитационных моделях;

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

задачи;

- исследование эффективности разработанных алгоритмов;

- разработка пакета прикладных программ для- имитационного моделирования сложных систем;

разработка диалоговой системы оптимизации проектных решений на имитационных неделях и методики ее применения для решения задач оптимального синтеза;

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

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

Научная новизна работы заключается в следующем:

- разработай и исследован локальный алгоритм для решения дискретных задач стохастического программирования;

- разработан к исследован локальный иерархический алгоритм для решения дискретных стохастических задач оптимизации повышенной размерности;

- для задач целочисленного стохастического программирования разработал к исследован алгоритм, основанный на замене исходной задачи непрерывной и применения к последней методов стохастической аппроксимации,

- для имитационного моделирования сложных дискретных систеы разработан пакет прикладных програии ПМДС-СОРТРАН с входные языкои типа ОРЗЗ и шрокими иоделируввдак возможностями ;

- разработана структура, пряицэтк функционирования к методика применения пакета программ ДЙСОЙ для диалоговой оптимизации проектный решений на имитационных моделях.

Практическая ценность. Пр0АЛ08:сниие "деленные методы и процедуры реализованы с виде раО.-тах срытзкм на языке ФОРТРАН для наиболее распространенных классов ЗРИ: ЕС ЭВМ, СМ ЗБ!4, НЭЗ!5. На основе этих програи:: разрабстеа диалоговый пакет ДНСОН для оптимизации по ккитоцяотшй иодсхяв. Внедрение пакета г. проектных к исследовательских организациях позволяет з 1.5-2 раза сократить в ревя решения задач овтятхыюго синтеза .

Реализации результатов работы. Пакет прикладных- програии

ПМДС-ФОРТРАН и комплекс програни по оптимизации имитационных моделей внедрены в Казанском научно-исследовательском институте вычислительных систем с годовым экономический эффектом 20.5 тыс.рублей, внедрены в КАИ в учебной процессе по дисциплинам "Моделирование систеи" , "АСНИ" и р учебно-исследовательской САПР АСУ ТП испытаний авиационных двигателей. Результаты диссертационной работы использована при выполнении Межвузовской научно-технической программы 'Автоматизация научных исследований" на 1986-1990 гг., утвержденной приказом Минвуза СССР от 5.08.86 г. Пакет прикладных програиы ПМДС-ФОРТРАН сдан в ОФАП ГИВЦ Минвуза РСФСР, а такае удостоен серебряной медали ВДНХ СССР.

Апробация работы. Диссертационная работа, отдельные ее разделы и результаты обсуждались на II симпозиума по метода« решения нелинейных уравнений и задач оптимизации (Таллинн, 1981), на девятой отраслевой научно-технической конференции молодых ученых и специалистов "Технология проектирования я внедрения средств вычислительной техники" (Казань, 1985), на республиканской научно-практической конференции "Автоматизация управления производством и технологическими процессами с применение!! ыики- и кикро-ЭВН" (Казань, 1Э85г), на республиканской научно-практической конференции молодых ученых, специалистов и студентоз "Порышеиие Эффективности технологических процессов химических, нефтехимических и биотехнологаческих производств" (Казань, 1906), на II Всесоазной конференции "Перспективы и опит внедрения статистических нетодов в АСУ ТП"(Тула,1Э87), на Всесоюзной школе передового опыта "Технические и програниннз средства для распределенной обработки данных в сетях ЕС ЗВ'Г (Уосквч,1988), на Зсесоязноа научно-техническом совещании "Интеллектуальные систегы в задачах проектирования, планирования а управления з условиях неполноты информации" (Казань,1990), на квфгдрах прикладной математики Казанского хиавко-теяпологмчесхого Эдз-титута и Казанского авиационного института.

Публикации. По теме диссертации опубликовано 10 научных работ.

Структура и обьеа работы. Диссертации состоит из введения, четырех глав, заключения ( страницы, // рисунков, .5" •.\ae-~

лиц), а также списка литературы и трех приложений.

На защиту выносятся:

- локальный алгоритм решения задачи дискретного стохастического программирования для оптимизации проектных решений на имитационных моделях;

- иерархический локальный алгоритм решения задачи дискретного стохастического программирования;

- алгоритм решения задачи целочисленного стохастического программирования;

- пакет прикладных программ [ЩС-ФОРТРЛН для имитационного моделирования сложных дискретных систем;

- диалоговая система ДИСОИ для решения задач оптимизации проектных решений на имитационных моделях;

- методика применения системы ДИСОИ при оптимизации проектных решений в САПР;

- применение разработанного математического и программного обеспечения для'реиания практических задач.

Содержание работы.

Во введении дается обоснование актуальности темы диссертации, форщ^ируютса цель- и основные задача исследования, указывается цовдзно к практическая и§иш>е?1> подученных . результатов, в рйвр краткой ащшташде рщ'.суьается основное содержание работы.

В первой главе сформулирована задача оптиилзацик проокт-ных решений на иуитавдюннын моделях. Анализ обцсй методологии применения и1Д1тащ;он)юго моделирования ОШ) в САПР показывает, что оптимизация на основе имит&циошкк моделей тесно связана с проблематикой планирования экстремального имитационного эксперимента. Ваиньш здесь является создание аффективных программных средств описания цоделей проектируемы]! систем и разработка численных уетодов и програиииих ср^ дсте оптимизации, учитизагидих спещ&Чнсу имитационного цоделкрова-нип.

Задача оптимизации проектных ранений для систаш-:, описываемой ииитацкониой ноделыа, ставится в следувксу гаде.

ООозначаа набор проектных варауетррр,, ра который про-

нстодит ТЯРИшизакия, овкторои X, Р0(1) - значение функционала эффективности работы системы, которое реализуется при заданно« наборе параметров. Тогда получим

Р0(х) -> ехЬ, (I)

■хеХ=Х'ПХ-.

где ХМхеХ^Лх) <0,Ы,И) - ограничения, заданные неявно с поыощьэ имитационной подели, принадлежность ХЕХ' может бить проверена только в ходе ¡шитационлого моделирования, л" = (ХЕХ:

Г ¿(.Х) < 0, ¿=Л!+1,-?) - ограничения, заданные явно з аналитическое виде. Г0(Х) также может определяться с понощью !1!4.

Задача (I) является задачей математического программирования, в которой ряд ограничений иди целевая функция заданы не в явной виде, а алгоритмически с поыощьа нодеаирувщего алгоритма.

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

Обозначим Ш - произвольную имитация процесса функционирования проектаруеуоЯ систгги. Будем считать, что СО носит «лучайный характер, т.е. СО - эле?лэнт ззроятностного пространства (52,3" ), которое, в общей случае, зависит от X. Стохастические свойства имитационной модели обеспечиваются наличием датчиков случайкнх чисел, иоделируэдих случайные факторы, влиявшие на проэхтяруевуа систему. Пр'л кгздоа 25К имитационная нодель позволяет вычислить значения случайных

функций характеризующих качество проекти-

рования. Предполагав!!, что ■} -изиарнгы. Необхо-

димо найти такое ХЕХ, чтобы среднее зппченне показателя !о(Х,Ц)) было кшшкалыю при ограничениях на средние значения

показателей ^(Х.Ш) ,¿=1 ,ГП. М::ееп задачу стохастического программирования:

Го<хьП?о(х,и>> -> пхп.

Лх,ы) £0, (2)

хеХ.

Здесь И - символ математического ожидания, усреднение проводится по всей возможный реализациям Ы. К задаче (2) могут быть сведены задачи и с другими вероятностными характеристиками показателей {¿(Х,Ц)') . Если Ш=0, имеем наиболее распространенную постановку задачи иишшизацни имитационного отклика.

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

Ф(2)=Н|(г,ы) Ш1, (з)

геЕсХ,

где 2 - параиетр» проектирования, Е - дискретное множество допустимых значений Е.

Анализ литературы показывает, что на сегодня не существует эффективных иетсдов решения задачи (3).

Отыетна основные особенности задач (3), связанные как с сапой формализацией, так к со спецификой, обусловленной наличием имитационной модели.

1. Наличие дискретных перененных. При Н(рЕ ииитециопная модель по определена п £(Е,М) на нокот быть вычислена.

2. Отсутствие информации о распределении величин {(2,Ы) и повозиоеность точного вычисления значений Ф(Н).В результате прогона имитационной иедэли становятся известными леиь значения реализаций |(Е,СО) ,ЕОИ.

3. Отсутствие, информации о виде и свойствах функций Ф(2), что не позволяет воспользоваться спецификой задачи для построения аффективки-ч катодов ревспия.

Больное число вариантов параметров системы,что делает невозиокньш решение задачи простим перебором.

5. Вычнслепие |Ч2,Ш) и оценка Ф(Е) связаны со значительными вычислительным! слохшостяии.

Заиетик, что модели (1)-(3) сблсдаст достаточно большой омцностьв и могут быть использованы в задачах проектирования и исследования вычислительных снстец , автоматизированных

систем научных исследования и др.

Во второй главе разрабатываются и мсслздувтся численные Методы решения ЗДСГ1 вида.(3).Отмечается, что перспективный подходом к решению этих задач является использование приближенных алгоритмов . Для решения ЗДСП э диссертации предлагается алгоритмы, основанные на идеях ракдошгаации, стохастической аппроксимации-я локальной оптимизация в дискретном программировании . В отличие от известных методов,-эти алгоритмы требует существенно меньших объемов оперативной памяти ЭВМ, остаются работоспособными в случае неизвестного или бесконечного числа допустимых вариантов и могут быть реализованы на ЭВМ с ограниченными ресурсами.

В работе рассматривается случай, когда Z - некоторое подмножество метрического пространства с метрикой 2(1,'i) ,X,ysZ и вначале рассматривается случай, когда Z состоит из конечного множества злеиентов,т.е. Z-{'J j,¿*Í,N}.

Для решения задачи (3) з диссертации осуществляется переход к ее вероятностному аналогу с поиоцьп рандомизации. Для этого вводится дискретная случайная величина Y со значениями

и вероятностями • P(Y=y j>=p j. Тогда вероятностный аналог задачи (3) запкпется в виде

F(P)=2 fí?('¿j,W)P¿ -> ИШ, (4)

Jal

Р=(РРа), jh Рj-i, Р»> О,- Í4SN.

Ja i

В соответствии с локальяии подходом в работе кдется точка 2й:

®(H%n?<^u)bnm ЯГ(г.ы). cs>

2S0r (S*)

где Qr JX ')»{'<?SE:Z(I,3}<2o}.

о.

Далее предполагается, что Ф{3) имеет «."тшстзешша минимум а наядой окрестности радиуса '¿о-

Для ■ решения задачи (5) с пспольэоааакеа иодехи СО в работе лостроеяо иноеэство локальный режэняа xм задали (t) и сформулирован критерия олтаиалькости для задачи (5), который устанавливает соответствие между ревснияки задачи (5) и точками г» К". Этот критерий позволяет реглать задачу (5) а тарна-

нах распределения р.

Алгоритм решения формируется следующий образок. Фиксируется решение е. и строится окрестность этого решения. Выбор точки, в которой производится имитационный эксперимент, осуществляется ь соответствие с некоторым распределением вероятностей р", которое- эдаптяруется к задаче от шага к кагу по форкулаи

рп" , н"*1 Фг"

(6)

где ЗТ::(р) - оператор проектирования вектора р на кнскэс-тво X,• р"=(р 1,...,Рп) - сектор условных вероятностей выбора вариантов на П-сы шаге,

5(н,сс)={реЕг'-. 22 РЛ а>0» ^еЗ(г), РА

¿и 1

3(н")=0:г(й ),гпх го)'.

о , ¿йзс-4).

(% (ад; II(г„,ы)-Д ])/р

??" I

1 0 , £„ -ргелкзьцив случайной велкчиш У с раскрсделеккс:? р" па Е1-0" ил'.?, |С?„,10> - иезаыгскваа от

{'Ой,. О)).....реализация 4ЧЗС.Ш) при Х=Х„,

С" - Н-цериаа векторы, Р„ - величина шага, 0„, -чистине последовательности, А - числовой парааетр, (' ) «торкая Функция.

Р то;; случае, когда одна из компонент вектопа Г1 ' станет СжгэкиГ- к I, происходит переход в новус окрестность, центр

!,>н-0!к'£ гч'фэдолемс!-: кп форпулак

, , - . р"< 1-й » »

■1 1

1,4 , Р» >1-Я „ ,

ири 1-й п.

'¿и „» Рг >1-1.1

0<X<i, P¡,M при Р, =0 при Д п - числовая

"п Н

последовательность, До<0.4, В " - вектор в Е такой,что

„ Г i, ÍGD(H"), I 0, j<£3(zn).

Сходимость алгоритма устанавливается следующей теоремой. Теорема I.

Пусть {(X„,OJ /-независимы для П=0,1,2.. ., I?(Х„, Ш) | < С, ¿UP flCtfdn.WJ-Hfdn.UJ))2}^ j<oo, X„=¡íj, ¿ Pn=°°,

п: 1

£ а* /ап«х>, S an=°°, 2 |pM<Xn+i-o<.nUv

n«i nsl nal

v п«о(рп),рп>0,а„>0,апе(0Л /М„),ап-»0,а„ /д „->0.

Тогда любая сходядаяся подпоследовательность из {р"), определенной согласно (6), сойдется почти наверное (п.н.) к множеству X* . -

В диссертации проводится доказательство теоремы, 'разра-батывавтся модификации алгоритма (6), а также показывается, что алгоритм (6) работоспособен и в случ'ао, когда Ъ содержит счетное множество точек.

Далее в работе рассиатривается случай, когда число точек, попавших в окрестность, оказывается слишком больсим и ал-горити (6) сложно реализовать. Для этого случая в диссертации предлагается использовать иерархический подход совместно с локальной схеиой. Такой подход позволяет произвести декоипозицив задачи и уменьшить размерность подзадач, решаемых на каждом саге.

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

. ии множества Xi={ X*{ií),K=l,Ni ), Mi - общее количество подмножеств, на которое оказывается разбито иночество Z. Точки НЕЕ, попавшие в ыножество l'uO, считаются злеиен- .

таки шюжсства Хг(К)={ Хг(j),j=l,Nj(K) }. И2(К) - число точек,попавших в Х1(К). Тогда каждый злеиент EEZ представи виде пары H=(I'<Ю ,Х2( j)) и f<Z, (jü)=|<X*<Ю ,Х\ j).gü )=(« ¡.

Поиск ревения задачи (3) в райках локальной txeuu выглядит следусзд'м образом.-Фиксируется точка НбЕ, окрестность

этой точки и строится разбиение этой окрестности. Для' даив-ния в окрестности в соответствии с некоторым распределение!! выбирается одно из множеств разбиения (элемент из X, с учетом значения Х1(К)бХ1 выбирается элемент Ха(})йХз(К) и в точке (X 1(К) ,Х2(¿)) вычисляется В соответствии со зна-

чением производится адаптация распределения выбора то-1 2 '

чек (X (К),Х (<))) таким образом, чтобы с течением времени вероятность выбора оптимального варианта стреуилась к I. Для адаптации предлагается адаптивный проекционный алгоритм автоматного типа с усреднением.

Для построения такого алгоритма■вводится случайная величина со значениями Х1(К),К=1,Н 1 и вероятностями

Р(У 1=Х1(К))=р„, Ы^гй случайная величина Уг со значе-Пиями X (<}) и условными . вероятностяии

Р(У2=Хг(<})|У1=Х1(К))=Р^ Тогда взроятность

выбора варианта (X'(К) ,Х2(<})) равна

Р('Л-х '(к) ,У2-х '( I)) ¿р «р.

Обозначай Ч=(Р(Г>, 1)>К=1»Мц¿=1»Мг{К)) - вектор вероятностей вы-1 бора вариантов Е£'£.

В работе в терцинах распределений Рх и р,^ форкйру- . ется вероятностная цодедь задачи (3), строится ино-хество X лоЧ кальных решений этой додели и формулируется достаточное условие оптимальности задачи {5)> ставящее в собтвегстзнв точкам. 9*ЕХ*логальшэ. ргаенйя задачи (5).

Алгоритм рекенкя задачи. (5) формируется езедукции образом.

Адаптация вероятностей Р*,К=1»М1 осуществляется по алго-рятиу ■

где р*г<р1,... ,ра") - вектор условных, вероятностей выбора паразитов из 1ц на Пгои шаге,,

Рм=1, если £ принадлежит шшжветлу .в .окрестности точки

. и р°=0 в противном случае,

5(2п,а)={ рбЕ Е р«=1,Рк> а.,к5Э(нп),р,,=0,х$3(2п) } ,

кя 1

1*=

где

•О , ¡^3(2"),

% ((Х^=Х 1(К))(^(1п Дп" (.0)- А ))/р" , К£Э(НП ),

о , Г.й3(г"),

Эга^Ск^ЧюсОг (нп)),

2 " - Манерные векторы, А - числовой параметр, (Х„, - числовые последовательности,Яп - величина гаага,

1 V 2

£„ - реализация случайной величины I! на П-ом шаге, Х„ -реализация случайной величины Уз на П-ои шаго, X <• ) - индикаторная функция.

Адаптация вероятностей р^ осуществляется, по алгоритму

■10

»„*« > '

(3)

4 г 1

Р'<п - зехтор условных вероятностей зыаора лархантов ;;з ¡агоиест-ва Х2(Н) на Л-оа ггаге,

Если Н. принадлежит К-ну ипонеству з окрестности этой точхи.то Р°"=1 при Нп + 1={21(к),хг{^)) -я Р^М) з проткано?) случае; р°ч -произвольное . 'распределение,если ' гп+1 пе прияадакетт ГС-иу йио-кестау.

зГ^]п-:)Г). хзЗш"),

„ Н Г» + 1

ЭJ . .=

аг=

О , яйЗ(2"),

^«'(Юд'иу.ы)- Л , 2=(Х'(К) ) 30Р (3я),

9 , г'Ш) 1*0,. (а11).

Условие перехода в новую окрестность запишется в виде , н", РГ Р"л< 1-Дг, , ДЛЯ всех * .¿=1,М2(К),

Н=(11(К*),12(^если р„г > 1-Д „ ,

ГД n , р" P"j < 1-JU „ , для всех K=i,N„j=í,N2(K),

Д n+l =

,если Рк" > i-Д п •

Здесь Рп - величина шага, OCn,Qn,JLin - числовые последовательности, 9С "" - последовательности ^(Ю-мерных векторов, 0< X <1, 6¡?=1, если в противной случае.

Условие сходимости алгоритма (7)-(9) устанавливается следующей теоремой. ■ -

Теорема 2.

Пусть для всех fl=0,I,2... совокупности { |(X¿,X2,U) } и { ((aí,I?,00),Is,lí,t=i,n-l,¿=l,n )- независимы,

llííH.u» |¡ <С, zeZ, ¿UP ¡•){(f(i^iñ.U))-Hf(i¿,xí,u)))}=6L<°°,

г»

где aó^YK), x2=x2(j), Pi, >0, pñ >0, cC>0, añ >0,

(X nE(O,I/N), а такке выполняются следующие

условия:

, £ añoua,;=°o , 2 £ <aj2/cxn < °° ,

nil nal nel • n*l

S(pjVa,;< со , Zl(p"j<xj 2< °° , 2(pñ)2< ,

net nsl n«l

n-» •• ПВ i nal

ü¡3 p'jp"n < °° , Д „ > ttnCxñ .

n^ «

Тогда двоая сходящаяся подпоследовательность из {ч"} . определенной согласно (7) - (9), сойдется почти наверное (п.н.) к шюгсеству решений X

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

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

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

Одной из специфических особенностей КМ является то, что в процессе моделирования имеется возможность управлять случайны'»: входными воздействиями и "тем самым влиять на дисперсию выходных показателей ноделей путем применения метода зависимых испытаний. В диссертации показано, что метод зависимых испытаний коясет бить применен в разработанных алгоритмах при оптимизации на имитационных моделях, и построены вычислительной схемы алгоритмов.

Эффективность разработанных методов оценивается в работе с помощью вычислительного эксперимента на ЭВМ типа 1Вп РС/АТ.

Вычислительные эксперименты показали,* что в тех задачах оптимизации проектных решений на имитационных моделях, гдо время моделирования мало (обращение к модели занимает 0.0001 сек.и менее), разработанные алгоритмы уступают методам типа случайного•поиска по времени репения. В задачах, где основное время приходится на обращение к {агитационной модели, разработанные в диссертации алгоритма вйоктивпоо алгоритмов типа случайного поиска. Кетодо зависишь испытаний способна существенно- (на порядок) увпзтать эффективность разработанных алгоритмов. В диссортсцк*: приведены графики и таблицы, которые галастрпруит возиокностя разработанных методов.

рашг ДЙСОИ для оотшшгсцга дискретных систем на- имитационных моделях;

Эффективное решен«* поставленных в диссертации задач возковло лквь при обьедшевпк чьеденных методсг, и программны}: средств ДЛЯ ИХ реиакг.я » програивнь'З комплекс - диахо-

говуи систему, вклачаылуп в себя эффектившга сргдства имитационного «одва1!рова1шя к оп'пигсэецдк.

НПП £1X03 прсдшгздоьдо рекония в диалоговом режима :.;;дач оптеетмщвк проекта р-г„ епкй сяояснх дискретных скстсгс па имитациокиня кодояг (в!гпгсд!ителышх, производственник, траиснортннх и др.)

ШШ ДИС0-' позволяет:

даотся описание пакета прикладных прог-

-в диалоговом режиме настроить пакет на требования пользователя: параметры объекта моделирования, размерность решаемой задачи, тип ЭВМ и т.д.;

-разработать имитационную, модель исследуеиого объекта с использованием входного языка пакета;

^в диалоговой режиме сформировать задачу оптимизации и скомпоновать программу решения задачи, экономную по ¡использование ресурсов ЭВМ;

-выполнить имитационное моделирование и оптимизации, осуществляя интерфейс между имитационной иодельв и цетодами оптимизации по управление и данный;

-осуществлять диалоговое управление ходом решения задачи Система ДИСОМ состоит из управляющей программы (УП), системы имитационного моделирования (СИМ), системы оптимизации (СОП), макрогенератора, средств генерации системы, подсистемы управления прерываниями.

Управляющая программа слуаит для инициализации пакета и передачи управления функциональным подсистемам ППП.

Система имитационного коделирования(СИМ) является имитационной компонентой пакета и предназначена для создания имитационных иоделвй дискретных систем и выполнения их на ЭВЙ с цельв вычисления значений показателей эффективности иселедуе-иого объекта.

Ядром СИП является разработанный и реализованный в диссертации пакет прикладных программ 1ВДС-Ф0РТРАН, который предоставляет пользователю все функциональные возможности по моделировании систем, имевшиеся в СРББ V и, кроне того, все языковые средства Фортрана. Последнее обеспечивает пакету ряд принципиальных преимуществ перед ЕР55 V: интерфейс мода/вывода (и, следовательно, возиошюсть работы с базами данных, диалог с пользователем), открытость, мобильность, вычислительные возможности Фортрана и т.д.

Одниа из существенных отличий ПНДС-ФОРТРАН от.своих аналогов яадяется возможность использования иакрогенератора, что позволяет решить две важные задачи:

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

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

Кроме этого, ГШДС-ФОРТРАН иыеет расширенные возможности по моделированию, управлению моделированием, что делает его эффективны« средствои для описания имитационных моделей сложных дискретных систем.

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

Макрогенератор является основным средство« формирования рабочих программ пакета. Он служит транслятором с входного языка пакета ПМДС-ФОРТРАН в программу на Фортране, а также для связи компонент ДИСОН в единое целое через интерфейсы СИЗ и СОП. В качестве макрогенератора используется макрогенератор языка RATFQR ОС РВ СМ ЭВМ, в которой были проведепы необходимые доработки с целью обеспечения мобильности макрогенератора.

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

ДИСОМ обладает высокой мобильностью. Он функционирует на ' галых ЭВМ типа СМ-4 в операционных системах ОС РВ и РАФОС, на персональных ЭВМ типа IBM PC в операционной систеие IS DOS. Имитационная компонента пакета реализована также на ЕС ЭВМ в : ОС ЕС. Пакет реализован на языках ФОРТРАН-« и ФОРТРАН 77. Часть компонент пакета реализована с использование« средств операционной систоиы, в которой он функционирует (процессор косвенных командных файлов в ОС РВ, интерактивный макропроцессор ПАГЕИ в ОС РАФОС и др.). ППП ДИСОМ ярлястся полностью открытый для расширения, модификации, развития, связи с другими программными средствами и ППП. Программное обеспечение (пзкета имеет модульную структуру.

Важной составной частью диалоговой системы является методика применения ДИСОМ в автоматизированном проектировании. В диссертации приводятся основные этапы иетаднш: к дается их

Т®рак1ёрис тика.

В четвертой гдаве с использованием разработанного в диссертации математического и программного обеспечения решена 5 задача синтеза оптимальной структуры локальной вычислительной сети (ЛВС) в цехе производства многослойных печатных плат (МПП).

На основе анализа организационной структуры и процесса производства ИПП в работе сделан вывод, что целесообразной формой организации комплекса технических средств системы управления цехом является двухуровневая иерархическая локальная вычислительная сеть. В диссертации разработана концептуальная модель ЛВС, имеющей шинную топологию. Данная концептуальная модель ЛВС явилась основой для построения математической модели системы и решения задачи синтеза.

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

В качестве варьируемых параметров выбраны количество и тип ЭВМ на верхнем уровне сети, тип системы передачи данных, длина кадра информации. В качестве критерия оптимальности предложено использовать критерий сбалансированности системы, который устанавливает компромисс иекду стоимостью и производительностью ЛЕС.

С использованием програжлшя средств ПГШ ЛПСОУ разработана имитационная модель ЛВС в цехе 1ШП. Работа с пакетом Дй-ССШ показала, что имитационная компонента системы - пакет прикладных програии ГШДС-ФОРТРАН - является мощный' и удобиыа средством разработки № слокныж реальных састэы.

С использованием програишшх средств ПГЗП ДИСОМ решена задача синтеза оптимальной структуры ЛВС. Машинное эксперименты показали, что разработашшй пакет является эффективным средством оптшшзацик проектных резаний сложных реальны" систем на имитационных воделях. Требуемое машинное время для решения реальных задач иетодани, разработанными в диссертации, б 2. 5-3 раза меньзе, чем методами случайного поиска. В диссертации приведены графики и таблицы, характеризующие процесс решения задачи, а такае параметры подученной структуры.

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

Основные выводы и результаты

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

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

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

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

5. На численных примера:: исследована вффехтивность предложенных алгоритмов, установлены пределы их целесообразного применения. Экспериментально' показано, что для широкого класса задач оптимизации по имитационным моделям (для задач со значительными затратами времени на моделирование) метода, разработанные в диссертации, эффективное известных алгоритмов типа случайного поиска.

6. Разработан пакет прикладных программ ДИСОИ для реса-ния в диалоговом режиме задач оптимизации проектных ресений на имитационных модоляк дхя екрокого кяасиа дискретных систем. Ядром имитационной компоненты системы является разрабо-

танный в диссертации пакет прикладных программ ПМДС-ФОРТРАН с ркодныи яз г,кои тип а 6Р8Б и широкими моделирующими возможностями. Использование ДИСОМ позволяет сократить сроки и повысить эффективность решения задач оптиуального проектирования.

?.Решение практических задач показало эффективность разработанных численных методов и программных средств оптимизации проектных решений на имитационных моделях для сложь^х реальных систем.

8. Результаты диссертационной работы внедрены в промышленность с годовым экономическим аффектом 20.5 тыс. рублей, использованы в учебном процессе по дисциплинам "Моделирование систем" и "АСНИ", внедрены в учебно-исследовательскув САПР в Казанском авиационном институте. Программные средства, разработанные в диссертации, сданы в ОФАП ГИВЦ Минвуза РСФСР и демонстрировались на ВДНХ СССР.

Основные результаты диссертации изложены в следующих опубликованных работах.

1. Ги&атдинова С.Г., Трегубов В.М. Расчет плена запус-ка-Еыпуска в цехе производства печатных плат//Технология проектирования и внедрения средств вычислительной техники: Тез.докладов девятой отраслевой научно-технической конференции молодых ученых и специалистов. - Казань,1985. - С.25-26.

2. Девяткоз В.В., Пьяиов Г. >4., Трегубов В.Н., Якимов И.М. Система имитационного моделирования сложных дискретных систем на Фортране (Г1МДС-ФОРТРАН)//Тез.докладов11 Всес .конференции "Перспективы и опыт внедрения статистических методов в АСУ ТП"(Гула,2-4 июня 1957г).Ч.2. - Тула,198?. - С.44-45.

3. Зайчик Р.Ш., Кузы-глн Н.В., Трегубов В.М. и др. Архитектура и принципы построения системы оперативного управления цехом производства печатных плат//Авто1гатизация управления производством и технологическими процессами с применением ми-ии- и 1:икро-ЭБа: Тезисы докладов республиканской научно-практической конференции (Казань,ноябрь1985г). - Казань:Татарский ЦНТИ, 1985.-С.95-97.

4. Коркяеико И.А., Трегубов В.М. Алгоритм решения одной задачи целочисленного стохастического программирования//По-вшяние эффективности технологических процессов химических, нефтехимическая и блотехнологических производств:Тез.докладов

;Республиканской научно-практической конференции молодых ученых, специалистов и студентов (Казань,нарт 1986г.). - Ка-аныКХТИ, 1986 .-С .115-116.

5. Корниенко И.А., Трегубов В.М., Девятков В.В. Об оптимизации сложных систем, описываемых имитационными моделями на языке GPSS//B сб.:11 симпозиум по нетодам решения нелинейных уравнений и задач оптимизации.-Таллинн,1981.- Том 2. -С.41-43.

6. Трегубов В.М. Алгоритм решения задачи целочисленного стохастического программирования// Исследование операций и аналитическое проектирование в технике. Межвузовский сборник. - Казань:Кззан.авиац.ин-г. ,1987. - С.96-100.

7. Трегубов В.М. Диалоговая оптимизация дискретных систем на имитационных моделях//йнтеллектуальные системы в задачах проектирования, планирования и управления в условиях неполноты информации:Материалы Всесовзного научно-технического совещания (Казань,15-20 января 1990г). - Казань,1990.-С.27-28.

8. Трегубов В.М. Локальные алгоритмы в задачах дискретного стохастического програимирования//Казан.хим.-технол.ин-т.

Казань,1989.-21с.-Деп в ВИНИТИ 12.06.89, М.3897-В89.

9. Трегубов В.М. Применение методов стохастического программирования в задачах оптимизации СКО на имитационных иоде-лях//Исследование операций и аналитическое проектирование в технике.Межвузовский сборник. - Казань:Казан.авиац.ин-т., 1988.-С.39-44.

10. Якииов И.Ц., Девятков В.В., Пьянов Г.Й., Трегубов В.М. Пакет имитационного моделирования дискретных систем на Фортране//Вичислительная техника социалистических стран. -М.:Финансы и статистика,1989,-Вып.25.-С.II6-I22.

Формат '60x84. Бумага офсетная. Печать офсетная. Печ.л. 1,25. Усл.печ.л. 1,16. Усд.кр.-отт. 1,16. Уч.-изд.д. 1.0. Тираж 100. Заказ

Казанский ордена Трудового Красного Знамени и ордена Дружбы народов авиационный институт .на.Л.Н.Туполева 420Ш Казань, ул. К.Царкса,' 10.

Типография КПО.ВС ■ 420062 Казань, ул. Сибирский тракт, 34.