基于動(dòng)態(tài)規(guī)劃的腸衣搭配模型與軟件設(shè)計(jì)

李 輝

(西南科技大學(xué)制造科學(xué)與工程學(xué)院，四川 綿陽 621010)

1 問題的重述

原料按長(zhǎng)度分檔，通常以0.5 米為一檔，如：3-3.4 米按3 米計(jì)算，3.5 米-3.9 米按3.5 米計(jì)算，其余的依此類推。表1 是幾種常見成品的規(guī)格，長(zhǎng)度單位為米，∞表示沒有上限，但實(shí)際長(zhǎng)度小于26 米。

根據(jù)以上成品和原料描述，設(shè)計(jì)一個(gè)原料搭配方案，工人根據(jù)這個(gè)方案“照方抓藥”進(jìn)行生產(chǎn)。公司對(duì)搭配方案的具體要求見2011 年競(jìng)賽題。

2 問題分析

原問題的本質(zhì)，是對(duì)腸衣原料按成品規(guī)格進(jìn)行組裝的問題。由于所生產(chǎn)的成品有三種規(guī)格，并且三種規(guī)格所對(duì)應(yīng)的最短長(zhǎng)度和最大長(zhǎng)度、根數(shù)等不相同，因此應(yīng)該先把原料表分為三種規(guī)格的原料表。由于要求充分利用原材料，并且剩余的原材料可以降級(jí)使用，因此應(yīng)該考慮從第三種規(guī)格的成品開始組裝，再依次組裝第二種成品、第一種成品。通過上述分析和本文要解決的問題，有以下兩個(gè)問題需要解決：

1）窮舉運(yùn)算量巨大，如何降低問題的規(guī)模。成品的組裝，是從符合成品規(guī)格的原料中，選擇一組合適的原料，滿足根數(shù)、總長(zhǎng)度等要求，即得到一個(gè)成品（捆），比較容易想到窮舉的辦法。但是，以題目中給出的數(shù)據(jù)，計(jì)算機(jī)運(yùn)算量是巨大的，如何保證給定一組原料數(shù)據(jù)時(shí)，可以在30 分鐘以內(nèi)給出搭配方案，是建立數(shù)學(xué)模型要解決的關(guān)鍵問題。

2）如何降級(jí)處理。例如，當(dāng)成品三的長(zhǎng)度為18 米的原料有剩余時(shí)，采用何種方式進(jìn)行分割的問題。

3 問題的假設(shè)

1）以0.5 米為一檔，如：3-3.4 米按3 米計(jì)算，因此每一根都是有誤差的。在組裝的過程中，不考慮累積誤差對(duì)成品總長(zhǎng)度的影響。

2）假設(shè)原料描述表中給出的根數(shù)和長(zhǎng)度數(shù)據(jù)都是準(zhǔn)確的。

4 符號(hào)說明

xij——表示第j 種規(guī)格的原料放到第i 個(gè)成品（捆）的根數(shù)；

cj——表示第j種規(guī)格原料的總根數(shù)；

mj——表示第j種規(guī)格原料的長(zhǎng)度；

yi——第i 捆是否成為一個(gè)成品，0-1 變量，0 表示不能；

n——原料總的規(guī)格種數(shù)；

w——假設(shè)模型可求得的最大捆數(shù)，比理論上計(jì)算的數(shù)據(jù)稍大即可；

v——某種規(guī)格的成品，每捆所包含的根數(shù)。

5 模型建立與求解

問題的實(shí)質(zhì)是根據(jù)題中的原料情況，建立適當(dāng)?shù)臄?shù)學(xué)模型，通過計(jì)算，給出合理的搭配方案，以方便工人“照方抓藥”。根據(jù)對(duì)問題的分析，用0-1 變量yi表示能否組裝成一個(gè)成品。我們可以根據(jù)題目中給出的數(shù)據(jù)，計(jì)算理論的成品數(shù)量。例如，對(duì)于符合成品三規(guī)格的原料，我們可以求得其總長(zhǎng)度為∑mjcj，理論上可以組裝成品的最大捆數(shù)為∑mjcj/89，約為136.62 捆，即最大可組裝136 捆。理論上，只要假設(shè)的值為137，再通過LINGO 軟件求得到的結(jié)果就是最大的成品捆數(shù)。

5.1 建立線性規(guī)劃模型

基于該思路，我們建立如下的數(shù)學(xué)模型：

決策變量：xij，表示第j 種規(guī)格的原料放到第i 個(gè)成品（捆）的根數(shù)；

目標(biāo)函數(shù)為：Max=∑yj

約束條件：

由于三種成品不同規(guī)格，因此需要根據(jù)上述思路建立三個(gè)類似的線性規(guī)劃模型。

在實(shí)際的計(jì)算中我們發(fā)現(xiàn)，基于該模型的LINGO 程序在進(jìn)行成品二和成品三搭配方案的運(yùn)算時(shí)，經(jīng)過長(zhǎng)達(dá)9 個(gè)小時(shí)的計(jì)算仍然未能得出結(jié)果。而在進(jìn)行成品一的計(jì)算時(shí)，LINGO 僅需要1 秒鐘左右的時(shí)間。

5.2 建立動(dòng)態(tài)規(guī)劃模型

在前面的計(jì)算中，我們發(fā)現(xiàn)當(dāng)w——假設(shè)模型可求得的最大捆數(shù)，它的值取得較小時(shí)，LINGO 的運(yùn)算速度很快，比如取w=10 時(shí)，程序運(yùn)算需要1 秒。此時(shí)的最優(yōu)值，并非原料所能組裝成該種規(guī)格的成品的最大捆數(shù)，而是從原料中選取了部分，組成了10 捆。

受此啟發(fā)，如果不斷的運(yùn)行該程序，每次僅從原料中選取一部分，組裝成10 捆，把用掉的原料從總的原料中減去，更新庫存。下一次運(yùn)算時(shí)，從上一次剩余的原料中，再選取一部分組裝成10 捆，依次這樣處理下去……直到所剩原料已經(jīng)不足以組成1 捆（即最優(yōu)值返回0時(shí)）為止，結(jié)束運(yùn)算。

5.3 關(guān)于原料降級(jí)處理的措施

在上述討論中，我們?yōu)榱顺浞掷迷希瑢⑹Ｓ嗟脑献鼋导?jí)處理。拿長(zhǎng)度為14 米的材料為例，如果有剩余，它可以和長(zhǎng)度介于7-13.5 米的進(jìn)行捆扎，成品屬于7-13.5 米的規(guī)格經(jīng)過分析，大概分為以下三種措施：

①直接降至下一級(jí)的最大長(zhǎng)度。如將剩余14 米長(zhǎng)度的原料，割成13.5 米，即從成品三的原料變成成品二的原料，并且是成品二的最大長(zhǎng)度。采用這樣的降級(jí)處理辦法，操作簡(jiǎn)單，程序設(shè)計(jì)中容易實(shí)現(xiàn)，但是對(duì)原料浪費(fèi)比較大。

②對(duì)半分割。觀察三種規(guī)格的成品的原料長(zhǎng)度，可以發(fā)現(xiàn)，上一級(jí)剩余的原料，無論長(zhǎng)度是多少，對(duì)半分割后都能落在下一級(jí)的長(zhǎng)度區(qū)間內(nèi)。采用這樣的降級(jí)處理辦法，操作簡(jiǎn)單，程序設(shè)計(jì)也容易實(shí)現(xiàn)，比第一種辦法更節(jié)約原料。

③按一定的尺寸，將其分割成不相等的兩段或者兩段以上。根據(jù)組裝過程中所缺少某種長(zhǎng)度的原料，將剩余原料切成該種長(zhǎng)度的原料。例如，在對(duì)成品三的組裝中，14 米長(zhǎng)的原料有剩余。在下一階段，對(duì)成品二的組裝中，11 米的原料緊缺，即將14 米的原料切成11+3米，11 米的降到下一級(jí)使用，3 米的降到再下一級(jí)使用。這樣的降級(jí)處理辦法看似比較科學(xué)，但是在動(dòng)態(tài)規(guī)劃過程中，很難得到哪種原料緊缺的數(shù)據(jù)。因此，在實(shí)際操作中比較困難。

5.4 利用EXCEL 和LINGO 開發(fā)腸衣搭配軟件

如果單純依靠LINGO 軟件逐步進(jìn)行求解，每進(jìn)行一次運(yùn)算，都要對(duì)矩陣xij中的數(shù)據(jù)進(jìn)行分析，統(tǒng)計(jì)每一種長(zhǎng)度的原料用掉了多少根，并計(jì)算剩余多少根，更新庫存。接著，修改LINGO 程序中的數(shù)據(jù)，再次進(jìn)行運(yùn)算。在對(duì)成品三的計(jì)算中，xij變量的個(gè)數(shù)達(dá)到10×24 個(gè)，統(tǒng)計(jì)起來很繁瑣，容易出錯(cuò)，并且需要較為專業(yè)的人員才能看懂LINGO 的結(jié)果報(bào)告，不便于公司的應(yīng)用。

為了使操作更加簡(jiǎn)單有效，我們將腸衣原料數(shù)據(jù)輸入到excel 電子表格中，并在LINGO 中使用excel 表格的數(shù)據(jù)，將每次運(yùn)行LINGO程序的結(jié)果返回給excel 電子表格的指定區(qū)域。配合使用VBA 和宏，對(duì)每次運(yùn)算結(jié)果進(jìn)行整理，統(tǒng)計(jì)用掉的原料根數(shù)、更新庫存量，并把搭配方案以“藥方”的形式通過二維表反饋給用戶，用戶界面如圖1 所示。

圖1 系統(tǒng)用戶界面

在圖1 所示的“腸衣搭配系統(tǒng)Beta 版”中，通過編寫VBA 程序，將每次運(yùn)行LINGO 得到的數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，更新原料余量，所有操作都轉(zhuǎn)化為簡(jiǎn)單的鼠標(biāo)操作。下面對(duì)具體的操作做簡(jiǎn)單的說明。

①打開名為“CasingData.xls”的EXCEL 電子表格；

②將原料描述表的數(shù)據(jù)，對(duì)應(yīng)輸入第26 列；

③單擊初始化；

④按彈出對(duì)話框的提示，打開LINGO 程序，求解名為“階段三”的LINGO 程序，如圖2 所示；求解完成后，切換到excel 窗口；

⑤單擊“更新成品三原料余量”，可以看到在EXCEL 窗口的右邊，已經(jīng)有了10 種搭配方案；

⑥單擊“成品三下一步”，按提示切換到LINGO 窗口，再次求解。求解完成后，切換到excel 窗口；注意，雖然這里求解的都是名為“階段三”的LINGO 程序，但EXCEL 傳遞給LINGO 的參數(shù)已經(jīng)改變，因此運(yùn)算結(jié)果是不一樣的。

⑦單擊“更新成品三原料余量”，新的搭配方案已經(jīng)追加到上一步方案的后面；

⑧當(dāng)成品三的原料再也不能組裝成品時(shí)，系統(tǒng)會(huì)提示采取降級(jí)處理。單擊“降級(jí)處理(3-＞2)”，系統(tǒng)提示運(yùn)行“階段二”的LINGO 程序；

⑨同理，直至程序?qū)⒊善芬坏脑洗钆渫瓿?，提示“第一種規(guī)格的成品分配方案運(yùn)算完畢，搭配完成！”時(shí)，表示運(yùn)算已結(jié)束；

⑩單擊“整理結(jié)果”，EXCEL 窗口的右邊，方案已經(jīng)給出，即是給工人的“藥方”，成品一的部分捆數(shù)的搭配表如表1 所示，其它捆的“藥方”形式也如表1 類似。

表1 成品一搭配表

［1］教材編寫組，編.運(yùn)籌學(xué)[M].3 版.北京：清華大學(xué)出版社，2005，6.

［2］謝金星，薛毅.優(yōu)化模型與LINGO/lindo 軟件[M].北京：清華大學(xué)出版社，2007.