Оптимальный раскрой материала с максимальной прибылью - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Оптимальный раскрой материала с максимальной прибылью

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Обычно при производстве изделий материал поступает в виде рулонов, полос, прямоугольных листов, стержней и т. д. Поступающий материал раскраивается на части заданных размеров и определенной конфигурации, представляющие собой в одних случаях заготовки, в других -- готовые детали. К задачам раскроя, относятся и задачи плотного размещения совокупности предметов на заданных участках.
Задачи рационального раскроя описываются сходными математическими моделями. Существенное различие этих моделей определяется главным образом двумя факторами:
1) конфигурацией получаемых при раскрое заготовок;
Задачи раскроя, определяемые первым фактором, подразделяют на два класса. К первому классу относятся задачи фигурного раскроя, ко второму -- задачи нефигурного раскроя. При фигурном раскрое материал раскраивается на заготовки самых различных конфигураций. К классу задач нефигурного раскроя относятся задачи линейного и прямоугольного раскроя. В первом случае материал раскраивают на заготовки различной длины, для которых задается только один линейный размер. Во втором случае получают заготовки прямоугольной формы, для которых задаются два размера.
Задачи раскроя, определяемые вторым фактором, также подразделяют на два класса: задачи раскроя в условиях массового (крупносерийного) выпуска изделий и задачи раскроя в условиях единичного (мелкосерийного) производства. К обоим классам могут принадлежать как задачи фигурного, так и задачи нефигурного раскроя. Задачи раскроя в условиях массового производства описываются непрерывными моделями линейного программирования, а в условиях единичного производства -- целочисленными. В связи с этим задачи раскроя в указанных условиях часто называют соответственно непрерывными и целочисленными.
Задачи рационального раскроя в условиях массового производства относятся к классу задач линейного программировании, с неявно заданными столбцами (способами раскроя). При решении таких задач методами линейного программирования возникает необходимость в генерировании раскроев на каждом шаге процесса. Ниже рассмотрена задача генерирования линейных раскроев.
Решить задачу гильотинного раскроя материала (длинномерного проката) с максимальной прибылью: кусок материала длиной L раскраивается на заготовки m наименований, для каждой заготовки с номером i = известны ее длина l i и оценка с i . Требуется найти раскрой с максимальной оценкой получаемого набора заготовок.
Задача оптимального раскроя длинномерного проката носит различный характер в зависимости от типа производства. Например, для крупносерийного производства характерны следующие задачи: стремление получить значительное число заготовок одинаковой длины, минимизировать остаток, получить максимальную прибыль от раскроя и т.д. В данной курсовой работе будет рассмотрено решение задачи оптимального раскроя материала с максимальной прибылью методом динамического программирования с использованием так называемой "сеточным методом", при котором возникает необходимость генерирования раскроев на каждом шаге процесса.
Предположим, что кусок материала длиной L раскраивается на заготовки m наименований. Для каждой заготовки с номером i = известны ее длина l i и оценка с i . Требуется найти раскрой с максимальной оценкой получаемого набора заготовок.
Раскрой может содержать любое число каждой из заготовок. Тогда набор заготовок характеризуется m-мерным вектором
Элементы которого представляют собой целые неотрицательные компоненты, указывающие на число заготовок каждого вида. При этом требуется максимизировать суммарную оценку
набора заготовок (1) при единственном линейном ограничении
Генерирование раскроя будем рассматривать как многошаговый циклический процесс, состоящий из последовательного выбора отдельных заголовок.
Для решения поставленной задачи рассмотрим функцию
где через X i обозначено множество неотрицательных векторов х, отвечающих раскроям, в которых общая длина заготовок не превосходит длины l. Пусть l 0 = min l i , где i =1…m.
Тогда при всех l[0,l 0 ] соответствующие множества X l состоят из одного нулевого элемента и, следовательно, f(l) = 0 для всех таких l. Для l[0,L 0 ], справедливы следующие рекуррентные соотношения:
где через I l обозначено множество тех i, при которых l i l.
Опираясь на рекуррентные соотношения (5), можно для решения задачи предложить простой численный метод, представляющий собой перебор всех допустимых раскроев. Реализация всего процесса основывается на двух этапах:
Решаем задачу сеточным методом: сначала выполняем прямой ход. Выбираем начальное значение длины раскроя, равное минимальной длине детали: l 0 = min l i = 7 и последовательно "шагаем" до конца проката, т.е. 40.
Чтобы найти максимальную стоимость на каждом шаге, мы перебираем все детали, которые могут поместиться в текущий раскрой, начиная с минимальной по длине. Для подсчета стоимости раскроя на текущем шаге мы вычитаем длину очередной выбранной детали из текущего раскроя и по таблице находим раскрой с длиной, равной полученному остатку и суммируем его оценку с оценкой выбранной детали. Из вычисленных оценок выбираем максимальную и заносим её в таблицу, вместе с номером детали, при которой эта оценка была получена.
Далее в таблице приведены результаты первого этапа (прямого хода) процесса:
Здесь и далее i(l) - номер детали, которой соответствует максимальная оценка раскроя (сумма стоимости всех деталей, входящих в раскрой) f(l) на шаге l.
Рассмотрим более подробно последовательное заполнение таблицы на примере шагов
Выбираем первую деталь: i = 1. Длина детали 7, оценка 9.
Вычисляем остаток от раскроя: 7 - 7 = 0. Поскольку остаток нулевой, то деталей, которые можно добавить в раскрой, нет. Следовательно, максимальная оценка текущего раскроя равна f = 9. Заносим в таблицу значения i(7) = 1, f(7) = 9 и переходим к следующему шагу раскроя.
Снова берём первую деталь: i = 1. Длина детали 7, оценка 9.
Остаток: 8 - 7 = 1. Так как деталей с такой длиной нет, максимальная оценка раскроя f = 9. Заносим в таблицу i(8) = 1, f(8) = 9.
Заносим в таблицу i(9) = 1, f(9) = 9.
Заносим в таблицу i(10) = 1, f(10) = 9.
Учитывая, что в текущий раскрой также уместится деталь i = 2 c длиной 11, получим: i = 2, остаток 11 - 11 = 0, f = 14.
Сравним оценки раскроев. Выберем максимальную оценку (f = 14) и соответствующую ей деталь (i = 2).
Заносим в таблицу i(11) = 2, f(11) = 14.
i = 2, остаток 12 - 11 = 1, f = 14 (максимум)
Заносим в таблицу i(12) = 2, f(12) = 14.
i = 2, остаток 13 - 11 = 2, f = 14.
i = 3, остаток 13 - 13 = 0, f = 16 (максимум)
Заносим в таблицу i(13) = 3, f(13) = 16.
Если мы видим, что длина остатка раскроя больше или равна начальному значению длины раскроя (l 0 = 7), т.е. в остаток может поместиться какая-либо деталь (в данном случае с индексом i = 1), из таблицы считываем значение оценки раскроя f(i) при i, равном значению остатка: f (7) = 9, тогда суммарная оценка раскроя f = f(7) + 9 = 9 + 9 = 18 (максимум)
i = 2, остаток 14 - 11 = 3, f = 14.
i = 3, остаток 14 - 13 = 1, f = 16.
Заносим в таблицу i(14) = 1, f(14) = 18.
i = 1, остаток 22 - 7 = 15, f (15) = 18, f = 18 + 9 = 27.
i = 2, остаток 22 - 11 = 11, f(11) = 14, f = 14 + 14 = 28 (максимум)
i = 3, остаток 22 - 13 = 9, f(9) = 9, f = 9 + 16 = 25.
i = 4, остаток 22 - 17 = 5, f = 22.
Заносим в таблицу i(22) = 2, f(22) = 28. и т.д., пока не достигнут конец проката.
Выполняем обратный ход (начинаем двигаться с конца таблицы):
Из таблицы получаем индекс детали, добавленной в текущий раскрой: i(40) = 1.
Находим длину детали с полученным индексом: l 1 = 7.
Вычисляем остаток раскроя: 40 - 7 = 33. Этот остаток используем для следующего шага обратного хода.
Остаток раскроя: 11 - 11 = 0. Обратный ход закончен.
Теперь подсчитываем количество деталей каждого типа, которые мы получили при обратном ходе. Деталь с индексом i = 1 встретилась 1 раз, деталь с индексом i = 2 встретилась 3 раза.
Таким образом, искомый оптимальный раскрой характеризуется следующим четырёхмерным вектором x = (1; 3; 0; 0).
В вышеприведённой таблице с результатами прямого хода выделены номера заготовок, которые при обратном ходе последовательно включались в оптимальный раскрой.
Результат работы программы (проверка алгоритма):
Длина детали №1….: 7 Цена детали №1….: 9
Длина детали №2….: 11 Цена детали №2….: 14
Длина детали №3….: 13 Цена детали №3….: 16
Длина детали №4….: 17 Цена детали №4….: 22
Оптимальное количество деталей каждого типа:
Результаты ручного и машинного вычислений совпадают, что говорит о работоспособности разработанного алгоритма для ЭВМ.
В данной работе поставленная задача была решена с помощью сеточного метода. Как показала проделанная работа, этот метод эффективен и прост для программной реализации на ЭВМ. Результат, полученный с помощью этого метода, является оптимальным. В нём реализуется целенаправленный перебор за конечное число шагов, в результате чего находится рациональный раскрой с максимумом прибыли.
В работе были произведены ручные вычисления и по ним проверена работа запрограммированного алгоритма на ЭВМ. Разработанная программа и сеточный метод оптимизации раскроя достаточно универсальны. Они могут применяться в различных отраслях промышленности при массовом производстве, при этом в алгоритм следует вносить коррективы, связанные с учетом технологии производства и применяемого оборудования.
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, Grids, ComCtrls, ExtCtrls;
max_i: integer;//максимальный индекс детали для текущей длины материала
procedure Button_ExitClick(Sender: TObject);
procedure Edit_DetailAmountChange(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Edit_MaterialLengthChange(Sender: TObject);
procedure Button_CalculateClick(Sender: TObject);
procedure Button1Click(Sender: TObject);
MAX_DETAIL_AMOUNT=10;//максимальное кол-во деталей
MAX_CUTRECORD_AMOUNT=10000;//максимальное кол-во записей раскроя
MAX_MATERIAL_LENGTH=10000;//максимальная длина материала
materialLength: integer;//длина материала
detailAmount: integer;//кол-во деталей
details: array[1..MAX_DETAIL_AMOUNT] of TDetail;//детали
x: array[1..MAX_DETAIL_AMOUNT] of integer;//результат
//процедура вычисления рационального раскроя
cutRecords: array[0..MAX_CUTRECORD_AMOUNT-1] of TCutRecord;
cutRecords1: array[1..MAX_CUTRECORD_AMOUNT] of TCutRecord;
if (currCut.max_i=-1) or (currCut.i>currCut.max_i) then
if (currCut.l>=l0) and (currCut.lmaxCut.c then
currCut.l:=currCut.l-details[currCut.i].l;
currCut.c:=currCut.c+details[currCut.i].c;
x[cutRecords[l].i]:=x[cutRecords[l].i]+1;
//ввод данных пользователя из таблицы
materialLength:=strToInt(Form_Main.Edit_MaterialLength.Text);
detailAmount:=strToInt(Form_Main.Edit_DetailAmount.Text);
details[i].l:=strToInt(Form_Main.StringGrid_In.Cells[1,i]);
details[i].c:=strToInt(Form_Main.StringGrid_In.Cells[2,i]);
//графическое отображение рационального раскроя
fillRect(rect(0, 0, image.width, image.height));
rectangle(trunc(k_x*sum), 0, trunc(k_x*materialLength), 50);
rectangle(0, 0, trunc(k_x*sum), 50);
curr_x_scr:=curr_x_scr+k_x*details[i].l;
textOut(trunc(curr_x_scr), 51, intToStr(curr_x));
// textOut(trunc(curr_x_scr-15), 21, '('+intToStr(i+1)+')');
procedure TForm_Main.Button_ExitClick(Sender: TObject);
procedure TForm_Main.Edit_DetailAmountChange(Sender: TObject);
new_d_a:=strToInt(Form_Main.Edit_DetailAmount.Text);
if (new_d_a<=MAX_DETAIL_AMOUNT) then
Form_Main.StringGrid_In.RowCount:=new_d_a+1;
Form_Main.StringGrid_In.Cells[0,i]:=intToStr(i);
Form_Main.Edit_DetailAmount.Text:=intToStr(MAX_DETAIL_AMOUNT);
Form_Main.Edit_DetailAmount.Text:=intToStr(1);
procedure TForm_Main.FormCreate(Sender: TObject);
Form_Main.UpDown_MaterialLength.Min:=1;
Form_Main.UpDown_MaterialLength.Max:=MAX_MATERIAL_LENGTH;
Form_Main.UpDown_DetailAmount.Min:=1;
Form_Main.UpDown_DetailAmount.Max:=MAX_DETAIL_AMOUNT;
Form_Main.StringGrid_In.Cells[0,0]:='№ детали';
Form_Main.StringGrid_In.Cells[1,0]:='Длина';
Form_Main.StringGrid_In.Cells[2,0]:='Цена';
Form_Main.StringGrid_In.Cells[0,1]:='1';
Form_Main.StringGrid_Out1.Cells[0,0]:='№ детали';
Form_Main.StringGrid_Out1.Cells[1,0]:='Количество';
procedure TForm_Main.Edit_MaterialLengthChange(Sender: TObject);
new_m_l:=strToInt(Form_Main.Edit_MaterialLength.Text);
if not (new_m_l<=MAX_MATERIAL_LENGTH) then
Form_Main.Edit_MaterialLength.Text:=intToStr(MAX_MATERIAL_LENGTH);
Form_Main.Edit_MaterialLength.Text:=intToStr(1);
//сортировка данных по возрастанию длины детали
for i:=1 to Form_Main.StringGrid_In.RowCount-2 do
if strToInt(Form_Main.StringGrid_In.Cells[1,i])>
strToInt(Form_Main.StringGrid_In.Cells[1,i+1]) then
Form_Main.StringGrid_In.cols[1].Exchange(i,i+1);
Form_Main.StringGrid_In.cols[2].Exchange(i,i+1);
//вычисление рационального раскроя и отображение результата
procedure TForm_Main.Button_CalculateClick(Sender: TObject);
searchRationalCut(materialLength, detailAmount, details, x);
Form_Main.StringGrid_Out1.RowCount:=detailAmount+1;
Form_Main.StringGrid_Out1.Cells[0,i]:=intToStr(i);
Form_Main.StringGrid_Out1.Cells[1,i]:=intToStr(x[i]);
Form_Main.Edit1.Text:=intToStr(cost);
Form_Main.Edit2.Text:=intToStr(materialLength-sum);
drawRationalCut(Form_Main.Image_Cut, materialLength, detailAmount, details, x);
procedure TForm_Main.Button1Click(Sender: TObject);
1. Э.А. Мухачева "Рациональный раскрой промышленных материалов". Москва, Машиностроение, 1984 г.
2. Э.А. Мухачева, Г.Ш. Рубинштейн "Математическое программирование". Новосибирск, Наука, 1977 г.
Создание необходимого количества заготовок различных размеров. Составление оптимального плана раскроя, учитывая, что суммарный остаток материала должен быть минимальным. Программы, реализованные в приложении VBA, которые прилагаются к данному отчету. курсовая работа [239,8 K], добавлен 26.03.2015
Типы резки метала, оценка преимуществ и недостатков каждого метода: лазерная, плазменная, гидроабразивная, высокоточная. Структура и общее описание исследуемого предприятия. Функциональная модель деятельности и разработка путей ее совершенствования. курсовая работа [124,3 K], добавлен 13.12.2013
Основные способы решения задач целочисленного программирования: округление решений до целого, метод полного перебора, применение оптимизационных алгоритмов. Алгоритм метода ветвей и границ. Пример с оптимизацией побочного производства лесничества. презентация [323,6 K], добавлен 30.10.2013
Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора. курсовая работа [202,6 K], добавлен 14.12.2013
Применение и генерирование независимого случайного процесса. Исследование вариантов формирования случайных величин с разными законами распределения. Оценка их независимости с помощью построения гистограммы распределения в программной среде LabVIEW. контрольная работа [611,5 K], добавлен 18.03.2011
Возможные тематики задач ЛП: рациональное использование сырья и материалов, задачи оптимизации раскроя. Преобразование неограниченных по знаку переменных. Алгоритм симплекс-метода. Максимизация основной функции и использования искусственных переменных. презентация [588,2 K], добавлен 28.05.2014
Требования к языкам программирования, их эффективность, лаконичность, ясность, реальные возможности. Создание языка С#. Применение систем линейных алгебраических уравнений для практических задач, сущность и особенности метода Крамера для их решения. курсовая работа [118,1 K], добавлен 13.11.2009
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Оптимальный раскрой материала с максимальной прибылью курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение Эссе Рассуждение О Будущем России
Контрольная Работа На Тему Международный Маркетинг: Особенности И Осуществление
Реферат На Тему Новоапостольская Церковь
Дипломная работа по теме Бухгалтерский учет и исследование доходов организации на примере 'Томскпромстройбанка'
Приемная Семья Курсовая Работа
Эссе Ванны Официальный
Курсовая работа: Палестино-израильский переговорный процесс до и после: начало Интифады
Дипломная Работа На Тему Відображення Завантаженості Мережі
Реферат: Методические рекомендации для педагогов по изучению курса новейшей истории России в аспекте проведения политико-экономических преобразований в России в начале 1990-х гг.
Дипломная работа по теме Влияние темперамента на характер общения подростка
Курсовая работа: Личные права граждан и их охрана
Курсовая работа по теме Безработица в современной России
Титульный Лист Реферата Образец На Английском
Сочинение Рассуждение На Тему Чем Опасны Молчалины
Конкурс Эссе Для Школьников
Учебное пособие: Методические указания по развитию навыков устной речи для студентов Iкурса Института лесного и лесопаркового хозяйства
Доклад по теме Человек и повседневность
Реферат На Тему Основи Криптографії
Реферат: Секты-убийцы. Скачать бесплатно и без регистрации
Курсовая Работа На Тему От Средневековья До Наших Дней
Толстопленочные интегральные микросхемы: общие сведения, резисторы, полупроводники, топология - Коммуникации, связь, цифровые приборы и радиоэлектроника реферат
Внутренняя миграция в России - География и экономическая география курсовая работа
Толковый словарь живого великорусского языка - Иностранные языки и языкознание презентация