Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації

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

Full description

Saved in:

Bibliographic Details
Date:	2009
Main Author:	Тимофієва, Н.К.
Format:	Article
Language:	Ukrainian Russian
Published:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2009
Series:	Управляющие системы и машины
Subjects:	Новые методы в информатике
Online Access:	http://dspace.nbuv.gov.ua/handle/123456789/82743
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації / Н.К. Тимофієва // Управляющие системы и машины. — 2009. — № 4. — С. 43–50. — Бібліогр.: 11 назв. — укр., рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-82743
record_format	dspace
spelling	irk-123456789-827432018-04-07T22:55:45Z Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації Тимофієва, Н.К. Новые методы в информатике Описаны самонастраивающиеся алгоритмы нахождения параметров в системе автоматизированного проектирования печатных плат, которые невозможно задать при определенных условиях, но которые появляются в процессе решения конкретной задачи комбинаторной оптимизации. Эта проблема решается путем введения формальных параметров на этапе подготовки входных данных и динамической перестройкой модели печатной платы. The self-adjusted algorithms of finding the indefinite parameters in a computer-aided printed-circuit-boards, which it is impossible to set in a condition are described, but they appear in the process of solution of certain combinatorial optimization problem. This problem is solved by introduction of formal parameters at a stage of preparation of the entrance data and dynamic reorganization of the model of the printed-circuit-board. Описано самоналагоджувальні алгоритми знаходження параметрів в системі автоматизованого проектування друкованих плат, які неможливо задати за умовою, але які з’являються в процесі розв’язання певної задачі комбінаторної оптимізації. Ця проблема вирішується шляхом уведення формальних параметрів на етапі підготовки вхідних даних та динамічною перебудовою моделі друкованої плати. 2009 Article Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації / Н.К. Тимофієва // Управляющие системы и машины. — 2009. — № 4. — С. 43–50. — Бібліогр.: 11 назв. — укр., рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/82743 519.14+519.168 uk ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian Russian
topic	Новые методы в информатике Новые методы в информатике
spellingShingle	Новые методы в информатике Новые методы в информатике Тимофієва, Н.К. Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації Управляющие системы и машины
description	Описаны самонастраивающиеся алгоритмы нахождения параметров в системе автоматизированного проектирования печатных плат, которые невозможно задать при определенных условиях, но которые появляются в процессе решения конкретной задачи комбинаторной оптимизации. Эта проблема решается путем введения формальных параметров на этапе подготовки входных данных и динамической перестройкой модели печатной платы.
format	Article
author	Тимофієва, Н.К.
author_facet	Тимофієва, Н.К.
author_sort	Тимофієва, Н.К.
title	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації
title_short	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації
title_full	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації
title_fullStr	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації
title_full_unstemmed	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації
title_sort	самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2009
topic_facet	Новые методы в информатике
url	http://dspace.nbuv.gov.ua/handle/123456789/82743
citation_txt	Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації / Н.К. Тимофієва // Управляющие системы и машины. — 2009. — № 4. — С. 43–50. — Бібліогр.: 11 назв. — укр., рос.
series	Управляющие системы и машины
work_keys_str_mv	AT timofíêvank samonalagodžuvalʹníalgoritmiznahodžennâneviznačenihparametrívuzadačahkombínatornoíoptimízacíí
first_indexed	2025-07-06T09:21:49Z
last_indexed	2025-07-06T09:21:49Z
_version_	1836888842245767168
fulltext	УСиМ, 2009, № 4 43 УДК 519.14+519.168 Н.К. Тимофієва Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації Описаны самонастраивающиеся алгоритмы нахождения параметров в системе автоматизированного проектирования печат- ных плат, которые невозможно задать при определенных условиях, но которые появляются в процессе решения конкретной задачи комбинаторной оптимизации. Эта проблема решается путем введения формальных параметров на этапе подготовки входных данных и динамической перестройкой модели печатной платы. The self-adjusted algorithms of finding the indefinite parameters in a computer-aided printed-circuit-boards, which it is impossible to set in a condition are described, but they appear in the process of solution of certain combinatorial optimization problem. This problem is solved by introduction of formal parameters at a stage of preparation of the entrance data and dynamic reorganization of the model of the printed-circuit-board. Описано самоналагоджувальні алгоритми знаходження параметрів в системі автоматизованого проектування друкованих плат, які неможливо задати за умовою, але які з’являються в процесі розв’язання певної задачі комбінаторної оптимізації. Ця проблема вирішується шляхом уведення формальних параметрів на етапі підготовки вхідних даних та динамічною перебудо- вою моделі друкованої плати. Вступ.∗ У теорії прийняття рішень виникають ситуації, які характеризуються певною мірою невизначеності [1–5], зокрема такі, що пов’яза- ні з неповною вхідною та поточною інформа- цією. В літературі при дослідженні цієї пробле- ми основна увага приділяється задачам з нечіт- кими, стохастичними або комбінованими вхід- ними даними (одночасно випадковими і нечіт- кими). Але в задачах комбінаторної оптиміза- ції в різних галузях людської діяльності вхідні дані характеризуються як нечіткою, так і чіт- кою структурою. Для задач, у яких вхідні дані мають чітку структуру, математичні моделі, відповідно і цільова функція, розроблено до- сить ґрунтовно, тому невизначеність для них зведена до мінімуму. Пошуком способів розв’я- зання задач з нечіткими вхідними даними за- ймаються не одне десятиліття, але точної мате- матичної постановки для них ще не розроблено. Незважаючи на спробу строго формалізувати поняття невизначеності, наприклад [5], цим поняттям користуються на інтуїтивному рівні. Для цих задач досить складно змоделювати цільову функцію таку, щоб глобальне розв'я- зання задовольняло дійсну мету дослідження. ∗ Ключевые слова: неопределенность в комбинатор- ной оптимизации, комбинаторная оптимизация, целевая функция, комбинаторная конфигурация, автоматизиро- ванное проектирование, печатные платы, размещение разногабаритных модулей. Постановка проблеми Розглянемо знаходження параметрів в умо- вах невизначеності в задачах з чіткою вхідною інформацією. Ця проблема виникає тому, що прикладні задачі комбінаторної оптимізації складні за своєю природою і розділяються на підзадачі, для розв'язання яких розробляють незалежні алгоритми, за допомогою яких ос- новна задача розв'язується їхньою послідовною роботою або вони працюють як вбудовані про- цедури в ітераційному режимі. Алгоритм, який об’єднує незалежні алгоритми, орієнтовані на розв'язання певних задач, називається гібрид- ним або комбінованим [6–8]. В процесі його роботи при передачі інформації, яка є резуль- татом розв'язання попередньої задачі, на вході наступного алгоритму можуть з'являтися нові, невизначені параметри, необхідні для розв'я- зання чергової задачі і які неможливо задати у вхідних даних за умовою. Виникає проблема знаходження параметрів в умовах невизначе- ності. Такі задачі трапляються і в конструктор- ському проектуванні обчислювальної апарату- ри. Від ефективного знаходження таких пара- метрів залежить зручність в експлуатації пев- них систем, можливість повної автоматизації всього процесу проектування. На прикладі кон- структорського проектування друкованих плат розглянемо цю проблему і опишемо самонала- годжувальні алгоритми знаходження парамет- рів в умовах невизначеності [9]. 44 УСиМ, 2009, № 4 Загальна задача конструкторського проек- тування друкованих плат розділяється на такі підзадачі [10]: задача компоновки базових еле- ментів у модулі, оптимальне розміщення виво- дів базових елементів у модулі і призначення їхніх бібліотечних (реальних) номерів, задача розміщення різногабаритних модулів на пове- рхні друкованої плати, моделювання констру- кції друкованої плати при підготовці її до на- ступного етапу проектування, трасування друко- ваних провідників, контроль топології друко- ваного монтажу, випуск конструкторської до- кументації, формування інформації для при- строїв з числовим програмним управлінням, де є задача комівояжера. У процес проектування входить підготовка електричної схеми і підго- товка бібліотеки постійної інформації. Вхідна інформація в цій задачі розділяється на змінну, яка задається для певної індивідуальної задачі, і постійну, яка однакова для серії індивідуаль- них задач. Постійну інформацію заносять по- передньо в бібліотеку і використовують її в процесі розв’язання задачі на різних етапах. Ви- користання бібліотечних даних економічно до- цільне, коли проектування проводиться для не- великої номенклатури багатосерійних виробів. Але такий підхід економічно неефективний при великій номенклатурі малосерійних виробів та розв’язанні задач, для яких деякі параметри за- нести в бібліотеку неможливо. Їх можна задати лише після розв’язання чергової задачі. Це сто- сується задачі розміщення виводів базових еле- ментів у модулі і призначення їхніх бібліотеч- них номерів та визначення посадкових місць для розміщення різногабаритних модулів. Так, призначити реальні номери виводам модулів можна лише після розв'язання задачі компону- вання, визначити структуру посадкових місць на монтажному полі для встановлення різнога- баритних модулів – після знаходження певного варіанту їхнього розміщення тощо. Уведення цієї інформації в діалоговому режимі досить трудомісткий процес, тому для автоматизації проектування на цьому етапі розроблено само- налагоджувальні алгоритми знаходження не- визначених параметрів. Оскільки на початку розв’язання задачі явно присутні невідомі па- раметри, то вона належить до класу парамет- ричних ситуацій рішення [5]. Розв’язання проблеми Математичну постановку загальної задачі проектування друкованих плат сформулюємо так. Нехай задано електричну схему, яку пода- мо графом G. Множиною A = {a1, …, an} позна- чимо його вершини, кожній aj з яких у відпові- дність поставлено заданий базовий елемент. Позначимо Φ(G) функціональні характеристи- ки заданої електричної схеми. Розміщення ком- понент електричної схеми проводиться на пла- ті, яка являє собою прямокутну поверхню з нанесеною на ній координатною сіткою. Вона може бути одношаровою, двошаровою, бага- тошаровою. Перенумеруємо комірки цієї сітки і їхню послідовну нумерацію подамо множиною },...,{ 1 ξ= ddD . Із елементів aj базової множини A, j ∈ {1, …, n}, утворюється комбінаторна множина W – сукупність комбінаторних кон- фігурацій певного типу (перестановки, розбит- тя тощо), а із елементів dl базової множини D, },...,1{ ξ∈l , утворюється комбінаторна множи- на M – розміщення без повторень. На елемен- тах w комбінаторної множини W і μ комбіна- торної множини M вводиться цільова функція. Тоді задача проектування друкованих плат по- лягає у знаходженні такого розміщення ком- понент заданої електричної схеми на одному або декількох шарах, тобто виборі для розмі- щення елементів w∗∈ W комбінаторної конфі- гурації μ∗ із множини M, для яких уведена ці- льова функція набуває оптимального значення з необхідним виконанням умови ( ) ( )G GΦ =Φ , де ( )GΦ – функціональні характеристики елек- тричної схеми G~ , одержаної із G в процесі проектування. Як було обумовлено, задача проектування друкованих плат розділяється на підзадачі, ар- гументом цільової функції в яких – комбінато- рні конфігурації різних типів [11]. Наприклад, аргументом цільової функції в задачі компоно- вки є розбиття n-елементної множини на під- УСиМ, 2009, № 4 45 множини, задачі розміщення різногабаритних модулів на поверхні друкованої плати і розпо- ділення виводів модулів – перестановка, тра- сування друкованих плат – розміщення без по- вторень. Виходячи з цього, функціонал для по- ставленої задачі запишемо як F(ρ∗, μ∗, ω∗) = ρ μ ω ext (ρ, μ,ω) M F ∈Θ ∈ ∈Ω = , де ρ – розбиття n-елементної множини на підмножини, μ – розміщення без повторень, ω – перестановка, а Θ, M, Ω – їхні множини. Далі опишемо самоналагоджувальні алго- ритми знаходження параметрів, які необхідно задавати як вхідні дані для розв’язання черго- вої задачі і які неможливо задати на початку обчислювального процесу. Оскільки основний результат проектування – оптимальне розмі- щення компонент електричної схеми на платі, то при виборі критеріїв якості, за якими оці- нюється результат розв'язання задачі на окре- мих етапах, ураховується оптимальне трасу- вання друкованих плат. Тобто критерії якості, які задаються на черговому етапі розв’язання задачі, моделюються з урахуванням прогнозу для майбутніх результатів. Виділимо підзадачі, які потребують обчис- лення параметрів в умовах невизначеності. Задача компоновки базових елементів у мо- дулі. Змістовна постановка цієї задачі така. За- дано n базових елементів різних типів, між яки- ми існують електричні зв'язки. Необхідно ці елементи розподілити по корпусах мікросхем так, щоб кількість зв'язків між останніми була мінімальною, або кількість зв'язків між елеме- нтами, об'єднаними у мікросхеми, була най- більшою. Кількість типів, до яких відносяться елементи, і кількість елементів, які необхідно об'єднати за мікросхемами, задано. Після розв’язання цієї задачі необхідно за- дати реальні номери виводів модулів, тобто знайти параметри в умовах невизначеності. Якщо компоновка проводиться довільно, то базові елементи об’єднуються в модулі без оп- тимізації, вручну, а виводам присвоюються но- мери згідно з конструкторськими вимогами. Оскільки призначення реальних номерів виво- дам включає в себе задачу оптимального роз- міщення базових елементів у модулі, то ця за- дача, як і компоновка, не оптимізується, що погіршує умови для оптимального трасування друкованих провідників на наступному етапі. Аналогічна задача призначення реальних но- мерів виводам базових елементів виникає при проектуванні надвеликих інтегральних мікро- схем в процесі розробки типових бібліотечних модулів. Якщо при проектуванні друкованих плат компоновку допускається проводити до- вільно, то при проектуванні інтегральних мік- росхем її розв’язують вручну, в діалоговому режимі і вона є досить трудомістка. Для автоматичного призначення реальних но- мерів виводам базових елементів на етапі під- готовки вхідної інформації присвоюються фор- мальні параметри і задаються типи модулів. Бі- бліотечні параметри генеруються автоматично самоналагоджувальною програмою-генератором постійних параметрів. Управління цією програ- мою проводиться формальними параметрами, які задаються на початку обчислювального про- цесу. При такій організації обчислювального процесу бібліотека не створюється. Побудуємо математичну модель цієї задачі. Нехай в результаті оптимальної компоновки утворено набір модулів, який задамо множиною 1{ ,..., }.t tV v vζ= Кожному елементу Vvt j ∈ поста- влено у відповідність деякий його тип )( t jvP , κ= ,1t , ζ= ,1j , де κ – кількість типів, ζ – кіль- кість елементів у V. Позначимо 1 { , ..., }, tq t t t j j jv a a= Aat jl ∈ множину базових елементів, які вхо- дять у модуль t-го типу, а }~,...,~{ ~1 t j t j t tqlj aaa = – множина формальних номерів виводів j-го елементу t-го типу, де qt – кількість базових елементів у t jv , tq~ – кількість номерів виводів j-го елементу t-го типу. Для розміщення базо- вих елементів t jl a у модулі t jv уведемо уста- новчі позиції, які позначимо множиною t jp = 46 УСиМ, 2009, № 4 1 { ,..., } tq t t j jp p= , а l t jp }~,...,~{ ~1 t j t j tq pp= – відповід- но множина позицій для установлення виводів базових елементів t-го типу. Задача призначення реальних номерів виво- дам базових елементів полягає у заміні їхніх формальних номерів бібліотечними так, щоб для знайденого варіанту розміщення цих виво- дів у посадкових місцях сумарна довжина дру- кованих електричних зв’язків була мінімаль- ною, тобто )(min)( * ω=ω Ω∈ω FF і виконувалася умова )~(~)( GG Φ=Φ . Розміщення базових еле- ментів у модулі і призначення реальних номе- рів виводам варто проводити на останній іте- рації розміщення модулів. Задача розміщення різногабаритних моду- лів формулюється таким чином. Множину мо- дулів, які мають різні розміри, необхідно роз- містити на поверхні плати так, щоб сумарна довжина зв'язків і площа, яку вони займають, були мінімальними, а зазори між модулями дорівнювали заданій величині. Цю задачу мо- жна звести до одногабаритної, використавши алгоритм компоновки базових елементів у мо- дулі з наступним розміщенням одержаних од- ногабаритних блоків на платі [8]. В процесі роботи алгоритму проводиться динамічна пе- ребудова позицій на платі для встановлення модулів, тобто оптимізується вибір посадкових місць для їхньої установки. Це – третя задача, в якій аргументом цільової функції є розмі- щення без повторень. Варіантів розміщення μ ∈ M, утворених із елементів dj ∈ D, може бу- ти багато. Тому в процесі розв’язання задачі розміщення різногабаритних модулів з’являєть- ся нечіткість і невизначеність, а цільова функ- ція залежить від перестановок, від розбиття n-елементної множини на підмножини і від розміщення без повторень. Запишемо для неї функціонал: ( ) ext ( ) Μ F F∗ ∗ ∗ ρ∈Θ ω∈Ω μ∈ ρ ,ω ,μ = ρ, ω,μ . На етапі розв'язання задач розміщення мо- дулів і трасування друкованих провідників не- обхідна інформація про конструкцію друкова- ної плати. Як правило, її модель попередньо описується і заноситься в бібліотеку. Оскільки електричні схеми відрізняються одна від однієї елементною базою, то така підготовка прово- диться або для серії індивідуальних задач, або для кожної схеми окремо. При попередній під- готовці моделі плати її поверхню, як правило, розбивають на смуги різної ширини, на кожній з яких можна установлювати модулі певного габариту. Тобто нечіткі параметри, якими є по- садкові місця для розміщення модулів і які ут- ворюються вибиранням елементів dj ∈ D, «огру- блюються». В результаті одержується чіткий, але не оптимальний результат. До того ж така підготовка моделі плати ускладнює експлуата- цію системи та обмежує її можливості. Сформулюємо математичну постановку і опишемо обчислювальну схему самоналагоджу- вального алгоритму знаходження параметрів в умовах невизначеності при розміщенні моду- лів і побудові моделі друкованої плати. Позна- чимо 1{ ,..., }rΥ Vυ υ= ⊂ множину модулів, ко- жен з яких має найбільші габарити, r ∈ {1, …, n}; },...,1{ nr∈ ; 1{ ,..., }rΥ Vυ υ= ⊂ – множину мо- дулів, кожен з яких має найменші габарити; }~,...,~{~ ~1 kkk vvV ζ = – множину модулів, утворену із заданої множини модулів V на k-й ітерації. Задамо }~,...,~{~ ~1 ξ = ddD – множину позицій для установлення модулів із ,kV утворених на k-й ітерації. В процесі роботи алгоритму проводить- ся динамічна перебудова моделі плати. Суть цього алгоритму полягає у проведенні послідов- них кроків, на кожному з яких задані елементи електричної схеми об’єднуються в модулі. На сформованому із найменших комірок коорди- натної сітки, яким відповідають елементи мно- жини D, регулярному полі позицій розміщу- ються модулі kk j Vv ~~ ∈ . Цей процес відбуваєть- ся доти, доки не буде розміщено найменший за габаритами модуль. Встановлення модуля Vvt j ∈ на платі про- водиться шляхом обчислення установчих ко- ординат ),( t j t j ll yx для його виводів за виразами: ),,,(0 τηοκ+= fxx j , ),,,(~ 0 τηοκ+= fyy j , де УСиМ, 2009, № 4 47 0x , 0y – базові координати для установлення модуля t -го типу, які визначаються за резуль- татами розміщення Vvt j ∈ , κ – тип модуля, ο – тип орієнтації модуля на платі, η – кількість виводів модуля t-го типу, τ – відстань між ви- водами модуля t-го типу. Модулі за типами класифікуються згідно з побудовою їхніх кор- пусів. Такий підхід дає можливість повністю автоматизувати розв'язання задачі розміщення різногабаритних модулів і підготовку моделі друкованої плати для подальшої автоматизації процесу проектування. Висновок. Уведення формальних парамет- рів на етапі підготовки вхідних даних та дина- мічна перебудова моделі друкованої плати до- зволяють знаходити параметри в умовах неви- значеності, що забезпечує повну автоматиза- цію проектування друкованих плат. Запропо- нована організація обчислювального процесу дозволяє перелаштовуватися на різні типи ін- дивідуальних задач, не потребує попередньої підготовки бібліотек, що є досить трудомісткою роботою, спрощує експлуатацію систем авто- матизованого проектування. 1. Трухаев Р.И., Лернер В.С. Динамические модели процессов принятия решений. – Кишинев: Штиин- ца, 1974. – 264 с. 2. Иваненко В.И., Лабковский В.А. Проблема неопре- деленности в задачах принятия решений. – К.: На- ук. думка, 1990 – 136 с. 3. Обработка нечеткой информации в системах при- нятия решений / А.Н. Борисов, А.В. Алексеев, Г.В. Меркурьева и др. – М.: Радио и связь, 1989. – 304 с. 4. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. – М.: Наука, 1981. – 208 с. 5. Іваненко В.І. Проблема невизначеності в теорії рі- шень і теорії керування // Матеріали XIII міжнар. конф. з автоматичного управління «Автоматика- 2006», Вінниця, 25–28 вер. 2006 р. – Вінниця, 2006. – С. 38–46. 6. Корбут А.А., Сигал И.Х., Финкельштейн Ю.Н. Ги- бридные алгоритмы в дискретной оптимизации // Изв. АН СССР. Техн. кибернетика. – 1986. – № 1. – С. 65–77. 7. Гуляницкий Л.Ф. Разработка гибридных методов дискретной оптимизации на основе G-алгоритмов // Компьютерная математика. – 2005. – № 1. – С. 143–151. 8. Гуляницкий Л.Ф., Тимофеева Н.К. О размещении разногабаритных элементов на печатных платах // УСиМ. – 1982. – № 3. – С. 50–53. 9. Тимофієва Н.К. Знаходження параметрів в умовах невизначеності при розв'язанні задач комбінатор- ної оптимізації гібридним алгоритмом / Міжнар. наук. конф. «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту (ISDMCI’2008)». Зб. наук. пр. у 3-х т. – Т. 2 (Ч. 2). – Херсонський нац. техн. ун-т. – Євпаторія, 2008. – С. 73–76. 10. Тимофеева Н.К. Вопросы разработки алгоритмичес- кого и программного обеспечения, предназначен- ного для решения одного класса задач конструктор- ского проектирования цифровой аппаратуры: Ав- тореф. дис... канд. физ-мат. наук / Ин-т кибернети- ки им. В.М. Глушкова АН УССР. – К., 1984. – 24 с. 11. Тимофієва Н.К. Теоретико-числові методи розв'я- зання задач комбінаторної оптимізації: Автореф. дис. ... докт. техн. наук / Ін-т кібернетики ім. В.М. Глушкова НАН України. – К., 2008. – 32 с. Поступила 08.01.2009 Тел. для справок: (044) 526-6332 (Киев) © Н.К. Тимофеева, 2009 Н.К. Тимофеева Самонастраивающиеся алгоритмы нахождения неопределенных параметров в задачах комбинаторной оптимизации Введение. В теории принятия решений возникают си- туации, характерные некоторой степенью неопределен- ности [1–5], в частности, связанные с неполной входной и текущей информацией. В литературе при исследова- нии этой проблемы основное внимание уделяется зада- чам с нечеткими, стохастическими или комбинирован- ными входными данными (одновременно случайными и нечеткими). Но в задачах комбинаторной оптимизации, наблюдаемых в различных отраслях человеческой дея- тельности, входные данные характеризуются как нечет- 48 УСиМ, 2009, № 4 кой, так и четкой структурой. Для задач, в которых входные данные имеют четкую структуру, математиче- ские модели, соответственно и целевая функция, разра- ботаны достаточно фундаментально, поэтому неопреде- ленность для них сведена к минимуму. Поиском спосо- бов решения задач с нечеткими входными данными за- нимаются не одно десятилетие, но точной математиче- ской постановки для них еще не разработано. Невзирая на попытку строго формализировать понятие неопределен- ности, например [5], этим понятием пользуются на ин- туитивном уровне. Для этих задач достаточно сложно смоделировать целевую функцию такую, чтобы глобаль- ное решение удовлетворяло действительной цели ис- следования. Постановка проблемы Рассмотрим нахождение параметров в условиях не- определенности в задачах с четкой входной информаци- ей. Эта проблема возникает потому, что прикладные задачи комбинаторной оптимизации сложны по своей природе и разделяются на подзадачи, для решения ко- торых разрабатывают независимые алгоритмы, с помо- щью которых основная задача решается их последова- тельной работой или они работают как встроенные про- цедуры в итерационном режиме. Алгоритм, объединяю- щий независимые алгоритмы, ориентированные на ре- шение определенных задач, называется гибридным или комбинированным [6–8]. В процессе его работы при пе- редаче информации, которая является результатом ре- шения предыдущей задачи, на входе следующего алго- ритма могут появляться новые, неопределенные пара- метры, необходимые для решения очередной задачи, ко- торые невозможно задать во входных данных по усло- вию. Возникает проблема нахождения параметров в усло- виях неопределенности. Такие задачи наблюдаются и в конструкторском проектировании вычислительной ап- паратуры. От эффективного нахождения таких парамет- ров зависит удобство в эксплуатации определенных сис- тем и возможность полной автоматизации процесса про- ектирования. На примере конструкторского проектиро- вания печатных плат рассмотрим эту проблему и опи- шем самонастраивающиеся алгоритмы нахождения па- раметров в условиях неопределенности [9]. Общая задача конструкторского проектирования пе- чатных плат разделяется на такие подзадачи [10]: задача компоновки базовых элементов в модули, оптимальное размещение выводов базовых элементов в модуле и на- значение их библиотечных (реальных) номеров, задача размещения разногабаритных модулей на поверхности печатной платы, моделирование конструкции печатной платы при подготовке ее к следующему этапу проекти- рования, трассировка печатных проводников, контроль топологии печатного монтажа, выпуск конструкторской документации, формирование информации для устройств с числовым программным управлением, где имеет место задача коммивояжера. В процесс проектирования вхо- дит подготовка электрической схемы и библиотеки по- стоянной информации. Входная информация в этой за- даче разделяется на переменную, которая задается для определенной индивидуальной задачи, и постоянную, одинаковую для серии индивидуальных задач. Постоян- ную информацию заносят предварительно в библиотеку и используют в процессе решения задачи на разных эта- пах. Использование библиотечных данных экономичес- ки целесообразно, когда проектирование проводится для небольшой номенклатуры многосерийных изделий. Но такой подход экономически неэффективен при большой номенклатуре малосерийных изделий и решении задач, для которых некоторые параметры занести в библиоте- ку невозможно. Их можно задать лишь после решения очередной задачи. Это касается задачи размещения вы- водов базовых элементов в модули и назначения их библиотечных номеров и определения посадочных мест для размещения разногабаритных модулей. Так, назна- чить реальные номера выводам модулей можно лишь после решения задачи компоновки, определить структу- ру посадочных мест на монтажном поле для установки разногабаритных модулей – после нахождения опреде- ленного варианта их размещения. Введение этой ин- формации в диалоговом режиме достаточно трудоемкий процесс, поэтому для автоматизации проектирования на этом этапе разработаны самонастраивающиеся алгорит- мы нахождения неопределенных параметров. Поскольку в начале решения задачи наблюдаются неизвестные па- раметры, то она принадлежит к классу параметрических ситуаций решения [5]. Решение проблемы Математическую постановку общей задачи проекти- рования печатных плат сформулируем так. Пусть задана электрическая схема, которую представим графом G. Множеством A = {a1, …, an} обозначим его вершины, каж- дой aj из которых в соответствие поставлен заданный базовый элемент. Обозначим Ф(G) функциональные ха- рактеристики заданной электрической схемы. Размеще- ние компонент электрической схемы проводится на пла- те, представляющей собой прямоугольную поверхность с нанесенной на ней координатной сеткой. Она может быть однослойной, двухслойной, многослойной. Перену- меруем ячейки этой сетки и их последовательную нуме- рацию представим множеством D = {d1, …, dξ}. Из эле- ментов aj базового множества A, j ∈ {1, …, n}, образует- ся комбинаторное множество W – совокупность комби- наторных конфигураций определенного типа (переста- новки, разбиения и т.п.), а из элементов dl базового множества D, l ∈ {1, …, ξ}, образуется комбинаторное множество M – размещение без повторений. На элемен- тах w комбинаторного множества W и μ комбинаторно- го множества M вводится целевая функция. Тогда зада- ча проектирования печатных плат заключается в нахож- дении такого размещения компонент заданной электри- ческой схемы на одном или нескольких слоев, т.е. вы- УСиМ, 2009, № 4 49 боре для размещения элементов w* ∈ W комбинаторной конфигурации μ* из множества M, для которых введен- ная целевая функция принимала бы оптимальное значе- ние с необходимым выполнением условия Ф(G) = )~(~ GΦ , где )~(~ GΦ – функциональные характеристики электри- ческой схемы G~ , полученной из G в процессе проекти- рования. Как было оговорено, задача проектирования печат- ных плат разделяется на подзадачи, аргумент целевой функции в которых – комбинаторные конфигурации раз- ных типов [11]. Например, аргументом целевой функ- ции в задаче компоновки является разбиение n-элемент- ного множества на подмножества, задачи размещения разногабаритных модулей на поверхности печатной платы и распределение выводов модулей – перестановка, трас- сировка печатных плат – размещение без повторений. Исходя из этого, функционал для поставленной задачи запишем как * * * ρ μ ω (ρ , μ ,ω ) ext (ρ, μ,ω) M F F ∈Θ ∈ ∈Ω = , где ρ – разбие- ние n-элементного множества на подмножества, μ – размещение без повторений, ω – перестановка, а Θ, M, Ω – их множества. Далее опишем самонастраивающиеся алгоритмы на- хождения параметров, которые необходимо задавать как входные данные для решения очередной задачи и кото- рые невозможно задать в начале вычислительного про- цесса. Поскольку основной результат проектирования – оптимальное размещение компонент электрической схе- мы на плате, то при выборе критериев качества, по ко- торым оценивается результат решения задачи на от- дельных этапах, учитывается оптимальная трассировка печатных плат, т.е. критерии качества, задаваемые на оче- редном этапе решения задачи, моделируются с учетом прогноза результатов. Выделим подзадачи, требующие вычисления пара- метров в условиях неопределенности. Задача компоновки базовых элементов в модули. Со- держательная постановка этой задачи такова. Задано n базовых элементов разных типов, между которыми су- ществуют электрические связи. Необходимо эти эле- менты распределить по корпусам микросхем так, чтобы количество связей между последними было минималь- ным, или количество связей между элементами, объеди- ненными в микросхемы, было наибольшим. Количество типов, к которым относятся элементы, и количество эле- ментов, которые необходимо объединить по микросхе- мам, задано. После решения этой задачи необходимо задать реальные номера выводам модулей, т.е. найти па- раметры в условиях неопределенности. Если компоновка проводится произвольная, то базо- вые элементы объединяются в модули без оптимизации, вручную, а выводам присваиваются номера согласно с конструкторскими требованиями. Поскольку назначе- ние реальных номеров выводам включает в себя задачу оптимального размещения базовых элементов в модуле, то эта задача, как и компоновка, не оптимизируется, что ухудшает условия для оптимальной трассировки печат- ных проводников на следующем этапе. Аналогичная задача назначения реальных номеров выводов базовых элементов возникает при проектировании сверхбольших интегральных микросхем в процессе разработки типич- ных библиотечных модулей. Если при проектировании печатных плат компоновка допускается произвольная, то при проектировании интегральных микросхем ее ре- шают вручную, в диалоговом режиме и она достаточно трудоемкая. Для автоматического назначения реальных номеров выводам базовых элементов на этапе подготовки вход- ной информации присваиваются формальные парамет- ры и задаются типы модулей. Библиотечные параметры генерируются автоматически самонастраивающей про- граммой-генератором постоянных параметров. Управ- ление этой программой осуществляется формальными параметрами, задаваемыми в начале вычислительного процесса. При такой организации библиотека не созда- ется. Построим математическую модель этой задачи. Пусть в результате оптимальной компоновки обра- зован набор модулей, который зададим множеством },...,{ 1 tt vvV ζ= . Каждому элементу Vvt j ∈ поставлен в соот- ветствие некоторый его тип )( t jvP , κ= ,1t , ζ= ,1j , где κ – количество типов, ζ – количество элементов в V. Обо- значим },...,{ 1 t j t j t j tq aav = , Aat jl ∈ , множество базовых эле- ментов, входящих в модуль t-го типа, а }~,...,~{ ~1 t j t j t tqlj aaa = – множество формальных номеров выводов j-го элемента t-го типа, где qt – количество базовых элементов в t jv , tq~ – количество номеров выводов j-го элемента t-го типа. Для размещения базовых элементов t jl a в модуле t jv введем установочные позиции, которые обозначим множеством },...,{ 1 t j t j t j tq ppp = , а }~,...,~{ ~1 t j t j t j tql ppp = – соот- ветственно множество позиций для установки выводов базовых элементов t-го типа. Задача назначения реальных номеров выводам базо- вых элементов заключается в замене их формальных но- меров библиотечными так, чтобы для найденного вари- анта размещения этих выводов в посадочных местах суммарная длина печатных электрических связей была бы минимальной, т.е. )(min)( * ω=ω Ω∈ω FF и выполнялось условие )~(~)( GG Φ=Φ . Размещение базовых элементов в модуле и назначение реальных номеров выводов жела- тельно проводить на последней итерации размещения модулей. Задача размещения разногабаритных модулей фор- мулируется так. Множество модулей, имеющих разные габариты, необходимо разместить на поверхности платы 50 УСиМ, 2009, № 4 так, чтобы суммарная длина связей и площадь, которую они занимают, были минимальными, а зазоры между модулями равнялись заданной величине. Эту задачу мож- но свести к одногабаритной, использовав алгоритм ком- поновки базовых элементов в модули с последующим размещением полученных одногабаритных блоков на пла- те [8]. В процессе работы алгоритма проводится дина- мическая перестройка позиций на плате для установки модулей, т.е. оптимизируется выбор посадочных мест для их установки. Это – третья задача, в которой аргу- ментом целевой функции является размещение без по- вторений. Вариантов размещения μ ∈ M, образованных из элементов dj ∈ D, может быть много. Поэтому в про- цессе решения задачи размещения разногабаритных мо- дулей появляется нечеткость и неопределенность, а це- левая функция зависит от перестановок, от разбиения n-элементного множества на подмножества и от разме- щения без повторений. Запишем для нее функционал: * * * ρ ω μ (ρ ,μ ,ω ) ext (ρ, μ,ω) M F F ∈Θ ∈Ω ∈ = . На этапе решения задачи размещения модулей и трассировки печатных проводников необходима инфор- мация о конструкции печатной платы. Как правило, ее модель предварительно описывается и заносится в биб- лиотеку. Поскольку электрические схемы отличаются одна от другой элементной базой, то такая подготовка проводится или для серии индивидуальных задач, или для каждой схемы отдельно. При предварительной под- готовке модели платы ее поверхность, как правило, раз- бивают на полосы разной ширины, на каждой из кото- рых можно устанавливать модули определенного габа- рита, т.е. нечеткие параметры, которыми являются по- садочные места для размещения модулей и которые об- разуются выбором элементов dj ∈ D, «огрубляются». В результате получается четкий, но далеко не оптималь- ный результат. К тому же такая подготовка модели пла- ты осложняет эксплуатацию системы и ограничивает ее возможности. Сформулируем математическую постановку и опи- шем вычислительную схему самонастраивающегося алго- итма нахождения параметров в условиях неопределен- ности при размещении модулей и построении модели печатной платы. Обозначим Vr ⊂υυ=Υ },...,{ 1 множество модулей, каждый из которых имеет наибольшие габари- ты },...,1{ nr∈ ; Vr ⊂υυ=Υ },...,{ ~1 – множество модулей, каждый из которых имеет наименьшие габариты; }~,...,~{~ ~1 kkk vvV ζ= – множество модулей, образованное из заданного множества модулей V на k-й итерации. Зада- дим }~,...,~{~ ~1 ξ= ddD – множество позиций для установки модулей из kV~ , образованных на k-й итерации. В про- цессе работы алгоритма проводится динамическая пере- стройка модели платы. Суть этого алгоритма заключа- ется в проведении последовательных шагов, на каждом из которых заданные элементы электрической схемы объ- единяются в модули. На сформированном из наименьших ячеек координатной сетки, которым соответствуют эле- менты множества D, регулярном поле позиций разме- щаются модули kk j Vv ~~ ∈ . Этот процесс проводится до тех пор, пока не будет размещен наименьший по габаритам модуль. Установка модуля Vvt j ∈ на плате проводится путем вычисления установочных координат ),( t j t j ll yx для его выводов по выражениям: 0 (κ, ο, η, τ)jx x f= + , 0jy y= + (κ, ο, η, τ)f+ , где x0, y0 – базовые координаты для уста- новки модуля t-го типа, определяемые по результатам размещения Vvt j ∈ , κ – тип модуля, о – тип ориентации модуля на плате, η – количество выводов модуля t-го типа, τ – расстояние между выводами модуля t-го типа. Модули по типам классифицируются согласно с по- строением их корпусов. Такой подход дает возможность полностью автоматизировать решение задачи размеще- ния разногабаритных модулей и подготовку модели пе- чатной платы для последующей автоматизации процес- са проектирования. Заключение. Ввод формальных параметров на этапе подготовки входных данных и динамическая пере- стройка модели печатной платы позволяют находить параметры в условиях неопределенности, что обеспечи- вает полную автоматизацию проектирования печатных плат. Предложенная организация вычислительного про- цесса позволяет достаточно гибко перестраиваться на разные типы индивидуальных задач, не требует образо- вания библиотек, подготовка которых – достаточно тру- доемка, упрощает эксплуатацию систем автоматизиро- ванного проектирования. << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Самоналагоджувальні алгоритми знаходження невизначених параметрів у задачах комбінаторної оптимізації

Institution

Similar Items