Решение задачи оптимального раскроя материала реферат

Обновлено: 30.06.2024

Курсовая работа состоит из введения, одной главы и заключения. В первой главе рассматриваются методы решения задач о раскрое.
Основной задачей моей курсовой работы является рассмотрение моделей задач о раскрое, а также решение их симплекс-методом и на компьютере при помощи Microsoft Excel.
Цель моей курсовой работы является поставить и решить задачу о раскрое.

Содержание

Работа содержит 1 файл

Курсач по ЗММиМ.doc

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

Кафедра: “Экономика управления в отраслях”

Гомель 2004

Глава 1 Теоретические основы решения задач о раскрое. 5

1.1 Сущность экономико-математических методов. 5-7

1.3 Характеристика симплекс-метода. 11-13

Глава 2 Решение задач о раскрое на Гомельском заводе пусковых

2.1 Краткое описание предприятия. 14-15

2.2 Краткое описание технического процесса. 16

2.3 Постановка и решение задачи. 17-26

2.4 Экономический эффект от полученного варианта раскроя. 27

Список использованной литературы. 29

Тема данной курсовой работы – Экономико-математические модели задач о раскрое.

В связи с высокой стоимостью ресурсов и снижением платёжеспособности предприятий республики Беларусь всё большую актуальность приобретает их экономия. Один из её главных путей – снижение материалоёмкости промышленной продукции. В промышленном производстве часто приходится раскраивать различные материалы на заготовки. Материалы могут быть в виде прутков, труб, листов. Так как раскрой листовых материалов выполняется на каждом машиностроительном предприятии в больших объёмах, необходимо рациональное его проведение. Изучение раскроев, выполняемых на многих машиностроительных предприятиях, показывает, что в настоящее время планы раскроя металлопроката выполняются вручную. Гораздо эффективнее в этом процессе экономико-математические методы, составление моделей, решаемых с применением электронно-вычислительных машин. Коэффициент использования материалов вырастает до 90 – 100% и, соответственно, уменьшаются отходы, которые при ручном раскрое составляют 20 – 40%.

Курсовая работа состоит из введения, одной главы и заключения. В первой главе рассматриваются методы решения задач о раскрое.

Основной задачей моей курсовой работы является рассмотрение моделей задач о раскрое, а также решение их симплекс-методом и на компьютере при помощи Microsoft Excel.

Цель моей курсовой работы является поставить и решить задачу о раскрое.

Глава 1. Теоретические основы решения задач о раскрое.

Сущность экономико-математических методов.

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

Особенностью решения задач планирования является необходимость учёта при их решении множества переменных величин, характеризующих постоянно изменяющиеся производственные условия. А так как число сочетаний этих величин в течение определённого времени – планового периода – может быть достаточно большим, то возможно существование значительного числа вариантов плановых решений. Отсюда большая размерность решаемых плановых задач. И, тем не менее, необходимо получить оптимальное, или близкое к нему решение. В этих условиях простой перебор и сравнение всех возможных вариантов решения конкретной плановой задачи нереальны из-за большой трудоёмкости вычислений. Поэтому требуются специальные методы, позволяющие в приемлемые сроки с достаточной степенью обоснованности с учётом особенностей конкретного производства выйти на искомое решение.

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

Методы классической математики включают математический анализ и теорию вероятностей.

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

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

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

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

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

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

Методы динамического программирования могут применяться для решения таких оптимизационных задач, в которых необходимо рассматривать процесс производства или управления в пространстве или во времени, т. е. в развитии. При этом процедура вычислений реализуется по своеобразной схеме: весь процесс поиска оптимального решения представляется в виде определённой последовательности шагов, для каждого из которых находится оптимальное решение, причём оптимальность определяется влиянием на последующие шаги. В основу использования методов динамического программирования положен принцип оптимальности Р. Беллмана.

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

методам близко подходят эвристические, основанные на опыте, интуиции исполнителя. Комбинаторные методы могут давать и точные и приближённые решения.

1.2 Методы решения задач о раскрое.

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

В настоящее время у нас в стране и за рубежом известен ряд работ по раскрою, в которых обычно используется метод индексов Л.В. Канторовича и симплекс-метод Д. Данцига или его модификации. Этими методами пользуются, чтобы найти оптимальный план раскроя, когда известны все возможные его варианты. Следует отметить, что работа по составлению всех раскроев (особенно когда число различных заготовок и исходного проката велико) трудоёмка и продолжительна – в итоге получается линейная задача с большим числом неизвестных, решение которой возможно только с использованием ЭВМ.

Задача о раскрое формулируется следующим образом.

Необходимо из листа проката размером MxN выкроить заготовки площадью mxn в заданном количестве p_i (i=1,2,…,k). Требуется определить оптимальный план раскроя листа, т.е. получить минимальные отходы с учётом комплектности заготовок. Показателем, определяющим экономичность раскроя, является коэффициент раскроя, рассчитываемый по формуле:

m_i - длина i-й заготовки, мм.;

n_i – ширина i-й заготовки, мм.;

M,N – соответственно длина и ширина исходного листа.

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

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

Варианты раскроя образуются путём комбинирования различных заготовок во всех возможных сочетаниях. При таком комбинировании даже при незначительном увеличении числа видов заготовок характерен быстрый рост числа возможных сочетаний, т.е. возможных вариантов раскроя. С увеличением числа вариантов раскроя сильно увеличивается размерность задачи линейного программирования, что приводит к резкому возрастанию общего времени решения задачи на ЭВМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

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

.(3)

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

Для решения поставленной задачи рассмотрим функцию

(4)

где через X_i обозначено множество неотрицательных векторов х, отвечающих раскроям, в которых общая длина заготовок не превосходит длины l. Пустьl₀ = min l_i , где i =1…m.

Тогда при всех lÎ[0,l₀ ] соответствующие множества X_l состоят из одного нулевого элемента и, следовательно, f(l) = 0 для всех таких l. Для lÎ[0,L₀ ], справедливы следующие рекуррентные соотношения:

,(5)

где через I_l обозначено множество тех i, при которых l_i £l.

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

Первый этап

На первом этапе осуществляется так называемый прямой ход: по формулам (5) для всех l = последовательно вычисляются функции f(l) и при этом фиксируются индексы i(l), при которых достигается максимум в выражении (5). Получаемая при этом информация l, f(l) и i(l) запоминается и построчно записывается в таблицу:

l	l₀	l₀ + 1	l₀ + 2	…	L
f(l)	f(l₀ )	f(l₀ + 1)	f(l₀ + 2)	…	f(L)
i(l)	i(l₀ )	i(l₀ + 1)	i(l₀ + 2)	…	i(L)

Второй этап

На втором этапе осуществляется так называемый обратный ход: для получения искомого вектора х (1), для которого выполняется равенство m(x) = f(L), в раскрой в первую очередь включаются заготовка с номером i(l₁ ), где l₁ = L, и подсчитывается значение l₂ = l₁ -l_i ₍ _l ₁₎ .

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

Работа состоит из 1 файл

доклад раскрой материала.docx

Федеральное государственное автономное образовательное учреждение высшего профессионального образования

«Уральский федеральный университет

Преподаватель: Алферьева Т.И.

Cтудентка группы ВИ-490401 Фролова Е.Д.

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

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

Одним из вариантов такой задачи является задача оптимального линейного раскроя материалов. Это касается раскроя:

- труб, швеллера, уголков и т.п.;

- рулонов материалов на продольные и поперечные полосы и других видов изделий.

Существующие методы раскроя материалов можно разделить на 3 группы:

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

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

Оптимизационные методы основаны на применении математических методов, реализованных на ЭВМ. Эти методы делятся на две группы - чисто оптимизационные и эвристические. Большинство из оптимизационных методов используют линейные модели и метод линейного программирования для их решения. Однако реальные задачи раскроя часто имеют нелинейные элементы, которые приводят к тому, что решение получается все-таки не оптимальным. Эвристические методы иногда приводят к очень неплохим результатам, если это укладывается в норматив отходов. Тем не менее, никогда не ясно, можно ли найти решение еще лучше.

Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы ( по длине, площади, объему, массе или стоимости) сводятся к минимуму.

На раскрой (распил, обработку) поступает материал нескольких видов в определенном количестве. Из этого материала необходимо изготовить различные изделия. Материал может быть раскроен разными способами. Каждый способ имеет свою себестоимость и позволяет получить разное количество изделий каждого вида. Необходимо определить способ раскроя, при котором суммарная себестоимость минимальна.

Пусть n - число различных видов материала, поступающего на раскрой;

d_j - количество материала j-го вида, j=1,2…n ,

m - число различных видов изделий, которые надо изготовить;

b_i - число изделий i-го вида, i=1,2…m;

l -число различных способов раскроя;

a_ijk - число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя, (k=1,2…l);

x_jk - количество единиц материала j-го вида, раскраиваемых k-м способом.

Модель А раскроя с минимальным расходом материалов:

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

(3) - условия неотрицательности переменных.

Специфическими для данной области приложения модели линейного программирования являются ограничения (2).

Модель В раскроя с минимальными отходами:
(4)

Здесь (4) - целевая функция (минимум отходов при раскрое материалов);
(6) - условия неотрицательности переменных.

Модель С раскроя с учетом комплектации:
→ max (7)

Здесь (7) - целевая функция (максимум комплектов, включающих заготовки различных видов); (8) - ограничения по количеству материалов;
(9) - система ограничений, определяющих количество заготовок,
необходимое для формирования комплектов; (10) - условия неотрицательности переменных.

Специфическими для данной области приложения модели линейного программирования являются ограничения (9).

Имеется некоторый материал в виде стандартных листов, которые надо раскроить для получения не менее 63 штук деталей типа I, не менее 27 штук деталей типа II и не менее 88 штук деталей типа III. Известны лишь пять способов раскроя листа и каждый из них дает результаты, представленные в таблице.