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

• Автор: Месягутов, Марат Артурович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Уфа
• Количество страниц: 134 с. : ил.

Оглавление

Символика и обозначения

Введение .
1 Методы решения задач одномерной и ортогональной упаковки аналитический обзор и эксперимент

1.1 Задача одномерной упаковки

1.2 Задача двухмерной упаковки

1.3 Задача продолженного одномерного раскроя

1.4 Численный эксперимент.

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

2.1 Математические модели.

2.2 Сокращение размерности задачи.
2.3 Ветвления . .
2.4 Нижние границы
2.5 Точный алгоритм.
2.6 Численный эксперимент.
2.7 Выводы
3 Поиск лучших решений задачи двухмерной упаковки в окрестностях с локальной нижней границей
3.1 Кодирование и декодирование ортогональной упаковки.
3.2 Локрестность допустимой упаковки
3.3 Нижняя граница в Локрестности
3.4 Поиск лучшего локально оптимального решения с использованием Локрестностей . .
3.5 Численный эксперимент. .
3.6 Выводы.
Результаты и выводы.
Список публикаций автора по теме диссертации.
Список литературы


Использование в общем методе ветвей и границ преироцессинга, критериев доминантности упаковок и правил отсечения неперспективных решений на этапе их построения, основанных на структуре допустимых решений, и решения вспомогательной задачи линейного программирования позволило сократить время решения задач и использовать разработанный метод в качестве алгоритма вычисления нижних границ. Применение линейного программирования для поиска верхней границы решения задачи одномерной продолженной упаковки. Ранее ограничивались использованием стратегии лучшей нижней границы - поиск в ширину, и поиском в глубину. Применение линейного программирования обеспечило улучшение верхней границы, т. Схема процесса принятия решений и метод локального поиска оптимума задачи двухмерной упаковки на основе решения задачи одномерной продолженной упаковки, которое позволяет выделять окрестности допустимых решений с локальной нижней границей, т. Практическая ценность. Программная реализация полученного точного метода для решения задач одномерной продолженной упаковки может использоваться для расчета нижних границ в реальных производственных задачах двухмерной упаковки. С помощью вычисленного значения нижней границы можно оценивать качество получаемых допустимых решений, что служит критерием для остановки счёта при достижении приемлемого значения отклонения решения от оптимального. Программная реализация полученного приближённого метода для задачи двухмерной упаковки показала преимущества перед известными приближёнными алгоритмами на широком классе задач, что подтверждено расчетами. Программное обеспечение, разработанное в рамках диссертационной работы, зарегистрировано в ВНТИЦ, свидетельство №3. Апробация работы. Работа выполнялась в рамках научной школы по раскрою-упаковке УГАТУ. РФФИ, грант №0-HHUO_a, гранта на исследования Германской службы академических обменов (DAAD), стипендии Georgius-Agricola Саксонского министерства наук и искусства, и Европейского исследовательского гранта Erasmus Mundus. Всероссийская конференция „Проблемы оптимизации и экономические приложения“, Омский филиал института математики им. Соболева СО РАН, г. Омск, , года. Всероссийская конференция „Математическое программирование и приложения“, институт математики и механики УрО РАН, г. Екатеринбург, год. Европейская конференция по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP), г. Л’Акуила, Италия, год. Юговосточный немецкий коллоквиум (Sudostdeutsches Kolloquium), г. Лейпциг, Германия, год. Симпозиум по дискретной оптимизации (Workshop on discrete Optimization), г. Кёнигштейн, Германия, год. Европейская конференция по раскрою и упаковке (Euro special interest group on cutting and packing, ESICUP), г. Вааенсия, Испания, год. Симпозиум международной федерации автоматики (International federation of automatic control, IFAC) по проблемам управления информацией в промышленном производстве, г. Москва, год. Международная школа-конференция для студентов, аспирантов и молодых ученых „Фундаментальная математика и ее приложения в естествознании“, БГУ, г. Уфа, , года. Международный симпозиум по информатике и информационным технологиям (International Workshop on Computer Science and Information Technologies, CSIT), г. Карлсруэ, Германия, г. Уфа, , года. Симпозиум по дискретной оптимизации (Workshop on discrete Optimization), г. Хольцхау, Германия, год. Региональная зимняя школа-семинар аспирантов и молодых ученых факультета Информатики и Робототехники УГАТУ, г. Уфа, год. Семинары института вычислительной математики Дрезденского Технологического Университета, г. Дрезден. Семинары кафедры вычислительной математики и кибернетики УГАТУ, г. Уфа. Семинары кафедры математики УГАТУ, г. Уфа. Семинар института математики с вычислительным центром Уфимского научного центра РАН, г. Уфа. Губликации. По теме диссертации автором опубликовано работ, в том числе три работы в рецензируемых журналах, рекомендованных ВАК. Структура и объём работы. Диссертация изложена на 2 страницах, содержит введение, три главы, заключение, 7 таблиц, - иллюстраций и список литературы, содержащий 9 наименований.