線性規(guī)劃模型及其舉例

1、線性規(guī)劃模型及其舉例摘要：在日常生活中，我們常常對一個問題有諸多解決辦法，如何尋找最優(yōu)方案，成為關(guān)鍵，本文提出了線性規(guī)劃數(shù)學(xué)模型及其舉例，在一定約束條件下尋求最優(yōu)解的過程，目的是想說明線性規(guī)劃模型在生產(chǎn)中的巨大應(yīng)用。關(guān)鍵詞：資源規(guī)劃；約束條件；優(yōu)化模型；最優(yōu)解在工農(nóng)業(yè)生產(chǎn)與經(jīng)營過程中，人們總想用有限的資源投入，獲得盡可能多的使用價值或經(jīng)濟(jì)利益。如：當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源(如資金、設(shè)備、原材料、人工、時間等)去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益(如產(chǎn)品量最多，利潤最大)。一. 背景介紹如果產(chǎn)出量與投入量存在(或近

2、似存在)比例關(guān)系，則可以寫出投入產(chǎn)品的線性函數(shù)式：f(x)=ax,i=1,2,m,m+1(1)iijjj=1若將(1)式中第(m+1)個線性方程作為待求的目標(biāo)函數(shù)，其余m個線性方程作為資源投入的限制條件(或約束條件)，則(1)式變?yōu)椋篛PT.f(x)=工cxjjj=1ST.工ax(=,0,j=1,2,nj(2)式特點(diǎn)是有n個待求的變量x.(j=1,2,n);有1個待求的線性目標(biāo)函數(shù)f(x)，有m個線j性約束等式或不等式，其中b(i=1,2,m)為有限的資源投入常量。將客觀實(shí)際問題經(jīng)過系統(tǒng)分i析后，構(gòu)建線性規(guī)劃模型，有決策變量，目標(biāo)函數(shù)和約束條件等構(gòu)成。1決策變量(DecisionVariabl

3、e,DV)在約束條件范圍內(nèi)變化且能影響(或限定)目標(biāo)函數(shù)大小的變量。決策變量表示一種活動，變量的一組數(shù)據(jù)代表一個解決方案，通常這些變量取非負(fù)值。2約束條件(SubjectTo,ST)在資源有限與競爭激烈的環(huán)境中進(jìn)行有目的性的一切活動，都應(yīng)考慮是否符合實(shí)際，有沒有可行性，因而要構(gòu)造基于科學(xué)預(yù)測的綜合性約束(或限定)條件。3. 目標(biāo)函數(shù)(ObjectiveFunction,0F)人們有目的活動，總是希望獲得最滿意的目標(biāo)值，該目標(biāo)值可以表達(dá)成決策變量的一個函數(shù)，即目標(biāo)函數(shù)。根據(jù)需要，目標(biāo)函數(shù)可以取極大化，極小化兩種類型，即求最優(yōu)解。4影子價格(ShadowPrice),用線性規(guī)劃方法計算出來的反映資

4、源最優(yōu)使用效果的價格。用線性規(guī)劃方法求解資源最優(yōu)利用時，即在解決如何使有限資源的總產(chǎn)出最大的過程中，得出相應(yīng)的極小值，其解就是對偶解，極小值作為資源的經(jīng)濟(jì)評價，表現(xiàn)為影子價格。二. 建模的基本步驟1. 確定目標(biāo)函數(shù)(按照模型所需要解決的問題，用數(shù)學(xué)函數(shù)來描述目標(biāo))2. 確定決策變量(目標(biāo)的實(shí)現(xiàn)與那些變量有關(guān)，這里有主要變量和次要變量，在建模的初期可以進(jìn)考慮主要變量對目標(biāo)的影響，隨后可以逐步增加變量的個數(shù))3. 確定約束條件(這是優(yōu)化模型建模過程中最重要，也是最難的，在很多情況下，是否能夠得到最優(yōu)解，最優(yōu)解是否合理，都是取決于約束條件的建立)4. 模型求解(使用數(shù)學(xué)工具或數(shù)學(xué)軟件求解)5. 結(jié)果

5、分析(分析結(jié)果的合理性、穩(wěn)定性、敏感程度等)三. 線性規(guī)劃的一般模型一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型，有m個約束，有n個決策變量x(j=1,2,n)，目標(biāo)函數(shù)的變量系數(shù)用c表示，c稱為價值系數(shù)。約束條件的變量系數(shù)用a表jjjij示，a稱為工藝系數(shù)。約束條件右端的常數(shù)用b表示，b稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一ijii般表達(dá)式可寫成：max(min)z二工cxjjj=1S.T.工ax,=)b,i=1,2,mijjij=1四線性規(guī)劃模型處理1. 圖解法就是在平面直角坐標(biāo)系上畫出各個約束條件所容許變化的范圍，通過圖上作業(yè)法求到最優(yōu)解和目標(biāo)函數(shù)極值。圖解法只適用于求解兩個決策變量的Lp(線性規(guī)劃)問題

6、。2. 單純形法lo給定一般的Lp問題：minz=cxIAx0。2o建立Lp問題的典式：minz=cc+cxINx+Bx=b0;x,x0。NNBBNBNB30計算檢驗(yàn)數(shù)：a=c-cB-1N。利用Q進(jìn)行基可行解x的最優(yōu)性檢驗(yàn)(i)Q0，x=0為最優(yōu)解，輸出最優(yōu)解X*=x,xT，Z*。BNBN(ii)a0(至少有一個a0，且p0)轉(zhuǎn)下步。Nkk40選擇進(jìn)基變量x:maxa,a0=a，k列的x為進(jìn)基變量。kNNkkb50選擇退基變量x:min0,0=0=0,1行的x0,根據(jù)主元進(jìn)行行換基：BB(V意為初等變換)。lk0170利用新基B對N，b，z進(jìn)行基變換：N=B-1N；b=B-1b=xBZ=cx再

7、轉(zhuǎn)第三步。BB3. 對偶單純形法(為求影子價格作準(zhǔn)備)10確定B為Lp問題的一個初始基，其對應(yīng)的變量為x0。020判斷x0的可行性：若x0=B-lb0，a0，則x0是Lp問題的最優(yōu)解，這時計算停止,BN輸出最優(yōu)解。否則進(jìn)行第30步。30若存在r(rei=1,2,m)，使得(B-ib)0，且在單純形表中與(B-ib)對應(yīng)行的非基變量rr的系數(shù)a全部非負(fù)，則Lp問題無可行解；否則進(jìn)行第40步。40確定基變量：令(B-1b)=maxl(B-1b)I,(B-1b)0，對應(yīng)的基變量為x為出基變量。lrrl50確定進(jìn)基變量：計算0=minjIa0二N。選擇0對應(yīng)的非基變量x為進(jìn)基變量。kajakkljlk

8、l行k列交叉的元素a為主元。lk60以a為主元，按單純形法換基迭代運(yùn)算，得到一個新的基可行解，仍記為xo，返回到20lk五線性規(guī)劃舉例例1.（圖形解）maxz=x+2x12x+x312st.彳x0V12這個問題的圖解如圖1所示。引進(jìn)松弛變量X,x0,問題變成為標(biāo)準(zhǔn)形式34maxz=X1+2x2-X1+x2+x3=3(1)x2+x4=1(2)X1x2x3x40其解如陰影部分所示例2.求線性規(guī)劃（對偶單純形求解）mino=2x+3x+5x+6x1234x+2x+3x+x2123431234x,x,x,x01234引入多余變量X、x把約束化為等式，然后再給兩邊同乘以（-1）后約束變?yōu)?56-x-2x

9、-3xx+x=-212345-2x1+x2-x+33x4+x=-36得對偶單純形表：此時基本解為X二（0，0，0，0，-2,-3），不可行。所以進(jìn)行第二步。因?yàn)閙in-3，-2=-3，所以x為換出變量；又因?yàn)閙in-2/-2，-5/-1=1，所以x為換入變61量，就是要將下的系數(shù)列向量由變換成。形式（和以前學(xué)過的單純形法中的線性變換完全一致）。做行線性變換，行（2）X（-1/2）；行（1）+彳亍（2）后得出另一個基本解為：X=（3/2,0，0，0，-1/2）此時單純形表如下：仍然不是CTj235600CBXBbX1X2X3X4X5X60X5-1/20-5/2-5/2-5/21-1/22X13/

10、21-1/21/2-3/20-1/2Zj2-11-30-1Z-Cjj0-4-4-90-1要繼續(xù)求解。因?yàn)?1/20,所以x為換出變量；由因?yàn)閙in二,二二二1|=8/5,所以x5555122222一和X3都可以作為換入變量，任選其中個X2,做線性變換:行(1)X(-2/5)；行(2)+行(1)X(1/2)得到一個基本解為X二(8/5,1/5,0,0,0),因解是可行的，所以是滿足最優(yōu)檢驗(yàn)下的基本可行解因而也是最優(yōu)解。此時單純形表如下CTj235600CBXBbX1X2X3X4X5X63X21/50111-2/51/52X18/5101-1-1/5-2/5Zj2351-8/5-1/5為了實(shí)現(xiàn)縮短作出最優(yōu)方案的時間，運(yùn)用MATLAB編程，運(yùn)用計算機(jī)模擬計算處理MATLAB是MATrixLABoratory的縮寫，它將計算可視化和編程功能集成在非常便于使用的環(huán)境中，是一個交