線性規(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)濟利益。如：當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟效益（如產(chǎn)品量最多，利潤最大）。一.背景介紹如果產(chǎn)出量與投入量存在（或近

2、似存在）比例關(guān)系，則可以寫出投入產(chǎn)品的線性函數(shù)式：， （1）若將（1）式中第（）個線性方程作為待求的目標(biāo)函數(shù)，其余個線性方程作為資源投入的限制條件（或約束條件），則（1）式變?yōu)椋篛PT. ST. > ( =, < ), . （2） （2）式特點是有個待求的變量（）；有1個待求的線性目標(biāo)函數(shù)，有個線性約束等式或不等式，其中（）為有限的資源投入常量。將客觀實際問題經(jīng)過系統(tǒng)分析后，構(gòu)建線性規(guī)劃模型，有決策變量，目標(biāo)函數(shù)和約束條件等構(gòu)成。1決策變量（Decision Variable,DV）在約束條件范圍內(nèi)變化且能影響（或限定）目標(biāo)函數(shù)大小的變量。決策變量表示一種活動，變量的一組數(shù)據(jù)代表一

3、個解決方案，通常這些變量取非負值。2約束條件（Subject To,ST）在資源有限與競爭激烈的環(huán)境中進行有目的性的一切活動，都應(yīng)考慮是否符合實際，有沒有可行性，因而要構(gòu)造基于科學(xué)預(yù)測的綜合性約束（或限定）條件。3目標(biāo)函數(shù)（Objective Function,OF）人們有目的活動，總是希望獲得最滿意的目標(biāo)值，該目標(biāo)值可以表達成決策變量的一個函數(shù)，即目標(biāo)函數(shù)。根據(jù)需要，目標(biāo)函數(shù)可以取極大化，極小化兩種類型，即求最優(yōu)解。4影子價格（Shadow Price），用線性規(guī)劃方法計算出來的反映資源最優(yōu)使用效果的價格。用線性規(guī)劃方法求解資源最優(yōu)利用時，即在解決如何使有限資源的總產(chǎn)出最大的過程中，得出相應(yīng)

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

5、變量（），目標(biāo)函數(shù)的變量系數(shù)用表示，稱為價值系數(shù)。約束條件的變量系數(shù)用表示，稱為工藝系數(shù)。約束條件右端的常數(shù)用表示，稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達式可寫成：ST. , , 四線性規(guī)劃模型處理1. 圖解法就是在平面直角坐標(biāo)系上畫出各個約束條件所容許變化的范圍，通過圖上作業(yè)法求到最優(yōu)解和目標(biāo)函數(shù)極值。圖解法只適用于求解兩個決策變量的Lp（線性規(guī)劃）問題。2. 單純形法 給定一般的Lp問題：。 建立Lp問題的典式： 。 計算檢驗數(shù)：。利用進行基可行解的最優(yōu)性檢驗（i），人工變量，判定，為最優(yōu)解，輸出最優(yōu)解，。（ii）>0 (至少有一個>0，且>0)轉(zhuǎn)下步。 選擇進基變量

6、>0=，列的為進基變量。 選擇退基變量>0=,行的退基。 確定主元>0，根據(jù)主元進行行換基：（意為初等變換）。利用新基對，進行基變換：；，再轉(zhuǎn)第三步。3. 對偶單純形法（為求影子價格作準(zhǔn)備） 確定為Lp問題的一個初始基，其對應(yīng)的變量為。 判斷的可行性：若，則是Lp問題的最優(yōu)解，這時計算停止，輸出最優(yōu)解。否則進行第步。 若存在，使得<0，且在單純形表中與對應(yīng)行的非基變量的系數(shù)全部非負，則Lp問題無可行解；否則進行第步。確定基變量：令<0，對應(yīng)的基變量為為出基變量。 確定進基變量：計算<0=。選擇對應(yīng)的非基變量為進基變量。行列交叉的元素為主元。以為主元，按單純形

7、法換基迭代運算，得到一個新的基可行解，仍記為，返回到五線性規(guī)劃舉例例1（圖形解）這個問題的圖解如圖1所示。引進松弛變量x3，x4³0，問題變成為標(biāo)準(zhǔn)形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3x4³0OABCDx1x23210123x3=0x4=0x1=0x2=0 其解如陰影部分所示例2.求線性規(guī)劃 (對偶單純形求解)引入多余變量x5、x6把約束化為等式，然后再給兩邊同乘以（-1）后約束變?yōu)椋?-x1 -2x2 -3x3 -x4 + x5 =-2 -2x1 +x2 - x3 + 3x4 +x6 =-3  

8、   得對偶單純形表： Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 -2 -1 -2 -3 -1 1 0 0 x6 -3 -2 1 -1 3 0 1 Zj 0 0 0 0 0 0 Zj -Cj -2 -3 -5 -6 0 0 此時基本解為X=（0，0，0，0，-2，-3），不可行。所以進行第二步。 因為min-3，-2=-3，所以x6為換出變量；又因為min-2/-2 ，-5/-1=1，所以x1為換入變量，就是要將x1下的系數(shù)列向量由 變換成 形式（和以前學(xué)過的單純形法中的線性變換完全一致）。做行線性變換， 行（2）×

9、;（-1/2）；行（1）+行（2）后得出另一個基本解為：X=（3/2，0，0，0，-1/2）此時單純形表如下：Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 0 x5 -1/2 0 -5/2 -5/2 -5/2 1 -1/2 2 x1 3/2 1 -1/2 1/2 -3/2 0 -1/2 Zj 2 -1 1 -3 0 -1 Zj -Cj 0 -4 -4 -9 0 -1 仍然不是可行解，還要繼續(xù)求解。 因為-1/2 < 0,所以x5為換出變量；由因為=8/5，所以x2和x3都可以作為換入變量，任選其中一個x2 ，做線性變換： 行（1）×（-2/5

10、）；行（2）+行（1）×（1/2） 得到一個基本解為X=（8/5，1/5，0，0，0），因解是可行的，所以是滿足最優(yōu)檢驗下的基本可行解因而也是最優(yōu)解。此時單純形表如下 Cj 2 3 5 6 0 0 CB XB b x1 x2 x3 x4 x5 x6 3 x2 1/5 0 1 1 1 -2/5 1/5 2 x1 8/5 1 0 1 -1 -1/5 -2/5 Zj 2 3 5 1 -8/5 -1/5 為了實現(xiàn)縮短作出最優(yōu)方案的時間，運用MATLAB編程，運用計算機模擬計算處理。MATLAB是MATrix LABoratory的縮寫，它將計算可視化和編程功能集成在非常便于使用的環(huán)境中，是一個交互式的，以距陣計算為基礎(chǔ)的科學(xué)和工程計算軟件