線性規(guī)劃理論在實(shí)際問題中的應(yīng)用

1、線性規(guī)劃理論在實(shí)際問題中的應(yīng)用內(nèi)容摘要 :企業(yè)是一個(gè)復(fù)雜的系統(tǒng) ,要研究它必須將其抽象出來形成模型。如果將系統(tǒng)內(nèi)部因素的相互關(guān)系和它們活動(dòng)的規(guī)律用數(shù)學(xué)的形式描述出來，就稱之為數(shù)學(xué)模型.線性規(guī)劃是運(yùn)用數(shù)學(xué)模型 ,對(duì)人力、設(shè)備、材料、資金等進(jìn)行系統(tǒng)和定量的分析，使生產(chǎn) 力得到最為合理的組織，以獲得最佳的經(jīng)濟(jì)效益。應(yīng)用線性規(guī)劃問題解決實(shí)際問題， 最重要的一個(gè)步驟就是首先要建立實(shí)際問題的線性規(guī)劃問題的數(shù)學(xué)模型 .一、線性規(guī)劃問題及其數(shù)學(xué)模型二、線性規(guī)劃模型的具體分析及應(yīng)用 Excel 求解線性規(guī)劃問題三、線性規(guī)劃的局限性一、線性規(guī)劃問題及其數(shù)學(xué)模型（一）線性規(guī)劃的模型決定于它的定義，線性規(guī)劃的定義是：

2、求一組變量的值， 在滿足一組約束條件下，求得目標(biāo)函數(shù)的最優(yōu)解。根據(jù)這個(gè)定義,就可以確定線性規(guī)劃模型的基本結(jié)構(gòu)。（ 1）變量變量又叫未知數(shù)， 它是實(shí)際系統(tǒng)的未知因素 ,也是決策系統(tǒng)中的可控因素， 一般稱為決策變量，常引用英文字母加下標(biāo)來表示 ,如 Xl,X2，X3，Xmn 等。（2）目標(biāo)函數(shù)將實(shí)際系統(tǒng)的目標(biāo)，用數(shù)學(xué)形式表現(xiàn)出來，就稱為目標(biāo)函數(shù)，線性 規(guī)劃的目標(biāo)函數(shù)是求系統(tǒng)目標(biāo)的數(shù)值，即極大值，如產(chǎn)值極大值、利潤(rùn)極大值或者極 小值，如成本極小值、費(fèi)用極小值、損耗極小值等等。（3）約束條件約束條件是指實(shí)現(xiàn)系統(tǒng)目標(biāo)的限制因素。它涉及到企業(yè)內(nèi)部條件和外 部環(huán)境的各個(gè)方面 ,如原材料供應(yīng)、設(shè)備能力、計(jì)劃指

3、標(biāo)、產(chǎn)品質(zhì)量要求和市場(chǎng)銷售狀 態(tài)等等，這些因素都對(duì)模型的變量起約束作用，故稱其為約束條件。約束條件的數(shù)學(xué) 表示形式為三種，即 二二、W線性規(guī)劃的變量應(yīng)為正值，因?yàn)樽兞吭趯?shí)際問題中所代 表的均為實(shí)物，所以不能為負(fù)。（二）在經(jīng)濟(jì)管理中，線性規(guī)劃使用較多的是下述幾個(gè)方面的問題：（1）投資問題確定有限投資額的最優(yōu)分配 ,使得收益最大或者見效快。（2）計(jì)劃安排問題 確定生產(chǎn)的品種和數(shù)量 ,使得產(chǎn)值或利潤(rùn)最大，如資源配制問 題。（3）任務(wù)分配問題 分配不同的工作給各個(gè)對(duì)象（勞動(dòng)力或機(jī)床 ），使產(chǎn)量最多、 效率最高，如生產(chǎn)安排問題。（4）下料問題 如何下料，使得邊角料損失最小。（5）運(yùn)輸問題在物資調(diào)運(yùn)過程中

4、，確定最經(jīng)濟(jì)的調(diào)運(yùn)方案。（6）庫存問題如何確定最佳庫存量 ,做到即保證生產(chǎn)又節(jié)約資金等等。（三）應(yīng)用線性規(guī)劃建立數(shù)學(xué)模型的三步驟：（1）明確問題，確定問題，列出約束條件。（2）收集資料，建立模型。（3）模型求解（最優(yōu)解） ，進(jìn)行優(yōu)化后分析。 其中，最困難的是建立模型，而建立模型的關(guān)鍵是明確問題、確定目標(biāo)，在建立 模型過程中花時(shí)間、花精力最大的是收集資料。(四) 線性規(guī)劃的數(shù)學(xué)模型的一般形式為 :目標(biāo)函數(shù) max (min) z=c1 Xi +c2 X2+cn Xn 滿足約束條件：all Xi +a12 X2,+ +a1nXn< (=,>) bl a21 Xi +a22 X2,+ +

5、a2nXn <(= ,>) b2ami Xi +am2 X2+amn Xn < (=,> ) bmXi, X2,Xn > 0線性規(guī)劃模型的矩陣形式：目標(biāo)函數(shù) max( min) Z = CX約束條件AX < (=,)b其中，C=(c1, c2,cn) , X=( Xi, X2,Xn) Tb=(b1, b2,bm)TGil, a12,a1n 'A= a21, a22,a2n乜mi, am2,amn 丿二、線性規(guī)劃模型的具體分析及應(yīng)用Excel求解線性規(guī)劃問題我們來看生產(chǎn)計(jì)劃問題：生產(chǎn)計(jì)劃是控制生產(chǎn)裝置運(yùn)行的命令，要利用有限的資源獲得最大的經(jīng)濟(jì)效益，就必

6、須制定最佳生產(chǎn)計(jì)劃。隨著公司生產(chǎn)裝置的不斷增多，生產(chǎn)計(jì)劃的制定變得越來越 復(fù)雜.采用現(xiàn)代管理技術(shù)，建立數(shù)學(xué)模型，利用電子計(jì)算機(jī)求解 ，很容易得出最優(yōu)生產(chǎn)計(jì) 劃。下面舉一案例說明(本案例出自運(yùn)籌學(xué)，林齊寧,北京郵電大學(xué)出版社，2003 年，P7)某工廠計(jì)劃用現(xiàn)有的銅、鉛兩種資源生產(chǎn) A、B兩種型號(hào)的電纜。A、B兩種型號(hào) 的電纜單位售價(jià)分別為6萬元和4萬元。市場(chǎng)對(duì)A型電纜的需要量無限制，而對(duì)B電纜 的最大需求量為7單位。生產(chǎn)單位產(chǎn)品A、B兩種型號(hào)電纜對(duì)銅、鉛的消耗量及可利 用的銅、鉛數(shù)量如下表所示：表1 ：基本信息表A型電纜B型電纜資源提供限量1消耗：銅(噸)2110消耗：鉛(噸)118產(chǎn)品需要限

7、量7售價(jià)(萬元)64工廠應(yīng)該如何讓安排生產(chǎn)，才能使工廠總收入最大?解答過程如下：(1) 決策變量設(shè)x1 , x2分別代表A、B兩種型號(hào)電纜的生產(chǎn)量,f(x)為工廠總收入(2) 目標(biāo)函數(shù)本問題的目標(biāo)是工廠收益最大值Maxf (x)=6 X i+4X2(3) 約束條件:A型電纜B型電纜資源提供限量消耗:銅（噸）2110消耗：鉛（噸）118產(chǎn)品需要限量7售價(jià)（萬元）64則上述問題可以用如下數(shù)學(xué)模型（線性規(guī)劃模型）來表示:Obj:Maxf（x）=6 X1+4X22 X1+X2W 10銅資源約束s.t. X1+X2 < 8鉛資源約束X2< 7產(chǎn)量數(shù)量約束Xi, X2>0產(chǎn)量質(zhì)量約束用E

8、xcel輔助計(jì)算求解。首先,根據(jù)問題建立電子表格模型具體步驟如下：1。收集問題的數(shù)據(jù)。2。在電子表格的數(shù)據(jù)單元格中輸入數(shù)據(jù)。3。確定對(duì)活動(dòng)水平需要作出的決策并且指定可變單元顯示這些決策。4。確定對(duì)這些決策的約束條件并引入需具體化這些約束條件的輸出單元格。5。選擇要輸入目標(biāo)單元格的完全績(jī)效測(cè)度。6。使用SUMPRODUC數(shù)為每個(gè)輸出單元格（包括目標(biāo)單元格）輸入合適的值然后,建立了起電子表格模型：A1.5 .CDEF1A型電統(tǒng)連源提供陶量取大用里2消孤洞（噸）2110>0 W消耗；鉛（噸）11>o n4產(chǎn)品需餐限重756土產(chǎn)量007售價(jià)（萬元<54總收入Q再進(jìn)行規(guī)劃求解:設(shè)星日標(biāo)

9、單元箱:HIT 窗等于：堆大值O最小值©) o值討o 可變單元格:抑擁：虻$E陽推測(cè)峋束QD：丨脈加® ) 更改© 求解王亍I關(guān)用J匱項(xiàng)1jBter$C$6 >= 0ICJ6 <= JC54$&$2；$D$3 >= $F$2：$F$3險(xiǎn)部重說® 幫助規(guī)劃求解的選項(xiàng)對(duì)話框:最后,保存求解結(jié)果：規(guī)劃求解結(jié)皋報(bào)告麴我解找到一解可滿足所有的約束及量憂®保存覬劃求解箱果.卄更復(fù)為原值0)i確定 助肖 假薦方葉盤)幫助最終結(jié)果如下圖所示r - aBCDEF1A型電纜F型電纜資源提供限量曰m曰取大用里22110>r 103消耗

10、:鉛（噸）118>4嚴(yán)品需要限量75>&二疔量2 67售價(jià)（萬元）64總收入368可以利用Excel中的“規(guī)劃求解”功能可以直接到“敏感性分析”，利用該報(bào)告可以很方便地進(jìn)行靈敏度分析：J變單兀格單元格名字終遞減 ft建目標(biāo)式 系數(shù)允許的 増量允許的$B$6注產(chǎn)量A型電纜20622$C$6護(hù)量>60421陰影約東允許的九許的單元格名字值價(jià)格限制值増量減量W$2梢耗*銅噸）賀源提供辰量10-201&$D$M梢耗:鉛（噸）資源提洪限量8-2030.5敏感性報(bào)告的內(nèi)容由兩部分組成：（1）位于報(bào)告上部的“可變單元格"部分反映了目標(biāo)函數(shù)中的系數(shù)變化對(duì)最優(yōu)解產(chǎn) 生

11、的影響第一列“單元格”是指決策變量所在單元格地址。 第二列“名字”是這些決策變量的名稱 第三列“終值”是決策變量的終值，即最優(yōu)解。第四列是“遞減成本”，它的絕對(duì)值表示目標(biāo)函數(shù)中決策變量的系數(shù)必須改進(jìn)多 少，才能得到該決策變量的正數(shù)解第五列“目標(biāo)式系數(shù)”是指目標(biāo)函數(shù)中的系數(shù)。第六列與第七列分別是“允許的增量"和“允許的減量”它們表示目標(biāo)函數(shù)中的 系數(shù)在允許的增量和減量范圍內(nèi)變化時(shí)，最優(yōu)解不變。（2）位于報(bào)告下部的“約束”部分反映了約束條件右端值變化目標(biāo)值產(chǎn)生的影響。 目標(biāo)函數(shù)系數(shù)同時(shí)變動(dòng)的情況：當(dāng)各個(gè)系數(shù)變動(dòng)的百分比之和小于 100%時(shí)，最優(yōu)解不發(fā)生變化；當(dāng)各個(gè)系數(shù)變動(dòng)的百分比之和等于

12、 100時(shí)，最優(yōu)解不發(fā)生變化； 當(dāng)各個(gè)系數(shù)變 動(dòng)的百分比之和大于 100時(shí)，不能確定最優(yōu)解的變化，可能改變，也可能不變 . 約束 右端值同時(shí)變動(dòng)：當(dāng)各個(gè)右端值變動(dòng)的百分比之和小于 100時(shí) , 影子價(jià)格有效 ; 當(dāng)各個(gè)右端值變動(dòng)的百分比之和等于 100%時(shí)，影子價(jià)格有效； 當(dāng)各個(gè)右端值變動(dòng)的百分比之和大于 100時(shí) , 不能保證影子價(jià)格依然有效。三、線性規(guī)劃的局限性公司生產(chǎn)的復(fù)雜性使得手編計(jì)劃的工作極其復(fù)雜 , 手編計(jì)劃的工作量大， 而且更為 重要的是很難甚至無法實(shí)現(xiàn)優(yōu)化，會(huì)給公司造成很大的機(jī)會(huì)損失。采用線性規(guī)劃模型 制定公司計(jì)劃和進(jìn)行決策分析是可行的、必要的 . 在這個(gè)效率優(yōu)先的時(shí)代 ,眾多

13、領(lǐng)域中， 但凡涉及最優(yōu)解的問題，首先考慮的方法即是線性規(guī)劃。要建立一個(gè)切合實(shí)際的線型規(guī)劃模型，需要工程技術(shù)人員、財(cái)務(wù)管理人員等的通 力配合，否則會(huì)失去很多有用的信息。線性規(guī)劃作為運(yùn)籌學(xué)的一個(gè)分支發(fā)展至今，從 建立模型到求的最優(yōu)解的整個(gè)過程 ,都有一套發(fā)展較為完備的體系和理論 .涉及到生產(chǎn) 計(jì)劃以及類似的問題時(shí)，線性規(guī)劃顯然是首選的方法。然而，線性規(guī)劃并不是沒有其因?yàn)榉椒ū旧砘蛘邌栴}本身超出方法談到的要求所產(chǎn) 生的某些局限性。非常明顯的一點(diǎn)是 ,線性規(guī)劃模型實(shí)質(zhì)上還是一個(gè)靜態(tài)的模型 .事實(shí)上， 隨著約束條件的變化，目標(biāo)函數(shù)中的一些指標(biāo)常常并非一成不變。舉例來說,在考慮生產(chǎn)計(jì)劃，即如何選擇產(chǎn)業(yè)結(jié)構(gòu)使生產(chǎn)成本最低的時(shí)候，成本系數(shù)實(shí)質(zhì)上是一個(gè)會(huì)根據(jù)產(chǎn)業(yè) 結(jié)構(gòu)和模式之變化而難以絕對(duì)保持靜態(tài)的變量， 這就勢(shì)必導(dǎo)致模型的理想化。 另一方面， 生產(chǎn)過程也不是一個(gè)絕對(duì)靜態(tài)的過程，即產(chǎn)業(yè)結(jié)構(gòu)本身，或者說約束條件中