Построение модели раскроя материала при помощи линейного программирования
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
°ются от стандартных, раскрой может получаться достаточно далеким от оптимального. Применение компьютера для реализации этих методов ускоряет работу, но не повышает значительно оптимальность получаемого решения.
Оптимизационные методы основаны на применении математических методов, реализованных на ЭВМ. Эти методы делятся на две группы - чисто оптимизационные и эвристические. Большинство из оптимизационных методов используют линейные модели и метод линейного программирования для их решения. Однако реальные задачи раскроя часто имеют нелинейные элементы, которые приводят к тому, что решение получается все-таки не оптимальным. Эвристические методы иногда приводят к очень неплохим результатам, если это укладывается в норматив отходов. Тем не менее, никогда не ясно, а можно ли найти решение еще лучше.
.2 Общие сведения
Опишем общую задачу линейного (одномерного) раскроя материала.
Необходимо из кусков материала длиной d i ( i = 1, 2, …, m ) выкроить заготовки длиной a j ( j = 1, 2, …, n ) в указанном ассортиментном наборе, заданном вектор-столбцом [b jo]. Требуется определить оптимальный план раскроя материала, т.е. получить максимум ассортиментных наборов m с минимальными отходами т.е. найти матрицу [x i j ] ( количество j - х заготовок в i - х кусках).
Рассмотрим в качестве основного критерий максимума ассортиментных наборов при заданном ограничении по минимуму отходов (для всех видов раскроя есть норматив отходов Z). Эта разница в критериях приводит к разнице в методах решения задачи.
На практике, если из кусков материала выкроить заготовки одного вида (одной длины), то критерий максимума ассортиментных наборов совпадает с минимумом отходов и задача решается быстро без компьютера. Если имеется один кусок материала и на нем можно разместить один-два ассортиментных набора, то критерий минимума отходов является определяющим. Наиболее часто встречается другой случай, когда имеется много кусков материала и требуется выкроить много ассортиментных наборов. В этом случае критерий максимума ассортиментных наборов является определяющим.
Пусть ? i - отходы, получаемые от i - го куска материала. Тогда сумма отходов равна
= - (2.1)
Итак, требуется найти матрицу оптимального решения [xijо], максимизирующую линейную форму L при условиях
L = m (2.2)aj x i j d i (2.3)
x i j b jo m (2.4)x i j 0 (2.5) j > 0 , b j o > 0 (2.6) ? i = d i - Z (2.7)
В принципе это задача линейного программирования. Однако большинство реальных задач раскроя имеют нелинейные эффекты, которые резко усложняют задачу.
Например, заготовки после разреза дополнительно обрабатываются. С тем, чтобы при разрезе не допустить брака, между заготовками при раскрое вводятся перемычки (припуски, зазоры и т.п.) между заготовками с определяющим размером p.
Таким образом, сумма длин перемычек q i в кусках материала равна
q i = 0 , если S x i j 1; q i = p (x i j - 1) , если x i j > 1 (2.8)
Кстати размер перемычек достигает несколько процентов и более от размера заготовки и может оказывать весьма существенное влияние на итоги раскроя.
Неравенство (2.3) будет выглядеть следующим образом:
a j x i j + q i d i (2.9)
Неравенство (2.7) будет:
? i = d i - Z (2.10)
Задача (2.2), (2.4) - (2.6), (2.8) -(2.10) является принципиально нелинейной, область изменения переменных невыпукла и представляет собой форму "ежа".
Существенным моментом в рассматриваемом методе решения задачи является следующее.
Первоначально находится максимум ассортиментных наборов заготовок. При этом равенство (2.7) может не соблюдаться, т.е. отходы могут превышать норматив. Для выхода из этой ситуации используется следующий подход. При вводе информации указывается в какой последовательности количество отдельных видов заготовок может превышать пропорцию, указанную вектором [b j o]. В этом случае уже решается задача с использованием неравенства (2.7) для остатков после нахождения максимума ассортиментных наборов. Если и в этом случае (2.7) не удовлетворяется, то полученный максимум ассортиментных наборов заготовок уменьшается на 1 и процесс повторяется до нахождения решения.
3. Практический пример решения задачи о раскрое материала
Имеется некоторый материал в виде стандартных листов, которые надо раскроить для получения не менее 63 штук деталей типа I, не менее 27 штук деталей типа II и не менее 88 штук деталей типа III. Известны лишь пять способов раскроя листа и каждый из них дает результаты, представленные в таблице.
Способы раскроя материала12345Результат1 деталь типа 1, 2 детали типа 2, 10 деталей типа 3.1 (1) 4 (2) 2 (3)6 (1) 1 (2) 1 (3)1 (1) 2 (2) 2 (3)1 (1) 1 (2) 3 (3)
Требуется так провести операцию изготовления деталей методами линейного программирования, что бы общий расход листов оказался минимальным.
Пусть количество листов раскроенных по способу .
Тогда целевая функция имеет вид:
с учетом способов раскроя и ограничением на количество деталей имеем:
,
,
,
, , , , .
Процесс движения по симплексу представим в виде таблицы.
№ (кол-во листов)127999362287993533299932433799315407892865082924760809238609072297090420108090219118091018
Количество деталей
№12799981688822879970708833299977508843379966528854078963409065082964318976080963299586090767289097090465279110809026427951180910632791
Ответ: Оптимальный план раскроя:
холодильных камер - по 1 способу;
холодильных камер- по 3 способу;
холодильная камера- по 4 способу.
При этом получается 63 детали первого типа, 27 второго