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

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

ПРИВАЛОВА Юлия Ивановна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ОПТИМИЗАЦИИ ВЫБОРА ОБЪЕКТОВ В ПРОЦЕССЕ ТЕХНИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА (НА ПРИМЕРЕ ЛЕГКОЙ ПРОМЫШЛЕННОСТИ)

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ на соискание ученой степени кандидата технических наук

003 15Э858

Уфа 2007

003159858

Работа выполнена

в ГОУ ВПО «Омский государственный университет им Ф М Достоевского» на кафедре прикладной и вычислительной математики

Научный руководитель Официальные оппоненты

д-р физ -мат наук, проф

КОЛОКОЛОВ Александр Александрович

д-р физ -мат наук, проф

ЖИТНИКОВ Владимир Павлович

канд техн. наук, доц

Григорчук Татьяна Ивановна

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

Институт автоматики и процессов управления ДВО РАН, г. Владивосток

Защита состоится« 26 » октября 2001т в 10 час на заседании диссертационного совета Д-212 288 03 при Уфимском государственном авиационном техническом университете по адресу 450000, г Уфа, ул К Маркса 12

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

Автореферат разослан « » 2007г

Ученый секретарь диссертационного совета д-р техн наук, проф

В.В. Миронов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Задачи о покрытии имеют значительное число приложений в различных отраслях, являются ./УР-трудными и требуют построения эвристических алгоритмов, которые могут быть использованы в прикладных исследованиях В последние годы в области дискретной оптимизации в этом направлении активно велись разработки алгоритмов локального поиска, муравьиной колонии, поиска с запретами, генетических алгоритмов и др

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

Задачи исследования. Для достижения указанной цели поставлены и решены следующие задачи

1 Разработать подход к оптимизации выбора объектов в процессе технической подготовки производства и определению доминирующих свойств материалов

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

3 Разработать математические модели для нахождения минимального множества доминирующих свойств, влияющих на оценку качества материала

4 Построить алгоритмы, основанные на методах локального поиска для решения поставленных задач

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

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

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

1 Подход к оптимизации выбора объектов в процессе технической подготовки производства и определению доминирующих свойств материалов, основанный на применении задач о покрытии и их обобщений

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

3 Математические модели для нахождения минимального множества доминирующих свойств, влияющих на оценку качества материала

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

5 Программная реализация разработанных алгоритмов, результаты экспериментальных исследований

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

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

2 С использованием указанного подхода построены новые математические модели и решены следующие задачи

• формирования наборов изделий с учетом нескольких критериев для запуска в производство,

• оптимизации выбора изделий для индивидуального потребителя,

• нахождения минимального множества доминирующих свойств материалов, влияющих на оценку его качества

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

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

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

Внедрение результатов работы. Результаты диссертационной работы применимы для решения практических задач в различных отраслях, а также в учебном процессе при подготовке специалистов в области применения математических методов и современных информационных технологий В частности, они внедрены на швейном предприятии по изготовлению детской и подростковой одежды, в ателье «Ренард» филиала «Иртыш» РООИВиВК (г Омск), на кафедре «Технология и методика преподавания технологии» Омского государственного педагогического университета при подготовке студентов специальности 030600 «Технология и предпринимательство» и направления 540500 «Технологическое образование» по дисциплинам «Компьютерное моделирование технологических процессов» и «Организация и технология предприятий бытового обслуживания»

Апробация работы. Основные результаты диссертации опубликованы в работах [1 — 15] и докладывались на следующих конференциях и семинарах Региональной научно-практической юбилейной конференции «Совершенствование системы подготовки специалистов для сферы сервиса», Омск, 2002, Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2003, Международной научно-практической конференции "Актуальные проблемы подготовки специалистов для сферы сервиса", Омск, 2003, Российской конференции «Дискретный анализ и исследование операций», Новосибирск, 2004, XXIX Региональной научной студенческой конференции «Молодежь III тысячелетия», ОмГУ, 2005, III Всероссийской научной молодежной конференции «Под знаком X», Омск, 2005, XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики", Екатеринбург, 2006, III Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2006, XIII Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, 2007, заседаниях семинара «Математическое моделирование и дискретная оптимизация» в Омском филиале Института математики СО РАН, заседаниях кафедр в Омском государственном университете и Уфимском государственном авиационном техническом университете

Публикации. Список публикаций по теме диссертации содержит 15 работ, в том числе одну в рецензируемом журнале из списка ВАК

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы, формулируются цель и задачи исследования, отмечается новизна и практическая значимость результатов работы, кратко излагается содержание диссертации, приводится информация об ее апробации

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

Задача о наименьшем покрытии множества может быть сформулирована следующим образом Пусть даны множество М={1, ,т} и набор его

подмножеств М^М, где ,п} Совокупность {Му}, JeJ,

называется покрытием множества М, если (^М^М Каждому М] приписан

вес с1 > 0 Требуется найти покрытие, имеющее минимальный суммарный вес

Приведем соответствующую модель ЦЛП Введем переменные х] = 1, если множество М входит в покрытие, иначе = 0, ; еИ Определим матрицу А = 1&М, ^eN

|1, если элемент ? входит в множество М ,

[О, иначе. Задача ЦЛП имеет вид

п

при условиях

п

геМ>

х,е{0,1}, уеЛГ (13)

В невзвешенной ЗИП коэффициенты целевой функции с = 1, _/ е N Кроме

того, в литературе изучаются обобщенные задачи о покрытии, в которых в правой части ограничения (1 2) используется вектор натуральных чисел 6 = (йр ,Ът)Т Это означает, что элемент г должен быть «покрыт» не менее Ъ1 раз, ¡еМ В работе приводятся также постановка задачи об упаковке множества и соответствующая модель ЦЛП Указанные задачи послужили основой для разработанных нами математических моделей в главах 2 и 3

О 1) (12)

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

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

Приведем математические модели для данной постановки задачи Пусть К = {ур множество покрывающих объектов, й^ = {■№,, ,и>,„)~ множество

объектов, потребности которых необходимо удовлетворить Для каждого известно подмножество покрываемых им объектов Й^сУ Элементы из V

разделены на I групп , кеТ, Т-{ 1, (в общем случае они могут пересекаться) Подмножество V' с V будем называть покрытием, если объекты из V полностью удовлетворяют потребности объектов из ¡V Покрытие называется допустимым, если в него входит не более одного элемента каждой группы .1к Объекту vJ приписан вес с] > 0, у = 1, ,п Вес покрытия V'

определяется как сумма весов его элементов Задача состоит в отыскании допустимого покрытия минимального веса Построим соответствующую модель ЦЛП Для этого введем переменные ху =1, если объект входит в

покрытие, иначе х =0, Напомним, что N = {1, ,п}, а М = { 1, ,т}

Определим матрицу А = (ао), г е М, ] е N

а

[О, иначе Задача ЦЛП имеет вид

1, если элемент может удовлетворять потребности объекта у/,,

(2 1)

при условиях

/7

геМ,

(2 2)

(2 3)

кеТ,

*,е{0,1},

J<sN

(2 4)

Условие (2 2) отражает требование удовлетворения потребностей всех объектов из Ж Поэтому, если из (2 1) - (2 4) исключить неравенство (2 3), то получится задача о наименьшем покрытии множества Отсюда вытекает, что задача (2 1) — (2 4) является ТУР-трудной Следует отметить, что имеются постановки задач, в которых в правой части ограничения (2 2) используется вектор натуральных чисел Ь = (Ьп ,Ът)т

Система неравенств (2 3) указывает на необходимость выбора из каждой группы У* не более одного объекта, к е Т В ряде случаев модель включает ограничения такого типа, в которых знак « < » заменяется на равенство Встречаются постановки задач, в которых группы не пересекаются Рассматриваемая задача может быть сформулирована с целевой функцией на максимум Кроме того, на практике возникают задачи, в которых вместо целевой функции (2 1) используются несколько критериев

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

Дадим содержательную постановку указанной задачи Имеется множество моделей одежды, из которого необходимо выбрать некоторую совокупность для запуска в производство В соответствии с психофизиологическими особенностями каждого типа потребителя ему подходит только часть модельного ряда Кроме того, каждая модель одежды отвечает некоторому направлению моды, т е имеет определенный коэффициент эстетического соответствия Необходимо сформировать набор моделей одежды, в котором в максимальной степени учитываются психофизиологические и эстетические особенности потребителей

Приведем математическую постановку данной задачи Пусть имеется т типов потребителей, п моделей одежды и рассматривается двудольный граф б = {У,Е) с множеством вершин У = У1}Ши множеством ребер Е, где

У={у,, ,у„}, вершина отвечает у-ой модели одежды, 7 = 1, ,п, а IV-{и^, ,»,„}, то, соответствует г-му типу потребителя, ? = 1, ,т

Если у-ая модель одежды может быть рекомендована ;-му типу потребителя, го в £ входит ребро Множество вершин V разделено на

вершины, соответствующие зрительно мало различимым моделям одежды

Известен целочисленный вектор Ъ-{Ьи ,Ът)т, характеризующий требуемую степень разнообразия моделей одежды о — нижняя граница количества моделей, выбираемых для потребителя 7-го типа, г = 1, ,т Кроме того, задана величина а-верхняя граница числа моделей, предлагаемых для внедрения в производство В ходе исследования для каждой модели у были определены веса 5 и с!], где соответствует психофизиологическому показателю, с1) — эстетическому, у = 1, ,«

Пусть V с V и Е - множество всех исходящих из V ребер Множество V называется допустимым 6-покрытием, если любая вершина м>1 является концом

не менее Ь: ребер из Е и | < а, / = 1, ,т Задача заключается в нахождении

допустимого Ъ -покрытия, которое является Парето-оптимальным по критериям психофизиологического и эстетического соответствия Для нахождения таких решений нами использован метод уступок

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

1 = 1, ,»1,у = 1, ,п

Введем вектор переменных х-(х„ ,хп)Т, где х=1, если вершина vJ входит в ¿-покрытие, иначе ху=0, / = 1, ,п Двухкритериальная задача ДЛП имеет вид

I непересекающихся групп

В одной группе находятся

1, если в графе б имеется ребро (у,г) е Е, О, в противном случае,

(2 6)

п

Р'~(х) = тах

(2 7)

при условиях

(2 8)

(2 9)

ХЛ-01' (2Ю)

Xх/-1' * = 1> '*> (2 11)

]Ш„ 4

луе{0,1}, ] = 1, ,п

Ограничения (2 8) соответствуют требованию выбора для ¡-го типа потребителя не менее Ь1 моделей одежды, г = 1, ,т Неравенство (2 9) означает, что мощность Ь -покрытия не должна превышать величины а Условия (2 10) указывают на необходимость включения в покрытие не более одной модели одежды из к-т группы зрительного различия, к = 1, ,/

Разработанную математическую модель можно рассматривать как один из вариантов моделей оптимизации выбора объектов

С целью апробации построенной математической модели ЦЛП проведен вычислительный эксперимент на ЭВМ с использованием пакета программ, разработанного в лаборатории дискретной оптимизации Омского филиала Института математики СО РАН

В эксперименте использовались 50 моделей плечевой одежды йлательно-блузочного ассортимента девочек (для 16 типов подростков), те и = 50, т = 16 Расчеты выполнялись с различными вариантами вектора Ь и числа а Значения компонент вектора Ьп 1 = 1, ,16 выбирались из интервала [1,10] и а е {10,15,20} Результаты вычислений на ЭВМ показали, что предложенный подход к формированию набора одежды представляется перспективным

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

Дадим математическую постановку задачи Предположим, что потребитель имеет 5 недостатков фигуры и для них известны приемы коррекции Рассмотрим граф С=(У,Е) с множеством вершин V =Р\Зй{}В'[}Ш и множеством ребер £ = иЩ В этом графе Р={р/, ,р3}, вершина р/, отвечает недостатку И фигуры, к=1 Дщ}, вершина ^ соответствует приему у

из дополнительного класса, ¡-1, ,тп, ,<!',}, вершина <4

сопоставляется приему к из вспомогательного класса, к=1, ,!, !¥-= {м>,, ,м>„}, вершина м>, отвечает приему г из основного класса, 1=1, ,п, (см Рисунок 1) Отметим, что все множества Д £)' и Ж попарно не пересекаются

Опишем множество ребер графа 0=(У,Е) В Е, входят ребра, связывающие вершины множества Р с вершинами, принадлежащими £>, О' и ]¥ Если вершина из £> и -ОУ отвечает приему, корректирующему какой-либо недостаток фигуры, то она соединяется ребром с соответствующей вершиной, содержащейся в Р Множество Е] состоит из ребер, которые связывают вершины множеств ДО'и И? Любые две вершины из 0\10\}1¥ соединены ребром, если соответствующие им приемы не согласуются между собой

В ходе исследования для каждой вершины из Пи£>'1)}У были определены коэффициенты у], у*, у], 1—1, ,п, ]=1, ,т, к=1, ,1, отражающие предпочтения специалиста по направлениям моды

Задача заключается в нахождении подмножества вершин К* из 0{]0'{]1¥, которое удовлетворяет следующим условиям

• каждая вершина из Р соединена, по крайней мере, одним ребром с некоторой вершиной из V*,

• любые две вершины из V* не связаны ребром,

• количество вершин из V* не превышает заданной величины,

• вес множества V* является максимальным

Чтобы не ограничивать потребителя одним решением, необходимо предложить несколько моделей одежды Это можно сделать, например, путем варьирования значений коэффициентов предпочтения у\, уг, у], 1-1, ,п, ]=1, ,т, к=1, ,1

С целью решения поставленной задачи построим модель ЦЛП Введем следующие обозначения

Г - число противоречий между приемами коррекции фигуры из основного и дополнительного классов,

о

Рисунок 1 Граф С=(У,Е) для оптимизации выбора изделий

д - число противоречий между приемами коррекции фигуры из основного и вспомогательного классов,

г - число противоречий между приемами коррекции фигуры из дополнительного и вспомогательного классов,

Р — верхняя граница числа приемов, требуемых для скрытия дефектов, а0 - число непересекающихся групп приемов основного класса, а\ а2, а' - количество противоречий между приемами коррекции внутри основного, дополнительного и вспомогательного классов соответственно,

у!' У]-> УI ~ коэффициенты (веса) предпочтений приемов для основного, дополнительного и вспомогательного классов соответственно, /=/, ,п, }-1, ,т, к=1, ,1

Введем переменные х, = I, если основной прием г используется и х, = О, в противном случае, 1=1, ,п, = 1, если дополнительный прием ] используется и ^=0, в противном случае,_/=/, ,т, гк =1, если вспомогательный прием к используется и гк = 0, в противном случае, к=1, ,1 Модель ЦЛП имеет вид

Ег,Ч+I»,+XУ'Л тах i=i /=1

при условиях

п т (

Ы j=.| i.l

п т /

+ JLSa)y, + 2 1 '

1-1 />| ЫI

Я ОТ

п /

i=i

1Л/Л +

а

2Хл=ь 1=1

(2 12)

(2 13)

а=1, (2 14)

(2 15)

а = 1, (2 16)

а=1. (2 17)

1 л а = 1, ,а , (2 18)

(2 19)

,аг, (2 20)

и

-J- - (2 21)

х,, у,, zk е{0,1}, г = 1, ,п, j = 1, ,т,к = \, ,/ (2 22)

В ограничениях (2 14) - (2 21) коэффициенты при переменных равны 1,

если в графе G имеется соответствующее ребро Например, 1, если в графе

G содержится ребро (w,,pa) и 5aJ=0 в противном случае

Неравенство (2 13) соответствует условию выбора для потребителя не более ß приемов коррекции Ограничение (2 14) показывает, что все недостатки фигуры должны быть «покрыты» Неравенства (2 15) - (2 17) отражают условие согласованности приемов из разных классов Равенства (218) отвечают требованию о включении в решение одного приема из каждой группы основных приемов Условия (2 19) - (2 21) означают, что приемы внутри каждого класса не должны противоречить друг другу Для получения нескольких вариантов изделий в процессе проектирования нами использовались различные значения у], у1, у;, i=l, ,n,j=l, ,т, к=1, ,1

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

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

Разработанный подход может быть использован и для других видов изделии

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

Приведем постановку задачи Пусть G = (V,E) - ориентированный связный граф с множеством вершин V и множеством дуг Е Каждая вершина из Vсоответствует определенному свойству материала Пусть vt, ,vn -рассматриваемые свойства, между которыми имеются зависимости, 2 = 1, ,п Если свойство vt зависит от v,, то в графе содержится дуга (v,, v^) е Е

Пусть V - множество всех вершин графа G, каждая из которых является началом хотя бы одной дуги Введем целочисленный вектор b = (b]t ,bn)T, bt > 1, i = 1, ,п, который используется для описания степени зависимости свойств Множество VcF называется ¿-доминирующим, если для любой вершины vk <£. V найдутся по крайней мере bt вершин из V такие, что vt является концом дуг, исходящих из указанных вершин

Задача состоит в отыскании ¿-доминирующего множества минимальной мощности В отличие от классической постановки задачи в нашем случае

каждая вершина ¿»-доминирующего множества должна иметь хотя бы одну выходящую из нее дугу

Для решения этой задачи использовалась модель ЦЛП, которая строится следующим образом Введем переменные х;, ] = 1, ,п

^ Г1, если свойство } входит в доминирующее множество,

1 [0, иначе

Построим целочисленную матрицу А = {ац), г,] -1, ,п по правилу 1, если дуга \ Ф ],

Ь,, если V, еV, I = у, О, в противном случае Модель ЦЛП имеет вид

/М = Хл ->тш ПП

при условиях

¿яЛ>&„ г=1, ,п, (3 2)

м

х,е{0,1}, 7 = 1, ,и (3 3)

Правая часть системы ограничений (3 2) содержит компоненты вектора чисел Ь Это означает, что свойство г должно быть «покрыто » не менее Ь/ раз, 2=1, ,п Задача (3 1) - (3 3) является //Р-трудной Для решения задач такого типа существует значительное число алгоритмов, основанных на методах ветвей и границ, отсечения, перебора ¿-классов и других

Для апробации математических моделей были использована совокупность свойств пушно-мехового полуфабриката Специалистами в области технологии меха и кожи определены 20 свойств кожевой ткани и установлены взаимосвязи между ними, на основе которых построен ориентированный граф и соответствующая математическая модель С помощью пакета программ для решения задач ЦЛП, разработанного в лаборатории дискретной оптимизации Омского филиала Института математики СО РАН, проведен вычислительный эксперимент на ЭВМ и найдено минимальное множество ведущих свойств кожевой ткани Аналогичные исследования выполнены для волосяного покрова пушно-мехового полуфабриката Полученные результаты согласуются с мнением экспертов

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

Рассмотрим задачу о покрытии (1 1)-(1 3) Пусть D - множество ее допустимых решений и г>0 Окрестностью радиуса г точки х e l) назовем множество Nr(x) = {y eD, p(x,y)<r, х Ф у}, где p(x,y)='YJ\xJ~yl\ -

JSN

расстояние Хемминга между х и у Точку х будем называть центром окрестности

В алгоритмах локального поиска (Local Search, сокращенно LS) выбирается некоторое начальное допустимое решение X Задается окрестность Nr{x) с центром в л: и находится локальный минимум х' е N] (х) Далее, если возможно, осуществляется переход в полученное решение и строится новая окрестность с центром в х' Процесс повторяется до выполнения какого-либо правила остановки

В основе алгоритмов поиска с запретами (Tabu Search, сокращенно TS) лежит идея «разумного» перебора локальных оптимумов В этих алгоритмах возможен переход в допустимое решение с ухудшением значения целевой функции Для избежания зацикливания в алгоритме используется список запрещенных элементов поиска (координат точек пространства, ребер графа и тд), те список запретов (Tabu List, сокращенно TL) В некоторых случаях элементы, находящиеся в списке запретов, становятся разрешенными, если они удовлетворяют условию перспективности (Aspiration Criterion, сокращенно АС), которое разрешает поиск в направлении данного элемента Правило перехода от одного элемента к другому определяется спецификой задачи

В разработанных алгоритмах TS в список запретов заносятся просмотренные точки Для задачи о покрытии и моделей из глав 2 и 3 условие перспективности АС означает следующее Пусть точка х - центр окрестности Если любая точка окрестности Nr(x) лежит в списке запретов или недопустима, тогда разрешается переход в направлении ухудшения значения целевой функции, причем в качестве центра следующей окрестности выбирается наилучшая точка из списка запретов Управляющими параметрами данного алгоритма являются доля просматриваемых точек окрестностей, длина списка запретов и количество итераций

Для поиска начальных решений и сокращения размерности задачи достаточно эффективным оказался метод Лагранжевой релаксации В данном подходе с помощью субградиентного алгоритма находятся множители Лагранжа, позволяющие выполнять отбор наиболее «перспективных» переменных задачи Предложены гибридные схемы поиска приближенных решений для рассматриваемых задач, в которых сочетаются алгоритмы локальной оптимизации, поиска с запретами и метода Лагранжевой релаксации В этих алгоритмах при решении задач использовались окрестности радиусов ге{ 1,2,3} Разработанные алгоритмы реализованы в среде программирования Borland С ++ Buildei 6

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

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

В качестве тестовых задач использовались серии 4 - 6, А, В и С из электронной библиотеки OR-Library (число переменных от 1000 до 4000, количество ограничений от 100 до 200), а также задачи специального вида (3 1)--(3 3) Вычисления проводились на компьютере со следующими характеристиками процессор Intel Pentium IV 1,6 GHz, объем оперативной памяти 512 Мб Для указанных задач во многих случаях были найдены оптимальные решения Относительная погрешность полученных приближенных решений по сериям задач 4-6, А не превышала в среднем 1,3% для алгоритмов LS2, LS3, и 1,1% - для TS2, TS3 Для серий В, С и тех же алгоритмов погрешность равнялась в среднем 5,7% и 4,3%, соответственно Среднее время счета по всем сериям задач составляло около 30 секунд

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

В заключении сформулированы основные результаты и выводы диссертационной работы

В приложениях содержатся исходные данные ряда решенных задач и некоторые результаты проведенных расчетов на ЭВМ

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

5 Создано программное обеспечение и с его помощью выполнены экспериментальные исследования, которые подтверждают эффективность и практическую значимость указанных моделей и разработанных алгоритмов Применение разработанного программного обеспечения позволяет сокращать затрачиваемые ресурсы, в том числе трудовые и временные на 20% и более Использование процедур метода поиска с запретами повышает эффективность локального поиска по точности решения до 1,4%

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

В рецензируемом журнале из списка ВАК

1 Разработка моделей дискретной оптимизации для формирования коллекции подростковой одежды / А А Колоколов, А Б Коробова, Е О Захарова, Ю й Привалова // Омский научный вестник Омск, 2006 № 7 (43) С 138-140

В других изданиях

2 Применение моделей дискретной оптимизации для исследования свойств пушно-мехового полуфабриката / А А Колоколов, ЗЕ Нагорная, Н И Ковалева, Ю И Привалова // Совершенствование системы специалистов для сферы сервиса матер per научн -практ юбилейной конф Омск, 2002 Ч 2 С 69-71

3 Применение некоторых задач о покрытии для выделения ведущих свойств пушно-мехового полуфабриката / А А Колоколов, 3 Е. Нагорная, Н И Ковалева, Ю И Привалова // Проблемы оптимизации и экономические приложения матер Всерос конф Омск, 2003 С 173

4 Выделение ведущих свойств пушно-мехового полуфабриката с применением дискретной оптимизации / А А Колоколов, 3 Е Нагорная, Н И Ковалева, Ю И Привалова // Омский научный вестник Омск, 2003 № 2 (23) С 41-43

5 Исследование свойств волосяного покрова пушно-мехового полуфабриката с использованием некоторых задач оптимизации на графах / А А Колоколов, 3 Е Нагорная, Н И Ковалева, Ю И Привалова // Актуальные проблемы подготовки специалистов для сферы сервиса сб статей Междунар научн -практ конф Омск, 2003 Ч 2 С 113-114

6 Определение ведущих свойств волосяного покрова пушно-мехового полуфабриката с использованием некоторых задач о покрытии /НИ Ковалева, Ю И Привалова // Дискретный анализ и исследование операций матер Росс

конф Новосибирск Издательство Института математики СО РАН, 2004

7 Алгоритмы решения некоторых задач о покрытии / Ю И Привалова, А Г Лукьянов // Под знаком X матер III Всеросс научн молодежной конф Омск, 2005 С 79-80

8 Применение методов дискретной оптимизации для формирования коллекции подростковой одежды препринт / А А Колоколов, А Б Коробова, Е О Захарова, Ю И Привалова // Омск Изд-во «КАН», 2005 24 с

9 Формирование коллекции моделей подростковой одежды с использованием дискретной оптимизации / А А Колоколов, А Б Коробова, Е О Захарова, Ю И Привалова // Современные тенденции и перспективы развития образования в высшей школе сб статей III Междунар научн -практ конф Омск, 2005 Ч 1 С 103-104

10 О решении одной задачи проектирования с использованием методов дискретной оптимизации / Ю И Привалова // Проблемы теоретической и прикладной математики Тр 37-й Per молодежной конф Екатеринбург УрО РАН, 2006 С 398-401

11 Двухкритериальная модель дискретной оптимизации для формирования коллекции подростковой одежды / А А Колоколов, Ю И Привалова // Проблемы оптимизации и экономические приложения матер III Всеросс конф Омск, 2006 С 178

12 Применение дискретной оптимизации для создания эскизов подростковой одежды с учетом особенностей фигуры препринт / А А Колоколов, А Б Коробова, Е И Кузнецова, Ю И Привалова // Омск Изд-во «КАН», 2006 20 с

13 Приложение методов оптимизации в создании коллекции одежды / А А Колоколов, Ю И Привалова // Исследование операций матер междунар конф , Германия, Карлсруе 2006 С 57 (На англ языке)

14 Формирование набора подростковой одежды с использованием методов дискретной оптимизации / Е И Кузнецова, Ю И Привалова // Матемашческое программирование и приложения матер XIII Всеросс конфер Екатеринбург

ИММ УрО РАН, 2007 С 126 - 127

15 Некоторые эвристические алгоритмы для задачи о покрытии множества препринт/Ю И Привалова//Омск Изд-во «КАН», 2007 18 с

С 222

Соискатель

Привалова Юлия Ивановна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ОПТИМИЗАЦИИ ВЫБОРА ОБЪЕКТОВ В ПРОЦЕССЕ ТЕХНИЧЕСКОЙ ПОДГОТОВКИ ПРОИЗВОДСТВА (на примере легкой промышленности)

Специальность 05 13 18 - Математическое моделирование, численные методы

и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 21 092007 Формат 60x84 1/16 Бумага офсетная Печать плоская Гарнитура Тайме Уел печ. л 1,0 Уел кр -отт 1,0 Уч.-изд л 0,9 Тираж 100 экз Заказ № 475

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул К Маркса, 12

Введение

Оглавление

1. Задачи о покрытии и их приложения в легкой 11 промышленности и других отраслях

1.1. Модели и методы оптимизации на этапе технической 11 подготовки производства

1.2. Постановки задач о покрытии и их свойства

1.2.1. Задача о наименьшем покрытии множества

1.2.2. Задача о наименьшем доминирующем множестве вершин графа

1.2.3. Некоторые свойства задач о покрытии

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

Актуальность темы исследования. В настоящее время математическое моделирование и компьютерные технологии широко применяются для решения различных задач, возникающих в экономике, управлении, проектировании и других сферах деятельности. Значительное внимание уделяется использованию моделей и методов дискретной оптимизации. Это обусловлено необходимостью решать достаточно сложные задачи с большим числом возможных вариантов и выбирать из них наилучшие с учетом различных ограничений [10,14,17,18,20, 27,36-38,40,42,43,71,81,94,109,110].

На предприятиях легкой промышленности в процессе технической подготовки производства часто возникают ситуации, связанные с проблемой формирования наборов объектов (например, машин, изделий, приемов, свойств), которые покрывают «потребности» другой совокупности (работ, клиентов, заказов и др.) при выполнении определенных условий, обусловленных спецификой задачи, причем указанные наборы должны быть оптимальными для одного или нескольких критериев. Во многих случаях данная проблема является весьма сложной и требует применения математического аппарата. В частности, в швейном производстве актуальным является создание наборов одежды, ориентированных на разные категории потребителей. Для решения подобных задач представляется достаточно естественным использование задач о покрытии и их обобщений, моделей и методов дискретной оптимизации, в частности, целочисленного линейного программирования (ЦЛП) [10,18,27,29,30,36,38,41,42,76,80,86,105].

Задачи о покрытии и их обобщения, как правило, являются yVP-трудными и требуют построения эвристических алгоритмов, которые могут быть использованы в прикладных исследованиях [9,19,37,40,74]. В последние годы в области дискретной оптимизации в этом направлении активно велись разработки методов локального поиска, известных как алгоритмы муравьиной колонии, поиска с запретами, генетические и др. [2,15,34,84,85,89,95,96,98, 100,102,106,108-110,]. Построение алгоритмов такого типа представляется перспективным и для рассматриваемых нами задач, возникающих на этапе технической подготовки производства.

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

Для достижения данной цели поставлены и решены следующие задачи:

1. Разработать подход к оптимизации выбора объектов в процессе технической подготовки производства и определению доминирующих свойств материалов.

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

3. Разработать математические модели для нахождения минимального множества доминирующих свойств, влияющих на оценку качества материала.

4. Построить алгоритмы, основанные на методах локального поиска для решения поставленных задач.

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

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

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

1. Подход к оптимизации выбора объектов в процессе технической подготовки производства и определению доминирующих свойств материалов, основанный на применении задач о покрытии и их обобщений.

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

3. Математические модели для нахождения минимального множества доминирующих свойств, влияющих на оценку качества материала.

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

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

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

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

2. С использованием указанного подхода построены новые математические модели и решены следующие задачи:

• формирования наборов изделий с учетом нескольких критериев для запуска в производство,

• оптимизации выбора изделий для индивидуального потребителя,

• нахождения минимального множества доминирующих свойств материалов, влияющих на оценку его качества.

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

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

Результаты диссертационной работы применимы для решения практических задач в различных отраслях, а также в учебном процессе при подготовке специалистов в области применения математических методов и современных информационных технологий. В частности, они внедрены на швейном предприятии по изготовлению детской и подростковой одежды, в ателье «Ренард» филиала «Иртыш» РООИВиВК (г. Омск), на кафедре «Технология и методика преподавания технологии» Омского государственного педагогического университета при подготовке студентов специальности 030600 «Технология и предпринимательство» и направления 540500 «Технологическое образование» по дисциплинам «Компьютерное моделирование технологических процессов» и «Организация и технология предприятий бытового обслуживания».

Апробация работы. Основные результаты диссертации опубликованы в работах [7,13,16,28,46,48,52,58,60-62,68,77,78, 91] и докладывались на следующих конференциях и семинарах: Региональной научно-практической юбилейной конференции «Совершенствование системы подготовки специалистов для сферы сервиса», Омск, 2002; Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2003; Международной научно-практической конференции "Актуальные проблемы подготовки специалистов для сферы сервиса", Омск, 2003; Российской конференции «Дискретный анализ и исследование операций», Новосибирск, 2004; XXIX Региональной научной студенческой конференции «Молодежь III тысячелетия», ОмГУ, 2005; III Всероссийской научной молодежной конференции «Под знаком £», Омск, 2005; XXXVII Региональной молодежной школе-конференции "Проблемы теоретической и прикладной математики", Екатеринбург, 2006; III Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омск, 2006; XIII Всероссийской конференции «Математическое программирование и приложения», Екатеринбург, 2007; заседаниях семинара «Математическое моделирование и дискретная оптимизация» в Омском филиале Института математики СО РАН, заседаниях кафедр в Омском государственном университете и Уфимском государственном авиационном техническом университете.

Публикации. По теме диссертации опубликовано 15 печатных работ, в том числе одна статья в рецензируемом журнале из списка ВАК.

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

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

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

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

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

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

5. Создано программное обеспечение и с его помощью выполнены экспериментальные исследования, которые подтверждают эффективность и практическую значимость указанных моделей и разработанных алгоритмов. Применение разработанного программного обеспечения позволяет сокращать затрачиваемые ресурсы, в том числе трудовые и временные на 20% и более. Использование процедур метода поиска с запретами повышает эффективность локального поиска по точности решения до 1,4%.

6. Результаты диссертационной работы могут использоваться при решении практических задач и в учебном процессе при подготовке специалистов в области применения математических методов и современных информационных технологий. В частности, они внедрены на швейном предприятии по изготовлению детской и подростковой одежды, в ателье «Ренард» филиала «Иртыш» РООИВиВК (г. Омск), на кафедре «Технология и методика преподавания технологии» Омского государственного педагогического университета при подготовке студентов специальности 030600 «Технология и предпринимательство» и направления 540500 «Технологическое образование».

Заключение

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

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

1. Алгоритм муравьиной колонии для задачи о минимальном покрытии / Д.А. Александров // Методы оптимизации и их приложения : тр. XI междунар. Байкальской школы-семинара. Иркутск, 1998. Т.З. С. 17-20.

2. Алгоритм определения типов телосложения подростков для автоматизированного проектирования гармоничного образа / А.Б. Коробова, Е.И. Кузнецова, Е.О. Захарова // Омский научный вестник. Омск, 2004. №4 (29). С. 150 153.

3. Алгоритм решения задачи прямоугольного гильотинного раскроя на базе метаэвристики имитации отжига / Т.Ю. Сиразетдинова, А.Ф. Валеева // Проблемы оптимизации и экономические приложения: матер. III Всеросс. конф. Омск, 2006. С. 126.

4. Алгоритмы и программы решения задач на графах и сетях / М.И. Нечепуренко, В.К. Попков, С.М. Майнагашев и др. Новосибирск: Наука, 1990. 515 с.

5. Алгоритмы муравьиной колонии для решения задачи о вершинном покрытии / JI.A. Заозерская, М.С. Седельников // Дискретный анализ и исследование операций: материалы международной конференции. Новосибирск: Изд-во ИМ СО РАН, 2000. С. 231.

6. Алгоритмы решения некоторых задач о покрытии / Ю.И. Привалова, А.Г. Лукьянов // Под знаком I: матер, докладов III Всеросс. научн. молодежной конфер. Омск, 2005. С.79 80.

7. Анализ процесса разработки конструкций и направления его совершенствования // Швейная промышленность. М., 1996. № 6. С. 15-16.

8. Асимптотическое исследование задачи о покрытии / Н.Н. Кузюрин // Проблемы кибернетики. М., 1980. Вып. 37. С. 19 57.

9. Введение в исследование операций. Пер. с англ./ Таха Хемди, А. М.: Издательский дом «Вильяме», 2001. 912 с.

10. Внедрение компьютерных технологий проектирования и изготовления одежды / Л.В. Мурашов, С.В. Наумович // Швейная промышленность, М., 2004. №2. С. 39-40.

11. Выделение ведущих свойств пушно-мехового полуфабриката с применением дискретной оптимизации / А.А. Колоколов, З.Е. Нагорная, Н.И. Ковалева, Ю.И. Привалова // Омский научный вестник. Омск, 2003. №2 (23). С. 41-43.

12. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. Пер. с англ. М.: Мир. 1982. 416 с.

13. Генетический алгоритм для задачи о покрытии / А.В. Еремеев// Дискретный анализ и исследование операций. 2000. Сер. 2, Т. 7, №1. С. 47-60.

14. Двухкритериальная модель дискретной оптимизации для формирования коллекции подростковой одежды / А.А. Колоколов, Ю.И.

15. Привалова // Проблемы оптимизации и экономические приложения: матер. III Всеросс. конф. Омск, 2006. С. 178.

16. Дискретные задачи размещения и полиномы от булевых переменных / B.JI. Береснев. Новосибирск: Издательство Института математики СО РАН. 2005. 408 с.

17. Дискретное программирование / А.А. Корбут, Ю.Ю. Финкельштейн. М.: Наука, 1969.368 с.

18. Задача о покрытии множества; сложность, алгоритмы, экспериментальные исследования / А.В. Еремеев, JI.A. Заозерская, А.А. Колоколов // Дискретный анализ и исследование операций. 2000. Сер. 2, Т.7, № 2. С. 22-46.

19. Задача оптимального размещения центров телекоммуникаций в регионе/ JI.A. Заозерская, Е. Китриноу, А.А. Колоколов // Методы оптимизации и их приложения: труды XIII Байкальской международной школы-семинара. Иркутск: ИСЭМ СО РАН, 2005. Т.1. С. 469-475.

20. Задачи о покрытии и их приложения / А.В. Еремеев, JI.A. Заозерская,

21. A.А. Колоколов // Вычислительные методы и решение оптимизационных задач: матер, междунар. семинара. Новосибирск, 2004. С. 70 76.

22. Использование метода группировки для задачи линейного раскроя /

23. B.М. Картак // Проблемы оптимизации и экономические приложения: матер. III Всеросс. конф. Омск: ОФИМ СО РАН, 2006. С. 98.

24. Использование элементов систем автоматизированного проектирования одежды в учебном процессе / Е. О. Захарова, А.Б. Коробова, В.М.

25. Рындина // Технолого-экономическое образование в XXI веке: от теории к практике : сб. тр. II Междунар. научн.-практ. конф. Новосибирск: Изд. НГПУ, 2005, 4.2. С. 22 25.

26. Исследование влияния элементов конструкции на функциональное состояние организма подростка для применения в САПР одежды /

27. A.Б. Коробова, Е.О. Захарова, Е.И. Кузнецова // Омский научный вестник. Омск, 2005. №1 (30). С. 178 180.

28. Исследование мощности L-накрытий некоторых задач о покрытии / Л.А. Сайко // Дискретная оптимизация и анализ сложных систем: Сб. науч. тр. Новосибирск: ВЦ СО АН СССР, 1989. С. 76 97.

29. Исследование операций / Е.С. Вентцель. М.: Наука, 1988. 208 с.

30. Качественные вопросы целочисленного програмиирования/

31. B.Н. Шевченко. М.: Физматлит, 1995. 190 с.

32. Комбинаторная оптимизация: алгоритмы и сложность/ X. Пападимитриу, К. М. Стайглиц //М.:Мир, 1985. 512 с.

33. Композиция костюма: Учеб. пособ. для студ. высш. учеб, завед. / Г.М. Гусейнов, В.В. Ермилова, Ермилова Д.Ю. и др. М.: Издательский центр «Академия», 2003. 432 с.

34. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. М.: Наука, 1990. 344 с.

35. Логический синтез каскадных схем /А.Д. Закревский. М.: Наука, 1981. 145 с.

36. Локальный поиск для дискретных задач размещения/ Ю.А. Кочетов// Проблемы оптимизации и экономические приложения: матер. III Всеросс. конф. Омск, 2006. С. 47 51.

37. Маркетинговые исследования как основа формирования структуры промышленных коллекций / Е.Б. Коблякова, И.А. Тузова, Е.К. Волкова // М.: Швейная промышленность. 1997. № 3. С. 33 36.

38. Математические модели и методы решения задач дискретной оптимизации/И.В. Сергиенко. Киев: Наук, дум., 1988.472 с.

39. Математические модели связности / В.К. Попков. Новосибирск: Изд. ИВМиМГ СО РАН, 2006. 490 с.

40. Математическое программирование. Теория и алгоритмы / М. Мину. М.:Наука, 1990.488 с.

41. Метод наискорейшего спуска в задачах на покрытие/ Р.Г. Нигматуллин // Вопросы точности и эффективности вычислительных алгоритмов: тр. симпоз. Киев, 1969. Вып. 5. С. 116-126.

42. Методы дискретной оптимизации / А.А. Колоколов. Учебное пособие. Омск: ОмГУ, 1984. 110 с.

43. Методы и модели исследования операций / А. Кофман, А. Анри-Лабодер. М.: Мир, 1977. 523 с.

44. Методы локального поиска в дискретных задачах оптимального распределения ресурса / Э.А. Мухачева, А.Ф. Валеева, А.С. Мухачева // Уфа:Изд-во УГАТУ, 2001. 103 с.

45. Многогранники, графы, оптимизация / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. М.: Наука, 1981. 384 с.

46. Некоторые эвристические алгоритмы для задачи о покрытии множества: препринт/Ю.И. Привалова//Омск: ОмГУ, 2007. 18 с.

47. Об изучении одежды в психологической науке / Е.А. Петрова, Н.А. Коробцева // Швейная промышленность. М., 1998. №3. С. 32 34.

48. Оптимизация выбора методов обработки швейных изделий / А.А. Колоколов, З.Е. Нагорная, Е.Ю. Печаткина // Динамика систем, механизмов и машин: сб. докладов V Международной научн.-техн. конф. Омск: ОмГТУ, 2004. С. 286 288.

49. О решении одной задачи проектирования с использованием методов дискретной оптимизации / Ю.И. Привалова // Проблемы теоретической и прикладной математики: тр. 37-й Per. молодежной конф. Екатеринбург: УрО РАН, 2006. С. 398 401.

50. О сложности задач минимизации полиномов от булевых переменных /

51. A.А. Агеев // Управляемые системы. Новосибирск, 1983. №23. С. 3 11.

52. Основные принципы разработки автоматизированной подсистемы проектирования рациональной структуры промышленной коллекции / И.А. Тузова, Е.Б. Коблякова, И.В. Мистюкова // Швейная промышленность. М.,1997. № 6. С. 34.

53. Парето-оптимальные решения многокритериальных задач/

54. B.В. Подиновский, В.Д. Ногин. М.:Наука, 1982. 256 с.

55. Приближенный алгоритм для решения задачи о покрытии множествами / А.А. Агеев // Дискретный анализ и исследование операций : матер. Росс. конф. Новосибирск. Институт математики СО РАН, 2002. С. 199.

56. Применение дискретной оптимизации для создания эскизов подростковой одежды с учетом особенностей фигуры: препринт / А.А. Колоколов, А.Б. Коробова, Е.И. Кузнецова, Ю.И. Привалова // Омск: ОГИС, 2006. 20 с.

57. Применение методов дискретной оптимизации для формирования коллекции подростковой одежды: препринт / А.А. Колоколов, А.Б. Коробова, Е.О. Захарова, Ю.И. Привалова // Омск: ОГИС, 2005. 24 с.

58. Применение регулярных разбиений в целочисленном программировании/ А.А. Колоколов // Изв. вузов, Омск, 1993. № 12. С.11-30.

59. Применение L-разбиения к исследованию некоторых задач выполнимости / А.А. Колоколов, А.В. Аделыпин, Ю.Н. Чередова // Методы оптимизации и их приложения: тр. 12-й Байкальской междунар. конф. Иркутск, 2001. С. 166 172.

60. Проектирование детской одежды.Учеб. пособие для студ. высш. учеб. заведений / Бескоровайная Г. П., Куренова С.В. М.: Мастерство. 2000. 128 с.

61. Проектирование меховых изделий с использованием математического моделирования / А.А. Колоколов, З.Е. Нагорная, М.Ю. Архипенко // Динамика систем механизмов и машин: сб. статей IV Международной научн.- техн. конф. Омск: ОмГТУ, 2002. С. 297 299.

62. Развитие основ формирования качества при проектировании конструкций одежды/Медведева Т.В. Автореф. дис. . докт. техн. наук. -М: МГУС, 2004. 48 с.

63. Разработка моделей дискретной оптимизации для формирования коллекции подростковой одежды / А.А. Колоколов, А.Б. Коробова, Е.О. Захарова, Ю.И. Привалова // Омский научный вестник. Омск, 2006. № 7 (43). С. 138- 140.

64. Регулярные разбиения и лексикография / А.А. Колоколов, J1.A. Заозерская // Учебно-методическое пособие. Омск: ОмГУ, 1999. 98 с.

65. Регулярные разбиения и отсечения в целочисленном программировании / А.А. Колоколов // Сибирский журнал исследования операций. Новосибирск, 1994. Т. 1. № 2. С. 18 39.

66. Социометрические методы в САПР одежды подростка / Е.О. Захарова, Е.И. Кузнецова, О.В. Драгун // Молодежь, наука, творчество : сб. статей второй межвузовской научн.-практ. конф. студентов и аспирантов. Омск: ОГИС, 2004. Ч. 2. С. 209-212.

67. Соционика: Психотипы. Тесты / А. Аугустинавичюте, Сост. JI. Филиппов. М.: ООО "Фирма "Издательство ACT". 1998. 416 с.

68. Теория графов. Алгоритмический подход / Н. Кристофидес. М.: Издательство «Мир», 1978. 432 с.

69. Теория графов / Ф. Харари. М.: Издательство «Мир», 1973. 300 с.

70. Теория линейного и целочисленного программирования. Пер. с англ. В 2-х т./ А. Схрейвер. М.: Мир, 1991. 702 с.

71. Формирование коллекции моделей подростковой одежды с использованием дискретной оптимизации / А.А. Колоколов, А.Б.

72. Коробова, Е.О. Захарова, Ю.И. Привалова // Современные тенденции и перспективы развития образования в высшей школе: сб. статей III Межд. научн.-практ. конф. Омск, 2005. Ч. 1. С. 32.

73. Формирование набора подростковой одежды с использованием методов дискретной оптимизации / Е.И. Кузнецова, Ю.И. Привалова // Математическое программирование и приложения: тезисы докладов XIII Всеросс. конф. Екатеринбург: УрО РАН, 2007. С. 126 127.

74. Целочисленное программирование и потоки в сетях. Пер. с англ./ Т.С. Ху. М.:Мир, 1974.519 с.

75. Экстремальные задачи стандартизации / B.J1. Береснев, Э.Х. Гимади, В.Т. Дементьев. Новосибирск: Наука. 1978. 333 с.

76. A Dynamic Subgradient-Based Branch and Bound Procedure for Set Covering / E. Balas, M.C. Carrera // Oper.Res., 1996. Vol. 44, N 6. P. 875 -890.

77. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem / A.V. Eremeev // In Proceedings of OR'98, Springer-Verlag, 1999. P.175-181.

78. A Genetic Algorithm for the SCP/ J.E. Beasley, P.C. Chu// European J. Oper. Res. 1996. Vol. 94, № 2. P. 394 404.

79. A Genetic Algorithm for the Set Covering Problems / J.E. Beasley, P.C. Chu // European Journal for Operation Research, 31,1990. P.85 93.

80. A greedy heuristic for the set-covering problem / V. Chvatal // Math. Oper. Res., 1979. №8. P.789- 810.

81. Algorithms for the set covering problem / A. Caprara, M. Fischetti, P. Toth // DEIS Operations Research Group, 1998. Techical Rep. No. OR-98-3.

82. A New Rank Based Version of the Ant System: A Computational Stady / B. Bullnheimer, R.F. Hart, C. Strauss // Central European Journal for Operation Research 7(1), 1999. P. 25 38.

83. Ant Algorithms for Discrete Optimizations / M. Dorigo, G. Di Caro, L.M. Gambardella // Artifical Life, 1999. V. 5(2). P. 137 172.

84. Ant Colony Optimization / M. Dorigo, T. Stutzle // MIT Press, 2004.

85. Application of Some Optimization Methods to Computer Added Design of Clothes Collections / A. Kolokolov, Yu. Privalova // Karlsruhe (Germany). International Conference on Operations Research, Abstract Guide, 2006. P. 57.

86. Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and Related Problems / D.S. Hochbaum // Approximation Algorithms for NP-Hard Problems. Ed. by S.D. Hochbaum. PWS Publishing Company, 1995. P.94 - 143.

87. Behavior of the Ant Colony Algorithm for the Set Covering Problem / D. Alexandrov, Y. Kochetov // Proc. of Symp. on Oper. Res.(SOR'99). -Springer Verlag, 2000. P. 255 260.

88. Discrete Location Theory / Ed. by Pitu B. Mirchamdani and Richard L. Franscis, 1990, by John Wiley & Sons, Inc.

89. Distributed optimization by ant colonies / A. Colorny, M. Dorigo, V. Maniezzo // In Proceedings of the First European Conference on Artifical Life, Elsevier, 1992. P. 134 142.

90. General local search methods / M. Pirlot / European Journal of Operational Reasearch. 1996. P. 493 511.

91. Hardness of Approximations / S. Arora, C. Lund // Approximation Algorithms for NP-Hard Problems, Ed. By S.D. Hochbaum.-PWS Publishing Company, 1995. P. 399 446.

92. Heuristic Method for the Set Covering Problem / A. Caprara, M. Fischetti, P. Toth // Operation Research, 47, 1999. P. 730 743.

93. Improved Approximation Guarantees for Packing and Covering Integer Programs / A. Srinivasan // SIAM Journ. on Computing. 1999. Vol. 29. P. 648 - 670.

94. Kirkpatrick S. Optimization by simulated annealing / S. Kirkpatrick, Jr. Gelatt, C.D., and M.P. Vecchi //. Science 220. 1983. P. 671 680.

95. Lagrangean heuristic for location problems / J.E. Beasley // European Journal of Operational Research, 1993. № 65. P. 383 399.

96. Local Search in combinatorial optimization / Edited by E.Aarts and J.K.Lenstra, 1997. John Wiley & Sons Ltd.

97. On Some Approximation Algorithms for Dense Vertex Cover Problem / A.V. Eremeev // Proc. of Symp. on Oper. Research (SOR'99). Springer Verlag, 2000. P. 58 62.

98. On the Ratio of Optimal Integral and Fractional Covers / L. Lovasz // Discrete Math. 1975. Vol.13. - P.383 - 390.

99. Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimizations / E. Balas, A. Ho // A Computational study. Mathematical Programming Stady, 12,1980. P. 37 60.

100. Simulated Annealing: Theory and Practice / van Laarhoven, P.J.M., and Aarts, E.H.L. //Kluwer Academic Publishers, Dordrecht, 1987. 512 c.

101. Some Optimal Inapproximability Results / J. Hastad / Report No. TR-97-037. Trier: Electronic Colloquium on Computational Complexity, 1997.

102. Tabu Search / F. Glover., and M. Laguna // C.R. Reeves (ed.) Modern Heuristic Techniques for Combinatorial Problems, Oxford, 1993. P.70 150.

103. Tabu Search Part I / F. Glover // ORSA Journal on Computing. 1, 1989. P. 190 -206.

104. Tabu Search Part II / F. Glover // ORSA Journal on Computing. 2, 1989. P. 4-32.

105. Модель Mi Модель М2 Модель М3 Модель М4 Модель М5

106. Модель М6 Модель М7 Модель М8 Модель М9 Модель М10ух1. Модель Мц1. Модель Мц1. Модель М)31. Модель М14 Модель М (5

107. Модель Mi6 Модель М17 Модель М18 Модель MJ9 Модель М20tX

108. Модель М26 Модель М27 Модель М28 Модель М29 Модель М30r

109. Модель М36 Модель М37 Модель М38 Модель М39 Модель М40

110. Модель M4i Модель М42 Модель М43 Модель М44 Модель М45

111. Группы моделей одежды по признаку зрительного подобия.группы № модели1 1,38,392 7,83 10,174 11,12,375 13, 146 15,317 16,478 18,24,25,33,48,499 20,32, 34,3510 21,40,4111 22,2312 27,5013 29,4614 42,4515 43,44св С1. С >