Введение к работе
Актуальность темы. В настоящее время математическое моделирование и компьютерные технологии широко применяются для решения различных задач, возникающих в экономике, управлении, проектировании и других сферах деятельности. Значительное внимание уделяется использованию моделей и методов дискретной оптимизации, что обусловлено необходимостью решать достаточно сложные задачи с большим числом возможных вариантов и выбирать из них наилучшие с учетом различных ограничений.
Среди подобного типа задач важное место занимают постановки, в которых требуется сформировать в определенном смысле оптимальное множество объектов (например, машин, наборов моделей одежды, приемов, свойств), покрывающее «потребности» другой совокупности (работ, клиентов, заказов, характеристик и др.) при выполнении условий, обусловленных спецификой задачи. Проведенные нами исследования показали, что во многих случаях указанные задачи могут быть сведены к задачам о покрытии и различным их модификациям. Для решения этих задач актуальным является применение методов дискретной оптимизации, в частности, целочисленного программирования.
Задачи о покрытии имеют значительное число приложений в различных отраслях, являются NP-трудными и требуют построения эвристических алгоритмов, которые могут быть использованы в прикладных исследованиях. В последние годы в области дискретной оптимизации в этом направлении активно велись разработки алгоритмов локального поиска, муравьиной колонии, поиска с запретами, генетических алгоритмов и др.
Цель диссертационной работы - построение математических моделей, численных методов и алгоритмов для решения задач оптимизации выбора объектов в процессе технической подготовки производства, в том числе при определении доминирующих свойств материалов.
Задачи исследования. Для достижения указанной цели поставлены и решены следующие задачи:
1. Разработать подход к оптимизации выбора объектов в процессе техниче
ской подготовки производства и определению доминирующих свойств мате
риалов.
Построить математические модели формирования наборов изделий с учетом нескольких критериев с целью запуска в производство и выбора для индивидуального потребителя.
Разработать математические модели для нахождения минимального множества доминирующих свойств, влияющих на оценку качества материала.
Построить алгоритмы, основанные на методах локального поиска для решения поставленных задач.
5. Разработать программную реализацию предложенных алгоритмов и про
вести экспериментальное исследование математических моделей и методов,
выявить возможности их применения для решения прикладных задач.
Методы исследования. В процессе выполнения работы использовались методы математического моделирования, дискретной оптимизации, целочис-
ленного линейного программирования, а также современные достижения в области проектировании изделий и применения компьютерных технологий. На защиту выносятся:
Подход к оптимизации выбора объектов в процессе технической подготовки производства и определению доминирующих свойств материалов, основанный на применении задач о покрытии и их обобщений.
Математические модели формирования наборов изделий с учетом нескольких критериев с целью запуска в производство и выбора для индивидуального потребителя.
Математические модели для нахождения минимального множества доминирующих свойств, влияющих на оценку качества материала.
Гибридные алгоритмы, основанные на поиске с запретами для задачи о покрытии множества, ее обобщений и задачи нахождения минимального множества доминирующих свойств материалов.
Программная реализация разработанных алгоритмов, результаты экспериментальных исследований.
Научная новизна работы состоит в следующем:
Предложен новый подход к оптимизации выбора объектов в процессе технической подготовки производства и определения доминирующих свойств материалов, основанный на использовании задач о покрытии на графах и их обобщений, отличающийся от применявшихся ранее методов возможностью находить оптимальные или приближенные решения с учетом различных ограничений и нескольких критериев.
С использованием указанного подхода построены новые математические модели и решены следующие задачи:
формирования наборов изделий с учетом нескольких критериев для запуска в производство,
оптимизации выбора изделий для индивидуального потребителя,
нахождения минимального множества доминирующих свойств материалов, влияющих на оценку его качества.
3. Разработаны гибридные алгоритмы, основанные на методах локального
поиска и поиска с запретами, для задачи о покрытии, ее обобщений и задачи
нахождения минимального множества доминирующих свойств, влияющих на
оценку качества материала, которые учитывают специфику задач. Для нахож
дения начального решения в этих алгоритмах использовался метод Лагранже-
вой релаксации. Приближенное решение находилось с помощью метода ло
кального поиска и впервые с использованием поиска с запретами, что позволи
ло повысить эффективность решения.
Практическая значимость работы. Предложенный подход и математические модели могут быть использованы на этапе технической подготовки производства в ситуациях, где необходимо формировать оптимальные наборы объектов, удовлетворяющие потребности другой совокупности объектов. На основе этого подхода построены математические модели для нахождения оптимальных наборов изделий, предназначенных для запуска в производство и индивидуального потребителя, выделения доминирующих свойств материалов. Опти-
мизация выбора объектов позволит сокращать трудовые и временные затраты на разработку новых изделий и оценку качества материалов, снижать влияние субъективного фактора.
Внедрение результатов работы. Результаты диссертационной работы применимы для решения практических задач в различных отраслях, а также в учебном процессе при подготовке специалистов в области применения математических методов и современных информационных технологий. В частности, они внедрены на швейном предприятии по изготовлению детской и подростковой одежды, в ателье «Ренард» филиала «Иртыш» РООИВиВК (г. Омск), на кафедре «Технология и методика преподавания технологии» Омского государственного педагогического университета при подготовке студентов специальности 030600 «Технология и предпринимательство» и направления 540500 «Технологическое образование» по дисциплинам «Компьютерное моделирование технологических процессов» и «Организация и технология предприятий бытового обслуживания».
Апробация работы. Основные результаты диссертации опубликованы в работах [1 - 15] и докладывались на следующих конференциях и семинарах: Региональной научно-практической юбилейной конференции «Совершенствование системы подготовки специалистов для сферы сервиса», Омск, 2002; Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2003; Международной научно-практической конференции "Актуальные проблемы подготовки специалистов для сферы сервиса", Омск, 2003; Российской конференции «Дискретный анализ и исследование операций», Новосибирск, 2004; XXIX Региональной научной студенческой конференции «Молодежь III тысячелетия», ОмГУ, 2005; III Всероссийской научной молодежной конференции «Под знаком », Омск, 2005; XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики", Екатеринбург, 2006; III Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2006; XIII Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, 2007; заседаниях семинара «Математическое моделирование и дискретная оптимизация» в Омском филиале Института математики СО РАН, заседаниях кафедр в Омском государственном университете и Уфимском государственном авиационном техническом университете.
Публикации. Список публикаций по теме диссертации содержит 15 работ, в том числе одну в рецензируемом журнале из списка ВАК.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка используемой литературы, приложений, содержит 134 страницы машинописного текста и включает 112 наименований использованных литературных источников.
