Войти в мой кабинет
Регистрация
ГОТОВЫЕ РАБОТЫ / ДИПЛОМНАЯ РАБОТА, ТЕХНОЛОГИЧЕСКИЕ МАШИНЫ И ОБОРУДОВАНИЕ

Разработка программно-математического обеспечения оптимального планирования технологического процесса раскроя материала

irina_k200 2100 руб. КУПИТЬ ЭТУ РАБОТУ
Страниц: 84 Заказ написания работы может стоить дешевле
Оригинальность: неизвестно После покупки вы можете повысить уникальность этой работы до 80-100% с помощью сервиса
Размещено: 05.10.2020
Целью данной бакалаврской работы является разработка программно-математического обеспечения оптимального планирования технологического процесса раскроя материала. Задачами данной выпускной квалификационной работы являются: - анализ предметной области; - обзор и анализ современных математических методов оптимального планирования технологического процесса; - обзор и анализ имеющегося программного обеспечения оптимального планирования технологического процесса; - выбор и обоснование инструментальных средств для решения задачи; - разработка и реализации программных средств для реализации задачи; - разработка структуры программного обеспечения - анализ экономической эффективности программного обеспечения; - подготовка документации.Структура выпускной квалификационной работы состоит из нескольких разделов: - в исследовательском разделе описана предметная область, выполнен обзор и анализ существующих математических методов решения, обзор и анализ существующих программных решений в предметной области, обоснован выбор методов для решения задачи; - в специальном разделе сделана постановка задачи об оптимальном планировании раскроя материала, сформирована математическая модель задачи, приведён алгоритм нахождения вариантов раскроя и нахождения оптимального плана раскроя, приведен генетический алгоритм многокритериальной оптимизации для нахождения вариантов раскроя, приведен алгоритм метода ветвей и границ для нахождения оптимального плана раскроя; - в технологическом разделе проведено обоснование выбора инструментальных средств, описана общая схема алгоритма работы программы, приведены схемы алгоритмов метода ветвей и границ, генетического алгоритма многокритериальной оптимизации. Приведена схема алгоритма визуализации результатов. Также было проведено тестирование программного обеспечения на исходных данных и приведены результаты работы программы. - в экономическом разделе определена продолжительность и трудоёмкость разработки, построен ленточный график, произведен расчет общей сметы, приведен плановый график получения денежных средств; - в разделе техническая документация приведены: руководство пользователя, руководство программиста, руководство системного администратора; в заключении описаны выводы по результатам выполненной работы.
Введение

Задача раскроя материала на производстве имеет большое прикладное значение: составление и выбор оптимального плана раскроя позволяет сэкономить время, снизить расходы и иные материальные затраты. Многие существующие программные продукты зачастую имеют ограниченный функционал, а также не имеют способов интеграции с базами данных предприятия. В связи с этим разработка программного обеспечения для решения задачи о раскрое, является актуальной задачей. Цель выпускной квалификационной работы – разработка программно-математического обеспечения оптимального планирования технологического процесса раскроя материала. В рамках данной работы решаются следующие задачи: - Анализ предметной области; - Постановка задачи оптимального планирования раскроя материала; - Создание математической задачи оптимального планирования раскроя материала; - Анализ методов решения задачи оптимального планирования раскроя материала; - Разработка математического и алгоритмического обеспечения; - Разработка программного обеспечения; - Анализ экономической эффективности программного обеспечения.?
Содержание

Введение 7 1. Исследовательский раздел 8 1.1. Описание предметной области 8 1.2. Обзор и анализ существующих математических методов решения задачи 11 1.3. Обзор и анализ программных решений в предметной области. 16 Выводы 20 2. СПЕЦИАЛЬНЫЙ РАЗДЕЛ 22 2.1. Формализованное описание предметной области 22 2.2. Реализуемый метод решения задачи. 23 2.2.1. Алгоритм нахождения вариантов раскроя. 23 2.2.2. Алгоритм определения оптимального плана использования вариантов раскроя. 31 Выводы 33 3. Технологический раздел 35 3.1. Структура программного обеспечения 35 3.1.1. Обоснование выбора инструментальных средств для реализации программного обеспечения 36 3.2. Алгоритмическая реализация решения задачи 37 3.3. Тестирование программного обеспечения 43 Выводы 44 4. Организационно-экономический раздел 45 4.1. Определение списка работ и состава исполнителей 45 4.2. Расчет продолжительности и трудоемкости работ 47 4.3. Планирование разработки программного продукта с построением диаграммы Ганта 50 4.4. Расчет экономической эффективности 51 4.4.1. Расчет затрат на основные материалы 52 4.4.2. Заработная плата исполнителей 52 4.4.3. Расчеты накладных расходов 53 4.4.4. Общая смета затрат на разработку проекта 54 4.4.5. Оценка рисков разработки программного обеспечения 55 4.5. Расчет окупаемости программного обеспечения 57 Выводы 59 5. Техническая документация 60 5.1. Руководство пользователя 60 5.2 Руководство программиста 62 5.3 Руководство системного администратора 62 Выводы 62 Заключение 64 Список использованных источников 65 Приложение А 67 Приложение Б 84
Список литературы

1. Г.Б. Бронфельд ( Н.Новгород )., РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО ЛИНЕЙНОГО РАСКРОЯ МАТЕРИАЛОВ. [Электронный ресурс]. – URL: http://sirius-2.narod.ru/stat_opt_raskr.htm 2. Валиахметова Ю.И., Филиппова А.С., ТЕОРИЯ ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ РЕСУРСОВ Л. В. КАНТОРОВИЧА В ЗАДАЧАХ РАСКРОЯ-УПАКОВКИ: ОБЗОР И ИСТОРИЯ РАЗВИТИЯ МЕТОДОВ РЕШЕНИЯ 3. Лазарев А.А., Гафаров Е.Р., ТЕОРИЯ РАСПИСАНИЙ. ЗАДАЧИ И АЛГОРИТМЫ 4. Генетические алгоритмы. [Электронный ресурс]. – URL: https://prog-cpp.ru/genetic/ 5. Метод ветвей и границ. [Электронный ресурс]. – URL: http://www.math.nsc.ru/AP/benchmarks/UFLP/uflp_bb.html 6. Рибчинский М.Р., Седова Е.Г., Графический метод решения задач линейного программирования. 7. Бабаев Ф.В., Оптимальный раскрой материалов с помощью ЭВМ. 8. Серов В.А., Холба Ю.Я., Суханов Н.А., КОМБИНИРОВАННАЯ ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА МНОГОКРИТЕРИАЛЬНОГО СИНТЕЗА ПАРАМЕТРОВ НЕЙРОКОНТРОЛЛЕРА В АДАПТИВНОЙ СИСТЕМЕ УПРАВЛЕНИЯ ПРОМЫШЛЕННЫМ РОБОТОМ. 9. Общие сведения о Visual Studio. [Электронный ресурс]. – URL: https://docs.microsoft.com/ru-ru/visualstudio/get-started/visual-studio-ide 10. Введение в язык C# и .NET Framework | Microsoft Docs. [Электронный ресурс]. – URL: https://docs.microsoft.com/ru-ru/dotnet/csharp/getting-started/introduction-to-the-csharp-language-and-the-net-framework
Отрывок из работы

Исследовательский раздел Описание предметной области Проблема оптимального планирования технологических процессов имеет большое значение для многих отраслей промышленности. Одним из разделов оптимального планирования является оптимального использования сырья. Эффективность экономии материальных ресурсов ? один из важнейших факторов повышения эффективности всего производства и деятельности предприятия в целом. Решение этой задачи непосредственно влияет на себестоимость продукции. Отходы производства составляют значительную часть себестоимости производимой продукции, а значит, минимизация отходов является первоочередной задачей. Одним из важнейших факторов, обеспечивающих экономию минимизации отходов производства, является их рациональный раскрой. Среди мероприятий этого направления одно из ведущих мест занимает автоматизация процесса раскроя, позволяющая повысить коэффициент раскроя с учетом централизованного метода раскроя и обеспечить оптимальность норм расхода ресурсов. Задача о раскрое – частный случай задач о комплексном использовании сырья, обычно сводящихся к методу программирования линейного или программирования целочисленного. Метод решения задачи о раскрое помогает с наименьшими отходами производства использовать прутки и листы металла, листы стекла и картона и других материалов при раскрое их на заданное количество деталей различных размеров[1]. Задача оптимального раскроя материалов является одной из самых важных в ресурсосберегающих технологиях для заготовительного производства, поскольку напрямую ведет к экономии материалов и снижению отходов[1]. Одним из вариантов такой задачи является задача оптимального линейного раскроя материалов. Это касается раскроя: - проволоки; - труб, швеллера, уголков и т.п.; - проводов; - рулонов материалов (металлов, тканей, стекла, бумаги и т.п.) на продольные и поперечные полосы и других видов изделий. Основополагающую роль в становлении и развитии теории оптимального использования ресурсов и линейного программирования сыграла опубликованная профессором Л. В. Канторовичем в 1939 г., где рассматривались различные практические задачи организации производства, в которых требовалось найти наилучший вариант решения задачи о раскрое[2]. Задачи раскроя представляют собой важную технологическую проблему, оптимальное решение которых позволяет минимизировать расход имеющихся ресурсов. Это такие задачи, как: • раскрой линейного материала; • продольная резка лент и рулонов; • раскрой листов на прямоугольные заготовки; • использование материалов смешанной длины; • раскрой для серийных и несерийных изделий; • упаковка трехмерных контейнеров; • раскрой фигурных заготовок; • размещение кругов; • геометрическое покрытие областей с препятствиями элементами различной формы; • задача о выборе наилучших размеров материала для последующего раскроя; • упаковка/покрытие элементами случайных размеров, и многие другие. Подобные задачи встречаются на практике в машиностроении, металлургии, деревообрабатывающей и швейной промышленности, целлюлозно-бумажной индустрии и др. Задача о раскрое является NP-трудной. Несмотря на это, практика требует решения этой задачи. Для этого существует несколько подходов. Первым подходом является разработка полиномиальных эвристических алгоритмов. Для некоторых эвристических алгоритмов известны оценки погрешности получаемого решения. Такие алгоритмы называются приближенными. Существуют приближенные алгоритмы, гарантирующие как относительную погрешность, так и абсолютную погрешность[2]. В настоящий момент широкое распространение имеют метаэвристические алгоритмы, которые находят “хорошее” решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения[3]. Содержательно задача о раскрое является оптимизационной, т.е. состоит в выборе (нахождении) среди множества допустимых вариантов (вариантов, допускаемых условиями задачи) тех решений, на которых достигается “оптимальное” значение целевой функции. Обычно под “оптимальностью” понимается минимальное или максимальное значение некоторой целевой функции. Допустимость варианта понимается в смысле его осуществимости, а оптимальность — в смысле его целесообразности[3]. Так как задача о раскрое являются оптимизационной она решается методами дискретной оптимизации[3]. Обзор и анализ существующих математических методов решения задачи Метод решения задач дискретной оптимизации – это общая идея, применимая к широкому классу задач. Алгоритм решения – это реализация метода решения для конкретной задачи. Различают следующие методы решения[3]: • Эвристические алгоритмы (в т.ч. вероятностные алгоритмы и локальный поиск); • Метаэвристические методы; • Метод динамического программирования; • Метод Ветвей и Границ; • Графический метод и т.д. Эвристические алгоритмы Эвристические алгоритмы – алгоритмы, основанные на правдоподобных, но не обоснованных математически предположениях о свойствах оптимального решения задачи. Фактически в эвристическом алгоритме учитывается одно или несколько свойств оптимального решения, на основе которых производится сокращение перебора возможных решений[3]. Эвристические алгоритмы обычно имеют малую сложность вычислений и часто выдают хорошие, близкие к оптимальным, решения. Поэтому они часто применяются для решения трудных задач[3]. Для задач оптимизации они могут давать далеко не оптимальные решения. Поэтому, если нужно найти точное решение задачи, эти методы неприменимы[3]. Метаэвристические методы В 70–90-е годы прошлого века в результате совершенствования эвристических алгоритмов появились т.н. метаэвристические методы, например, Генетические алгоритмы (Genetic algorithms), метод имитации отжига (Simulated annealing), метод муравьиных колоний (Ant Colony Optimization) и др. Идеи этих методов были “заимствованы” из разных областей науки. Например, идея Генетического алгоритма из генетики, идея метода муравьиных колоний из биологии и т.д[3]. Генетические алгоритмы Генетические алгоритмы (ГА) — это стохастические, эвристические оптимизационные методы, впервые предложенные Джоном Холландом в 1975 году. Они основываются на идее эволюции с помощью естественного отбора[4]. Генетические алгоритмы работают с совокупностью особей –популяцией, где каждая особь представляет возможное решение данной проблемы. Она оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции[4]. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что наследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время[4]. Вначале ГА-функция генерирует определенное количество возможных решений (особей), а затем вычисляет для каждого приспособленность – близость к истине. Эти решения дают потомство (производится операция кроссовера). Более приспособленные решения имеют больший шанс к воспроизводству, а «слабые» особи постепенно «отмирают». Таким образом, происходит процесс эволюции. Полезные изменения, приводящие к увеличению приспособленности особи, дают свое потомство, в то время как «бесполезные» изменения «отмирают». После скрещивания определяется приспособленность особей нового поколения. Процесс повторяется до тех пор, пока не найдено решение или не получено достаточное к нему приближение[4]. Метаэвристические методы обычно обладают двумя важными особенностями: • В результате их работы последовательно строятся несколько решений; • Построение каждого нового решения основывается на накопленных знаниях о качестве предыдущих полученных решений. Метод динамического программирования Метод динамического программирования получил большое распространение при решении некоторых задач дискретной оптимизации. Динамическое программирование – раздел математического программирования, посвященный исследованию многошаговых задач принятия оптимальных решений. При этом многошаговость задачи отражает реальное протекание процесса принятия решений во времени, либо вводится в задачу искусственно за счет расчленения процесса принятия однократного решения на отдельные этапы, шаги. Цель такого представления состоит в сведении исходной задачи высокой размерности к решению на каждом шаге задачи меньшей размерности[3]. В основе динамического программирования лежит следующая простая характеристика оптимальной стратегии, сформулированная Р.Беллманом в 50-е годы 20-го века и названная принципом оптимальности Беллмана: каково бы ни было начальное состояние и первое решение, последующие решения составляют оптимальную политику по отношению к начальному состоянию, полученному в результате первого решения[3]. Метод Ветвей и Границ Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям[5]. В основе метода лежит идея последовательного разбиения множества допустимых решений. На каждом шаге метода элементы разбиения (подмножества) подвергаются анализу – содержит ли данное подмножество оптимальное решение или нет. Если рассматривается задача на минимум, то проверка осуществляется путем сравнения нижней оценки значения целевой функции на данном подмножестве с верхней оценкой функционала. В качестве оценки сверху используется значение целевой функции на некотором допустимом решении. Допустимое решение, дающее наименьшую верхнюю оценку, называют рекордом. Если оценка снизу целевой функции на данном подмножестве не меньше оценки сверху, то рассматриваемое подмножество не содержит решения лучше рекорда и может быть отброшено. Если значение целевой функции на очередном решении меньше рекордного, то происходит смена рекорда. Будем говорить, что подмножество решений просмотрено, если установлено, что оно не содержит решения лучше рекорда. Если просмотрены все элементы разбиения, алгоритм завершает работу, а текущий рекорд является оптимальным решением. В противном случае среди непросмотренных элементов разбиения выбирается множество, являющееся в определенном смысле перспективным. Оно подвергается разбиению (ветвлению). Новые подмножества анализируются по описанной выше схеме. Процесс продолжается до тех пор, пока не будут просмотрены все элементы разбиения[5]. Графический метод Графический метод применяется для задач линейного программирования с двумя переменными, когда ограничения выражены неравенствами, и задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. Графический метод основан на геометрическом представлении допустимых решений и целевой функции задачи. Каждое из неравенств задачи линейного программирования определяет на координатной плоскости (x1, x2) некоторую полуплоскость. Пересечение этих полуплоскостей задает область допустимых решений (ОДР), то есть любая точка из этой области является решением системы ограничений[6]. Суть метода состоит в выполнении следующих этапов: • Находим область допустимых решений системы ограничений задачи; • Формируем графическое изображение целевой функции; • Определяем направление возрастания целевой функции; • Находим оптимальное решение задачи ЛП; • Находим координаты точки экстремума и значение целевой функции в этой точке; Обзор и анализ программных решений в предметной области. В настоящее время существует множество программ по раскрою материала: Быстрый линейный раскрой Программа предназначена для оптимизации раскроя деталей из линейных заготовок. Чем больше разброс деталей по длине и их количество, тем более актуальным становится проблема их оптимально размещения. В отличии от подобных программ в программе реализован мощный алгоритм оптимизации размещения деталей для уменьшения доли отходов от заготовок. Достоинством программы является высокая скорость вычислений. Недостатком является то, что доступная для скачивания демоверсия не позволяет оценить качество раскроя из-за существенных ограничений. Интерфейс программы «Быстрый линейный раскрой» представлен на рисунке 1.1. Рисунок 1.1 – Интерфейс программы «Быстрый линейный раскрой». Оптимизация раскроя профиля – Optimize Программа предназначена для оптимизации линейного раскроя деталей из заготовок профиля различной длины (длина хлыста — от 500 до 12000 мм). В основу программы заложен мощный алгоритм рационального раскроя линейных материалов. Достоинством программы является высокая скорость вычислений. Недостатком является то, что демоверсия позволяет использовать программу только 10 раз. Так же тестирование показало, что качество раскроя является не оптимальным. Интерфейс программы «Оптимизация раскроя профиля – Optimize» представлен на рисунке 1.2. Рисунок 1.2 – Интерфейс программы «Оптимизация раскроя профиля – Optimize». Cutting Line Программа предназначена для оптимального раскроя линейных заготовок на линейные отрезки различной длины и может быть использована в деревообрабатывающей и целлюлозно-бумажной промышленности, металлообработке, швейном производстве и т.д. В основу программы положен уникальный высокоскоростной алгоритм, позволяющий быстро произвести раскрой и добиться минимального процента отходов на линейных заготовках. В программе реализованы следующие функции и возможности: • задание произвольного числа раскраиваемых заготовок и отрезков; • расчет суммарных длин отрезков и остатков; • задание разных режимов выполнения раскроя; Недостатком является наличие только платной версии программы, а также не всегда достигается оптимальный план раскроя. Интерфейс программы «Cutting Line» представлен на рисунке 1.3. Рисунок 1.3 – Интерфейс программы «Cutting Line». Выводы В исследовательском разделе была описана предметная область. Подробно описана и рассмотрена задача о раскрое. Приведен обзор существующих математических методов решения задачи. Произведен анализ методов. Также был приведен обзор существующих программных решений в предметной области и произведен анализ возможностей и недостатков. На основе анализа существующих математических методов решения задачи был сделан Выбор алгоритмов для решения задачи и обоснование выбора. Для решения задачи выбраны два математических метода: 1. Генетические алгоритмы хороши при больших исходных данных, а так как количество видов раскраиваемых может быть большим, то генетические алгоритмы хорошо справляются с первичным построением вариантов раскроя. 2. Метод ветвей и границ – наиболее подходит для определения оптимального плана раскроя, т.к. выполняется не полный перебор, а откидываются решения с заведомо неоптимальными вариантами. Его результаты наиболее близки к оптимальным, сам вычислительный процесс не особо сложный и при правильной реализации можно сохранить достаточно большой объем оперативной памяти. ? СПЕЦИАЛЬНЫЙ РАЗДЕЛ Формализованное описание предметной области Формулировка задачи: В прокатный цех поступают заказы на производство заготовок. Необходимо прокатные прутки длиной 6м разрезать на заготовки длиной 1,4; 2 и 2,5м в количестве 40, 60 и 50шт соответственно. В общем виде задачу можно формализовать так: Необходимо из материала длиной L выкроить заготовки длинной l1, l2, ..., li, ..., ln в заданном количестве pi (i=1, 2, ..., n). Требуется определить оптимальный план раскроя материала, т.е. получить минимальные отходы с учетом заданного количества заготовок. При создании математической модели задач раскроя необходимо учитывать ряд требований, связанных с производством[7]: число заготовок, полученных по определенному варианту раскроя, должно соответствовать установленной производственной программе; общее количество материалов (прутков), израсходованных на выполнение производственной программы, или величина отходов, полученных от раскроя по выбранным вариантам должны быть наименьшими; Это можно сделать, используя различные варианты раскроя материала. Задача оптимального раскроя состоит в том, чтобы выбрать один или несколько вариантов раскроя материала и определить, какое количество материала следует раскраивать, применяя каждый из выбранных вариантов[7]. Выделяют два этапа решения задачи оптимального раскроя. На первом этапе определяются варианты раскроя материала, на втором — решается задача линейного программирования для определения оптимального плана использования вариантов раскроя[7]. Реализуемый метод решения задачи. Алгоритм нахождения вариантов раскроя. Имеется материал длиной L. Необходимо выкроить из него заготовки длиной l1, l2, ..., li, ..., ln. Определить все варианты раскроя. Примем следующие обозначения: i – номер вида заготовок (i = ?(1,n)); L – длина материала; li – длина заготовки; yi – количество заготовок выкраиваемых из материала; ? – отходы, получаемые при раскрое материала; Суммарная длина заготовок должна быть меньше длины материала: . (2.1) Отходы получаются вычитанием суммарной длины заготовок из длины материала: . (2.2) Так же отходы не могут быть больше длины любой из заготовок, иначе заготовка попадает в вариант раскроя: ; (2.3) ; (2.4) . (2.5) Из этого следует: . (2.6) Определить: (2.7) При решении этой системы неравенства получим варианты раскроя материала. Для нахождения рациональных вариантов будем использовать генетический алгоритм многокритериальной оптимизации. Исходные функции: . (2.8) . (2.9) Требуется решить систему неравенств: (2.10) Составим вспомогательные функции: (2.11) (2.12) (2.13) Решаем задачу многокритериальной оптимизации: Определить минимум векторной функции. (2.14) Генетический алгоритм многокритериальной оптимизации ГАМО имеет структуру, представленную на рисунке 2.1, и состоит из следующих основных функциональных блоков. Рисунок 2.1 – Схема генетического алгоритма многокритериальной оптимизации. Генерация первого поколения тестовых точек-особей (ТТО). Осуществляется генерация первого поколения популяции ТТО в двоичном виде: , где - кратное 4 число, характеризующее размер популяции ТТО (число битовых строк ); - длина битовой строки ; - номер текущего поколения[8]. Разряды битовых строк заполняются на основе механизма случайных чисел с равномерным законом распределения. В каждой закодирована информация обо всех компонентах вектора (рисунок 2.2). Численность популяции остается постоянной для каждого , где - номер последнего поколения[8]. Многокритериальная оценка пригодности ТТО. Данный функциональный блок является важнейшим структурным элементом ГАМО, в котором последовательно выполняются следующие шаги[8]. Шаг 1. Декодирование популяции ТТО осуществляется с помощью оператора , . (2.15) Каждый участок , битовой строки (рисунок 2.2) преобразуется в натуральное число в соответствии с формулой , (2.16) где (2.17) В (2.17) - -й бит в -ом компоненте ТТО ; ; , где z - количество нулевых разрядов, расположенных левее текущего в . Двоичную запись компонента вектора считаем кодом Грея, который относится к группе отраженных двоичных кодов, обладающих единичным кодовым расстоянием, т.е. отображение единичного сдвига из двоичного пространства дает единичный сдвиг в пространстве вещественных чисел. Наличие этого свойства улучшает сходимость оптимизационной процедуры[8]. Рисунок 2.2 – Схема кодирования вектора в ТТО Для вектора справедливо включение . Поэтому значения координат вектора , , могут быть вычислены с помощью линейного преобразования: . (2.18) Шаг2. Вычисление функции пригодности. Сформируем функцию пригодности в следующем виде: , (2.19) где - параметр выбирается из практических соображений и влияет на скорость сходимости алгоритма многокритериальной оптимизации. Очевидно, что при , и при Воспроизведение популяции точек-родителей. В рамках данного функционального блока формируется вероятностный механизм отбора ТТО в родители. С этой целью производится построение интервала с помощью следующих рекуррентных соотношений: (2.20) Далее полагаем . Генерация популяции точек-родителей осуществляется следующим образом. Генерируется значение случайной величины с равномерным законом распределения на интервале . ТТО, на подинтервал которой выпало значение случайной величины, выбирается в родители, после чего соответствующий подинтервал исключается из интервала . Указанную процедуру повторяем N/2 раз. Механизм генерации с исключением устраняет свойство вырождения популяции, обеспечивая построение аппроксимации всего множества оптимальных решений на множестве достижимых векторных оценок , что улучшает свойства ГАМО[8]. Кроссовер (рисунок 2.3). Битовые строки родителей, обменявшиеся наборами бит (генов), становятся ТТО потомками и каждый из них несет наследственную информацию о своих родителях. Для осуществления кроссовера все ТТО родительского массива разбиваем на пары. Далее N/2 раз генерируется значение случайной величины с равномерным законом распределения на интервале для определения номера пары, участвующей в кроссовере. Пары ТТО-родителей, оставшиеся без кроссовера, дают потомков прямым копированием. Если происходит переполнение формируемой популяции потомков, то лишние ТТО удаляются из нее случайным образом[8]. Мутация (рисунок 2.4). Применяется мутация двух видов: однобитовая мутация - происходит замена состояния некоторого разряда битовой строки на противоположное; инверсия - битовая строка делится в средней точке и относительно нее меняются местами блоки бит. Вероятность проведения мутации и инверсии в популяции ТТО задаются априорно и требуют настройки под конкретную задачу. Для каждой ТТО генерируется значение случайной величины с равномерным законом распределения на интервале . Если значение случайной величины выпало на интервал , то производится мутация. Аналогичным образом для каждой ТТО реализуется вероятностный механизм инверсии[8]. Критерии останова. Формируются следующие критерии останова ГАМО. Проверяется условие: , (2.21) где - число ТТО в популяции размером , для которых выполняется неравенство: . (2.22) Параметры , назначаются эмпирически из следующих диапазонов: ; . Если неравенство (2.21) выполняется, то полагаем, что множество точек , соответствующее популяции является аппроксимацией множества оптимальных решений, т.е., и ГАМО завершает работу. Иначе проверяется следующий критерий останова. 2. Если , то полагаем, что множество точек , является аппроксимацией множества оптимальных решений и ГАМО завершает работу. Алгоритм определения оптимального плана использования вариантов раскроя. Имеется материал длиной L. Необходимо выкроить из него заготовки длиной l1, l2, …, li, …, ln в количестве p1, p2, …, pi, …, pn. Необходимо определить оптимальный план раскроя материала на заготовки, обеспечивающий минимальные отходы и обеспечивающий необходимым количеством заготовок. Примем следующие обозначения: i – типа заготовок (i = ?(1,n)); j – вариант разрезания материала (j = ?(1,m)); ajk – количество заготовок k-го типа полученных, при разрезании материала j-ым вариантом; cj – количество отходов полученных, при разрезании материала j-ым вариантом; xj – количество материала разрезанного j-ым вариантом; pi – количество заготовок i-го типа необходимое по заданию. Составим математическую модель для решения задачи оптимального раскроя материала. Минимальное количество отходов является критерием оптимальности: (2.23) При этом количество заготовок каждого типа должно удовлетворять заданному необходимому количеству: (2.24) В итоге получается модель:
Не смогли найти подходящую работу?
Вы можете заказать учебную работу от 100 рублей у наших авторов.
Оформите заказ и авторы начнут откликаться уже через 5 мин!
Похожие работы
Дипломная работа, Технологические машины и оборудование, 72 страницы
1800 руб.
Дипломная работа, Технологические машины и оборудование, 76 страниц
1900 руб.
Дипломная работа, Технологические машины и оборудование, 66 страниц
1650 руб.
Дипломная работа, Технологические машины и оборудование, 87 страниц
2175 руб.
Дипломная работа, Технологические машины и оборудование, 71 страница
990 руб.
Дипломная работа, Технологические машины и оборудование, 85 страниц
2125 руб.
Служба поддержки сервиса
+7(499)346-70-08
Принимаем к оплате
Способы оплаты
© «Препод24»

Все права защищены

Разработка движка сайта

/slider/1.jpg /slider/2.jpg /slider/3.jpg /slider/4.jpg /slider/5.jpg