線性規劃模型在腸衣原材料分配中的應用

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

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

?

線性規劃模型在腸衣原材料分配中的應用

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

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

天然腸衣被廣泛地用于肉制品加工,腸衣企業都把提升腸衣生產效率和材料利用率作為企業發展的核心競爭力。利用冒泡思想來優化解決線性規劃模型的算法，成功地解決天然腸衣的原材料分配問題?？梢愿鶕煌脩舻膶嶋H要求,找到合適的原材料分配方案。

冒泡算法；數學建模；線性規劃；腸衣加工

一、引言

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

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

二、線性規劃模型求解

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

(一)線性規劃模型

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

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)為給定的常數。

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

(二)模型求解方法

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

圖1　for循環流程圖

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

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

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內存，Windows XP系統)上實現的。具體的實現過程是在eclipse環境下用Java語言編寫程序完成。實驗中所使用的數據全部都來自于2011高教社杯全國大學生數學建模競賽D題。已知材料中給出了腸衣的成品規格和原材料描述表,如表1和表2所示。

表1　成品規格表

表2　原料描述表

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

(2)

(3)

(4)

通過第二部分介紹的方法求解這個數學模型，我們得到了最優解的集合。第一種規格最多裝出的成品捆數是11，成品的解空間為8(8種方案都可以裝出最大成品捆數)。第二種規格最多裝出的成品捆數是22，成品的解空間為3。第三種規格最多裝出的成品捆數是42，解空間是31。在同一個規格中，對于成品捆數相同的方案，最短長度最長的方案被認為最好。根據這個原則，我們從方法集中找出{0 5 3 3 2 2 3 1 }作為第一種規格的最優解，因為在最短項里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}分別是規格二和規格三的最優解。

為了提高材料的利用率，如果三種規格對應的原材料有剩余，相應的材料就可以降級使用。例如，對于長度為15米的原料可以降級到規格二中使用，制造出的成品屬于規格二。

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

表3　降級后原料描述表

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

四、總結

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

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

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

[3]李興華.Java開發實戰經典[M].北京：清華大學出版社，2009.

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

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

[6]曹衛華,郭正.最優化技術方法及Matlab實現[M].北京：化學工業出版社,2014.

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

O221

A

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