Содержание к диссертации
Введение
1 Задачи дискретной оптимизации с логическими ограничениями и их приложения 12
1.1 Задача выполнимости и ее обобщения 12
1.2 Методы решения задач выполнимости и максимальной выполнимости 16
1.3 Некоторые приложения 25
2 Математические модели и алгоритмы для задач формирования сложных изделий 33
2.1 Постановка задачи 34
2.2 Модель целочисленного линейного программирования . 36
2.3 Примеры применения подхода 38
2.4 Постановка задачи и модель ЦЛП с учетом групп составляющих и характеристик изделия 47
2.5 Алгоритмы решения задачи 53
3 Комплекс программ для создания эскизов одежды . 68
3.1 Общая схема программного комплекса и методология проведения расчетов 68
3.2 База данных 76
3.3 Модуль визуализации 81
4 Экспериментальные исследования 85
4.1 Задача формирования эскизов женских демисезонных пальто 85
4.2 Результаты вычислительного эксперимента и анализ полученных решений 94
Заключение 104
Список литературы 105
- Методы решения задач выполнимости и максимальной выполнимости
- Модель целочисленного линейного программирования
- База данных
- Результаты вычислительного эксперимента и анализ полученных решений
Введение к работе
Актуальность темы исследования. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, управлении, исследовании социально-экономических, технических и других систем. Весьма актуальным является направление, связанное с процессами создания сложных изделий, которые комбинируются из большого числа разнотипных элементов с учетом логических, ресурсных и других ограничений.
Ограничения логического типа играют важную роль при формировании сложных изделий, поскольку они существенно влияют на основную структуру изделия и его свойства. Эти ограничения относятся к выбору и возможным сочетаниям элементов, из которых образуется изделие, а также к отысканию конструктивных, технологических и экономических решений.
В настоящее время в области создания сложных изделий имеются системы, которые обеспечивают высокое качество принимаемых решений, сокращают расход ресурсов и время на изготовление новых изделий, повышают эффективность труда специалистов. Вместе с тем в указанных разработках недостаточно применяются модели и методы оптимизации, что во многих случаях приводит к перебору и сравнению большого числа вариантов.
Ранее в работах А.А. Колоколова и А.В. Ярош предложен подход к построению эскизов одежды, основанный на использовании задач дискретной оптимизации с логическими и ресурсными ограничениями. Экспериментальные исследования показали необходимость дальнейшего развития данного подхода с расширением сферы его применения.
Задачи дискретной оптимизации с логическими ограничениями достаточно интересны как в теоретическом, так и в прикладном отношении. Наиболее известными среди них являются задачи выполнимости (задача SAT) и максимальной выполнимости логической формулы (задача MAX-SAT). Имеется значительное число работ, посвященных изучению сложности и структуры этих задач, выделению полиномиально разрешимых случаев и семейств «трудных» задач, разработке точных и приближенных алгоритмов их решения, различных эвристик, проведению теоретического и экспериментального анализа алгоритмов. Среди основных методов, на которых базируются разрабатываемые алгоритмы, можно выделить методы расщепления, ветвей и границ, отсечения, перебора L-классов, локальный поиск и ряд других.
Одним из широко известных подходов к решению задач SAT и MAX-SAT является использование аппарата целочисленного линейного
программирования (ЦЛП). Для анализа задач целочисленного
программирования, построения и исследования алгоритмов
А.А. Колоколовым был предложен метод регулярных разбиений. С использованием этого подхода исследована сложность решения ряда задач, изучена структура релаксационных множеств, рассмотрены вопросы устойчивости задач и алгоритмов, получены оценки числа итераций и ряд других важных теоретических результатов. Значительное число исследований проведено на основе L-разбиения, в частности, для задач SAT и MAX-SAT, которые показали перспективность его применения. Поэтому актуальным является дальнейшее использование метода регулярных разбиений для анализа и решения задач с логическими и ресурсными ограничениями.
Цель диссертации — разработка и исследование математических моделей для решения задач формирования сложных изделий, построение и анализ алгоритмов их решения.
Для достижения поставленной цели решались следующие задачи:
Построить и исследовать математические модели для задач формирования сложных изделий с учетом логических и ресурсных ограничений.
Разработать алгоритмы решения рассматриваемых задач с использованием целочисленного линейного программирования и метода перебора L-классов.
Провести экспериментальное исследование построенных математических моделей и алгоритмов, возможностей их применения для решения задач формирования сложных изделий.
Создать программный комплекс для апробации развиваемого подхода на примере построения эскизов одежды.
Методы исследования. В процессе выполнения работы использовались
методы математического моделирования, математической логики, дискретной оптимизации, целочисленного линейного программирования, а также современные достижения в области применения компьютерных технологий.
На защиту выносятся:
1. Математические модели для решения задач формирования сложных изделий, в частности эскизов одежды, с учетом логических и ресурсных ограничений, основанные на использовании дискретной оптимизации.
Алгоритмы перебора L-классов для решения предложенных задач целочисленного линейного программирования, результаты экспериментальных исследований.
Комплекс программ для построения эскизов одежды, разработанный на основе развиваемого подхода к формированию сложных изделий.
Научная новизна работы состоит в следующем:
Для решения задач формирования сложных изделий с учетом логических и ресурсных ограничений построены и исследованы новые математические модели с использованием дискретной оптимизации, в том числе целочисленного линейного программирования.
На основе метода перебора L-классов разработаны алгоритмы решения задач целочисленного линейного программирования, предложенных для формирования сложных изделий.
Указанные математические модели и алгоритмы применены к построению эскизов одежды с учетом логических и ресурсных ограничений.
Практическая значимость работы. Предложенные математические модели могут быть использованы для нахождения оптимальных решений на этапе технической подготовки производства сложных изделий. Проведенные экспериментальные исследования показали, что с помощью разработанных алгоритмов можно достаточно быстро получать множество разнообразных вариантов изделий. Результаты диссертационной работы применимы для решения практических задач в различных отраслях, а также при подготовке специалистов в области оптимизации и сфере сервиса.
Внедрение результатов работы. Результаты работы используются в учебном процессе в Омском государственном университете им. Ф.М. Достоевского.
Апробация работы. Основные результаты диссертации опубликованы в работах [1 - 12] и докладывались на следующих конференциях и семинарах: II межвузовской научно-практической конференции студентов и аспирантов «Молодежь, наука, творчество - 2004» (г. Омск, 2004); Российской конференции «Дискретный анализ и исследование операций» (DAOR'04) (г. Новосибирск, 2004); V Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск, 2004); межвузовской научно-методической конференции «Модернизация профессионального образования в условиях интеграции: проблемы обеспечения качества»
(г. Омск, 2005); XIII Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Иркутск, 2005); Международной конференции «Operations Research 2005» (г. Бремен, Германия, 2005); III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2006); Третьей азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (г. Бишкек, 2007); VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (г. Омск, 2007); научных семинарах в Омском государственном университете им. Ф.М. Достоевского, Омском филиале Института математики им. С.Л. Соболева СО РАН и Институте вычислительной математики и математической геофизики СО РАН.
Публикации. По теме диссертации опубликовано 12 печатных работ, 2 из них в рецензируемых изданиях из списка ВАК.
Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и списка используемой литературы (104 наименования). Текст диссертации изложен на 118 страницах.
Методы решения задач выполнимости и максимальной выполнимости
Значительное число работ посвящено алгоритмическим и вычислительным вопросам решения задач выполнимости и максимальной выполнимости [2, 3, 24, 28, 51, 58, 68, 81].
Широкое практическое применение рассматриваемых задач и их обобщений является стимулом для разработки алгоритмов их решения.
Существующие алгоритмы для задачи SAT могут быть разделены на две основных группы: полные (способные выяснить, выполнима формула или нет) и неполные (иногда определяют, что формула выполнима, но -не могут установить ее невыполнимость). Значительное число алгоритмов первой группы обычно основаны на методах расщепления. В неполных алгоритмах, как правило, используется локальный поиск или эволюционные вычисления. Эти алгоритмы часто намного быстрее по сравнению с полными находят для формулы выполняющий набор (если он существует). Подробное описание алгоритмов для задачи выполнимости содержится в обзоре [68].
Поскольку задача максимальной выполнимости является обобщением задачи выполнимости, многие подходы к решению задачи SAT могут быть использованы в алгоритмах решения задачи MAX-SAT.
Пусть F - формула в КНФ, содержащая п переменных. Обозначим через \F\ длину формулы F, т.е. общее число вхождений всех переменных.
Обозначим через F[x] формулу, полученную из формулы F в результате следующих операций: переменной х присваивается значение истина; исключаются все скобки, содержащие перемершую х без отрицания; литерал х удаляется из оставшихся скобок. Аналогично определяется формула F[x] (переменной х присваивается значение ложь).
Под расщепляющим алгоритмом понимается алгоритм, который сводит задачу выполнимости исходной формулы F к серии задач для более простых формул Fi, F2,..., Fp, где р - полином от F. Это сведение может быть детерминированным (рекурсивно вызывать алгоритм для каждой из формул Fi) или вероятностным (случайно выбирать одну из формул Fi). Существующие расщепляющие алгоритмы для задачи выполнимости можно разделить на два семейства: DPLL-подобные и PPSZ-подобные алгоритмы. DPLL-подобные алгоритмы основаны на процедурах, описанных в работах М. Davis, Н. Putnam, G. Logemann и D. Loveland [60, 61]. Эти процедуры принято считать первыми алгоритмами для задачи SAT. На них основано большинство современных алгоритмов расщепления, описание которых выглядит следующим образом [8]. 1. Упростить исходную формулу F, т.е. преобразовать F в другую формулу G, используя некоторые правила преобразования. 2. Если задача выполнимости для G тривиальна, выдать ответ. 3. В формуле G выбрать переменную х: используя некоторую эвристику. Вместо G рассмотреть две формулы G[x] и G[x], полученные из формулы G в результате назначений х = истина и х = лооюь соответственно. Рекурсивно вызвать процедуру для каждой из них. Формула G выполнима, если в результате хотя бы одного рекурсивного вызова получен выполняющий набор. В противном случае G невыполнима.
Таким образом, для получения конкретного алгоритма в этой общей схеме следует выбрать: 1. Правила преобразования для упрощения формул (предполагается, что на упрощение тратится полиномиальное (от \F\) время). 2. Способ (эвристику) выбора переменной для расщепления (также за полиномиальное время).
Известно большое число различных правил преобразования и эвристик. Простейшими являются эвристики "выбрать переменную, входящую в самую короткую скобку" и "выбрать переменную, входящую в наибольшее количество скобок". Приведем список некоторых правил преобразования. Правило тавтологии. Исключить из формулы все скобки, которые содержат одновременно переменную и ее отрицание. Правило единичной скобки. Если F содержит скобку, состоящую из единственного литерала v, положить v — истина. Правило чистого литерала. Если F содержит чистый литерал, т.е. литерал v, такой что его отрицание не входит в F, положить v = истина. Резолюция. Пусть х - переменная из F. Резольвентой двух скобок [х V V\\ V ... V Vis) и (ж V г 2і V ... V V2t) по х называется скобка (г и V ... V Vis V г 2і V ... V г г), если v\j ф щ для всех г, j, и истина в противном случае. Метод резолюции заключается в добавлении к формуле F всех резольвент по # и удалении из F скобок, содержащих х или х.
Модель целочисленного линейного программирования
Чтобы построить модель целочисленного линейного программирования необходимо от логических переменных перейти к булевым, а логические ограничения заменить эквивалентными им линейными неравенствами.
Введем множества индексов переменных Cf и С/", входящих в d с отрицанием и без него, соответственно. Заменим Xj на булеву переменную yj, ее отрицание Xj на 1 — у а символ дизъюнкции V - на знак +. Условию выполнимости логической формулы Сг-для мягкого логического ограничения соответствует разрешимость следующего линейного неравенства:
Для формулы С{, соответствующей мягкому логическому ограничению, которое при определенных условиях может не выполняться, вводится вспомогательная булева переменная и строится неравенство:
Например, логической формуле С — х\ V х2 V х з соответствуют: Ух + 2/2 - 2/з 1 или ух + у2 - уъ + z 2. Модель ЦЛП для сформулированной выше задачи формирования сложных изделий имеет вид:
Если в оптимальном решении этой задачи для некоторого г имеет место zi = 1, то соответствующая формула Q принимает значение истина.
Для решения задачи (2.3)-(2.8) могут быть применены различные методы и пакеты прикладных программ [23, 31, 49, 88]. Оптимальное решение этой задачи дает предварительный вариант создаваемого изделия с учетом сформулированных требований и степени их важности, который может быть подвергнут корректировке по желанию специалиста. Однако оптимальное решение часто не является единственным, поэтому в процессе выбора могут оказаться полезными и другие решения, которые будут порождать новые варианты изделий. Фактически на данном этапе осуществляется выделение совокупности перспективных для дальнейшего рассмотрения вариантов изделия
Для оптимизации выбора подходящих вариантов кроме функции (2.3) целесообразно использовать еще ряд критериев, например, можно минимизировать трудоемкость изготовления изделия, повысить эксплуатационные характеристики и другие, то есть перейти к многокритериальной оптимизации. В п. 2.5.2 рассматриваются возможности получения множества разнообразных эскизов.
База данных
Важную роль в формировании сложных изделий, в данном случае, эскизов одежды играют базы данных, от полноты и правильности организации которых существенно зависит качество получаемых проектных решений.
В разработанном нами программном комплексе создана реляционная БД «Женские верхние плечевые изделия», которая включает информацию: о размерных признаках типовых фигур женщин, их графических изображениях, составляющих и характеристиках верхних женских плечевых изделий, технических и художественных эскизах готовых изделий, логических, ресурсных и других ограничениях, необходимых для построения математических моделей и применения алгоритмов дискретной оптимизации.
Общая схема базы данных представлена на рис. 3.5. Прямоугольниками обозначены сущности, овалами их атрибуты, а двойная стрелка показывает связь «один ко многим» [50].
Выбор реляционной модели базы данных обусловлен ее достаточно широким распространением и удобством реализации с помощью современных языков программирования.
В настоящее время в БД содержится более двадцати реляционных таблиц, имеющих сходную между собой структуру. Каждая таблица с названием N содержит не более четырех полей, среди которых обязательными являются - Номер N , Наименование N и Общий код N . В некоторые таблицы, называемые подчиненными (табл. 3.1 к ним направлены двойные стрелки), добавляется еще одно поле Номер Nl из предшествующей таблицы с названием N1 для взаимосвязи с ней. Так, например, в таблицу 3.2 «Виды рукавов» добавляется поле Номер покроя рукавов из предшествующей таблицы 3.1 «Покрой рукавов». Для неподчипенных таблиц первичным ключом является поле Номер N , а для подчиненных он состоит из двух полей: Номер N и Номер Nl .
Поле Оби1 ий код N вводится для взаимосвязи с модулем визуализации и предназначен для однозначной идентификации изображения составляющей изделия. Этот код может содержать в себе от трех до семи компонент, первые две из которых отводятся под номер таблицы (неподчиненной), а остальные несут в себе информацию о соответствующей составляющей (или характеристике) изделия.
Так, например, код 1311120 определяет покрой воротника (13 - номер таблицы «Покрой воротника»), третья цифра, значение которой равно 1, указывает на выбор отложного воротника (вид воротника), четвертая цифра определяет его ширину - узкий (характеристика воротника), а пятая - форму с тупыми углами (форма воротника). Седьмая цифра 0 не несет в себе никакой информации, она добавляется в конец вектора с целью, чтобы по числу его компонент (их максимальное число равно семи), можно было определить, что данный код идентифицирует составляющую изделия, а не одну из стадий ее построения. В последнем случае код будет содержать менее семи компонент. Перечень всех кодов и их расшифровка хранятся в отдельном файле и используется в модуле визуализации, который описан в п. 3.3.
Нетрудно проверить, что все таблицы реляционной БД соответствуют нормальной форме Бойса-Кодда, так как любая функциональная зависимость между полями таблицы сводится к полной такой зависимости от возможного ключа [50].
На практике этого достаточно, чтобы с большей гарантией считать, что все таблицы находятся в 5НФ (пятой нормальной форме), и следовательно, можно предположить выполненной процедуру нормализации, что позволяет исключить возможность противоречивости хранимых данных и избыточности информации.
Информация о готовых эскизах изделий (в том числе о предварительных и незаконченных вариантах) хранится в отдельных графических файлах.
Важная роль в рассматриваемом комплексе программ отводится разделу БД, предназначенному для хранения логических и других ограничений. Предполагается, что основная часть из них разработана и содержится в БД. Вместе с тем, в процессе конструирования могут быть созданы и использованы новые ограничения, возникающие в результате творческой деятельности специалиста при разработке новых эскизов и модификации имеющихся.
Результаты вычислительного эксперимента и анализ полученных решений
Нами были проведены экспериментальные исследования на ЭВМ с целью апробации математической модели из п. 2.4 и разработанного программного комплекса. Для этого использовалась задача создания эскизов женского демисезонного пальто, описанная в п. 4.1. Здесь представлены результаты эксперимента для трех серий задач, отличающихся исходными данными.
На начальной стадии были выполнены расчеты для случая, когда все мягкие логические ограничения имели вес, равный единице. Кроме того, предполагалось, что все коэффициенты в левой части неравенств (4.32), (4.33) равны единице и р = О, b 27, так что дополнительные ограничения по умолчанию выполнены. Было получено следующее решение из 9 элементов: v\, vf, vf, vf, v%, v%, v\, v\, vf.
Далее были проведены расчеты при р = Ь. Это означает, что фактически фиксировалось число составляющих, входящих в эскиз изделия. Рассмотрим результаты, полученные при изменении значений параметра р от 5 до 12. 1. При значениях р, равных 5 и 12, задачи ЦЛП не имеют допустимых решений, т.е. в этих случаях не существует эскиза пальто, удовлетворяющего всем жестким логическим ограничениям. 2. Для значений р от 6 до 11 получены оптимальные решения задач, которые приведены в таблице на рис. 4.1.
Отметим, что здесь и в дальнейшем в таблицах используются следующие обозначения: ер - номера нарушенных логических ограничений; и - номера логических ограничений, веса которых увеличивались.
Следует отметить, что для р = б,..., 9 все мягкие логические ограничения выполнены. В случае при = 10 нарушено ограничение с номером 34, связывающее составляющие vl и ff, которые желательно включать в изделие одновременно. Для р = 11 нарушены логические ограничения 25, 34.
Из полученных результатов можно сделать вывод, что для рассматриваемых исходных данных максимальное число составляющих эскиза пальто, у которого выполнены все логические ограничения, не может быть более 9.
Следующая часть эксперимента (решение задач серии 2) была связана с последовательным увеличением весов невыполненных мягких логических ограничений. В этих задачах р = Ъ = 10, а веса всех составляющих равнялись 1.
Расчеты для серии 2 проводились следующим образом. Сначала решалась задача ЦЛП, в которой вес ограничения 34 полагался равным 50, а веса остальных мягких логических ограничений равнялись 1. В ее оптимальном решении оказалось невыполненным лишь ограничение 25. Далее решалась задача, у которой веса ограничений 36 и 25 равнялись 50. В новом оптимальном решении нарушилось логическое ограничение с номером 28. Его вес был увеличен до 50, затем решалась новая задача ЦЛП и т.д.
В таблице на рис. 4.2 приводятся результаты расчетов для задач этой серии. В колонке ш указываются номера логических ограничений, вес которых был увеличен до 50. Расчеты для задач серии 2 показали, что с помощью подбора весов можно добиваться выполнения тех или иных мягких логических ограничений.
В задачах серии 3 веса составляющих и мягких ограничений подбирались специалистом на основе своих предпочтений. Расчеты проводились для р — 100. Следует отметить, что полученные эскизы отличаются большим разнообразием (см. таблицу на рис. 4.3). Например, в метрике Хемминга расстояния между оптимальными решениями любой пары задач этой серии не меньше десяти.
Проведенные расчеты показали, что во всех полученных оптимальных решениях нарушалось в основном не более одного логического ограничения, т.е. эскизы оказались достаточно «логичными».
