Математична модель та метод розв'язання задачі розбиття і трасування з урахуванням просторової форми області

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Элькин А. Б. Математическая модель прикладной задачи оптимизации разбиения геометрической области / А. Б. Элькин // Вісник Харк. нац. ун-ту. № 775. Сер. «Математичне моделювання. Інформаційні технології. Автоматизовані системи керування». Х.: Харків. нац. ун-т ім. В. Н. Каразіна, 2007. Вип. 7. С. 258-267.

2. Путятин В. П. Математическая модель задачи оптимизации разбиений в АПК / В. П. Путятин, А. Б. Элькин // Вестник НТУ «ХПИ». Сборник научных трудов. Тематический выпуск «Системный анализ, управление и информационные технологии». Х.: Нац. техн. ун-т «Харьк. политех. ин-т», 2007. № 18. С. 98-105.

3. Смеляков С. В. Численная реализация математической модели дискретной задачи оптимизации сети трасс / С. В. Смеляков, А. Б. Элькин // Вісник Харк. нац. ун-ту. № 809. Сер. «Математичне моделювання. Інформаційні технології. Автоматизовані системи керування». Х.: Харків. нац. ун-т ім. В. Н. Каразіна, 2008. Вип. 9. С. 178-191.

4. Путятин В. П. Комбинаторные аппаратные модели задач геометрического проектирования / В. П. Путятин, А. Б. Элькин // Системи обробки інформації. Х.: Харків. ун-т Повітр. Сил ім. І. Кожедуба, 2007. Вип. 3 (61). С. 86-91.

5. Пат. на корисну модель № 22708 Україна, МПК (2006) G 06 F 5/06. Пристрій для моделювання та оптимізації трас / В. П. Путятін, О. Б. Елькін; замовник та патентовласник Харків. нац. техн. ун-т сільськ. госп. ім. П. Василенка. № u200613268; заявл. 15.12.2006; опубл. 25.04.2007. Бюл. № 5.

6. Пат. на корисну модель № 22623 Україна, МПК (2006) G 06 F 17/00. Пристрій для комбінаторної оптимізації розміщення об'єктів та трасування / В. П. Путятін, О. Б. Елькін; замовник та патентовласник Харків. нац. техн. ун-т сільськ. госп. ім. П. Василенка. № u200612839; заявл. 05.12.2006; опубл. 25.04.2007. Бюл. № 5.

7. Элькин А. Б. Модель задачи оптимизации разбиения области по заданному критерию / А. Б. Элькин // Управління розвитком: зб. наукових статей за матеріалами науково-практ. конф. «Інформатизація бізнесу очима молодих: прогресивні технології, наука, підприємництво», 17-18 травня 2007. Х.: Харків. нац. екон. ун-т, 2007. Вип. 3. C. 121-122.

8. Путятін В. П. Пристрій для моделювання та оптимізації трас / В. П. Путятін, О. Б. Елькін // Новое время: cб. изобретений и разработок по материалам IV Междунар. салона изобретений и новых технологий, посвященного 40-ю Междунар. Федерации ассоциаций изобретателей (IFIA Jubilee, 1968-2008), 25-27 сентября 2008 г. Севастополь: Укр. культурно-информац. центр, 2007. С. 61.

9. Путятін В. П. Пристрій для комбінаторної оптимізації розміщення об'єктів та трасування / В. П. Путятін, О. Б. Елькін // Новое время: cб. изобретений и разработок по материалам IV Междунар. салона изобретений и новых технологий, посвященного 40-ю Междунар. Федерации ассоциаций изобретателей (IFIA Jubilee, 1968-2008), 25-27 сентября 2008 г. Севастополь: Укр. культурно-информац. центр, 2007. С. 95-96.

10. Смеляков С. В. Решение задачи оптимизации сети полевых дорог / С. В. Смеляков, В. П. Путятин, А. Б. Элькин // Современные информационные системы. Проблемы и тенденции развития: материалы II Междунар. научной конференции, 2-5 октября 2007 г. Х.: Харьк. нац. ун-т радиоэлектроники, 2007. С. 154-155.

11. Элькин А. Б. Модели задач разбиений и трассировки в АПК / А. Б. Элькин // Ринкова трансформація економіки: стан, проблеми, перспективи: матеріали Міжнар. Форуму молодих вчених, 19-20 квітня 2007 г. Х.: Харків. нац. техн. ун-т сільськ. госп. ім. П. Василенка, 2007. С. 219-220.

12. Элькин А. Б. Аппаратурная реализация математических моделей задач геометрического проектирования / А. Б. Элькин // Радиоэлектроника и молодежь в XXI в.: материалы ХI Междунар. молод. форума, 10-12 апреля 2007 г. Х.: Харьк. нац. ун-т радиоэлектроники, 2007. С. 119.

13. Елькін О. Б. Реалізація математичних моделей задач призначення об'єктів та прокладки трас між ними / О. Б. Елькін // Современные научные достижения - '2007: материалы ІІ Междунар. научно-практ. конференции, 1-14 февраля 2007 г. Днепропетровск: Наука и образование, 2007. Том 6, естественные науки. С. 40-42.

АНОТАЦІЯ

Елькін О. Б. Математична модель та метод розв'язання задачі розбиття і трасування з урахуванням просторової форми області. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання і обчислювальні методи. - Інститут проблем машинобудування ім. А. М. Підгорного НАН України, 2008.

Побудована математична модель основної оптимізаційної задачі розбиття і трасування з урахуванням технологічних обмежень (геометричних, фізичних та геодезичних особливостей). Досліджені основні особливості математичної моделі основної задачі, що дозволило здійснити її декомпозицію на задачу розбиття області з урахуванням її просторової форми і задачу прокладання допоміжних трас у ній. Запропоновані математична модель і метод розв'язання задачі розбиття області на рівновеликі прямокутні підобласті з урахуванням її просторової форми. Запропоновані математична модель і метод розв'язання задачі про прокладання мережі допоміжних трас для загального випадку неортогональної структури розбиття вихідної області, при цьому рубіж магістральних шляхів, від якого слід проводити допоміжні траси, може знаходитися як на границі області, так і всередині неї. Запропоновані і запатентовані основні апаратні структури для реалізації математичних моделей, що розглянуті у роботі.

Рекомендується застосування розглянутих математичних моделей та методів для розв'язання дискретних задач розбиття і трасування в агропромисловому комплексі (паювання землі), в облаштуванні міських територій (організація стоянок автотранспорту і проектування під'їзних доріг), у ветеринарії (штучний поділ ембріонів), у приладобудуванні (раціональне різання штучних монокристалів), у машинобудуванні і легкій промисловості (раціональне використання матеріалу) та інше.

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

АННОТАЦИЯ

Элькин А. Б. Математическая модель и метод решения задачи разбиения и трассировки с учетом пространственной формы области. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт проблем машиностроения им. А. Н. Подгорного НАН Украины, Харьков, 2008.

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

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

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

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

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

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

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

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

SUMMARY

Elkin O. B. Mathematical model and solution method of decomposition and tracing with regard for the region's space form. - Manuscript.

Dissertation for obtaining PhD Degree in Technical Sciences, Specialization 01.05.02 - mathematical modeling and computational methods. - A. M. Pidgorny Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Kharkiv, 2008.

A mathematical model has been constructed of a basic optimization problem of decomposition and tracing of a given region taking into account a number of technical restrictions (geometric, physics and geodesic properties). The characteristics of the basic mathematical model have been studied, which made it possible to reduce the problem to decomposition of the region with regard for its space form and subsidiary tracing within the region.

A mathematical model and solution method are proposed for the region decomposition into equal rectangular sub-regions taking account of the region's space form. A mathematical model and solution method are offered for the problem of laying out a subsidiary tracing network for a general case of non-orthogonal area decomposition structure with the main-line trackage border from which subsidiary tracing is to be laid, located either on the region frontier or within the region. Also developed and patent registered are instrument structures for the realization of the mathematical models suggested.

The proposed mathematical models and solution methods are recommended for solving decomposition and tracing discrete problems in the agro-industrial sector (land plotting), urban area development (parking space and access roads design), in veterinary science (artificial separation of embryos), instrument-building (rational cutting of single crystals), machine-building and light industry (rational utilization of materials), etc.

Key words: mathematical modeling, decomposition, tracing, optimization, computational methods, instrumental models, geometric design, technical restrictions, decision-making.

Размещено на Allbest.ru