矩形木板最優(yōu)切割方案的設(shè)計(jì)與實(shí)現(xiàn)

鄒涵 李濤 朱婷婷

摘要：本文所設(shè)計(jì)的最優(yōu)切割方案使用了回溯法和遞歸算法對(duì)最優(yōu)切割問(wèn)題進(jìn)行劃分，使木板最優(yōu)切割問(wèn)題轉(zhuǎn)化為不同切割方式下木板的最大利用率問(wèn)題，同時(shí)根據(jù)切割要求對(duì)切割方案進(jìn)行優(yōu)化，選擇最優(yōu)方案。

關(guān)鍵詞：木板;最大利用率;優(yōu)化排樣;回溯法;遞歸

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1009-3044（2019）29-0267-02

1概述

把較大的矩形木板切割成若干個(gè)不同規(guī)格大小的小矩形產(chǎn)品，在工業(yè)生產(chǎn)和家居設(shè)計(jì)中有著廣泛的應(yīng)用。在木板切割生產(chǎn)過(guò)程中因?yàn)橐瓿筛鞣N需求的生產(chǎn)任務(wù)而極易造成資源浪費(fèi)，對(duì)木板最優(yōu)切割方案進(jìn)行設(shè)計(jì)，可以在生產(chǎn)前得到利用率最高的方案，結(jié)合生產(chǎn)任務(wù)進(jìn)行調(diào)整，在保證生產(chǎn)任務(wù)完成的前提下，節(jié)約生產(chǎn)成本，減少資源浪費(fèi)，提高經(jīng)濟(jì)收益。

方案設(shè)計(jì)可以利用優(yōu)化排樣的方法，傳統(tǒng)的優(yōu)化排樣都是人工憑借經(jīng)驗(yàn)直接進(jìn)行的，浪費(fèi)時(shí)間并且效果不理想，如今隨著科技的發(fā)展，已經(jīng)可以利用智能優(yōu)化排樣也就是計(jì)算機(jī)輔助優(yōu)化排樣來(lái)達(dá)到目的。

2問(wèn)題分析

要想得到木板最優(yōu)切割方案，需要利用計(jì)算機(jī)輔助處理，設(shè)計(jì)出優(yōu)化排樣算法，搜索出使木板利用率最高的方案作為最優(yōu)方案，本文利用整數(shù)規(guī)劃和回溯法嘗試不同方案進(jìn)行標(biāo)記，進(jìn)而得出使木板利用率最高的切割方案。因?yàn)楫a(chǎn)品分割尺寸與木板尺寸多半相差較大，所以需要依據(jù)木板尺寸及產(chǎn)品切割尺寸，對(duì)切割方案進(jìn)行篩選。木板分割過(guò)程中一款木板所需要分割成的產(chǎn)品的種類也會(huì)有所限制，所以需要考慮產(chǎn)品的多樣性，同時(shí)依照需求進(jìn)行分割設(shè)計(jì)，也就是需要考慮優(yōu)化排樣的約束條件。

所謂回溯法，就是按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)，它采用試錯(cuò)的思想，在前進(jìn)與回撤的過(guò)程中進(jìn)行標(biāo)記，直到所有方案嘗試完為止，由于木板數(shù)量只能為整數(shù)，所以規(guī)劃中的變量限制為整數(shù)。它將問(wèn)題的解空間轉(zhuǎn)化成了圖或樹(shù)的結(jié)構(gòu)表示，然后使用深度優(yōu)先搜索策略進(jìn)行遍歷，遍歷的過(guò)程中記錄和尋找所有可行解得到最優(yōu)解。我們用迭代來(lái)實(shí)現(xiàn)回溯法，提高效率。

在算法設(shè)計(jì)過(guò)程中假設(shè)木板厚度和割縫寬度忽略不計(jì)，假設(shè)分割木板時(shí)均按照橫向分割（沿著木板長(zhǎng)的方向）或縱向分割（沿著木板寬的方向），忽略其他角度的分割方式。即可得出四種切割方式：一是木板橫向切割，產(chǎn)品縱向放置;二是木板縱向切割，產(chǎn)品橫向放置;三是木板橫向切割，產(chǎn)品橫向放置;四是木板縱向切割，產(chǎn)品橫向放置。模擬圖如下圖1表示：

這四種方式任意組合便可引申出其他組合切割方式，但是，對(duì)于不同產(chǎn)品如何組合切割的問(wèn)題，還需要采用一些約束條件來(lái)尋找出最優(yōu)方案。

3算法設(shè)計(jì)

按規(guī)定在木板上，分割出多種不同產(chǎn)品，設(shè)計(jì)優(yōu)化木板分割方法，記木板原材料長(zhǎng)c，寬為K，產(chǎn)品種類為i，產(chǎn)品長(zhǎng)為厶，產(chǎn)品寬為W（默認(rèn)橫向?yàn)殚L(zhǎng)，縱向?yàn)閷挘瑪?shù)量為N，則目標(biāo)函數(shù)為：

4總結(jié)

本文主要研究的是木板在切割成不同矩形產(chǎn)品時(shí)如何使資源得到充分利用，減少資源浪費(fèi)，文章利用回溯法來(lái)輔助優(yōu)化排樣，可以將算法和模型推廣到工廠生產(chǎn)或加工等實(shí)際問(wèn)題中，它們常需要將大矩形板材（如鋼板、玻璃、印刷電路板、包裝紙等）切割成各種形狀的小板材，利用計(jì)算機(jī)輔助處理可以提高工作效率和資源利用率，但本文木板切割時(shí)沒(méi)有考慮到割縫寬度及木板厚度差異，算法模型較為理想化，實(shí)際情況中存在誤差，所以還需要進(jìn)一步研究處理。