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

• Автор: Гуселетова, Ольга Николаевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Омск
• Количество страниц: 118 с. : ил.

Оглавление
Введение

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]. Вместе с тем в указанных разработках недостаточно применяются модели и методы оптимизации, что во многих случаях приводит к перебору и сравнению большого числа вариантов.
Ранее в работах A.A. Колоколова и A.B. Ярош предложен

К характеристикам отнесем различные ведущие качественные и количественные признаки изделия.
Для формулировки задачи введем следующие обозначения:
3 - множество номеров составляющих изделия, ,/ = {1
V] - составляющая изделия с номером j Є J
X] - логическая переменная, которая принимает значение истина, если Vj входит в изделие, и - значение ложь в противном случае, є 3 Sj - вес составляющей Vj, характеризующий степень целесообразности включения Vj в изделие, ') Є 3
р - нижняя граница для суммарного веса составляющих, включенных в изделие;
I - множество номеров логических формул, используемых в задаче, I = {1
I' - множество номеров логических формул, которые должны быть обязательно выполнены, І' = {1
Сі - логическая формула, соответствующая г-му логическому ограничению, г Є /, которая представляет собой дизъюнкцию литералов;
ф - вес формулы Сі, характеризующий степень необходимости ее выполнения, і Є ҐІ']
щу - объем к-то ресурса, требуемого для изготовления у-ой составляющей изделия, к Є К, К — {1
Ьк - имеющийся объем к-го ресурса, к Є К.
Задача формирования сложных изделий состоит в отыскании значений логических переменных, при которых выполняются формулы Сі с номерами і Є 1 ограничения по ресурсам и по суммарному весу включенных в изделие составляющих, а общий вес выполненных формул Сі, і Є ІІ' будет максимальным.