Построение модели раскроя материала при помощи линейного программирования

 

Введение


Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:

· количество продукции - расход сырья

· количество продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

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

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

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

. Учет ограничений.

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

Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.

1. Линейное программирование


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

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

С точки зрения математики производственную программу предприятия в первом приближении можно записать как набор чисел в котором обозначает запланированный выпуск изделий i-го типа, n - количество типов изделий.

Если - доход от произведенного изделия i-го типа и каждое произведенное изделие покупается по одной и той же цене, то суммарный доход предприятия является простой суммой


,(1)


что отражает присутствие слова ''линейное'' в названии ''линейное программирование''.

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

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

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


,(2)


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

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

Другим неотъемлемым элементом экономической ситуации, где непосредственно применим подход линейного программирования, являются ограничения, налагаемые на возможные варианты планов производства.

Чаще всего это так называемые ресурсные ограничения, описывающие тот факт что

·для производства товаров приходиться тратить ресурсы;

·количество ресурсов, которое можно затратить на производство товаров, ограничено.

Если считать, что в нашем производстве используются i=1,2,…,m ресурсы (труд, различные виды сырья, энергия и т.д. ), то в модели линейного программирования эти два факта описываются с помощью коэффициентов , которые задают затраты i-го ресурса на производство единицы j-го продукта.

Если затраты ресурсов линейно возрастают в зависимости от роста объемов производства, то для выпуска продукта j в количестве единиц требуется единиц i-го ресурса. Выпуск всего плана потребует при этом



единиц i-го ресурса.

Когда в наличии имеется не более единиц этого ресурса, то ясно, что любой реализуемый план производства x должен удовлетворять ограничению



Учитывая то, то у нас несколько (m) видов ресурсов и допустимый план должен удовлетворять каждому из таких ограничений, получаем систему линейных неравенств


(3)


где - запасы соответствующих ресурсов. Эту систему можно записать компактнее, как



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

Ограничения в задаче линейного программирования могут быть разных типов: для определенных видов ресурсов можно с самого начала потребовать выполнение строгих равенств вида



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


(4)


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

С точки зрения практического экономиста, применение линейного программирования означает, таким образом:

1.определение структуры задачи - что в ней является критерием, какие в ней присутствуют ограничения, какими переменными величинами () мы можем управлять, в чем заключается желаемый экономический эффект;

.сбор необходимой информации - определение, часто путем статистических исследований, анализа рынка, прогнозов и пр., значений коэффициентов задачи: стоимостных коэффициентов , расходных , объемов доступных ресурсов .

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

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

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

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


2. Задача о раскрое материала


2.1 Методы раскроя материала

линейный программирование оптимизация экстремум

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

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

Øпроволоки;

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

Øпроводов;

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

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

üнормативные;

üтехнологические;

üоптимизационные.

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

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

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


.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 второго типа, 91 третьего типа.

Заключение


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


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


1. Амбос Э., Нойбауер А., Освальд Ю. И др. Экономия сырья и материалов. - М.: Металлургия, 1989. - 255 с.

. Бабаев Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. - М.: Машиностроение, 1982. - 168 с.

. Фурин А.И. Производство мягкой мебели. - М.: Высшая школа, 1988. - 267 с.

. Справочник конструктора штампов: Листовая штамповка/ Под общ. Ред. Л.И.Рудмана. - М.: Машиностроение, 1988. - 496 с.

. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. - Новосибирск: Наука, 1971. - 299 с.

. Бронфельд Г.Б., Патокин Д.В. Программа оптимального раскроя ткани на ПЭВМ типа "ИСКРА-1030М". Руководство пользователя. - Н.Новгород: НПЧВП "ВЕХА", 1991. - 5 с.

. Бронфельд Г.Б. Алгоритм решения задачи оптимального распределения плана производства // Труды института. Автоматизация и механизация управления производством, Горький, НИИУавтопром, 1977, вып.2, с. 75-83.


Введение Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например: · количество продукции - расход сырья

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ