Задача о раскрое

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

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

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

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

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

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