Курсовая работа: Оптимальный раскрой материала с максимальной прибылью

Содержание

Введение

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

2. Решение задачи

3. Описание алгоритма

4. Описание программы

5. Контрольный пример

Вывод

Текст программы

Литература

1. Введение

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

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

1) конфигурацией получаемых при раскрое заготовок;

2) объемом выпускаемой продукции.

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

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

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

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

Решить задачу гильотинного раскроя материала (длинномерного проката) с максимальной прибылью: кусок материала длиной L раскраивается на заготовки m наименований, для каждой заготовки с номером i = известны ее длина l_i и оценка с_i . Требуется найти раскрой с максимальной оценкой получаемого набора заготовок.

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

2. Решение задачи

Предположим, что кусок материала длиной L раскраивается на заготовки m наименований. Для каждой заготовки с номером i = известны ее длина l_i и оценка с_i . Требуется найти раскрой с максимальной оценкой получаемого набора заготовок.

Раскрой может содержать любое число каждой из заготовок. Тогда набор заготовок характеризуется m-мерным вектором

X = (x₁ , x₂ , … , x_m ), (1)

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

(2)

набора заготовок (1) при единственном линейном ограничении

.(3)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--