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

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

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

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

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

5、變量（），目標函數(shù)的變量系數(shù)用表示，稱為價值系數(shù)。約束條件的變量系數(shù)用表示，稱為工藝系數(shù)。約束條件右端的常數(shù)用表示，稱為資源限量。則線性規(guī)劃數(shù)學模型的一般表達式可寫成：ST. , , 四線性規(guī)劃模型處理1. 圖解法就是在平面直角坐標系上畫出各個約束條件所容許變化的范圍，通過圖上作業(yè)法求到最優(yōu)解和目標函數(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. 對偶單純形法（為求影子價格作準備） 確定為Lp問題的一個初始基，其對應的變量為。 判斷的可行性：若，則是Lp問題的最優(yōu)解，這時計算停止，輸出最優(yōu)解。否則進行第步。 若存在，使得<0，且在單純形表中與對應行的非基變量的系數(shù)全部非負，則Lp問題無可行解；否則進行第步。確定基變量：令<0，對應的基變量為為出基變量。 確定進基變量：計算<0=。選擇對應的非基變量為進基變量。行列交叉的元素為主元。以為主元，按單純形

7、法換基迭代運算，得到一個新的基可行解，仍記為，返回到五線性規(guī)劃舉例例1（圖形解）這個問題的圖解如圖1所示。引進松弛變量x3，x4³0，問題變成為標準形式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ù)列向量由 變換成 形式（和以前學過的單純形法中的線性變換完全一致）。做行線性變換， 行（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ǔ)的科學和工程計算軟件