ВКР: Математическое и программное обеспечение для исследования простых эвристик при решении задач линейного раскроя

Содержание

Слайд 2

Цель работы:
Сравнение эффективности различных алгоритмов для решения разных классов задач линейного раскроя

Цель работы: Сравнение эффективности различных алгоритмов для решения разных классов задач линейного
на основе вычислительного эксперимента.
Задачи:
выполнить аналитический обзор методов решения целочисленных задач линейного раскроя;
реализовать в виде программного продукта алгоритмы линейного раскроя на базе метода простых эвристик;
провести вычислительный эксперимент для исследования влияния исходных данных на результат решения задачи линейного раскроя;
разработать рекомендации по выбору алгоритма в зависимости от исходных данных.

Слайд 3

ПОСТАНОВКА ЗАДАЧИ

ПОСТАНОВКА ЗАДАЧИ

Слайд 4

СТРУКТУРА РЕШЕНИЯ

СТРУКТУРА РЕШЕНИЯ

Слайд 5

КЛАССИФИКАЦИЯ ЗАДАЧ РАСКРОЯ

КЛАССИФИКАЦИЯ ЗАДАЧ РАСКРОЯ

Слайд 6

 

ЗАДАЧА ЛИНЕЙНОГО РАСКРОЯ В УСЛОВИЯХ ЕДИНИЧНОГО (МЕЛКОСЕРИЙНОГО) ПРОИЗВОДСТВА
ПОСТАНОВКА ЗАДАЧИ

 
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

ЗАДАЧА ЛИНЕЙНОГО РАСКРОЯ В УСЛОВИЯХ ЕДИНИЧНОГО (МЕЛКОСЕРИЙНОГО) ПРОИЗВОДСТВА ПОСТАНОВКА ЗАДАЧИ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

Слайд 7

КЛАССИФИКАЦИЯ МЕТОДОВ

. . .

. . .

КЛАССИФИКАЦИЯ МЕТОДОВ . . . . . .

Слайд 8

МЕТОД ПРОСТЫХ ЭВРИСТИК

МЕТОД ПРОСТЫХ ЭВРИСТИК

Слайд 9

БЛОК-СХЕМА АЛГОРИТМОВ ЛИНЕЙНОГО РАСКРОЯ

Сортировка по длине
sort_length()

БЛОК-СХЕМА АЛГОРИТМОВ ЛИНЕЙНОГО РАСКРОЯ Сортировка по длине sort_length()

Слайд 10

БЛОК-СХЕМА АЛГОРИТМОВ ЛИНЕЙНОГО РАСКРОЯ

Следующий подходящий (NF)
Next_Fit()

Первый подходящий (FF)
First_Fit()

БЛОК-СХЕМА АЛГОРИТМОВ ЛИНЕЙНОГО РАСКРОЯ Следующий подходящий (NF) Next_Fit() Первый подходящий (FF) First_Fit()

Слайд 11

СТРУКТУРА ПРОГРАММНОГО ПРОДУКТА

СТРУКТУРА ПРОГРАММНОГО ПРОДУКТА

Слайд 12

ИНТЕРФЕЙС ПРОГРАММЫ

ИНТЕРФЕЙС ПРОГРАММЫ

Слайд 13

установить параметры исходных данных (границу между большими и маленькими заготовками, долю больших

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

МЕТОДИКА ПРОВЕДЕНИЯ ИССЛЕДОВАНИЯ

Слайд 14

 

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Слайд 15

 

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Слайд 16

Вывод:
при v = 0,5L алгоритм FFD работает качественнее остальных и находит лучшие

Вывод: при v = 0,5L алгоритм FFD работает качественнее остальных и находит
коэффициенты раскроя при любом проценте больших заготовок;
при v = 0,5L алгоритм NF работает наименее качественно и находит худшие коэффициенты раскроя при любом проценте больших заготовок;
с увеличением доли больших заготовок падает качество решения.

КАЧЕСТВО РАБОТЫ АЛГОРИТМОВ

Слайд 17

Вывод:
разброс оценки дисперсии минимален, это значит, что в целом все рассмотренные алгоритмы

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

СТАБИЛЬНОСТЬ РАБОТЫ АЛГОРИТМОВ

Слайд 18

РЕЗУЛЬТАТЫ ВКР

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

РЕЗУЛЬТАТЫ ВКР выполнен аналитический обзор методов решения целочисленных задач линейного раскроя и
для реализации метод простых эвристик;
рассмотрены и реализованы в виде программного продукта алгоритмы линейного раскроя на базе выбранного метода;
предложен способ разбиения множества заготовок на две группы: “большие” (длина которых больше половины длины стержня) и “маленькие” заготовки;
проведен вычислительный эксперимент, который показал влияние различных вариантов соотношения количества “больших” заготовок к общему числу заготовок на результат решения задачи: с повышением доли больших заготовок ухудшается качество решения;
разработаны рекомендации по выбору алгоритма для решения задач линейного раскроя: алгоритм FFD работает качественнее остальных и находит лучшие коэффициенты раскроя при любом проценте больших заготовок, при этом стабильность работы всех алгоритмов практически одинакова.