線性規(guī)劃模型在腸衣原材料分配中的應(yīng)用

杜向然，李春亞，李　成，李旭嬌

(天津海運(yùn)職業(yè)學(xué)院，天津　300350)

?

線性規(guī)劃模型在腸衣原材料分配中的應(yīng)用

杜向然，李春亞，李成，李旭嬌

(天津海運(yùn)職業(yè)學(xué)院，天津300350)

天然腸衣被廣泛地用于肉制品加工,腸衣企業(yè)都把提升腸衣生產(chǎn)效率和材料利用率作為企業(yè)發(fā)展的核心競(jìng)爭(zhēng)力。利用冒泡思想來(lái)優(yōu)化解決線性規(guī)劃模型的算法，成功地解決天然腸衣的原材料分配問(wèn)題?？梢愿鶕?jù)不同用戶的實(shí)際要求,找到合適的原材料分配方案。

冒泡算法；數(shù)學(xué)建模；線性規(guī)劃；腸衣加工

一、引言

近幾年，國(guó)際市場(chǎng)和國(guó)內(nèi)市場(chǎng)對(duì)于腸衣的需求在不斷地?cái)U(kuò)大，腸衣企業(yè)間的競(jìng)爭(zhēng)也變得更加激烈。傳統(tǒng)的腸衣生產(chǎn)主要靠管理者和工人們的經(jīng)驗(yàn)完成，這種方法的優(yōu)點(diǎn)是速度快，缺點(diǎn)是占用過(guò)多的人力資源、加工速度慢，原材料的利用率低。腸衣企業(yè)為了提升企業(yè)自身的競(jìng)爭(zhēng)力，幾乎所有生產(chǎn)廠家都把提高產(chǎn)品生產(chǎn)率和原材料的利用率作為企業(yè)發(fā)展的核心任務(wù)。當(dāng)腸衣原材料和成品規(guī)格是已知的情況下，如何按照公司的要求合理地設(shè)計(jì)出一套原料搭配方案，使得原材料的利用率最高，節(jié)約材料成本，這正是需要解決的問(wèn)題。

用線性規(guī)劃方法解決腸衣原材料的分配問(wèn)題,并通過(guò)求解最優(yōu)的目標(biāo)函數(shù)找出材料的最佳分配方案。為了更加貼近企業(yè)提高原材料的利用率的需求,也就是使原材料剩余最少,加工后剩余的原材料需要降級(jí)使用,從而達(dá)到充分利用原材料的目的。求解線性規(guī)劃模型時(shí)，一個(gè)新的求解方法被采用，該方法可以對(duì)解空間進(jìn)行全局搜索，并通過(guò)冒泡算法的思想提高了程序的執(zhí)行效率。本文中涉及的實(shí)驗(yàn)是在通過(guò)Java語(yǔ)言在Eclipse和JDK環(huán)境下實(shí)現(xiàn)的，它解決了matlab和Lingo只能在windows系統(tǒng)環(huán)境下解決線性規(guī)劃問(wèn)題的限制，而且操作簡(jiǎn)單。實(shí)驗(yàn)表明該方法可以在保證搜索準(zhǔn)確性的前提下，有效地解決腸衣生產(chǎn)過(guò)程中的原材料分配問(wèn)題。

二、線性規(guī)劃模型求解

線性規(guī)劃模型是運(yùn)籌學(xué)的重要分支，它是輔助人們進(jìn)行科學(xué)管理和規(guī)劃的有效方法之一。線性規(guī)劃研究的問(wèn)題是如何在線性約束條件下使線性目標(biāo)函數(shù)達(dá)到極值。1947年,喬治·丹齊格首次提出用單純形方法來(lái)解決線性規(guī)劃模型以來(lái)，經(jīng)過(guò)60多年的發(fā)展，線性規(guī)劃理論趨向成熟，它已經(jīng)成功地應(yīng)用到社會(huì)、經(jīng)濟(jì)、文化和工業(yè)等領(lǐng)域中。到目前為止，線性規(guī)劃模型已經(jīng)成為科學(xué)與工程領(lǐng)域廣泛應(yīng)用的數(shù)學(xué)模型，特別是在計(jì)算機(jī)能高速處理海量約束條件和設(shè)計(jì)變量的線性規(guī)劃問(wèn)題之后，線性規(guī)劃就更加受到青睞。

(一)線性規(guī)劃模型

線性規(guī)劃問(wèn)題的核心就是在滿足線性約束條件的前提下，使線性目標(biāo)函數(shù)達(dá)到最優(yōu)(最大值或最小值)。線性約束條件可以用一組線性等式或線性不等式表達(dá)，目標(biāo)函數(shù)用于衡量方案的優(yōu)劣。根據(jù)線性規(guī)劃的定義，線性規(guī)劃問(wèn)題即求取自變量x=[x1, x2, … xn]T的值，使得線性目標(biāo)函數(shù)在線性約束條件下達(dá)到最大，線性規(guī)劃問(wèn)題的一般標(biāo)準(zhǔn)型為：

Maxf = c1x1+ c2x2+ … + c3x3

S.T.a11x1+ a12x2+ … +a1nxn<= b1

a21x1+ a22x2+ … +a2nxn<= b2

……

(1)

am1x1+ am2x2+ … +amnxn<= b1

xj>= 0 (j=1,2,…,n)

其中ci、aij、bi(i,j=1,2,…n)為給定的常數(shù)。

目標(biāo)函數(shù)的確定是由自變量和達(dá)到目的之間的函數(shù)關(guān)系決定的，在實(shí)際應(yīng)用中，自變量所受到的限制條件就是它本身的約束條件。當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。

(二)模型求解方法

求解線性規(guī)劃模型的方法包括：?jiǎn)渭冃畏ā⒋驧法、兩段法和圖解法等，求解線性規(guī)劃問(wèn)題的相關(guān)軟件包括matlab和lingo等。這些方法只能得到滿足目標(biāo)函數(shù)的一個(gè)最優(yōu)解，而不能得到滿足目標(biāo)函數(shù)的多個(gè)解。為了解決避免這個(gè)問(wèn)題，本文采用java語(yǔ)言中的for循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)從解空間中找到多個(gè)最優(yōu)解。該方法通過(guò)快速地搜索每個(gè)變量的取值范圍，全局搜索符合目標(biāo)函數(shù)的所有解。圖1描述了for循環(huán)的流程圖。

圖1　for循環(huán)流程圖

如果只用for循環(huán)進(jìn)行全局搜索，整個(gè)過(guò)程會(huì)產(chǎn)生很多重復(fù)搜索的地方，造成求解時(shí)間較長(zhǎng)。為了提高解題的效率，避免不必要的時(shí)間浪費(fèi)和減少程序的時(shí)間復(fù)雜度，冒泡算法被用于對(duì)循環(huán)程序進(jìn)行優(yōu)化，合理地減少程序的搜索空間。

冒泡算法的特點(diǎn)是每次都從未排序的記錄中找出一個(gè)最大值(或最小值)，使這個(gè)值以氣泡方式逐漸往上“漂浮”，直至插入到排好序的記錄中，已排好序的記錄不需要做任何調(diào)整。這個(gè)特點(diǎn)可以被用于減少for循環(huán)的全局搜索范圍。例如，在標(biāo)準(zhǔn)模型(1)中，每個(gè)變量之間是有約束關(guān)系的。例如式子a11x1+a12x2+…+a1nxn=bn，x1的取值范圍是[0,bn/a11],當(dāng)x1取定為某值時(shí)，x2的取值范圍不是[0,bn/a12]，而是[0, (bn/a11-x1)/a12]。相應(yīng)的，x3,x4,…xn的取值范圍也會(huì)發(fā)生相應(yīng)的改變。冒泡算法優(yōu)化循環(huán)語(yǔ)句的搜索范圍可以避免重復(fù)搜索空間，減少求解線性規(guī)劃模型所花費(fèi)的時(shí)間。代碼表示下。

for ( int x1=0; a1x1

for (int x2=0; a2x2

……

for (int xn=0; anxn

if (線性條件)// 同時(shí)滿足的線性約束條件

{

Maxvalue = c1x1+ x2x2+ …… + cn

}

}

……

}

}

三、腸衣原材料分配

所涉及的所有試驗(yàn)都是在一臺(tái)筆記本電腦(Intel(R) Core(TM) i3 CPU M370 2.40GHz，3G內(nèi)存，Windows XP系統(tǒng))上實(shí)現(xiàn)的。具體的實(shí)現(xiàn)過(guò)程是在eclipse環(huán)境下用Java語(yǔ)言編寫(xiě)程序完成。實(shí)驗(yàn)中所使用的數(shù)據(jù)全部都來(lái)自于2011高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題。已知材料中給出了腸衣的成品規(guī)格和原材料描述表,如表1和表2所示。

表1　成品規(guī)格表

表2　原料描述表

腸衣原材料需要按照指定根數(shù)和總長(zhǎng)度組裝出成品,也就是我們常說(shuō)的捆。表1中給出了需要裝出成品的幾種規(guī)格，長(zhǎng)度單位為米。符號(hào)∞在數(shù)學(xué)中表示無(wú)上限，但實(shí)際長(zhǎng)度應(yīng)小于26米。表2顯示的腸衣加工原材料，這是由公司丈量好的。腸衣廠家希望設(shè)計(jì)一個(gè)原料搭配方案，使得裝出的成品捆數(shù)越多越好。這里涉及到求最大值，我們可以根據(jù)線性規(guī)劃模型求解。根據(jù)成品規(guī)格表描述的數(shù)據(jù)，成品被分為3種規(guī)格(3-6.5、7-13.5、14-26.)。0.5米被認(rèn)為是每個(gè)檔次的間隔米數(shù)，xi(i=1,2,3,…46)表示三種規(guī)格中每個(gè)檔次實(shí)際產(chǎn)生的根數(shù)，yi(j=1,2,3)表示每個(gè)檔次的最大捆數(shù)。如果出現(xiàn)成品捆數(shù)相同的方案，最短長(zhǎng)度最長(zhǎng)的方案被認(rèn)為最好。考慮到實(shí)際生產(chǎn)過(guò)程中難免會(huì)出現(xiàn)誤差，每種規(guī)格的總長(zhǎng)度可以有±0.5米的誤差，相應(yīng)的總根數(shù)允許比標(biāo)準(zhǔn)少1根。目標(biāo)函數(shù)是求解最大捆數(shù)，用y=y1+y2+y3表示，根據(jù)已知原材料，式子(2)、(3)、(4)三種規(guī)格的約束條件。

(2)

(3)

(4)

通過(guò)第二部分介紹的方法求解這個(gè)數(shù)學(xué)模型，我們得到了最優(yōu)解的集合。第一種規(guī)格最多裝出的成品捆數(shù)是11，成品的解空間為8(8種方案都可以裝出最大成品捆數(shù))。第二種規(guī)格最多裝出的成品捆數(shù)是22，成品的解空間為3。第三種規(guī)格最多裝出的成品捆數(shù)是42，解空間是31。在同一個(gè)規(guī)格中，對(duì)于成品捆數(shù)相同的方案，最短長(zhǎng)度最長(zhǎng)的方案被認(rèn)為最好。根據(jù)這個(gè)原則，我們從方法集中找出{0 5 3 3 2 2 3 1 }作為第一種規(guī)格的最優(yōu)解，因?yàn)樵谧疃添?xiàng)里x1=0，而其他的x1都大于0。同道理，{0 1 0 1 0 0 0 0 1 1 1 2 0 1}，{0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0}分別是規(guī)格二和規(guī)格三的最優(yōu)解。

為了提高材料的利用率，如果三種規(guī)格對(duì)應(yīng)的原材料有剩余，相應(yīng)的材料就可以降級(jí)使用。例如，對(duì)于長(zhǎng)度為15米的原料可以降級(jí)到規(guī)格二中使用，制造出的成品屬于規(guī)格二。

表3給出了降級(jí)后原料的剩余情況。

表3　降級(jí)后原料描述表

根據(jù)降級(jí)后的原料表和成品規(guī)格表，我們?cè)俅斡蒙鲜龇椒ń⒉⑶蠼鈹?shù)學(xué)模型。三種規(guī)格的最優(yōu)解分別是{7 1 1 1 1 0 2 6}、{0 0 0 1 1 1 1 0 0 0 1 1 0 2}、{0 0 1 0 0 1 0 0 0 0 2 0 1 0 0 0 0 0 0 0}。這時(shí)需要重復(fù)之前的方法，原材料再次被降級(jí)使用直到降到不能再降為止。通過(guò)總共9次(降級(jí))迭代程序最終產(chǎn)生的最多捆數(shù)為：166捆。實(shí)驗(yàn)表明利用線性規(guī)劃模型求解腸衣原材料分配問(wèn)題是有效的，而且通過(guò)冒泡思想優(yōu)化后的算法在運(yùn)行時(shí)間上被大大縮短了，由之前的2931秒減少到1121秒(小于30分鐘)。算法不僅可以滿足用戶的實(shí)際要求，而且有操作性較強(qiáng)、易于理解和實(shí)現(xiàn)等優(yōu)點(diǎn)。

四、總結(jié)

提出了一種腸衣原材料分配方案的數(shù)學(xué)模型，該數(shù)學(xué)模型首先從已給定的成品規(guī)格表入手，列出滿足條件的線性方程，通過(guò)求解線性規(guī)劃模型計(jì)算出每種規(guī)格中捆數(shù)最多的方法集(方法集中的每個(gè)方法都可以在相應(yīng)的規(guī)格中組裝出成品)，然后從每種方法集中，根據(jù)用戶的要求找出各自最好的方法。如果原料還有剩余的話，可是降級(jí)使用，提高產(chǎn)品的利用率。該模型的求解是通過(guò)改進(jìn)后的循環(huán)程序?qū)饪臻g進(jìn)行全局搜索找出最優(yōu)目標(biāo)函數(shù)。為了使我們的模型更加貼近人的使用習(xí)慣，我們假設(shè)每次只取出一種方法作為該規(guī)格的最優(yōu)方法，這樣還保證了模型可以在一定的時(shí)間內(nèi)(30分鐘)產(chǎn)生最優(yōu)方案。

[1]吳育華，杜綱.管理科學(xué)基礎(chǔ)(第三版)[M].天津：天津大學(xué)出版社，2009.

[2]李明.詳解MATLAB在最優(yōu)化計(jì)算中的應(yīng)用[M].北京：電子工業(yè)出版社，2011.

[3]李興華.Java開(kāi)發(fā)實(shí)戰(zhàn)經(jīng)典[M].北京：清華大學(xué)出版社，2009.

[4]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京：清華大學(xué)出版社，2009.

[5]黃雍檢,陶冶,錢(qián)祖平.最優(yōu)化方法——MATLAB應(yīng)用[M].北京：人民郵電出版社,2010.

[6]曹衛(wèi)華,郭正.最優(yōu)化技術(shù)方法及Matlab實(shí)現(xiàn)[M].北京：化學(xué)工業(yè)出版社,2014.

[7]張峰,呂震宙,趙新攀.基于序列Shepard插值的結(jié)構(gòu)可靠性分析[J].機(jī)械工業(yè)學(xué)報(bào),2010，(05).

Application of Liner Programming Model in Casing Raw Material Distribution

DU Xiang-ran, LI Chun-ya, LI Cheng, LI Xu-jiao

(Tianjin Maritime Vocational College, Tianjin, 300350)

natural casings are widely used in the processing of meat products. The enterprises in the casing industry have promoted the production efficiency and material utilization ratio of the casing as the core competitiveness of the enterprise development. Optimizing the algorithm to solve the linear programming model with bubbling algorithm successfully solved the problem of raw material distribution of natural casings. A suitable raw material distribution program can be found according to the actual requirements of different users.

bubbling algorithm; mathematical modeling; linear programming; casing processing

2015-08-15

杜向然(1982-)，男，天津人，天津海運(yùn)職業(yè)學(xué)院信息工程系助教，碩士研究生，主要從事人工智能與機(jī)器博弈，運(yùn)籌學(xué)等專業(yè)的教學(xué)與研究工作。

O221

A

1673-582X(2016)11-0101-05