運(yùn)籌學(xué)-線性規(guī)劃模型在實(shí)際生活中的應(yīng)用

1、線性規(guī)劃模型在實(shí)際生活中的應(yīng)用【摘要】線性規(guī)劃在實(shí)際生活中扮演著很重要的角色,研究對(duì)象是方案治理工作中有關(guān)安排和估值的問題,其廣泛應(yīng)用于經(jīng)濟(jì)等領(lǐng)域,是實(shí)際生活中進(jìn)行治理決策的最有效的方法之一.解決的主要問題是在給定條件下,按某一衡量指標(biāo)來尋找安排的最優(yōu)方案.本文通過對(duì)例題利用線性規(guī)劃分析,如何合理的分配利用,最終找到最優(yōu)解使企業(yè)利潤(rùn)最大,說明了線性規(guī)劃在實(shí)際生活中的應(yīng)用,而且對(duì)線性規(guī)劃問題模型的建立,模型的解進(jìn)行了分析,運(yùn)用圖解法和單純形法解決問題.【關(guān)鍵詞】線性規(guī)劃、建模、實(shí)際生活、圖解法、單純形法前言：線性規(guī)劃(Linearprogramming,簡(jiǎn)稱LP)是運(yùn)籌學(xué)中研究較早、開展較快、應(yīng)

2、用廣泛、方法較成熟的一個(gè)重要分支,它是輔助人們進(jìn)行科學(xué)治理的一種數(shù)學(xué)方法.研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法.英文縮寫LP.它是運(yùn)籌學(xué)的一個(gè)重要分支,廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營(yíng)治理和工程技術(shù)等方面.為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策,提供科學(xué)的依據(jù).在實(shí)際生活中,經(jīng)常會(huì)遇到一定的人力、物力、財(cái)力等資源條件下,如何精打細(xì)算巧安排,用最少的資源取得最大的效益的問題,而這正是線性規(guī)劃研究的根本內(nèi)容,它在實(shí)際生活中有著非常廣泛的應(yīng)用.任何一個(gè)組織的治理者都必須對(duì)如何向不同的活動(dòng)分配資源的問題做出決策,即如何有效地利用人力、物力完成更多的任務(wù),或在預(yù)定的

3、任務(wù)目標(biāo)下如何耗用最少的人力、物力去實(shí)現(xiàn)目標(biāo).在許多情況下,大量不同的資源必須同時(shí)進(jìn)行分配,需要這些資源的活動(dòng)可以是不同的生產(chǎn)活動(dòng),營(yíng)銷活動(dòng),金融活動(dòng)或者其他一些活動(dòng).隨著計(jì)算技術(shù)的不斷開展,使成千上萬個(gè)約束條件和決策變量的線性規(guī)劃問題能迅速地求解,更為線性規(guī)劃在經(jīng)濟(jì)等各領(lǐng)域的廣泛應(yīng)用創(chuàng)造了極其有利的條件.線性規(guī)劃已經(jīng)成為現(xiàn)代化治理的一種重要的手段.本文運(yùn)用常用的圖解法和單純形法解決利潤(rùn)最大化決策問題,貼近生活,很好的吧線性規(guī)劃應(yīng)用到生活實(shí)踐中.1、簡(jiǎn)單線性問題步驟簡(jiǎn)單介紹建模是解決線性規(guī)劃問題極為重要的環(huán)節(jié),一個(gè)正確的數(shù)學(xué)模型的建立要求建模者熟悉線性規(guī)劃的具體實(shí)際內(nèi)容,要明確目標(biāo)函數(shù)和約束條

4、件,通過表格的形式把問題中的條件和各種數(shù)據(jù)進(jìn)行整理分析,從而找出約束條件和目標(biāo)函數(shù).1.1 從實(shí)際問題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟；(1)根據(jù)影響所要到達(dá)目的的因素找到?jīng)Q策變量；-1-(2)由決策變量和所在到達(dá)目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；(3)由決策變量所受的限制條件確定決策變量所要滿足的約束條件線性規(guī)劃的數(shù)學(xué)模型的一般形式為：目標(biāo)函數(shù)：max(min)z=c1x1+C2X2+-+Cnxn滿足約束條件：a11x1+212x2+a1nxnW(=,>)b1a21x1+222x2+a?nxn<(=,>)b2am1x1+am2x2+amnxn<(=,>)bmx1,

5、x2,xn>01.2 所建立的數(shù)學(xué)模型具有以下特點(diǎn)：(1)每個(gè)模型都有假設(shè)干個(gè)決策變量(x1,x2,x3,xn),其中n為決策變量個(gè)數(shù).決策變量的一組值表示一種方案,同時(shí)決策變量一般是非負(fù)的.(2)目標(biāo)函數(shù)是決策變量的線性函數(shù)根據(jù)具體問題可以是最大化(max)或最小化(min),二者統(tǒng)稱為最優(yōu)化(opt).(3)約束條件也是決策變量的線性函數(shù).當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù),約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型.1.3 線性規(guī)劃模型的根本結(jié)構(gòu)：(1)變量變量又叫未知數(shù),它是實(shí)際系統(tǒng)的未知因素,也是決策系統(tǒng)中的可控因素,一般稱為決策變量,常引用英文字母加下標(biāo)來表

6、示,如X,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è)方面,如原材料供給、設(shè)備水平、方案指標(biāo)、產(chǎn)品質(zhì)量要求和市場(chǎng)銷售狀態(tài)等等,這些因素都對(duì)模型的變量起約束作用,故稱其為約束條件.約束條件的數(shù)學(xué)表示形式為三種,即?、=、<0線性規(guī)劃的變量應(yīng)為正值,由于變量在實(shí)際問題中所代表的均為實(shí)物,所以不能為負(fù).把線性規(guī)劃的知識(shí)運(yùn)用到企業(yè)中去,可以使

7、企業(yè)適應(yīng)市場(chǎng)劇烈的競(jìng)爭(zhēng),及時(shí)、準(zhǔn)確、科學(xué)的制定生產(chǎn)方案、投資方案、對(duì)資源進(jìn)行合理配置.過去企業(yè)在制定方案,調(diào)整分配方面很困難,既要考慮生產(chǎn)本錢,又要考慮獲利水平,人工測(cè)算需要很長(zhǎng)時(shí)間,不易做到機(jī)動(dòng)靈活,運(yùn)用線性規(guī)劃并配合計(jì)算機(jī)進(jìn)行測(cè)算非常簡(jiǎn)便易行,幾分鐘就可以拿出最優(yōu)方-2-案,提升了企業(yè)決策的科學(xué)性和可靠性.其決策理論是建立在嚴(yán)格的理論根底之上,運(yùn)用大量根底數(shù)據(jù),經(jīng)嚴(yán)格的數(shù)學(xué)運(yùn)算得到的,從而在使企業(yè)能夠在生產(chǎn)的各個(gè)環(huán)節(jié)中優(yōu)化配置,提升了企業(yè)的效率,對(duì)企業(yè)是大有益處的.2、線性規(guī)劃問題的標(biāo)準(zhǔn)形式：由于目標(biāo)函數(shù)和約束條件內(nèi)容和形式上的差異,線性規(guī)劃可以有多種表達(dá)式.為方便和制定統(tǒng)一算法,規(guī)定線性

8、規(guī)劃問題的標(biāo)準(zhǔn)形式如下：nmaxzCjXjjinaijXjbi(i1,K,m)stjixj0(i1,K,m)標(biāo)準(zhǔn)形式的線性規(guī)劃模型中,目標(biāo)函數(shù)為極大值(有些書上規(guī)定是級(jí)小值),約束條件全為等式,約束條件右端為常數(shù)項(xiàng)b全為非負(fù)數(shù),變量x的取值全為非負(fù)值.符合標(biāo)準(zhǔn)形式的線性規(guī)劃問題,課通過以下方法化為標(biāo)準(zhǔn)式.(1)目標(biāo)函數(shù)為極小值,即為：nminzCjXjj1由于求minz等價(jià)于求max(-z),令z'-z,即化為：nmaxz'cjxjj1(2)約束條件右端b<0,時(shí),只需要等式或不等式兩端同乘(-1),那么等式右端必大于00(3)約束條件不等式.當(dāng)約束條件為y時(shí),如：6x1

9、+2x2024,可令x3=24-6x1-2x2,得6x1+2x2+x3=24,顯然,x3>0.當(dāng)約束條件為f時(shí),如有10次+12發(fā)?18,可令X4=10X1+12x2-18,得10x1+12x2-x4=18,x4>0.x3,x4是新加上去的變量,取值均為非負(fù)值,加到原約束條件中去的變量,其目的是使不等式轉(zhuǎn)化為等式,其中X3為松弛變量,X4一般稱為一般變量,等也稱松弛變量.松弛變量或剩余變量在實(shí)際問題中分別表示為未被允分利用的資源和超出的資源數(shù),均未轉(zhuǎn)化為價(jià)值和利潤(rùn),所以引進(jìn)模型后他們?cè)谀繕?biāo)函數(shù)中的系數(shù)為零.(4)取值無約束的變量.如果變量x代表某產(chǎn)品當(dāng)年方案與上一年方案數(shù)之差,顯然

10、x的取值可能是正的也可能是負(fù)的,這時(shí)令x=x'-X'',將其代入線性規(guī)劃模型.(5)對(duì)x00的情況,令x'=-x,顯然x'>3、簡(jiǎn)單線性規(guī)劃問題的解法線性規(guī)劃作為數(shù)學(xué)規(guī)劃中最簡(jiǎn)單的一種問題.它的研究對(duì)象是方案治理工作中有關(guān)安排和估值的問題,解決的主要問題是在給定條件下,按某一衡量指標(biāo)來尋找安排的最優(yōu)方案.它可以表示成求函數(shù)在滿足約束條件下的極大或極小值問題.如果約束條件和目標(biāo)函數(shù)都是呈線性關(guān)系的就叫線性規(guī)劃.要解決線性規(guī)劃問題,從理論上講都要解線性方程組,而解線性方程組的常見方法是圖象法和單純?cè)?將實(shí)際生活中的線性規(guī)劃問題,抽象為數(shù)學(xué)形式,目的在

11、于找到解決問題的方法.為此,我們作以下一些討論.3.1 最大利潤(rùn)問題例1某工廠在方案期內(nèi)要安排生產(chǎn)I、R兩種產(chǎn)品,生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗.如表1所示：表aIR設(shè)備128臺(tái)時(shí)原材料A4016kg原材料B0412kg該廠每生產(chǎn)一件產(chǎn)品I可獲利2元,每生產(chǎn)一件產(chǎn)品II可獲利3元.問應(yīng)如何安排方案使該工廠在限定條件下獲利最多顯見,這個(gè)問題可以用以下的數(shù)學(xué)模型來描述設(shè)xi,x2分別表示在方案期內(nèi)產(chǎn)品I、R的產(chǎn)量.由于設(shè)備的有效臺(tái)時(shí)是8,這是一個(gè)限制產(chǎn)量的條件,所以確定產(chǎn)品I、n的產(chǎn)量時(shí),要考慮不超過設(shè)備的有效臺(tái)時(shí)數(shù),即可用不等式表示為：X2x28.同理,因原材料的限量,可以得

12、到兩個(gè)不等式：4xi16,4x212.該廠的目標(biāo)是在不超過所有資源限量的條件下,如何確定產(chǎn)量xx2以得到最大的利潤(rùn)用z表示利潤(rùn),這時(shí)z2x13x2.綜合上述,此方案問題可用數(shù)學(xué)模型表示為目標(biāo)函數(shù)：z2x13x2x12x28約束條件:4xi164x212Xi,X203.2 兩個(gè)變量的線性規(guī)劃問題的圖解法現(xiàn)在我們用圖解法來解上述的例1：在以xi,x2為坐標(biāo)軸的直角坐標(biāo)系中,非負(fù)條件xi0,x20是指第一象限.每一個(gè)約束條件都代表一個(gè)半平面,如約束條件xi2x28是代表以直線xi2x28為邊界的左下方的平平面.假設(shè)同時(shí)滿足：xi0,x20,xi2x28,4xii6和4x2i2的約束條件的點(diǎn),必然落在

13、xx2坐標(biāo)軸和由這三個(gè)半平面交成的區(qū)域內(nèi)如以下圖.陰影區(qū)域中的每一個(gè)點(diǎn)包括邊界都是這個(gè)線性規(guī)劃問題的解,因而此區(qū)域是此線性規(guī)劃問題的解集合,稱它為可行域.再來分析目標(biāo)函數(shù)z2%3x2.在這個(gè)坐標(biāo)平面上,它可表示以z為參數(shù),以2,2z、2為斜率的一族平行線：x22xi：.位于同一直線上的點(diǎn),具有相同的目標(biāo)函數(shù)值,因而稱它為“等值線.當(dāng)z值由小變大時(shí),直線x2-xi-沿其法線方向33向右上方移動(dòng).當(dāng)移動(dòng)到Q2點(diǎn)時(shí),使z值在可行域邊界上實(shí)現(xiàn)最大化如以下圖：這就得到了例1的最優(yōu)解對(duì)應(yīng)的點(diǎn)Q2,Q2點(diǎn)的坐標(biāo)為(4,2).于是可計(jì)算出滿足所有約束條件的最大值z(mì)14.這說明該廠的最優(yōu)生產(chǎn)方案方案是：生產(chǎn)4件

14、產(chǎn)品I,生產(chǎn)2件產(chǎn)品可得最大利潤(rùn)為14元.【拓展延伸探究】例2預(yù)算有2000元購(gòu)置單價(jià)為50元的桌子和20元的椅子,希望使桌椅的總數(shù)量盡可能的多,但椅子數(shù)不少于桌子數(shù),且不多于桌子數(shù)的1.5倍,問桌子和椅子各購(gòu)置多少分析這是生活實(shí)際中的一個(gè)物資采購(gòu)問題,可歸結(jié)為線性規(guī)劃問題,利用圖解法進(jìn)行求解.解設(shè)桌子和椅子各購(gòu)置x、y張,那么x、y必須滿足線性約束條件50x20y2000xyx,y0其目標(biāo)函數(shù)z=x+y.xxy,由50x20y2000,解得yx,yN20,7200200200、.,r二,7故圖14中點(diǎn)A的坐標(biāo)為77y1.5x由50x20y2000x257575./口y(25,)解得2故圖中點(diǎn)

15、B的坐標(biāo)為2滿足以上條件的可行域?yàn)槿缦聢D的陰影局部(包括邊界和內(nèi)部),以A、BO為頂點(diǎn)三角形區(qū)域.動(dòng)直線z=x+y表示斜率為1,在y軸上的截距為z的直線,如下圖的虛75一一.yt線,當(dāng)動(dòng)直線運(yùn)動(dòng)到如圖所小的B點(diǎn)時(shí),z的取值最大,止匕時(shí)x=25,20但由于x、y的取值均為整數(shù),故y應(yīng)取37,即購(gòu)置25張桌子、椅子37張,是最優(yōu)選擇.25,點(diǎn)悟：由于此題是一個(gè)實(shí)際問題,當(dāng)求得最優(yōu)解2后,顯然它不滿足題意,故應(yīng)取最優(yōu)解的近似值,這便是實(shí)際問題與一般的非應(yīng)用問題的最大區(qū)別.在實(shí)際問題中椅子必須是整數(shù),所以x=25,y=37.3.3用單純?cè)ń鈨蓚€(gè)變量的線性規(guī)劃問題例3:某車間生產(chǎn)甲、乙兩種產(chǎn)品,制造一

16、件甲產(chǎn)品需要A種元件5個(gè),B種元件3個(gè)；制造一件乙產(chǎn)品需要A種元件2個(gè),B種元件3個(gè).現(xiàn)因某種條件限制,只有A種元件180,B種元件135個(gè)；每件甲種產(chǎn)品可獲利20元,每件乙種產(chǎn)品可獲利15元.試問在這種條件下,應(yīng)該生產(chǎn)甲、乙兩種產(chǎn)品各多少件才能得到最大利潤(rùn)?解：設(shè)應(yīng)該生產(chǎn)甲產(chǎn)品%件,乙產(chǎn)品X2件,才能得到最大利潤(rùn)S元.根據(jù)題意,此問題可用數(shù)學(xué)模型表示為：目標(biāo)函數(shù)S20為15x2滿足約束條件5x13x12x23x2180135x1,x20S20x115x20x30x4將上述問題化成標(biāo)準(zhǔn)形式:5x12x2x3180343x2x4135x1,x2,x3,x4添加的松弛變量x3和x4在約束方程組中其

17、系數(shù)列正好構(gòu)成一個(gè)2階單位陣,它們可以作為初始基變量,初始基可行解為X=0,0,180,135'表1Cj一201500Cb基bXixx2x3x40%18052100X41353301Cj-Zj02015-00由于只有72>0,說明表中基可行解不是最優(yōu)解,所以確定x1為換入非基變量；以x1的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列,最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量.min(180135)5,3)36因此確定5為主元素(表1中以防括號(hào)口括起),意味著將以非基變量X2去置換基變量X6,采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換,將Xi的系數(shù)列(20,15)T變換成X3的系數(shù)列(

18、0,1):變換之后重新計(jì)算檢驗(yàn)數(shù).變換結(jié)果見表2表2Cj一201500Cb基bX1XX2X3X403612/51/500X42709/5-3/51Cj-Zj-72007-40再按上述方法可得表3表3Cj一201500Cb基bX1lX2X3X40K30103/5-2/90X41501-1/55/9Cj-Zj-88900-1/5-7此時(shí),2個(gè)非基變量的檢驗(yàn)數(shù)都小于0,(T3=-1/5,(74=-7,說明已求得最T優(yōu)解：X(30,15,0,0)To去除添加的松弛變量,原問題的最優(yōu)解為：*TX(30,15),最打值為20*30+15*15=825.假設(shè)企業(yè)在生產(chǎn)、運(yùn)輸、市場(chǎng)營(yíng)銷等方面,沒有很好地利用線性規(guī)劃進(jìn)行合理的配置,往往會(huì)導(dǎo)致增加了企業(yè)的生產(chǎn),使企業(yè)的利潤(rùn)不