Изучение методов оптимизации раскроя, создание компьютерной программы на основе одного из методов

Оглавление

 

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..3

1.      Определение  рациональных способов раскроя  материала . . . . . . . . . . . . . . 4

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

3.     Практическое приложение теории раскроя к решению задач . . . . . . . . .8

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

5.    Программа вычисления оптимального раскроя. . . . . . . . . . . . . . . . . . . .13

6.     Описание  работы программы на контрольном примере . . . . . . . . . . . . 15

Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

Для достижения поставленной цели были решены следующие задачи:

1. Анализ литературы по теме работы
2. Изучение основных понятий
3. Изучение методов оптимизации раскроя стандартных форм
4. Создание программы по оптимизации раскроя
5. Практическое приложение теории к решению текстовых задач

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

 

1. Определение рациональных способов раскроя материала

 

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

 Пусть k — индекс вида заготовки, k = 1, ..., q; i — индекс способа раскроя единицы материала, i = 1,..., р; a_ik — количество (целое число) заготовок вида к, полученных при раскрое единицы материала i-м способом.

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

Способ раскроя v называется рациональным (оптимальным по Парето), если для любого другого способа раскроя i из соотношений a_ik>a_vk,k = 1, ..., q, следуют соотношения a_ik = a_vk , k = 1, ..., q.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Определение интенсивности использования рациональных способов раскроя

 

Обозначения:

j —индекс материала, j = 1, …, n;

k — индекс вида заготовки, k = 1, ..., q;

i — индекс способа раскроя единицы материала, i = 1, ..., р;

a_jik  — количество (целое число) заготовок вида k, полученных при раскрое единицы j-го материала i-м способом;

b_k— число заготовок вида k в комплекте, поставляемом заказчику;

d_j — количество материала j-го вида;

x_ji — количество единиц j-го материала, раскраиваемых по i-му способу (интенсивность использования способа раскроя);

c_ji— величина отхода, полученного при раскрое единицы j-го

материала по i-му способу;

у — число комплектов заготовок различного вида, поставляемых заказчику.

Рассмотрим следующие  модели оптимизации раскроя стандартных  форм:

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

 

                                    (1)          

 

    (2)

                  (3)

 

Здесь (1) — целевая функция (минимум количества используемых материалов);

(2) — система ограничений,  определяющих количество заготовок,  необходимое для выполнения заказа;

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

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

2. Модель В раскроя с минимальными отходами:

 

                               (4)

    (5)

           (6)

 

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

(5) — система ограничений,  определяющих количество заготовок,  необходимое для выполнения заказа;

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

3. Модель С раскроя с учетом комплектации:

 

                                               (7)

                        (8)

          (9)

    (10)

 

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

(8)    —  ограничения  по количеству материалов;

(9)  — система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Практическое приложение теории раскроя к решению задач

 

Пример 1. Способы раскроя металлического стержня.

Определить все рациональные способы раскроя металлического стержня длиной 100 см на заготовки трех типов: длиной 20, 30 и 50 см. Указать величину отходов для каждого способа.

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

 

Способ раскроя	Количество заготовок  длиной			Величина отходов, см
		50 см	30 см .		20 см
1	2	0	0	0
2	1	1	1	0
3	1	0	2	10
4	0	3	0	10
5	0	2	2	0
6	0	1	3	10
7	0	0	5	0

Табл. 1

 

Пример 2. Способы раскроя куска кожи.

Определите все рациональные способы раскроя прямоугольного куска кожи размером 100 х 60 см на квадратные заготовки со сторонами 50,40 и 20 см и укажите величину отходов для каждого способа.

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

 

 

Способ раскроя	Количество заготовок  со стороной			Величина отходов, см
		50 см	40 см		20 см
1	2	0	0	1000
2	1	1	2	1100
3	1	0	6	1100
4	0	2	7	0
5	0	1	11	0
6	0	0	15	0

Табл. 2

 

Пример 3. Изготовление парников из металлических стержней.

При изготовлении парников используется материал в виде металлических стержней длиной 220 см. Этот материал разрезается на стержни длиной 120, 100 и 70 см. Для выполнения заказа требуется изготовить 80 стержней длиной 120 см, 120 стержней длиной 100 см и 302 стержня длиной 70 см.

Вопросы:

1.  Сколько существует  рациональных способов раскроя?

2.  Какое минимальное  количество материала следует  разрезать, чтобы выполнить заказ?

3.  Сколько способов  раскроя следует использовать  при выполнении заказа?

Решение. Определяем все рациональные способы раскроя материала на заготовки. Таких способов оказывается пять:

 

 

 

 

 

 

Способ раскроя	Количество заготовок  длиной			Величина отходов, см
		120 см	100 см		70 см
1	1	1	0	0
2	1	0	1	30
3	0	2	0	20
4	0	1	1	50
5	0	0	3	10

Табл. 3

 

Используем модель А для одного вида материала. Тогда x_i — количество единиц материала, раскраиваемых по i-му способу.

Для ответа на второй и третий вопросы задачи получаем следующую   модель линейного программирования с критерием «минимум общего количества используемого материала»:

 

	X1	X2	X3	Х4	Х5
Minimize	1	1	1	1	1
Заготовка 120 см	1	1	0	0	0	>=	80
Заготовка 100 см	1	0	2	1	0	>=	120
Заготовка 70 см	0	1	0	1	3	>=	102