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

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

ГУСЕЛЕТОВА Ольга Николаевна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ФОРМИРОВАНИЯ СЛОЖНЫХ ИЗДЕЛИЙ

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

Омск - 2008

003456342

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Омский государственный университет им. Ф.М.Достоевского»

Научный руководитель: доктор физико-математических наук, профессор

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

Официальные оппоненты: доктор физико-математических наук, профессор

Попков Владимир Константинович

кандидат технических наук, доцент Коробова Антонина Брониславовна

Ведущая организация: Государственное образовательное учреждение

высшего профессионального образования «Уральский государственный университет им. A.M. Горького»

(г. Екатеринбург)

Защита состоится «23» декабря 2008 г. в 14 00 часов на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан «/<? » ноября 2008 г.

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

С.Б.Сорокин

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

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

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

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

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

Задачи дискретной оптимизации с логическими ограничениями достаточно интересны как в теоретическом, так и в прикладном отношении. Наиболее известными среди них являются задачи выполнимости (задача SAT) и максимальной выполнимости логической формулы (задача MAX-SAT). Имеется значительное число работ, посвященных изучению сложности и структуры этих задач, выделению полиномиально разрешимых случаев и семейств «трудных» задач, разработке точных и приближенных алгоритмов их решения, различных эвристик, проведению теоретического и экспериментального анализа алгоритмов. Среди основных методов, на которых базируются разрабатываемые алгоритмы, можно выделить методы расщепления, ветвей и границ, отсечения, перебора L-классов, локальный поиск и ряд других.

Одним из широко известных подходов к решению задач SAT и MAX-SAT является использование аппарата целочисленного линейного

программирования (ЦЛП). Для анализа задач целочисленного программирования, построения и исследования алгоритмов А.А. Колоколовым был предложен метод регулярных разбиений. С использованием этого подхода исследована сложность решения ряда задач, изучена структура релаксационных множеств, рассмотрены вопросы устойчивости задач и алгоритмов, получены оценки числа итераций и ряд других важных теоретических результатов. Значительное число исследований проведено на основе L-разбиения, в частности, для задач SAT и MAX-SAT, которые показали перспективность его применения. Поэтому актуальным является дальнейшее использование метода регулярных разбиений для анализа и решения задач с логическими и ресурсными ограничениями.

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

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

1. Построить и исследовать математические модели для задач формирования сложных изделий с учетом логических и ресурсных ограничений.

2. Разработать алгоритмы решения рассматриваемых задач с использованием целочисленного линейного программирования и метода перебора L-классов.

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

4. Создать программный комплекс для апробации развиваемого подхода на примере построения эскизов одежды.

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

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

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

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

3. Комплекс программ для построения эскизов одежды, разработанный на основе развиваемого подхода к формированию сложных изделий.

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

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

2. На основе метода перебора Ь-классов разработаны алгоритмы решения задач целочисленного линейного программирования, предложенных для формирования сложных изделий.

3. Указанные математические модели и алгоритмы применены к построению эскизов одежды с учетом логических и ресурсных ограничений.

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

Внедрение результатов работы. Результаты работы используются в учебном процессе в Омском государственном университете им. Ф.М. Достоевского.

Апробация работы. Основные результаты диссертации опубликованы в работах [1 - 12] и докладывались на следующих конференциях и семинарах: II межвузовской научно-практической конференции студентов и аспирантов «Молодежь, наука, творчество - 2004» (г. Омск, 2004); Российской конференции «Дискретный анализ и исследование операций» (БА(Ж'04) (г. Новосибирск, 2004); V Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск, 2004); межвузовской научно-методической конференции «Модернизация профессионального образования в условиях интеграции: проблемы обеспечения качества»

(г. Омск, 2005); XIII Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Иркутск, 2005); Международной конференции «Operations Research 2005» (г. Бремен, Германия, 2005); III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2006); Третьей азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (г. Бишкек, 2007); VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (г. Омск, 2007); научных семинарах в Омском государственном университете им. Ф.М. Достоевского, Омском филиале Института математики им. C.JI. Соболева СО РАН и Институте вычислительной математики и математической геофизики СО РАН.

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и списка используемой литературы (104 наименования). Текст диссертации изложен на 118 страницах.

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

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

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

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

Сформулируем задачу выполнимости логической формулы. Пусть х\,..., хп - логические переменные, литералом назовем переменную или ее

отрицание. Рассмотрим формулу F в КНФ

F = Ci Л С2 Л ... Л Ст,

где каждая формула (скобка) С; является дизъюнкцией литералов.

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

Одним из широко известных подходов к анализу и решению задачи SAT является применение целочисленного программирования. Построим модель ЦЛП для задачи SAT. Для этого введем булевы переменные у\,... ,уп такие, что j/j соответствует переменной Xj, а (1 — yj) - ее отрицанию. Условие выполнимости логической формулы F эквивалентно существованию решения системы:

Е Уз - Е Уз > 1 - |СГ1, * = 1>--->™. (1)

jecf jeer

0<%<1, j = l,...,n, (2)

yj 6 Z, j = l,...,n. (3)

где C~ и C+ — множества индексов переменных, входящих в г-ю скобку с отрицанием и без него соответственно. В качестве целевой функции можно

п

использовать, например, f(y) = у\ —> max или f(y) = Е yj —* шах, где

;'=1

У= {Vll • • • ! Уп)-

Приведем формулировку задачи MAX-SAT, которая является обобщением задачи выполнимости логической формулы. Пусть скобки Ci,..., Ст имеют неотрицательные веса ci,...,cm. Задача максимальной выполнимости логической формулы состоит в отыскании набора значений переменных, при котором суммарный вес выполненных скобок будет наибольшим.

Построим модель ЦЛП для задачи MAX-SAT. Для каждой скобки Ci вводим вспомогательную булеву переменную z; и рассматриваем неравенство:

Е Уз+ Е (1 - Уз) > Ъ-

jeC+ j€C~ Тогда модель ЦЛП имеет вид:

771

2 CiZi —* max (4)

¿=1

при условиях

Т. Уз~ Е Уз + 2г < |СГ1. г = 1, . . . , 771, (5)

О < У] < 1, У] 6 Л, ¿ = 1,...,п, (6)

О < < 1, г* е г, г = 1,...,ш. (7)

Если в допустимом решении задачи (4) - (7) для некоторого г имеет место г,- = 1, то формула С{ принимает значение истина. Оптимальное значение целевой функции равно максимальному суммарному весу выполненных скобок.

Указанные задачи послужили основой для разработанных нами математических моделей.

Во второй главе описывается развиваемый нами подход к формированию сложных изделий, основанный на использовании моделей дискретной оптимизации, связанных с задачей максимальной выполнимости логической формулы. В п. 2.1 приводится постановка задачи дискретной оптимизации с логическими, ресурсными и другими ограничениями. Для этой задачи в п. 2.2 строится модель целочисленного линейного программирования. В п. 2.3 иллюстрируется применение подхода к созданию эскизов одежды и одного' технического устройства.

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

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

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

Для формулировки задачи введем следующие обозначения:

3 - множество номеров составляющих изделия, 3 = {1,... ,п};

V] - составляющая изделия с номером ] € J;

X] - логическая переменная, которая принимает значение истина, если Vj входит в изделие, и - значение ложь в противном случае, ] е 7;

Sj - вес составляющей характеризующий степень целесообразности включения V] в изделие, ] 6 У;

р ~ нижняя граница для суммарного веса составляющих, включенных в изделие;

/ - множество номеров логических формул, используемых в задаче, I = {1,...,т};

/' - множество номеров логических формул, которые должны быть обязательно выполнены, V — {1,... ,т'}, I' С /; логические ограничения, соответствующие таким формулам назовем жесткими, а все остальные, необходимость выполнения которых зависит от степени их важности -мягкими;

С\ - логическая формула, соответствующая г-му логическому ограничению, г € I, которая представляет собой дизъюнкцию литералов;

йг - вес формулы Си характеризующий степень необходимости ее выполнения, г £ /\/';

а у - объем к-го ресурса, требуемого для изготовления ^'-ой составляющей изделия, к е К, К = {1,..., д}, у €

Ьк - имеющийся объем к-го ресурса, к £ К.

Задача формирования сложных изделий состоит в отыскании значений логических переменных, при которых выполняются формулы Сх с номерами г 6 ограничения по ресурсам и по суммарному весу включенных в изделие составляющих, а общий вес выполненных формул С;, г € 1\Г будет максимальным.

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

Модель ЦЛП для сформулированной выше задачи имеет вид:

Уо = Е ¿А -* тах (8)

ш\г

при условиях

Е Уз- Е %<|С4-|-1, (9)

Е У:- Е У1 + Ъ<\Сг\, ieI\Г, (10)

£ sj Уз > Р.

(п) (12) (13)

jeJ

£ akj У] < h, к е К,

jeJ

Zi, Уз 6 {0,1}, г € I\r, j б J.

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

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

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

На основе предложенных моделей ЦЛП нами разработаны алгоритмы для получения оптимальных решений задач формирования сложных изделий с учетом их специфики. Среди таких особенностей следует выделить наличие в задачах не только логических формул, которые соответствуют жестким логическим ограничениям, но и формул, отвечающих мягким логическим ограничениям. Кроме того, в задачах вместе с логическими используются ресурсные ограничения, а также требования специалиста по включению в изделие составляющих. Необходимо отметить, что данные отличия заметно усложняют нахождение как допустимых, так и оптимальных решений по сравнению с задачами SAT и MAX-SAT.

Изложим идею одного из предложенных алгоритмов (далее обозначим его DLE), основанного на методе перебора ¿-классов. В этом алгоритме используется отношение лексикографического порядка для множеств. Пусть X, Y С R'\ полагаем X У Y, если х У у для любого х € X и любого у € Y.

Здесь и далее >--символ лексикографического порядка. Запись х У у

означает, что либо х >- у, либо х = у.

Приведем определение L-разбиения. Точки х,у е Rn (х >- у) называются L-жвивалентными, если не существует отделяющей их точки z 6 Zn, т. е. такой, что выполняется х >z z У у. Это отношение эквивалентности порождает разбиение любого множества X с Rn на непересекающиеся L-классы. Фактор-множество X/L называется L-разбиением множества X. Указанное разбиение обладает рядом полезных свойств, применяемых при

разработке и исследовании алгоритмов целочисленного программирования, в частности, алгоритмов перебора ¿^классов.

Отметим, что каждая точка z & Zn образует отдельный L-класс, остальные классы состоят из нецелочисленных точек и называются дробными. L-разбиение согласовано с лексикографическим порядком. Это означает, что если X - непустое множество из R" и Vj, V2 - некоторые различные /у-классы из X/L, тогда либо Vi У V2, либо Vi У Vi. Поэтому, если X - ограниченное множество, то X/L можно записать следующим образом:

X/L = {Vu..., Vp}, Ц у Vi+U г = 1, ...,р - 1.

Рассмотрим лексикографическую задачу ЦЛП следующего вида:

у* = 1ехтах(М П Zn), (14)

где М - многогранник, определяемый системой (1)-(2). Важную роль в исследовании задачи (14) и методов ее решения играет множество

Aff = {у € М : УУ z V 2 6 (М П Zn)},

которое называется вертим дробным накрытием задачи (14). Фактормножество /Ь называется верхним L-накрытием задачи. Отметим, что для задачи (14) множество М?¡L является конечным.

Опишем идею метода перебора ¿-классов для задачи SAT, представленной в виде (14). Пусть верхнее L-накрытие задачи состоит из классов Vi, V2..., Vp, причем V\ у V% >- ... >- Vp. Основной шаг метода заключается в переходе от одного класса из Mf ¡L к другому в порядке лексикографического убывания. В процессе перебора порождается последовательность точек у® € М?, обладающая свойствами:

. y(Vy(1+", t= 1,2,..., s — 1; s<p-,

• все точки принадлежат различным L-классам.

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

Особенностью предложенного нами алгоритма DLE является декомпозиция задачи ЦЛП (8)—(13) по ограничениям и использование алгоритма перебора ¿-классов LCE для решения задачи выполнимости, который был предложен А.А. Колоколовым. В алгоритме DLE решение

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

Процесс начинается с подстановки найденного решения в ограничения (11)-(12). Если хотя бы одно из этих ограничений не выполняется, то происходит переход к следующему L-классу многогранника задачи SAT в порядке лексикографического убывания. Если же указанные ограничения выполняются, то решение подставляется в систему мягких логических ограничений (10), далее вычисляется значение целевой функции и переопределяется её рекорд (наилучшее значение этой функции к данному моменту). После этого также происходит переход к следующему ¿-классу. Важным этапом такого перехода является процедура упрощения формулы, используемая в алгоритме LCE и позволяющая уменьшать размерность решаемой задачи SAT, а в некоторых случаях и вовсе обходиться без поиска ее решения.

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

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

Третья глава посвящена описанию программного комплекса, предназначенного для создания эскизов одежды (женского демисезонного пальто). В п. 3.1 дается общая схема программного комплекса и методология выполнения расчетов на ЭВМ. В п. 3.2 приводится описание базы данных, ее схема и структура. В п. 3.3 содержится описание модуля визуализации и примеров его использования.

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

На первом этапе с целью построения модели дискретной оптимизации

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

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

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

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

С целью апробации предложенных математических моделей и разработанного программного комплекса нами были выполнены экспериментальные исследования на ЭВМ, результаты которых приводятся в п. 4.2. Вычисления проводились на компьютере со следующими характеристиками: процессор Intel Corel Duo 1,1GHz x 1,7GHz, объем оперативной памяти 2046 Мб.

Для проведения эксперимента использовалась задача формирования эскизов женского демисезонного пальто, в которой имеется 27 составляющих, объединенных в 8 групп (рукава, воротники, карманы и др.) и 37 логических ограничений. Соответствующие задачи ЦЛП содержали 47 переменных и 64 ограничения. При проведении расчетов менялись веса

мягких логических ограничений, веса переменных, входящие в ограничения вида (11), коэффициенты переменных, связанные с ограничениями вида (12), значения параметров pub. Указанные значения подбирались экспертным путем. Система (12) включала по одному ограничению. Время решения каждой задачи не превышало 15 сек.

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

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

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

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

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

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

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

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

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

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

[1] Гуселетова О.Н., Колоколов A.A. Решение задач дискретной оптимизации с логическими ограничениями при проектировании сложных изделий // Автоматика и телемеханика, 2008. - № 10. - С. 176 - 182.

[2] Гуселетова О.Н. Модели и алгоритмы дискретной оптимзации для некоторых задач проектирования // Тезисы XIV Всероссийской школы-коллоквиума по стохастическим методам и VIII Всероссийского симпозиума по прикладной и промышленной математике - журнал "Обозрение прикладной и промышленной математики", 2007. - 14 том, 6 Выпуск. -С. 1100 - 1101.

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

[3] Гуселетова О.Н. Об одном алгоритме решения задач дискретной оптимизации с логическими ограничениями // Динамика систем, механизмов и машин: Матер. VI Междунар. науч.-техн. конф. - Омск: Изд-во ОмГТУ, 2007. - Кн.З - С. 26 - 30.

[4] Гуселетова О.Н. Разработка алгоритмов и комплекса программ для некоторых задач проектирования // Труды ИВМиМГ СО РАН. Сер. Информатика. - Новосибирск: Изд. ИВМиМГ СО РАН, 2007. - Вып.7 : Материалы Третьей азиатской школы-семинара "Проблемы оптимизации сложных систем". - С. 193 - 197.

[5] Гуселетова О.Н., Колоколов АА. Разработка алгоритмов для некоторых задач дискретной оптимизации с логическими ограничениями// III Всероссийская конференция "Проблемы оптимизации и экономические приложения": Материалы конференции (Омск, 11-15 июля 2006)/ Омский филиал Института математики им. С. JI. Соболева СО РАН - Омск: Изд-во ОмГТУ, 2006. - С. 176.

[6] Гуселетова О.Н., Ярош A.B. Использование программного комплекса эскизного проектирования одежды для повышения качества подготовки специалистов // Материалы межвуз. науч.-методич. конф. "Модернизация профессионального образования в условиях интеграции: проблемы обеспечения качества". Омск, 2-3 марта 2005 г. - Омск: Изд-во СибАДИ. - 2005. - С. 89 - 91.

[7] Колоколов А.А, Нагорная З.Е., Гуселетова О.Н., Ярош A.B. Задачи дискретной оптимизации и программный комплекс для эскизного проектирования одежды // Труды XIII Байкальской междунар. шк-семинара "Методы оптимизации и их приложения", Иркутск, Байкал, 2-8 июля 2005 г. Том 1: Иркутск, ИСЭМ СО РАН. - 2005. - С. 509-514.

[8] Колоколов A.A., Нагорная З.Е., Гуселетова О.Н., Ярош A.B. Математические модели и программный комплекс для проектирования эскизов одежды // Прикладная математика и информационные технологии: Сб. науч. и метод, трудов. - Омск: Изд-во ОмГТУ. - 2005. - С. 80 - 98.

[9] Колоколов A.A., Нагорная З.Е., Гуселетова О.Н., Ярош A.B. Применение задач дискретной оптимизации с логическими ограничениями для автоматизации эскизного проектирования одежды // Междунар. науч-технич. конф. "Динамика систем, механизмов и машин", 16 -18 ноября 2004г. ОмГТУ. Омск: Изд-во ОмГТУ. - 2004. - С. 281-284.

[10] Колоколов A.A., Нагорная З.Е., Гуселетова О.Н., Ярош A.B., Богутова Т.М. Автоматизация эскизного проектирования одежды с использованием некоторых задач дискретной оптимизации // Российская конф. Дискретный анализ и исследование операций. Материалы конф. -Новосибирск, Академгородок: ИМ им. C.JI. Соболева СО РАН, 28 июня -2 июля 2004. - С. 223.

[11] Ярош A.B., Гуселетова О.Н., Богутова Т.М. Разработка алгоритмов и программ для автоматизации эскизного проектирования одежды // Молодежь, наука, творчество - 2004. Сборник статей II межвуз. науч.-практич. конф. студентов и аспирантов, 12 - 16 апреля 2004г. Ч. 2. / Под общ. Ред. проф. Н.У. Казачуна. - ОГИС. - 2004. - С. 152 - 153.

[12] Kolokolov A., Guseletova О., Yarosh А. Application of Some Discrete Optimization Methods to Computer-Added Design of Clothes // International Conference on Operations Research 2005, Bremen. - 2005. - P. 107.

Подписано в печать 17.11.08. Формат 60x84/16. Бумага писчая. Оперативный способ печати. Усл. печ. л. 1,25. Тираж 120 экз. Заказ № 416.

Отпечатано в «Полиграфическом центре КАН» 644050, г. Омск, пр. Мира, 11А тел. (3812) 65-23-73. Лицензия ПЛД № 58-47 от 21.04.97

Введение.

1 Задачи дискретной оптимизации с логическими ограничениями и их приложения.

1.1 Задача выполнимости и ее обобщения

1.2 Методы решения задач выполнимости и максимальной выполнимости.

1.3 Некоторые приложения

2 Математические модели и алгоритмы для задач формирования сложных изделий.

2.1 Постановка задачи.

2.2 Модель целочисленного линейного программирования

2.3 Примеры применения подхода.

2.4 Постановка задачи и модель ЦЛП с учетом групп составляющих и характеристик изделия.

2.5 Алгоритмы решения задачи.

3 Комплекс программ для создания эскизов одежды

3.1 Общая схема программного комплекса и методология проведения расчетов

3.2 База данных.

3.3 Модуль визуализации.

4 Экспериментальные исследования.

4.1 Задача формирования эскизов женских демисезонных пальто.

4.2 Результаты вычислительного эксперимента и анализ полученных решений.

Актуальность темы исследования. Современный этап развития прикладной математики характеризуется активной разработкой и применением математических моделей и методов в планировании, управлении, исследовании социально-экономических, технических и других систем [6, 19, 20, 37, 45, 46, 88, 99, 101]. Весьма актуальным является направление, связанное с процессами создания сложных изделий, которые комбинируются из большого числа разнотипных элементов с учетом логических, ресурсных и других ограничений.

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

В настоящее время в области создания сложных изделий имеются системы, которые обеспечивают высокое качество принимаемых решений, сокращают расход ресурсов и время на изготовление новых изделий, повышают эффективность труда специалистов [1, 4, 7, 47, 102 - 104]. Вместе с тем в указанных разработках недостаточно применяются модели и методы оптимизации, что во многих случаях приводит к перебору и сравнению большого числа вариантов.

Ранее в работах А.А. Колоколова и А.В. Ярош предложен подход к построению эскизов одежды [37, 40 - 44, 82], основанный на использовании задач дискретной оптимизации с логическими и ресурсными оганичениями. Экспериментальные исследования показали необходимость дальнейшего развития данного подхода с расширением сферы его применения.

Задачи дискретной оптимизации с логическими ограничениями достаточно интересны как в теоретическом, так и в прикладном отношении. Наиболее известными среди них являются задачи выполнимости (задача SAT) и максимальной выполнимости логической формулы (задача MAX-SAT). Имеется значительное число работ, посвященных изучению сложности и структуры этих задач, выделению полиномиально разрешимых случаев и семейств «трудных» задач, разработке точных и приближенных алгоритмов их решения, различных эвристик, проведению теоретического и экспериментального анализа алгоритмов [17, 21, 56, 62, 64]. Среди основных методов, на которых базируются разрабатываемые алгоритмы, можно выделить методы расщепления, ветвей и границ, отсечения, перебора L-классов, локальный поиск и ряд других [2, 3, 24, 28 - 31, 38, 39, 69, 79, 92].

Одним из широко известных подходов к решению задач SAT и MAX-SAT является использование аппарата целочисленного линейного программирования (ЦЛП). Для анализа задач целочисленного программирования (ЦП), построения и исследования алгоритмов А.А. Колоколовым был предложен метод регулярных разбиений [27]. С использованием этого подхода исследована сложность решения ряда задач, изучена структура релаксационных множеств, рассмотрены вопросы устойчивости задач и алгоритмов, получены оценки числа итераций и ряд других важных теоретических результатов.

Значительное число исследований проведено на основе L-разбиения, в частности, для задач SAT и MAX-SAT, которые показали перспективность его применения [24, 28 - 30, 38, 39, 51, 78, 79, 81]. Поэтому актуальным является дальнейшее использование метода регулярных разбиений для анализа и решения задач с логическими и ресурсными ограничениями.

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

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

1. Построить и исследовать математические модели для задач формирования сложных изделий с учетом логических и ресурсных ограничений.

2. Разработать алгоритмы решения рассматриваемых задач с использованием целочисленного линейного программирования и метода перебора L-классов.

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

4. Создать программный комплекс для апробации развиваемого подхода на примере построения эскизов одежды.

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

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

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

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

3. Комплекс программ для построения эскизов одежды, разработанный на основе развиваемого подхода к формированию сложных изделий.

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

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

2. На основе метода перебора L-классов разработаны алгоритмы решения задач целочисленного линейного программирования, предложенных для формирования сложных изделий.

3. Указанные математические модели и алгоритмы применены к построению эскизов одежды с учетом логических и ресурсных ограничений.

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

Внедрение результатов работы. Результаты работы используются в учебном процессе в Омском государственном университете им. Ф.М. Достоевского.

Апробация работы. Основные результаты диссертации опубликованы в работах [11 - 16, 33 - 36, 52, 80] и докладывались на следующих конференциях и семинарах: II межвузовской научно-практической конференции студентов и аспирантов «Молодежь, наука, творчество - 2004» (г. Омск, 2004); Российской конференции «Дискретный анализ и исследование операций» (DAOR'04) (г. Новосибирск, 2004); V Международной научно-технической конференции «Динамика систем, механизмов и машин», (г. Омск, 2004); межвузовской научно-методической конференции «Модернизация профессионального образования в условиях интеграции: проблемы обеспечения качества» (г. Омск, 2005); XIII Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Иркутск, 2005); Международной конференции «Operations Research 2005» (г. Бремен, Германия, 2005); III Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2006); Третьей азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (г. Бишкек, 2007); VI Международной научно-технической конференции «Динамика систем, механизмов и машин» (г. Омск, 2007); научных семинарах в Омском государственном университете им. Ф.М. Достоевского, Омском филиале Института математики им. C.JI. Соболева СО РАН и Институте вычислительной математики и математической геофизики СО РАН.

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения и списка используемой литературы (104 наименования). Текст диссертации изложен на 118 страницах.

Заключение

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

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

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

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

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

1. Абдулин С.Ф. Системы автоматизированного проектирования и управления: Аннотированный ретроспективный библиографический указатель (1990 - 2000г.г.). - Омский государственный институт сервис. - 2001. - 234 с.

2. Аделыпин А.В. Задача максимальной выполнимости и некоторые алгоритмы целочисленного программирования: Труды межд. семинара, посвященного 90-летию со дня рождения С.Н. Черникова. Екатеринбург: Уро РАН. - 2002. - С. 235 - 239.

3. Аделыпин А.В. Исследование задач максимальной и минимальной выполнимости с использованием Ir-разбиения // Автоматика и телемеханика, 2004. № 3. - С. 35 - 42.

4. Андреева М.В., Холина Т.Ю. Конструктивное моделирование в САПР "Ассоль"// Швейн. пром-сть. 2001. - №1. - С. 34 - 37.

5. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотичная динамика», 2001. - 288 с.

6. Береснев B.J1. Дискретные задачи размещения и полиномы от булевых переменных. Изд-во Ин-та математики, Новосибирск, 2005. - 408 с.

7. Булатова Е.Б., Размахнина В.В., Ещенко В.Г. Компьютерные технологии проектирования одежды на базе системы "Грация"// Швейн. пром-сть. 2000. - № 1. - С. 38 - 40.

8. Всемирнов М.А., Гирш Э.А., Данцин Е.Я., Иванов С.В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Зап. науч. семин. ПОМИ, 2001. Т. 277. - С. 14 -46.

9. Гегечкори Е.Т. К вопросу о формировании исходного множества альтернатив в принятии управленческих решений // Матер. V Межд. науч. техн. конф. Омск: Изд-во ОмГТУ, 2004. Кн. 2. -С. 261 - 264.

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

11. Гуселетова О.Н. Об одном алгоритме решения задач дискретной оптимизации с логическими ограничениями // Динамика систем, механизмов и машин: Матер. VI Междунар. науч.-техн. конф. -Омск: Изд-во ОмГТУ, 2007. Кн.З - С. 26 - 30.

12. Гуселетова О.Н., Колоколов А.А. Решение задач дискретной оптимизации с логическими ограничениями при проектировании сложных изделий // Автоматика и телемеханика, 2008. № 10. -С. 176 - 182.

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

14. Данцин Е.Я. Две системы доказательства тавтологичности, основанные на методе расщеплений. Зап. науч. семин. ЛОМИ 105, 1981. - С. 24- 44.

15. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Изд-во НГУ, Новосибирск, 1996. - 167 с.

16. Еремин И.И., Мазуров Вл.Д., Скарин В.Д., Хачай М.Ю. Математические методы в экономике. Екатеринбург: УрГУ -Центр "Фактория Пресс", 2000. - 303 с.

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

18. Забиняко Г.И. Пакет программ целочисленного линейного программирования //Дискретный анализ и исследование операций. 1999. Т.6. -№ 2. - С. 32 - 41.

19. Калльрат Ю.Н., Колоколов А.А., Ягофарова Д.И. Алгоритм перебора L-классов для задачи выполнимости // Материалы Всероссийской конференции "Проблемы оптимизации и экономические приложения", 1-5 июля 2003 г. Омск. - С. 94.

20. Козлова Т.В. Основы теории проектирования костюма: Учеб. Для вузов. М.: Легпромбытиздат. - 1988. - 352 с.

21. Колоколов А.А. Регулярные разбиения в целочисленном программировании // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ. - 1992.- С. 67 - 93.

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

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

24. Колоколов А.А., Аделынин А.В., Ягофарова Д.И. Алгоритмы точного и приближенного решения задачи максимальной выполнимости // Материалы III Всероссийской конференции "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 42 - 46.

25. Колоколов А.А., Девятерикова М.В., Заозерская JI.A. Регулярные разбиения в целочисленном программировании: Учебное пособие. -Омск: ОмГУ. 2007. - 48 с.

26. Колоколов А.А., Нагорная З.Е., Ярош А.В. Системы автоматизированного проектирования в сервисе: Уч. пособие. Ч 1. Омск: ОГИС, 2006.

27. Колоколов А.А., Тюрюмов А.Н., Ягофарова Д.И. Разработка и экспериментальное исследование алгоритмов решения задач выполнимости и максимальной выполнимости. Препринт. Омск: ОмГУ, 2006. - 19 с.

28. Колоколов А.А., Ягофарова Д.И., Тюрюмов А.Н. Разработка алгоритмов для задачи выполнимости и некоторых ее обобщений с использованием перебора L-классов // Омский научный вестник. 2006. - № 5 (39) - С. 57 - 61.

29. Колоколов А.А., Ярош А.В. Автоматизация некоторых этапов проектирования одежды на основе моделей дискретной оптимизации // Препринт. Омск: Изд-во ОмГТУ. 2004. -24 с.

30. Колоколов А.А., Ярош А.В. Применение некоторых многокритериальных задач дискретной оптимизации для автоматизации проектирования одежды // Всероссийская конф. "Проблемы оптимизации и экономические приложения". Омск: ОФ ИМ СО РАН. - 2003. - С. 174.

31. Колоколов А.А., Ярош А.В. Проектирование одежды с использованием некоторых моделей дискретной оптимизации // Омский научный вестник. 2002. - Вып. 20. - С. 91 - 94.

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

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

34. Солтанбаева Г.Ш. Разработка метода автоматизированного проектирования конструкций новых моделей одежды: Автореф. дис. канд. техн. наук. М. - 1992.

35. Страуструп Б. Язык программирования С++. Специальное издание. М.: Бином. - 2001. - 1099 с.

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

37. Федоров А., Елманова Н. Базы данных для всех. М.: КомпьютерПресс. - 2001. - 256 с.

38. Ягофарова Д.И. Анализ L-структуры задачи 2-выполнимости // Материалы ежегодного научного семинара "Под знаком "Е". -Омск: ООО "Издатель-Полиграфист". 2003. - С. 71 - 77.

39. Aytemiz Т. A probabilistic study of 3-Satisfiability. Dissertation for the degree of Doctor of Philosophy. 2001. - 119 p.

40. Back Т., Eiben A.E., Vink M.E. A superior evolutionary algorithm for 3-SAT //In Proc. of the 7th Annual Conference on Evolutionary Programming, LNCS 1744. 1998. - P. 125 - 136.

41. Blair С.E., Jeroslow R.G., Lowe J.K. Some results and experiments in programming techniques for propositional logic //Computers and Operations Research. 1986. - V.13. - №5. - P. - 633 - 645.

42. Boros E., Hammer P.L., Sun X. Recognition of q-Horn formulae in linear time // Discrete Applied Mathematics, 1994. V.55. P. 1 - 13.

43. Cheriyan J., Cunningham W.H., Tuncel L., and Wang Y. A linear programming and rounding approach to max 2-sat // DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. V. 26. P. 395 - 414.

44. Cook S.A. The complexity of theorem-proving procedure // Proc. 3rd Annual ACM Symposium on the Theory of Computing. 1971. -P. 151 - 159.

45. Davis M., Logemann G., Loveland D. A machine program for theorem-proving // Communications of the ACM, 1962. V. 5. N. 7. P. 394 -397.

46. Davis M., Putnam H. A computing procedure for quantification theory // Journal of the ACM, 1960. V. 7. N. 3. P. 201 - 215.

47. Dowling W.F., Gallier J.H. Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae. // Journal of Logic Programming, 1. 1984. - P. 267 - 284.

48. Eremeev A. Modeling and Analysis of Genetic Algorithm with Tournament Selection // Proc. of Artificial Evolution Conference. Lecture Notes in Computer Science, 2000. Vol. 1829. - P. 84 - 95.

49. Franco J., Van Gelder A. A perspective on certain polynomial time solvable classes of Satisfiability // Discrete Applied Mathematics.

50. Goemans M.X., Williamson D.A. New 3/4-approximation algorithms for MAX SAT // SIAM Journal on Discrete Mathematics. 1994. -Ж7. - P. 656 - 666.

51. Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. Reading: Addison Wesley, 1989.

52. Gu J. Local Search for the Satisfiability (SAT) Problem. // IEEE Transaction on Sistems, Man and Cibernetics 23 (4), 1993, P. 1108 -1129.

53. Gu J., Purdom P. W., Franco J., Wah B. W. Algorithms for the Satisfiability (SAT) Problem: A Survey DIMACS Series in Discrete Mathematics and Theoretical Computer Science. - 1996. - P. 131.

54. Hansen P., Jaumard B. Algorithms for the Maximum Satisfiability Problem // Computing 44. 1990. - P. 279 - 303.

55. Hastad J. Some optimal inapproximability results //Proc. of the 29th Annual ACM Symposium on Theory of Computing, 1997. P. 1 - 10.

56. Hooker J.N. Generalized resolution and cutting planes //Annals of Operations Research. 1988. - V.12. - P. 217 - 239.

57. Jaumard В., Stan M., Desrosiers J. Tabu Search and a Quadratic Relaxation for the Satisfiability Problem // DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. Vol. 26. -P. 457 - 477.

58. Johnson D. Approximation algorithms for combinatorial problems //Journal of Comput. System Science. 1974. - V.9. - P. 256 - 278.

59. Joy S., Mitchell J., Borchers B. A branch and cut algorithm for MAX-SAT and weighted MAX-SAT // DIM ACS Series in Discrete Mathematics and Theoretical Computer Science. 1997. V.35. P. 519 536.

60. Karloff H., Zwick U. A 7/8-approximation algorithm for MAX 3-SAT? //Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, 1997. P. 406 - 415.

61. Kautz H., Selman B. Planning as Satisfiability, in Proceedings of the 10th European Conference on Artificial Intelligence (ECAI 92), August 1992.

62. Kohli R., Krishnamurti R. Average perfomance of heuristics for satisfiability //SIAM Journal on Discrete Mathematics. 1989. - V.2.- P. 508 523.

63. Kolokolov A., Adelshin A., Cheredova J. The L-Partition Approach To SAT And MAX SAT // Annual Conference of the GOR. Book of Abstracts. 2001. - P. 118.

64. Kolokolov A., Devyaterikova M., Cheredova J. A Study of Satisfiability Problem Using L-Partition // International Conference on Operations Research.Book of Abstracts. TU Dresden. 2000. - P. 39.

65. Kolokolov A., Guseletova O., Yarosh A. Application of Some Discrete Optimization Methods to Computer-Added Design of Clothes // International Conference on Operations Research 2005, Bremen. 2005.- P. 107.

66. Kolokolov A., Kallrath J., Yagofarova D. Analysis and Solving the Satisfiability Problem using L-partition International Conference on Operations Research 2003, Heidelberg. - 2003. - P. 128.

67. Kullmann O. New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science 223 (1-2), 1999. - P. 1 - 72.

68. Marathe M.V., Ravi S.S. On approximation algorithms for the minimum satisfiability problem // Information Processings Letters. -1996. V.58. - P. 23 - 29.

69. Marchiori E., Rossi C. A flipping genetic algorithm for hard 3-SAT problems //In Proc. of the Genetic and Evolutionary Computation Confeence (GECCO-99). 1999. - P. 393 - 400.

70. Mazure В., Sais L., Gregorie E. Tabu Search for SAT. // Proceedings of CP'95 Workshop on Solving Really Hard Problems, 1995, P. 127 -130.

71. Monien В., Speckenmeyer E. Solving Satisfiability in less then2n steps. // Discrete Applied Mathematics 10, 1985. P. 287 - 295.

72. Nemhauser G.L., Wolsey L.A. Integer and combinatorial optimization. A Wiley-Interscience Publication: John Wiley and Sons, inc., 1999.

73. Papadimitriou C.H. On selecting a satisfying truth assignment // Proc. of FOCS'91. 1991. - P. 163 - 169.

74. Paturi R., Pudlak P., Saks M.E., Zane F. An improved exponential-time algorithm for k-SAT // Proc. of FOCS'98. 1998. - P. 628 - 637.

75. Paturi R., Pudlak P., Zane F. Satisfiability coding lemma //Proc. of FOCS'97, 1997. P. 566 - 574.

76. Reeves C. Genetic Algorithms for the Operation Researcher // INFORMS Journal on Computing. 1997. - Vol.9, №3. - P. 231 -250.

77. Resende M.G.C., Feo T.A. A GRASP for Satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 26: Clicues, Coloring and Satisfiability: Second DIMACS Challenge, 1996, P. 499 520.

78. Schoning U. A probabilistic algorithm for k-SAT and constraint satisfaction problems // Proc. of FOCS'99. 1999. - P. 410 - 414.

79. Selman В., Kautz H., Cohen B. Local Search Strategies for Satisfiability Testing. DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 26: Clicues, Coloring and Satisfiability: Second DIMACS Challenge, 1996. P. 521 - 531.

80. Spears M.W. Simulated Annealing for Hard Satisfiability Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 26: Clicues, Coloring and Satisfiability: Second DIMACS Challenge, 1996. P. 533 - 557.

81. Stiitzle Т., Hoos H., Roli A. A review of the literature on local search algorithms for MAX-SAT // Technical Report AIDA-01-02. Darmstadt University of Technology. Computer Science Department. Intellectics Group. 2001.

82. Velev M.N., Bryant R.E. Effective use of boolean satisfiability procedures in thr formal verification of superscalar and VLIM microprocessors. In 38th Design Automation Conference (DAC '01). P. 226 - 231.

83. Vijey V. Vazirani. Approximation Algorithms, j j Springer, 2001.

84. Yannakakis M. On the approximation of maximum satisfiability // Proc. of the 3rd ACM-SIAM Symposium on Discrete Algorithms. -1992. P. 1 - 9.

85. Zvi Drezner, Horst W. Hamacher. Facility Location. Approximations and Theory. // Springer Verlag, 2004.102. http://www.aomt.kiev.ua103. http://sapr.ru104. http://corp. fortdialog. ru/nd/sapr/unigraphics/