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

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

2、（Linear programming,簡(jiǎn)稱LP）是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。研究線性約束條件下線性目標(biāo)函數(shù)的極值問(wèn)題的數(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ì)算巧安排，用最少的資源取得最大的效益的問(wèn)題，而這正是線性規(guī)劃研究的基本內(nèi)容，它在實(shí)際生活中有著非常廣泛的應(yīng)用任何一個(gè)組織的管理者都必須對(duì)如何向不同

3、的活動(dòng)分配資源的問(wèn)題做出決策，即如何有效地利用人力、物力完成更多的任務(wù)，或在預(yù)定的任務(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ù)的不斷發(fā)展，使成千上萬(wàn)個(gè)約束條件和決策變量的線性規(guī)劃問(wèn)題能迅速地求解，更為線性規(guī)劃在經(jīng)濟(jì)等各領(lǐng)域的廣泛應(yīng)用創(chuàng)造了極其有利的條件。線性規(guī)劃已經(jīng)成為現(xiàn)代化管理的一種重要的手段。本文運(yùn)用常用的圖解法和單純形法解決利潤(rùn)最大化決策問(wèn)題，貼近生活，很好的吧線性規(guī)劃應(yīng)用到生活實(shí)踐中。1、簡(jiǎn)單線性問(wèn)題步驟簡(jiǎn)單介紹建模是解決線性規(guī)劃問(wèn)題極為重要的環(huán)節(jié)，一

4、個(gè)正確的數(shù)學(xué)模型的建立要求建模者熟悉線性規(guī)劃的具體實(shí)際內(nèi)容，要明確目標(biāo)函數(shù)和約束條件，通過(guò)表格的形式把問(wèn)題中的已知條件和各種數(shù)據(jù)進(jìn)行整理分析，從而找出約束條件和目標(biāo)函數(shù)。1.1 從實(shí)際問(wèn)題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟； （1）根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量； （2）由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)； （3）由決策變量所受的限制條件確定決策變量所要滿足的約束條件。線性規(guī)劃的數(shù)學(xué)模型的一般形式為：目標(biāo)函數(shù)： max(min) z=c1 x1+c2x2+cn xn滿足約束條件： a11x1+a12x2+a1nxn (,) b1 a21x1+a22x2+a2nxn (,)

5、 b2 . . am1x1+am2x2+amnxn (,) bm x1, x2, ,xn 01.2 所建立的數(shù)學(xué)模型具有以下特點(diǎn)： （1）每個(gè)模型都有若干個(gè)決策變量（x1，x2，x3，xn），其中n為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。 （2）目標(biāo)函數(shù)是決策變量的線性函數(shù)根據(jù)具體問(wèn)題可以是最大化（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ù)，它

6、是實(shí)際系統(tǒng)的未知因素，也是決策系統(tǒng)中的可控因素，一般稱為決策變量，常引用英文字母加下標(biāo)來(lái)表示，如Xl，X2，X3，Xmn等。  （2）目標(biāo)函數(shù)  將實(shí)際系統(tǒng)的目標(biāo)，用數(shù)學(xué)形式表現(xiàn)出來(lái)，就稱為目標(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ì)劃指標(biāo)、產(chǎn)品質(zhì)量要求和市場(chǎng)銷售狀態(tài)等等，這些因素都對(duì)模型的變量起約束作用，故稱其為約束條

7、件。約束條件的數(shù)學(xué)表示形式為三種，即、。線性規(guī)劃的變量應(yīng)為正值，因?yàn)樽兞吭趯?shí)際問(wèn)題中所代表的均為實(shí)物，所以不能為負(fù)。把線性規(guī)劃的知識(shí)運(yùn)用到企業(yè)中去，可以使企業(yè)適應(yīng)市場(chǎng)激烈的競(jìng)爭(zhēng)，及時(shí)、準(zhǔn)確、科學(xué)的制定生產(chǎn)計(jì)劃、投資計(jì)劃、對(duì)資源進(jìn)行合理配置。過(guò)去企業(yè)在制定計(jì)劃，調(diào)整分配方面很困難，既要考慮生產(chǎn)成本，又要考慮獲利水平，人工測(cè)算需要很長(zhǎng)時(shí)間，不易做到機(jī)動(dòng)靈活，運(yùn)用線性規(guī)劃并配合計(jì)算機(jī)進(jìn)行測(cè)算非常簡(jiǎn)便易行，幾分鐘就可以拿出最優(yōu)方案，提高了企業(yè)決策的科學(xué)性和可靠性。其決策理論是建立在嚴(yán)格的理論基礎(chǔ)之上，運(yùn)用大量基礎(chǔ)數(shù)據(jù)，經(jīng)嚴(yán)格的數(shù)學(xué)運(yùn)算得到的，從而在使企業(yè)能夠在生產(chǎn)的各個(gè)環(huán)節(jié)中優(yōu)化配置，提高了企業(yè)的效率

8、，對(duì)企業(yè)是大有益處的。2、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：由于目標(biāo)函數(shù)和約束條件內(nèi)容和形式上的差別，線性規(guī)劃可以有多種表達(dá)式。為方便和制定統(tǒng)一算法，規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式如下：標(biāo)準(zhǔn)形式的線性規(guī)劃模型中，目標(biāo)函數(shù)為極大值（有些書(shū)上規(guī)定是級(jí)小值），約束條件全為等式，約束條件右端為常數(shù)項(xiàng)b全為非負(fù)數(shù)，變量x的取值全為非負(fù)值。符合標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題，課通過(guò)下列方法化為標(biāo)準(zhǔn)式。（1） 目標(biāo)函數(shù)為極小值，即為：因?yàn)榍髆in z等價(jià)于求max(-z),令z=-z,即化為：（2） 約束條件右端b<0，時(shí)，只需要等式或不等式兩端同乘（-1），則等式右端必大于0。（3） 約束條件不等式。當(dāng)約束條件為“”時(shí)，

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

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

11、1 最大利潤(rùn)問(wèn)題例1 某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)、兩種產(chǎn)品,已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗.如表1所示:表a 設(shè)備128臺(tái)時(shí)原材料A4016原材料B0412該廠每生產(chǎn)一件產(chǎn)品可獲利2元,每生產(chǎn)一件產(chǎn)品可獲利3元.問(wèn)應(yīng)如何安排計(jì)劃,使該工廠在限定條件下獲利最多?顯見(jiàn),這個(gè)問(wèn)題可以用以下的數(shù)學(xué)模型來(lái)描述:設(shè)分別表示在計(jì)劃期內(nèi)產(chǎn)品、的產(chǎn)量.因?yàn)樵O(shè)備的有效臺(tái)時(shí)是8,這是一個(gè)限制產(chǎn)量的條件,所以確定產(chǎn)品、的產(chǎn)量時(shí),要考慮不超過(guò)設(shè)備的有效臺(tái)時(shí)數(shù),即可用不等式表示為:.同理,因原材料的限量,可以得到兩個(gè)不等式:,.該廠的目標(biāo)是在不超過(guò)所有資源限量的條件下,如何確定產(chǎn)量以得到最大的利潤(rùn)

12、.用z表示利潤(rùn),這時(shí).綜合上述,此計(jì)劃問(wèn)題可用數(shù)學(xué)模型表示為: 目標(biāo)函數(shù): 約束條件: 3.2 兩個(gè)變量的線性規(guī)劃問(wèn)題的圖解法現(xiàn)在我們用圖解法來(lái)解上述的例1:在以為坐標(biāo)軸的直角坐標(biāo)系中,非負(fù)條件【精品文檔】束條件都代表一個(gè)半平面,如約束條件是代表以直線為邊界的左下方的半平面.若同時(shí)滿足:x1x2Ox1+2x2=84x1=164x2=12Q3Q2Q1Q4,和的約束條件的點(diǎn),必然落在坐標(biāo)軸和由這三個(gè)半平面交成的區(qū)域內(nèi)(如下圖).陰影區(qū)域中的每一個(gè)點(diǎn)(包括邊界)都是這個(gè)線性規(guī)劃問(wèn)題的解,因而此區(qū)域是此線性規(guī)劃問(wèn)題的解集合,稱它為可行域.再來(lái)分析目標(biāo)函數(shù).在這個(gè)坐標(biāo)平面上,它可表示以z為參數(shù),以為斜率

13、的一族平行線:.位于同一直線上的點(diǎn),具有相同的目標(biāo)函數(shù)值,因而稱它為“等值線”.當(dāng)z值由小變大時(shí),直線沿其法線方向向右上方移動(dòng)當(dāng)移動(dòng)到點(diǎn)時(shí)，使z值在可行域邊界上實(shí)現(xiàn)最大化（如下圖）:這就得到了例的最優(yōu)解對(duì)應(yīng)的點(diǎn),點(diǎn)的坐標(biāo)為.于是可計(jì)算出滿足所有約束條件的最大值這說(shuō)明該廠的最優(yōu)生產(chǎn)計(jì)劃方案是：生產(chǎn)件產(chǎn)品，生產(chǎn)件產(chǎn)品，可得最大利潤(rùn)為14元【拓展延伸探究】例2 預(yù)算有2000元購(gòu)買單價(jià)為50元的桌子和20元的椅子，希望使桌椅的總數(shù)量盡可能的多，但椅子數(shù)不少于桌子數(shù)，且不多于桌子數(shù)的倍，問(wèn)桌子和椅子各購(gòu)買多少？分析這是生活實(shí)際中的一個(gè)物資采購(gòu)問(wèn)題，可歸結(jié)為線性規(guī)劃問(wèn)題，利用圖解法進(jìn)行求解。解設(shè)桌子和椅

14、子各購(gòu)買x、y張，則x、y必須滿足線性約束條件其目標(biāo)函數(shù)z=x+y。由 解得故圖14中點(diǎn)A的坐標(biāo)為。由 解得故圖中點(diǎn)B的坐標(biāo)為。滿足以上條件的可行域?yàn)槿鐖D所示的陰影部分（包括邊界和內(nèi)部），以A、B、O為頂點(diǎn)三角形區(qū)域。動(dòng)直線z=x+y表示斜率為1，在y軸上的截距為z的直線，如圖所示的虛線，當(dāng)動(dòng)直線運(yùn)動(dòng)到如圖所示的B點(diǎn)時(shí)，z的取值最大，此時(shí)x=25，。但由于x、y的取值均為整數(shù)，故y應(yīng)取37，即購(gòu)買25張桌子、椅子37張，是最優(yōu)選擇。點(diǎn)悟：由于本題是一個(gè)實(shí)際問(wèn)題，當(dāng)求得最優(yōu)解后，顯然它不滿足題意，故應(yīng)取最優(yōu)解的近似值，這便是實(shí)際問(wèn)題與一般的非應(yīng)用問(wèn)題的最大區(qū)別。在實(shí)際問(wèn)題中椅子必須是整數(shù)，所以x

15、=25,y=37。3.3 用單純?cè)ń鈨蓚€(gè)變量的線性規(guī)劃問(wèn)題例3：某車間生產(chǎn)甲、乙兩種產(chǎn)品，已知制造一件甲產(chǎn)品需要種元件個(gè),種元件個(gè)；制造一件乙產(chǎn)品需要種元件個(gè)，種元件個(gè).現(xiàn)因某種條件限制,只有A種元件180,B種元件135個(gè)；每件甲種產(chǎn)品可獲利20元, 每件乙種產(chǎn)品可獲利15元.試問(wèn)在這種條件下,應(yīng)該生產(chǎn)甲、乙兩種產(chǎn)品各多少件才能得到最大利潤(rùn)?解: 設(shè)應(yīng)該生產(chǎn)甲產(chǎn)品件,乙產(chǎn)品件,才能得到最大利潤(rùn)元.根據(jù)題意,此問(wèn)題可用數(shù)學(xué)模型表示為: 目標(biāo)函數(shù) 滿足約束條件 將上述問(wèn)題化成標(biāo)準(zhǔn)形式： 添加的松弛變量x3和x4在約束方程組中其系數(shù)列正好構(gòu)成一個(gè)2階單位陣，它們可以作為初始基變量，初始基可行解為

16、X=（0, 0, 180,135）表1cj201500CB基bx1x2x3x40X318052100X41353301cj-zj02015-00由于只有2> 0，說(shuō)明表中基可行解不是最優(yōu)解，所以確定x1為換入非基變量；以x1的系數(shù)列的正分量對(duì)應(yīng)去除常數(shù)列，最小比值所在行對(duì)應(yīng)的基變量作為換出的基變量。因此確定5為主元素（表1中以防括號(hào)括起），意味著將以非基變量x2去置換基變量x6，采取的做法是對(duì)約束方程組的系數(shù)增廣矩陣實(shí)施初等行變換，將x1的系數(shù)列(20,15)T變換成x3的系數(shù)列(0,1)T，變換之后重新計(jì)算檢驗(yàn)數(shù)。變換結(jié)果見(jiàn)表2表2cj201500CB基bx1x2x3x40X33612/51/500X42709/5-3/51cj-zj-72007-40再按上述方法可得表3表3cj201500CB基bx1x2x3x40X330103/5-2/90X41501-1/55/9cj-zj-88900-1/5-7此時(shí)，2個(gè)非基變量的檢驗(yàn)數(shù)都小于0，3= -1/5，4= -7，表明已求得最優(yōu)解：。去除添加的松弛變量，原問(wèn)題的最優(yōu)解為：,最打值為20*30+15*15=825。若企業(yè)在生產(chǎn)、運(yùn)輸、市場(chǎng)營(yíng)銷等方面，沒(méi)有很好地