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

(天津海運職業(yè)學院，天津　300350)

?

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

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

(天津海運職業(yè)學院，天津300350)

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

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

一、引言

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

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

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

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

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

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

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ù)。

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

(二)模型求解方法

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

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

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

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

for ( int x1=0; a1x1

for (int x2=0; a2x2

……

for (int xn=0; anxn

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

{

Maxvalue = c1x1+ x2x2+ …… + cn

}

}

……

}

}

三、腸衣原材料分配

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

表1　成品規(guī)格表

表2　原料描述表

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

(2)

(3)

(4)

通過第二部分介紹的方法求解這個數(shù)學模型，我們得到了最優(yōu)解的集合。第一種規(guī)格最多裝出的成品捆數(shù)是11，成品的解空間為8(8種方案都可以裝出最大成品捆數(shù))。第二種規(guī)格最多裝出的成品捆數(shù)是22，成品的解空間為3。第三種規(guī)格最多裝出的成品捆數(shù)是42，解空間是31。在同一個規(guī)格中，對于成品捆數(shù)相同的方案，最短長度最長的方案被認為最好。根據(jù)這個原則，我們從方法集中找出{0 5 3 3 2 2 3 1 }作為第一種規(guī)格的最優(yōu)解，因為在最短項里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ī)格對應(yīng)的原材料有剩余，相應(yīng)的材料就可以降級使用。例如，對于長度為15米的原料可以降級到規(guī)格二中使用，制造出的成品屬于規(guī)格二。

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

表3　降級后原料描述表

根據(jù)降級后的原料表和成品規(guī)格表，我們再次用上述方法建立并求解數(shù)學模型。三種規(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}。這時需要重復之前的方法，原材料再次被降級使用直到降到不能再降為止。通過總共9次(降級)迭代程序最終產(chǎn)生的最多捆數(shù)為：166捆。實驗表明利用線性規(guī)劃模型求解腸衣原材料分配問題是有效的，而且通過冒泡思想優(yōu)化后的算法在運行時間上被大大縮短了，由之前的2931秒減少到1121秒(小于30分鐘)。算法不僅可以滿足用戶的實際要求，而且有操作性較強、易于理解和實現(xiàn)等優(yōu)點。

四、總結(jié)

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

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

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

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

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

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

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

[7]張峰,呂震宙,趙新攀.基于序列Shepard插值的結(jié)構(gòu)可靠性分析[J].機械工業(yè)學報,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è)學院信息工程系助教，碩士研究生，主要從事人工智能與機器博弈，運籌學等專業(yè)的教學與研究工作。

O221

A

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