基于線性規(guī)劃模型的天然腸衣原材料搭配方案

甄海燕，張 猛

(山東商業(yè)職業(yè)技術(shù)學(xué)院，山東濟(jì)南 250103)

0 引言

在工程技術(shù)、經(jīng)濟(jì)管理、科學(xué)研究和日常生活等諸多領(lǐng)域中，人們經(jīng)常遇到的一類決策問題:在一系列客觀或主觀限制條件下，尋求所關(guān)注的某個(gè)或多個(gè)指標(biāo)達(dá)到最大(或最小)的決策.它們的特點(diǎn)就是:在若干可能的方案中尋求某種意義下的最優(yōu)方案.數(shù)學(xué)上稱為最優(yōu)化問題，而研究處理這種問題的方法叫最優(yōu)化的方法［1］.線性規(guī)劃方法是最優(yōu)化方法中的一種非常重要的方法，它是借助LINGO工具解決最大最小問題的一中非常簡單實(shí)用的方法.天然腸衣的原材料搭配是一個(gè)線性規(guī)劃問題.問題解決的方法主要是通過對(duì)不同規(guī)格腸衣的搭配、合理的降級(jí)使用以及搭配出更多最優(yōu)成品捆等問題進(jìn)行了分析討論，并利用線性規(guī)劃模型對(duì)腸衣搭配進(jìn)行了優(yōu)化，借助LINGO軟件求解得出一個(gè)最優(yōu)的搭配方案，這個(gè)模型不僅僅適用于天然腸衣搭配問題，它對(duì)規(guī)劃類問題的求解都可以起到指導(dǎo)作用.

1 問題提出

天然腸衣(以下簡稱腸衣)制作加工是我國的一個(gè)傳統(tǒng)產(chǎn)業(yè)，出口量占世界首位.腸衣經(jīng)過清洗整理后被分割成長度不等的小段(原料)，進(jìn)入組裝工序.傳統(tǒng)的生產(chǎn)方式依靠人工，邊丈量原料長度邊心算，將原材料按指定根數(shù)和總長度組裝出成品(捆).原料按長度分檔，通常以0.5 m為一檔，如:3～3.4 m按3 m 計(jì)算，3.5 ～3.9 m 按3.5 m 計(jì)算，其余的依此類推.表1是幾種常見成品的規(guī)格，長度單位為米，∞表示沒有上限，但實(shí)際長度＜26 m.

表1 成品規(guī)格表 根

為了提高生產(chǎn)效率，公司計(jì)劃改變組裝工藝，先丈量所有原料，建立一個(gè)原料表.表2為某批次原料描述.

表2 原料描述表根

根據(jù)以上成品和原料描述，設(shè)計(jì)一個(gè)原料搭配方案，工人根據(jù)這個(gè)方案“照方抓藥”進(jìn)行生產(chǎn).

公司對(duì)搭配方案有以下具體要求:

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

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

(3)某種規(guī)格對(duì)應(yīng)原料如果出現(xiàn)剩余，可以降級(jí)使用.如長度為14 m的原料可以和長度介于7～13.5 m的進(jìn)行捆扎，成品屬于7～13.5 m的規(guī)格.

2 問題分析

本題根據(jù)搭配方案的3個(gè)具體要求來建立線性規(guī)劃模型和優(yōu)化模型;由題意知搭配方案的具體要求無先后之分.經(jīng)分析，將要求(1)、(2)、(3)一起考慮，建立一個(gè)求單個(gè)規(guī)格總捆數(shù)最大的線性規(guī)劃模型.在建立線性規(guī)劃模型時(shí)，我們主要考慮每個(gè)規(guī)格的根數(shù)和總長度，由此建立約束條件.同時(shí)因?yàn)槲覀兪欠謩e求每個(gè)規(guī)格的總捆數(shù)，且考慮到要求(2)，所以，我們先求出第三個(gè)規(guī)格的總捆數(shù)，將規(guī)格三中剩余的原材料降級(jí)使用投放入規(guī)格二中，再求第二個(gè)規(guī)格的總捆數(shù)，同理，按照降級(jí)使用原則將所有剩余的放入規(guī)格一求規(guī)格一的總捆數(shù).

3 模型假設(shè)

(1)假設(shè)工作人員輸入數(shù)據(jù)的時(shí)間為零，讀取結(jié)果的時(shí)間為零.

(2)假設(shè)原料測量無誤差或誤差較小，不會(huì)對(duì)計(jì)算與分組產(chǎn)生影響.

(3)假設(shè)方案產(chǎn)生后可立即進(jìn)行組裝，組裝時(shí)間不會(huì)對(duì)食品保鮮產(chǎn)生影響.

(4)假設(shè)原料質(zhì)量不會(huì)對(duì)分組、組裝產(chǎn)生影響.

(5)第三種規(guī)格的原料如果出現(xiàn)剩余，可以分別降到第二種規(guī)格或第一種規(guī)格使用.

4 符號(hào)說明

模型符號(hào)說明，見表3.

表3 符號(hào)說明

5 模型建立

從題意中看出，搭配方案的三個(gè)具體要求沒有先后順序之分，故將要求(1)、(2)、(3)一起考慮.根據(jù)要求(1)，使原料數(shù)量一定的情況下，裝出的成品總捆數(shù)最多，即為目標(biāo)函數(shù);整個(gè)方案的總捆數(shù)最多，即為最終的目標(biāo)函數(shù).再根據(jù)表1的數(shù)據(jù)和要求(2)“總長度允許有±0.5 m的誤差，總根數(shù)允許比標(biāo)準(zhǔn)少1根”，以及每個(gè)長度段所用的總根數(shù)

不能大于其原有的總根數(shù).由此得到模型1.

約束條件:

(上式中，Δx×Δc表示在上一規(guī)格的長度段中剩下的長度與段數(shù)之積的總和)同時(shí)注意，由于要求(3)“可以降級(jí)使用”，故計(jì)算時(shí)應(yīng)先從規(guī)格三開始.

6 模型求解

模型已經(jīng)建立完成，只要將丈量的數(shù)值代入以上的模型中，便可以得到一個(gè)符合題目要求的原料分配方案.將題目中的表1、表2的數(shù)據(jù)代入以上的模型中，求解如下:

由于要求(3)“可以降級(jí)使用”，故計(jì)算時(shí)應(yīng)先從規(guī)格三開始.若原材料有剩余，則加入規(guī)格二中，成品屬于規(guī)格二;若計(jì)算規(guī)格二后仍有剩余，則將所有剩余加入規(guī)格一.按此原則，求解如下:

(1)求解規(guī)格三

將規(guī)格三的數(shù)據(jù)(見表4)代入模型1中，得到:

表4 規(guī)格三數(shù)據(jù)

目標(biāo)函數(shù):

約束條件:

通過LINGO軟件對(duì)以上線性規(guī)劃模型進(jìn)行求解［2］，結(jié)果為 n3=137，即規(guī)格三最多有137捆成品，xj(j=1，2，…，24)的結(jié)果見表5.

表5 規(guī)格三求解結(jié)果 根

比較表4與表5，可得到:最后剩下了2根15 m長的原材料.

(2)求解規(guī)格二

將規(guī)格二的數(shù)據(jù)(見表6)代入模型一中，得到:

表6 規(guī)格二相關(guān)數(shù)據(jù)

目標(biāo)函數(shù):

約束條件:

通過LINGO軟件對(duì)以上線性規(guī)劃模型進(jìn)行求解(15 m的長度段是第25段，故程序中用x25表示Δx，表7)，結(jié)果為n2=37，即規(guī)格二最多有37捆成品，xj(j=1，2，…，14)的結(jié)果見表7.

表7 規(guī)格二求解結(jié)果 根

比較表6與表7，可得到:最后共剩下了24根7 m長的、24根7.5 m 長的、6根8 m 長的、4根8.5 m長的、2根15 m長的原材料.

(3)求解規(guī)格一

將規(guī)格一的數(shù)據(jù)(見表8)代入模型一中，得到:

表8 規(guī)格一相關(guān)數(shù)據(jù)

目標(biāo)函數(shù):

約束條件:

上式中，Δx×Δc表示在上一規(guī)格的長度段中剩下的長度與段數(shù)之積的總和.

通過LINGO軟件對(duì)以上線性規(guī)劃模型進(jìn)行求解(Δx 包括 x9、x10、x11、x12、x25，5 種情況，同表 7)，結(jié)果為n1=16，即規(guī)格一最多有16捆成品，xj(j=1，2，…，8)的結(jié)果見表9.比較表8與表9，可得到:最后共剩下了6根7 m長的、24根7.5 m 長的、6根8 m 長的、4根8.5 m長的、2根15 m長的原材料.

表9 規(guī)格一求解后的結(jié)果 根

7 結(jié)語

通過對(duì)題目的解讀我們不難發(fā)現(xiàn)這是一類規(guī)劃問題.建立了一個(gè)整數(shù)線性規(guī)劃模型.這個(gè)模型不僅僅適用于天然腸衣搭配問題，它對(duì)規(guī)劃類問題的求解都可以起到指導(dǎo)作用.比如投資時(shí)，有限的資金如何分配到各種投資方式上;工廠選址時(shí)，要兼顧距離原料區(qū)和服務(wù)區(qū)的路程等這一類問題均能得到較好的解決.規(guī)劃模型在工業(yè)、商業(yè)、交通運(yùn)輸、工程技術(shù)、行政管理等領(lǐng)域有著廣泛的應(yīng)用.

［1］王兵團(tuán).數(shù)學(xué)建?；A(chǔ)［M］.北京:清華大學(xué)出版社，2004.

［2］謝金星，薛 毅.優(yōu)化建模與LINDO/LINGO軟件［M］.北京:清華大學(xué)出版社，2005.