Раскрой рулонов

Ниже приведено условие задачи и текстовая часть решения.  Все решение полностью, в архиве rar, вы можете скачать. Некоторые символы могут не отображаться на странице, но в архиве в формате doc все отображается. Еще примеры работ по ЭМММ можно посмотреть  здесь.

СОДЕРЖАНИЕ

 

Введение ………………………………………………………………………….4

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

2. Построение математической модели решения задачи………………………6

2.1. Определение вариантов раскроя рулонов………………………………….6

2.2. Математическая модель оптимизации………………………………..….....8

3. Решение задачи оптимизации в Mathcad………………...………………..…11


ВВЕДЕНИЕ

 

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

Оптимизационные задачи (ОЗ) решаются с помощью оптимизационных моделей (ОМ) методами математического программирования.

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

*  управляемых переменных;

*  неуправляемых переменных;

*  формы функции (вида зависимости между ними).

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

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

 


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

 

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

Исходные данные приведены в таблице 1.

Таблица 1

Номера раскроенных рулонов

1

2

3

Ширина раскроенных рулонов, см.

50

60

90

Задание по количеству раскроенных рулонов

100

120

150

 

Задача должна решаться методом линейного программирования в Mathcad 2000/2001.


2. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ
ЗАДАЧИ

 

2.1. Определение вариантов раскроя рулонов

 

В курсовой работе рассматривается модель оптимального раскроя рулонного материала на рулоны меньшей ширины.

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

1. Сначала рассматривается вариант раскроя, при котором получаются только самые узкие рулоны шириной 50 см.

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

3. Делается попытка повторить предыдущий пункт для рулонов следующего размера (60 см.).

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

5. После перебора всех вариантов, получаемых по пунктам 1-2, исключаются из рассмотрения самые узкие рулоны, и все повторяется заново для рулонов с размерами 60 и 90 см. и т.д.

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

В таблице 2 приводятся все возможные варианты раскроя рулонов.

 

 

Таблица 2

№ варианта раскроя

Количество рулонов заданной ширины, шт.

Отходы,

см.

42 см.

70 см.

84 см.

1

4

0

0

0

2

2

0

1

10

3

2

1

0

40

4

1

2

0

30

5

1

1

1

0

6

0

3

0

20

7

0

0

2

20

 

 

2.2. Математическая модель оптимизации

 

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

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

,

где х1, х2, …, хn – вектор искомых переменных, определяющих количество рулонов, которые раскраиваются по i-му варианту, i = 1, 2, …, n, n = 7;

n – количество всех возможных вариантов раскроя рулонов;

c – вектор, элементами которого является количество отходов при раскрое по i-му варианту, i = 1, 2, …, n.

Целевую функцию можно записать в векторной форме:

 

Кроме целевой функции, необходимо ввести ограничения.

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

Составим их следующим образом.

Для рулонов шириной 50 см. должно быть получено по заданию не меньше чем 100 рулонов. Во втором столбце таблицы 2 указано, сколько рулонов шириной 50 см. получится из одного рулона шириной 2м. (200 см.) по каждому из вариантов раскроя. Так, по первому варианту раскроено х1 исходных рулонов – из одного рулона получается 4 рулона шириной 50 см., в итоге имеем 4х1 таких рулонов, разрезанных первым способом. Общее число рулонов шириной 50 см. равно сумме таких произведений, полученных при раскрое всеми способами. Таким образом, ограничение по количеству рулонов шириной 50 см., определяется следующим неравенством:

                                                          (1)

Следующие два ограничения построим аналогично из условия получения не менее, чем заданное количество рулонов шириной 60 и 90 см. соответственно:

                                                                 (2)

                                                                                (3)

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

                                                                                                          (4)

Выражения (1) – (4) описывают математическую модель решения задачи минимизации отходов.

Вторая часть целевой функции должна минимизировать потери от лишних рулонов.

Для вывода выражения второй части целевой функции вернемся к неравенствам (1) – (3). Если умножить левые части этих неравенств на ширину соответствующих рулонов, то их сумма выражает общую ширину всех разрезанных рулонов. Часть целевой функции, минимизирующая расход материалов, выражается формулой

Целевая функция, минимизирующая общий расход материалов и соответственно минимизирующая потери за счет отходов и лишних рулонов, определяется следующим выражением:

 

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

 

 

 

.                                                                                                          (5)


3. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD

 

Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор х оптимального решения задачи:

х := Minimize (Q, x),

с учетом ограничений, приведенных в системе (5).

Решение приводится в приложении. В результате решения данной задачи линейного программирования получен результат вычислений:

хТ = (0   0   0   0   100   7   25),                                  Q(x) = 26 330.

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

Элементы вектора х – это оптимальное количество рулонов, которые должны быть раскроены i-м способом I = 1, 2, …, n. Решение задачи осуществляется следующим образом. в начале расчета заданы нулевые начальные значения вектора х. В векторе с заданы значения отходов для каждого из способов раскроя. В разделе между ключевым словом Given и функцией Minimize помещены ограничения.

После выражения с функцией Minimize в той же строке приводятся результаты решения задачи. Вектор х содержит оптимальное количество рулонов, раскроенных разными способами, а именно: хТ = (0  0  0  0  100  7  25). Это означает, что пятым способом должны быть раскроены 100 рулонов, шестым – 7 рулонов, седьмым – 25 рулонов. Другие способы раскроя не применяются как неэкономичные. Всего для выполнения заданий по раскрою требуется 132 рулона шириной 2 м. В метрах это значение выражается критерием оптимизации Q (x) = 263,3 м.

В трех нижних строках приложения анализируется количество лишних рулонов путем вычитания фактического количества разрезанных рулонов каждой ширины с заданием. Нулевые разности свидетельствуют, что лишних разрезанных рулонов нет. А разность равная 1 свидетельствует о том, что остается один лишний рулон шириной 60 см.

Следовательно, полученное решение задачи раскроя является оптимальным и обеспечивает минимум потерь материалов. Общие потери материала определяются как произведение векторов: с × х / 100 = 6,4 м.

Скачать решению полностью:


Имя файла: 6.rar
Размер файла: 27.93 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке