天然腸衣搭配問(wèn)題的優(yōu)化模型研究

夏 英

（海南工商職業(yè)學(xué)院基礎(chǔ)課部，海南?？?570203）

天然腸衣搭配問(wèn)題的優(yōu)化模型研究

夏 英

（海南工商職業(yè)學(xué)院基礎(chǔ)課部，海南海口 570203）

以2011年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題為背景，針對(duì)天然腸衣搭配問(wèn)題建立了雙目標(biāo)規(guī)劃模型及整數(shù)規(guī)劃模型，采用了“三步走”方法對(duì)模型進(jìn)行簡(jiǎn)化，為制定出“照方抓藥”的搭配方案提供了重要思路。

天然腸衣;雙目標(biāo)規(guī)劃;整數(shù)規(guī)劃;分組搭配

一 問(wèn)題的提出

考慮如下天然腸衣搭配問(wèn)題。天然腸衣的原料按長(zhǎng)度分檔，通常以0.5米為一檔，如:3－3.4米按3米計(jì)算，3.5米 －3.9米按3.5米計(jì)算，其余依此類(lèi)推。為提高生產(chǎn)效率，公司計(jì)劃改變組裝工藝，先丈量所有原料，建立一個(gè)原料表，數(shù)據(jù)來(lái)源2011年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題附表［1］。根據(jù)以上成品和原料描述，設(shè)計(jì)一個(gè)原料搭配方案，工人根據(jù)這個(gè)方案“照方抓藥”進(jìn)行生產(chǎn)。公司對(duì)搭配方案有以下具體要求:

（一）對(duì)于給定的一批原料，裝出的成品捆數(shù)越多越好;

（二）為提高原料使用率，總長(zhǎng)度允許有±0.5米的誤差，總根數(shù)允許比標(biāo)準(zhǔn)少1根;

（三）某種規(guī)格對(duì)應(yīng)原料如果出現(xiàn)剩余，可以降級(jí)使用。如長(zhǎng)度為14米的原料可以和長(zhǎng)度介于7－13.5米的進(jìn)行捆扎，成品屬于7－13.5米的規(guī)格。建立上述問(wèn)題的數(shù)學(xué)模型，給出求解方法。

二 問(wèn)題的分析

首次按將46種原材料進(jìn)行依次編號(hào)，每種原材料的長(zhǎng)度按要求規(guī)范化，并將三種成品的原材料進(jìn)行了分組（見(jiàn)表1、2、3）。在已知成品標(biāo)準(zhǔn)和原料規(guī)格的情況下［2，3］，制定出符合多種要求的搭配方案，故其實(shí)質(zhì)是一個(gè)優(yōu)化問(wèn)題。本文建立了雙目標(biāo)規(guī)劃模型及整數(shù)規(guī)劃模型［4］，采用了“三步走”方法對(duì)模型進(jìn)行分解，為制定出“照方抓藥”的搭配方案提供了重要思路。

表1 產(chǎn)品一原料描述表

表2 產(chǎn)品二原料描述表

表3 規(guī)格要求產(chǎn)品三原料描述表

三 基本假設(shè)

（一）假設(shè)原材料1—8號(hào)生產(chǎn)成品一，9—22號(hào)生產(chǎn)成品二，23—46號(hào)生產(chǎn)成品三;

（二）假設(shè)在計(jì)算成品時(shí)允許總長(zhǎng)度有0.5米的誤差;

（三）假設(shè)允許計(jì)算成品時(shí)總根數(shù)比標(biāo)準(zhǔn)少一根;

（四）假設(shè)某種規(guī)格對(duì)應(yīng)原料如果出現(xiàn)剩余，可以降級(jí)使用。降級(jí)使用時(shí)為避免余料浪費(fèi)過(guò)多，將余料統(tǒng)一降級(jí)到下一個(gè)等級(jí)中的最大檔使用。

四 雙目標(biāo)規(guī)劃的模型建立與求解探討

（一）雙目標(biāo)規(guī)劃模型的建立

1.雙目標(biāo)規(guī)劃模型的目標(biāo)函數(shù)和約束條件的分析

（1）先考慮目標(biāo)函數(shù)

用Z表示三種成品i的總捆數(shù)，Zi表示成品i的捆數(shù)，為使給定的原材料最大程度得到利用，組裝出的成品捆數(shù)越多越好，即要實(shí)現(xiàn)目標(biāo)一:

另一方面，用F表示三種成品i的總誤差和，δi表示Zi捆成品i的誤差和，要求余料越少越好，最大程度減少原料浪費(fèi)，即要實(shí)現(xiàn)目標(biāo)二:

（2）約束條件分析

其中:

aij表示制作成品i所需要的第j種原材料1根的長(zhǎng)度;當(dāng) i=1時(shí)，k1=1，k2=8;當(dāng)i=2時(shí)，k1=9，k2=22;當(dāng) i=3 時(shí)，k1=23，k2=46。

②為提高原材料使用率，每捆要求總長(zhǎng)度允許有±5米的誤差，從而Zi捆成品i的誤差和δi的絕對(duì)值應(yīng)該小于每捆誤差要求0.5米的捆數(shù)Zi倍。那么:

③采用第j種原材料制作第i種成品的根數(shù)xij應(yīng)該不多于第i種原材料的總根數(shù)bj，那么:

⑤整數(shù)非負(fù)限制

顯然需要 xij≥0（i=1，2，3;j=1，2，…，46）并且取整數(shù)。

2.雙目標(biāo)規(guī)劃模型的建立

由此可得到一個(gè)雙目標(biāo)優(yōu)化模型:

其中:

當(dāng) i=1 時(shí)，k1=1，k2=8;當(dāng)i=2 時(shí)，k1=9，k2=22;當(dāng) i=3 時(shí)，k1=23，k2=46.

3.雙目標(biāo)規(guī)劃模型的求解探討

其中:

當(dāng) i=1 時(shí)，k1=1，k2=8;當(dāng)i=2 時(shí)，k1=9，k2=22;當(dāng) i=3 時(shí)，k1=23，k2=46.

鑒于上述模型用數(shù)學(xué)軟件Matlab編程的難度比較大，實(shí)際操作難以實(shí)現(xiàn)。于是進(jìn)一步改進(jìn)思路，采用“三步走”方法實(shí)現(xiàn)模型簡(jiǎn)化。

3 ）可以具體轉(zhuǎn)化為。于是，由模型（2）可以得到生產(chǎn)一捆成品三的單目標(biāo)規(guī)劃模型:

借助于數(shù)學(xué)軟件Matlab，對(duì)上述模型（3）進(jìn)行編程可以得到成品三搭配成一捆的搭配方案。同樣，可以取i=1，2，求出成品一、二搭配成一捆的搭配方案。

第二步:先對(duì)成品三按照搭配一組的最優(yōu)成捆方案進(jìn)行“照方抓藥”，直到有某種原材料短缺，無(wú)法再組裝搭配下一捆為止。再將成品三的余料匯總，全部作降級(jí)處理，為避免浪費(fèi)太大，全部降級(jí)到成品二的原材料中的最長(zhǎng)檔使用。按照這種思路接著搭配處理成品二、成品一。

第三步:最后將三種“照方抓藥”成品i的捆數(shù)Zi求和，就得到了三種成品的總捆數(shù)Z。

（二）整數(shù)規(guī)劃模型的建立與求解探討

1.整數(shù)規(guī)劃模型的目標(biāo)函數(shù)和約束條件的分析

（1）先考慮目標(biāo)函數(shù)

（2）再考慮約束條件

①由于天然腸衣每一種規(guī)格成品的長(zhǎng)度是89米，那么對(duì)于捆數(shù)為Zi的第i種成品的總長(zhǎng)度為89Zi，這正好就是制作的成品i采用原料j的長(zhǎng)度與采用次數(shù)的乘積。而每捆要求總長(zhǎng)度允許有±5米的誤差，故1捆成品i的長(zhǎng)度應(yīng)該介于88.5～89.5米之間。那么Zi捆成品i總長(zhǎng)度的范圍為:

其中:

aij表示制作成品i所需要的第j種原材料1根的長(zhǎng)度;

當(dāng) i=1 時(shí)，k1=1，k2=8;當(dāng)i=2 時(shí)，k1=9，k2=22;當(dāng) i=3 時(shí)，k1=23，k2=46.

②采用第j種原材料制作第i種成品的根數(shù)xij應(yīng)該不多于第種原材料的總根數(shù)bj，并且根數(shù)xij應(yīng)該是非負(fù)數(shù)整數(shù)，那么:

x ij≤ bj（i=1，2，3;j=1，2，…，46），xij≥ 0且取整數(shù)

注:當(dāng) i=1時(shí)，k1=1，k2=8;當(dāng)i=2時(shí)，k1=9，k2=22;當(dāng) i=3 時(shí)，k1=23，k2=46。

④成品i所取原料的總根數(shù)ni除以每種成品要求成捆的根數(shù)mi后取整就是成品i的捆數(shù)Zi（Zi為非負(fù)的整數(shù)）。而題中允許每捆成品i成捆時(shí)可以少一根，那么:

且取整數(shù)

2.整數(shù)規(guī)劃模型的建立

由此可得到一個(gè)整數(shù)規(guī)劃模型［6］:

其中:

當(dāng) i=1 時(shí)，k1=1，k2=8;當(dāng)i=2 時(shí)，k1=9，k2=22;當(dāng) i=3 時(shí)，k1=23，k2=46。

3.整數(shù)規(guī)劃模型的求解探討

由于上述模型綜合考慮了三種規(guī)格的成品以及約束條件，對(duì)于求解比較復(fù)雜，為了簡(jiǎn)便起見(jiàn)，對(duì)三種規(guī)格的成品分組進(jìn)行求解。在目標(biāo)函數(shù)中要求成品捆數(shù)越多越好，這里可以理解為:每種規(guī)格的成品捆數(shù)都達(dá)到最大時(shí)，總捆數(shù)Z也達(dá)到最大。運(yùn)用這個(gè)想法，對(duì)于三種規(guī)格的成品分別建立相應(yīng)的整數(shù)規(guī)劃模型。

同理可以分別針對(duì)成品二、成品一構(gòu)建類(lèi)似的整數(shù)規(guī)劃模型，運(yùn)用Matlab軟件可以求得三種成品的成捆的各自最大捆數(shù)Zi。當(dāng)三種成品的捆數(shù)Zi均達(dá)到最大值，那么對(duì)于給定的這批原料，裝出成品的總捆數(shù)Z就最大。

五 模型的評(píng)價(jià)與改進(jìn)

（一）模型的優(yōu)點(diǎn)

1.模型針對(duì)天然腸衣搭配問(wèn)題構(gòu)建了兩個(gè)優(yōu)化模型，全面地考慮題目中的各種要求;

2.模型結(jié)構(gòu)清晰、層次分明、數(shù)學(xué)表達(dá)式含義直觀、易懂;

3.巧妙將模型一由原來(lái)雙目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題，并針對(duì)該模型提出“三步走”策略，將模型一的編程求解難度大大降低。同時(shí)巧妙地將模型二按照生產(chǎn)產(chǎn)品的種類(lèi)分解開(kāi)，將模型二的編程求解難度大大降低;

4.此模型可推廣應(yīng)用于材料切割、材料的優(yōu)化搭配選取、制定批量生產(chǎn)與存儲(chǔ)問(wèn)題、企業(yè)的各項(xiàng)管理活動(dòng)等方面。

（二）模型的缺點(diǎn)

1.在成品原料分組的情況下分析解決問(wèn)題，使得某些長(zhǎng)的原料因?yàn)闊o(wú)法與該組的其他原料有效組合，導(dǎo)致在該輪組裝中被迫降級(jí)使用，造成不必要浪費(fèi);

2.兩個(gè)模型的算法思路很好，但是算法實(shí)現(xiàn)耗時(shí)太長(zhǎng)，對(duì)于30分鐘內(nèi)產(chǎn)生最優(yōu)搭配方案有一定難度。

（三）模型的改進(jìn)

模型在此基礎(chǔ)上考慮結(jié)合其他優(yōu)化方法和決策控制知識(shí)作進(jìn)一步改進(jìn)。

［1］2011 高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)［EB/OL］.http://www.mcm.edu.cn/html_cn/node/a1ffc4c5587c8a6f96eacefb8dbcc34e.html.

［2］朱錦林.天然腸衣加工指南［M］.北京:中國(guó)計(jì)量出版社，2009.

［3］劉德明.腸衣的生產(chǎn)與加工［J］.甘肅畜牧獸醫(yī)，1985（2）.

［4］姜啟源.數(shù)學(xué)模型（第二版）［M］.北京:高等教育出版社，1993.

［5］朱道元.數(shù)學(xué)建模精品案例［M］.南京:東南大學(xué)出版社，1999.

［6］教材編寫(xiě)組.運(yùn)籌學(xué)（第三版）［M］.北京:清華大學(xué)出版社，2005.

Study on the Optimal Models of the Tie－in Problem of Natural Casing

XIA Ying
（Department of Basic Courses，Hainan Technology and Business College，Haikou 570203，China）

The article is based on the 2011 Mathematical Contest in Modeling D（MCM）of China.It sets up a dual－ goal programming model and integer programming model for the natural casing tie－in problem，and uses the"three－step"method to simplify the models，providing referential ideas for working out a"fill a prescription as"match scheme.

Natural casing;Dual－goal programming;Integer pro;Block matching

O 224

A

1009－9743（2012）01－0149－05

2011－12－15

夏英（1975－），女，漢族，湖南岳陽(yáng)人。碩士。海南工商職業(yè)學(xué)院基礎(chǔ)課部講師。主要研究方向:運(yùn)籌學(xué)。

（責(zé)任編輯:張玉秀）