天然腸衣搭配問題

劉八平

摘要

“天然腸衣搭配問題”數(shù)學模型是通過對原料描述表中的數(shù)據(jù)進行分析并整理，為改變組裝工藝，提高生產(chǎn)效率，而設計原料搭配方案。由于原料長短不一，不同長度區(qū)段的腸衣數(shù)量不同，需要組裝的成品規(guī)格有限定要求，利用數(shù)學知識聯(lián)系實際問題，做出相應的解答和處理。結(jié)合使用LINGO數(shù)學軟件對數(shù)據(jù)進行最優(yōu)化分析，解決天然腸衣的搭配問題。

根據(jù)公司對腸衣搭配方案的具體要求，參照成品規(guī)格表（表1），首先對原料描述表（表2）中的數(shù)據(jù)進行分析，建立純整數(shù)線性規(guī)劃模型，再把數(shù)據(jù)用LINGO量化分析。具體分為以下幾個步驟：

1、對于給定的一批原料，建立初步的數(shù)學模型（考慮總長度允許有±0.5米的誤差，總根數(shù)允許比標準少1根的情況），把所整理的數(shù)據(jù)輸入LINGO分析并得出各種規(guī)格成品捆數(shù)最多的最優(yōu)解并得出下一問的初步解法。

2、對初步解法進行分析，建立成品捆數(shù)最多的推廣方案。為提高原料使用率，對于剩余原料可以降級使用和成品捆數(shù)相同而最短長度最長的成品越多的方案，這就要建立成品捆數(shù)最多的推廣方案進行LINGO分析計算。

根據(jù)LINGO分析的結(jié)果，我們選用其中符合所有要求的搭配方案作為模型設計的最后結(jié)果，作為該公司設計的最佳原料搭配方案。

本次模型設計在數(shù)據(jù)編程軟件LINGO的支持下，實現(xiàn)了方案的最優(yōu)化設計，體現(xiàn)的是一種對事物分析和解決問題的一種方式方法和對資源最優(yōu)化配置的理念。

關鍵詞：數(shù)學規(guī)劃模型，整數(shù)線性規(guī)劃，搭配問題，組合最優(yōu)化，LINGO軟件

一、問題的重述

某公司將經(jīng)過清洗整理后被分割成長度不等的小段的腸衣原料按照規(guī)格要求進行組裝生產(chǎn)。傳統(tǒng)的生產(chǎn)方式是依靠人工邊丈量原料長度邊心算，將原材料按指定根數(shù)和總長度組裝出成品（捆）（表1）。為了提高生產(chǎn)效率，公司計劃改變組裝工藝，先丈量所有原料，建立原料表（表2），設計一個原料搭配方案，工人根據(jù)這個方案“照方抓藥”進行生產(chǎn)。

公司對搭配方案有以下具體要求：

(1)對于給定的一批原料，裝出的成品捆數(shù)越多越好；

(2)對于成品捆數(shù)相同的方案，最短長度最長的成品越多，方案越好；

(3)為提高原料使用率，總長度允許有±0.5米的誤差，總根數(shù)允許比標準少1根；

(4)某種規(guī)格對應原料如果出現(xiàn)剩余，可以降級使用。如長度為14米的原料可以和長度介于7-13.5米的進行捆扎，成品屬于7-13.5米的規(guī)格；

(5)為了食品保鮮,要求在30分鐘內(nèi)產(chǎn)生方案。

建立上述問題的數(shù)學模型，給出求解方法，并對表1、表2給出的實際數(shù)據(jù)進行求解，給出搭配方案。

二、問題的分析

由題意可知，目的就是為了建立一種模型，通過計算，按照成品規(guī)格表，獲得原料的一種最佳搭配方案而使工人能夠根據(jù)這個方案“按方抓藥”進行生產(chǎn)，提高生產(chǎn)效率，實現(xiàn)生產(chǎn)數(shù)據(jù)化和最大產(chǎn)出率。

分析如下：

1、題中給出兩個參考的表格：一個是某批次的原料表格（表2），一個是成品所需要達到要求的規(guī)格表格（表1）。

1）原料表格里面有很多不同區(qū)間長度和根數(shù)，這是給定的。按最小值計算長度，而實際的長度越大越好，譬如3.5-3.9米長的區(qū)段，計算時按3.5米計算，而實際長度在允許范圍內(nèi)越長的方案越好。

2）成品表格里面給定了“根數(shù)”和“總長度”，“根數(shù)”可以有±0.5米的誤差，“總長度”允許比標準少1根。

2、兩個表格的關系是：批次的原料按照成品表格里面指定的“根數(shù)”和“總長度”組裝成“捆”。

所組裝成品的最優(yōu)方案是：a、裝出來的捆數(shù)越多，方案越好；b、且每捆里面單根腸衣在選擇時在一個區(qū)段里面越長的根數(shù)越多越好；c、原料表格里面的材料出現(xiàn)剩余時，可降級使用，不浪費，按降級后的區(qū)段計算長度。

3、按照成品規(guī)格表，有20根一捆，8根一捆和5根一捆，三種捆類劃分。

4、

規(guī)格一：3米到6.5米之間有（3-3.4米43根，3.5-3.9米59根，4-4.4米39根，4.5-4.9米41根，5-5.4米27根，5.5-5.9米28根，6-6.4米34根，6.5-6.9米21根）8個可供選擇的長度區(qū)段，從這8個長度區(qū)段里面任意選擇，滿足兩個條件，即總根數(shù)為20根，總長為89米即可（考慮允許誤差范圍）。

同理，

規(guī)格二：7-13.5米之間的有14個長度區(qū)段，總根數(shù)為8根，總長為89米。

規(guī)格三：14-26米之間（∞表示沒有上限，但實際長度小于26米）有24個長度區(qū)段，總根數(shù)為5根，總長度為89米。

5、通過初步分析這些問題，可以運用數(shù)學規(guī)劃模型里的整數(shù)規(guī)劃對該問題進行求解。由于腸衣的根數(shù)都為整數(shù)，因此此題可以用到數(shù)學規(guī)劃模型中的純整數(shù)線性規(guī)劃來建立相應的數(shù)學模型。

三、模型假設

1、假設3-3.4米按3米計算，3.5米-3.9米按3.5米計算，其余的依此類推；

2、假設原料降級只能從成品規(guī)格三向成品規(guī)格二或成品規(guī)格二向成品規(guī)格一降級使用；

3、假設總長度在±0.5米的誤差之內(nèi)，總根數(shù)允許比標準少1根不會對結(jié)果產(chǎn)生影響；

4、假設工人在腸衣捆綁的過程中不受外界因素干擾，且對腸衣的保鮮度不受影響；

5、假設丈量所有原料時，丈量誤差都在誤差允許范圍之內(nèi)；

6、假設在每個長度區(qū)段選擇的根數(shù)都非負；

7、忽略在生產(chǎn)過程中對腸衣長度的損耗。

四、符號說明

：成品規(guī)格為捆成20根一捆的腸衣成品捆數(shù)（規(guī)格一成品捆數(shù)）

：成品規(guī)格為捆成8根一捆的腸衣成品捆數(shù)（規(guī)格二成品捆數(shù)）

：成品規(guī)格為捆成5根一捆的腸衣成品捆數(shù)（規(guī)格三成品捆數(shù)）

：不同成品規(guī)格裝出的成品捆數(shù) =1,2,3

：第i個方案中的j根腸衣數(shù)

：可以組裝成規(guī)格為3-6.5米的成品在第 個長度區(qū)段選用的原料根數(shù)　　

：可以組裝成規(guī)格為7-13.5米的成品在第 個長度區(qū)段選用的原料根數(shù)　　

：可以組裝成規(guī)格為14~26米的成品在第 個長度區(qū)段選用的原料根數(shù)　　

(注：文中出現(xiàn)的其他未在此處說明的符號將在后文解釋備注)

五、模型的建立與求解

最優(yōu)化原理：

全過程的最優(yōu)策略具有這樣的性質(zhì)：不管該最優(yōu)策略上某狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)而言，余下的諸決策必定構(gòu)成最優(yōu)子策略。即：最優(yōu)策略的任一后部子策略都是最優(yōu)的。

這只是最優(yōu)性定理的一個推論，即最優(yōu)策略的必要條件。

整數(shù)規(guī)劃：

當線性規(guī)劃問題的部分或所有的變量局限于整數(shù)值時，我們稱這一類問題為整數(shù)規(guī)劃問題。

模型的建立與求解：

對于給定的一批原料，設計一個原料的搭配方案，使這個方案最優(yōu)

（注：下列模型中表示在i區(qū)段原料的總長度，i取1,2,3

其中 表示在i區(qū)段成品的根數(shù)，i取1,2,3…

決策變量：

，

，

，

模型一：（規(guī)格一成品捆數(shù)最多優(yōu)化方案）

目標函數(shù)：

（1）

（2）

約束條件：

1）原料供應范圍：

（3）

2）每捆的根數(shù)：

（4）

3）對于附加約束：

（5）

由以上條件構(gòu)成數(shù)學模型；

4）模型求解

將式(1)~(5)構(gòu)成的線性整數(shù)規(guī)劃模型輸入LINGO軟件求解，程序見附錄中程序1.1，求解可以得到最優(yōu)解如下：

VariableValue

X10.000000

X213.00000

X30.000000

X41.000000

X50.000000

X60.000000

X70.000000

X86.000000

即按照模型一所得結(jié)果進行原料的搭配，工人可以從3.5-3.9米的長度區(qū)段取13根腸衣原料，從4.5-4.9米的長度區(qū)段取1根，從6.5-6.9米的長度區(qū)段取6根作為成品規(guī)格一的最優(yōu)方案進行原料搭配組裝。

為了提高原料使用率，在總長度允許有±0.5米的誤差，總根數(shù)允許比標準少1根的情況下，改變式（3）和式（4）的條件，程序如附錄中程序1.2~1.6,可以解出不同的最佳方案。將以上各程序的數(shù)據(jù)整理得出不同原料搭配方案，如下表3所示：

表3

模型二：（規(guī)格二成品捆數(shù)最多優(yōu)化方案）

目標函數(shù)：

(6）

（7）

約束條件：

1）原料供應范圍：

（8）

2）每捆的根數(shù)：

（9）

3）對于附加約束：

（10）

由以上條件構(gòu)成數(shù)學模型；

4）模型求解

將式(6)~(10)構(gòu)成的線性整數(shù)規(guī)劃模型輸入LINGO軟件求解，程序見附錄中程序2，求解可以得到最優(yōu)解如下：

VariableValue

Y10.000000

Y20.000000

Y30.000000

Y40.000000

Y51.000000

Y60.000000

Y70.000000

Y84.000000

Y90.000000

Y100.000000

Y110.000000

Y122.000000

Y131.000000

Y140.000000

即按照模型二所得結(jié)果進行原料的搭配，工人可以從9-9.4米的長度區(qū)段取1根腸衣原料，從10.5-10.9米的長度區(qū)段取4根，從12.5-12.9米的長度區(qū)段取2根，從13-13.4米的長度區(qū)段取1根作為成品規(guī)格二的最優(yōu)方案進行原料搭配組裝。

為了提高原料使用率，在總長度允許有±0.5米的誤差，總根數(shù)允許比標準少1根的情況下，改變式（8）和式（9）的條件，程序與附錄中程序1.2~1.6類似,可以解出不同的最佳方案。將各程序的數(shù)據(jù)整理得出不同原料搭配方案，如下表4所示：

表4

模型三：（規(guī)格三成品捆數(shù)最多優(yōu)化方案）

目標函數(shù)：

（11）

（12）

約束條件：

1）原料供應范圍：

（13）

2）每捆的根數(shù)：

（14）

3）對于附加約束：

（15）

由以上條件構(gòu)成數(shù)學模型；

4）模型求解

將式(11)~(15)構(gòu)成的線性整數(shù)規(guī)劃模型輸入LINGO軟件求解，程序見附錄中程序3，求解可以得到最優(yōu)解如下：

VariableValue

Z10.000000

Z21.000000

Z32.000000

Z40.000000

Z50.000000

Z60.000000

Z70.000000

Z80.000000

Z90.000000

Z100.000000

Z111.000000

Z120.000000

Z130.000000

Z140.000000

Z150.000000

Z160.000000

Z170.000000

Z180.000000

Z190.000000

Z200.000000

Z210.000000

Z220.000000

Z230.000000

Z241.000000

即按照模型三所得結(jié)果進行原料的搭配，工人可以從14.5-14.9米的長度區(qū)段取1根腸衣原料，從15-15.4米的長度區(qū)段取2根，從19-19.4米的長度區(qū)段取1根，從25.5-25.9米的長度區(qū)段取1根作為成品規(guī)格三的最優(yōu)方案進行原料搭配組裝。

為了提高原料使用率，在總長度允許有±0.5米的誤差，總根數(shù)允許比標準少1根的情況下，改變式（13）和式（14）的條件，程序與附錄中程序1.2~1.6類似,可以解出不同的最佳方案。將各程序的數(shù)據(jù)整理得出不同原料搭配方案，如下表5所示：

表5

長度	方案1	方案2	方案3	方案4	方案5	方案6
14	0	2	0	0	0	0
14.5	1	1	0	0	0	0
15	2	0	1	0	0	0
15.5	0	0	2	0	0	0
16	0	0	0	0	0	1
16.5	0	0	0	1	0	0
17	0	0	0	0	1	0
17.5	0	0	0	0	0	0
18	0	0	0	0	0	0
18.5	0	0	0	0	0	0
19	1	0	1	0	0	0
19.5	0	0	0	0	0	0
20	0	0	0	0	0	0
20.5	0	0	0	0	0	0
21	0	0	0	0	0	0
21.5	0	0	0	0	0	0
22	0	0	0	0	0	0
22.5	0	0	0	0	0	0
23	0	0	0	0	0	0
23.5	0	2	1	2	2	2
24	0	0	0	0	0	0
24.5	0	0	0	0	0	0
25	0	0	0	0	0	0
25.5	1	0	0	1	1	1

結(jié)論：

由附錄中的程序1、程序2和程序3分析知，上面建立的三個模型實現(xiàn)的最優(yōu)化搭配方案只能滿足剩余原料在不降級使用情況下的原料搭配方案要求。為充分利用腸衣原料，不造成原料資源浪費，建立推廣模型，以實現(xiàn)原料的充分利用，提高產(chǎn)出率。

六、模型的推廣與計算

求原料降級使用的最優(yōu)搭配方案

考慮剩余原料降級使用時腸衣捆數(shù)最多的優(yōu)選方案

目標函數(shù)：

max=x+y+z；(16)

max表示考慮剩余原料降級使用時規(guī)格一、二、三這三種類別的腸衣的最多捆數(shù)；

（ 的取值滿足表2）

整理數(shù)據(jù)，在LINGO軟件中運行的結(jié)果是193捆，具體的搭配方案及運算程序見附件程序4、5。

七、模型的評價與改進

本文通過對問題的充分分析，用了整數(shù)規(guī)劃模型，使問題的思路清晰明了。創(chuàng)造性的把問題的要求轉(zhuǎn)化為用LINGO數(shù)學軟件解決的線性規(guī)劃問題。大大簡化了問題討論過程的復雜程度。分析原料數(shù)據(jù)的時候，從整體的大的方面開始處理，然后再一步步細化，這種討論問題的方法簡潔易懂，具有很高的可讀性。建立純整數(shù)線性規(guī)劃模型，在理論上有一定的基礎，在實際操作中具有一定的可行性。在使用LINGO軟件求解的整數(shù)線性規(guī)劃的過程中，有些最優(yōu)解可能是分數(shù)或小數(shù)，不符合本文的要求。故模型的結(jié)果有一定的誤差，但考慮到本問題可以降級使用原料，按需可以獲得不同規(guī)格的成品，在允許的誤差范圍內(nèi)是可以接受的。

因所需設計的搭配方案需要從原料處在不同的長度區(qū)段來獲取一定長度的成品，決策變量是原料的根數(shù)，所求的解必須是整數(shù)，為滿足整數(shù)的要求，化整后的數(shù)趨近于最優(yōu)解。

整數(shù)規(guī)劃的主要缺點是：

沒有統(tǒng)一的標準模型，也沒有構(gòu)造模型的通用方法，甚至還沒有判斷一個問題能否構(gòu)造動態(tài)規(guī)劃模型的準則。這樣就只能對每類問題進行具體分析，構(gòu)造具體的模型。對于較復雜的問題在選擇狀態(tài)、決策、確定狀態(tài)轉(zhuǎn)移規(guī)律等方面需要豐富的想象力和靈活的技巧性，這就帶來了應用上的局限性。

組合最優(yōu)化通常都可表述為整數(shù)規(guī)劃問題。兩者都是在有限個可供選擇的方案中，尋找滿足一定約束的最好方案。有許多典型的問題反映整數(shù)規(guī)劃的廣泛背景。例如，背袋（或裝載）問題、固定費用問題、和睦探險隊問題（組合學的對集問題）、有效探險隊問題（組合學的覆蓋問題）、旅行推銷員問題,車輛路徑問題等。因此整數(shù)規(guī)劃的應用范圍也是極其廣泛的。它不僅在工業(yè)和工程設計和科學研究方面有許多應用，而且在計算機設計、系統(tǒng)可靠性、編碼和經(jīng)濟分析等方面也有新的應用。

八、參考文獻

【1】 趙靜 但琦，數(shù)學建模與數(shù)學實驗（第3版），北京：高等教育出版社，2008.1

【2】 劉來福曾文藝，數(shù)學模型與數(shù)學建模，北京：北京師范大學出版社，2002

【3】 （美）吉奧丹諾（Giordano,F.R.）；葉其孝譯，數(shù)學建模（原書第3版），北京：機械工業(yè)出版社，2005.1

【4】 趙東方，數(shù)學模型與計算，北京：科學出版社，2007

【5】 姚恩瑜 何勇，數(shù)學規(guī)劃與組合優(yōu)化，杭州：浙江大學出版社，2001.10

【6】 謝金星雪毅，優(yōu)化建模與LINDO/LINGO軟件，北京：清華大學出版社，2005

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/25101017/337042.html