1、Operations Research 運籌學（OR）,主講：邢延銘,管理科學與工程學院信息管理及信息系統,第一章 線性規劃,1,一、線性規劃（Linear Programming),1947年由美國人丹齊克（Dantzing）提出,線性,x,y,O,x+y=1,1,1,x=2,y=3,2,3,規劃,LP(linear programming)的基本概念 LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經濟效益的優化方法。 LP有三個要素: 決策變量、目標函數、約束條件,二、 LP的數學模型難點,例題1生產計劃問題,美佳公司計劃制造I、II兩種家電產品。已知各制造一件時分別占用設備

2、A、B的臺時、調試時間、調試工序每天可用于這種家電的能力、各售出一件時的獲利情況，如表1-1所示。問該公司應制造兩種家電各多少件，使其獲取的利潤最大。,該計劃的數學模型,目標函數 Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,x1,x2,例2 營養配餐問題,假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質和800毫克的鈣。如果市場上只有四種食品可供選擇(當然可以擴充到n種食品），它們每千克所含的熱量和營養成分和市場價格見下表。問如何選擇才能在滿足營養的前提下使購買食品的費用最小？,各種食物的營養成分

3、表,解：設xj為第j種食品每天的購入量，則配餐問題的線性規劃模型為： min Z=14x1+6x2 +3x3+2x4 s.t. 1000 x1+800 x2 +900 x3+200 x4 3000 50 x1+ 60 x2 + 20 x3+ 10 x4 55 400 x1+200 x2 +300 x3+500 x4 800 x1，x2 ， x3 ， x4 0,例3. 運輸問題,某名牌飲料在國內有三個生產廠，分布在城市A1、A2, A3,其一級承銷商有4個，分布在城市B1、B2、B3、B4，已知各廠的產量、各承銷商的銷售量及從Ai到Bj的每噸飲料運費為Cij，為發揮集團優勢，公司要統一籌劃運銷問

4、題，求運費最小的調運方案。,(1)決策變量。設從Ai到Bj的運輸量為xij， (2)目標函數。則運費最小的目標函數為 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)約束條件。產量之和等于銷量之和,故要滿足： 供應平衡條件,x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3,銷售平衡條件,x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=1,非負性約束 xij0 (i=1,2,3；j=1,2,

5、3,4),例4.倉庫租用問題 捷運公司擬在下一年度的1-4月的4個月內需租用倉庫堆放物資.已知各月份所需倉庫面積數列于表1.倉庫租借費用隨合同期而定,期限越長,折扣越大,具體數字見表2.租借倉庫的合同每月初都可辦理,每份合同具體規定租用面積數和期限.因此該廠可根據需要,在任何一個月初辦理租借合同.每次辦理時可簽一份,也可簽若干份租用面積和租借期限不同的合同,試確定該公司簽訂租借合同的最優決策,目的是使所付租借費用最小.,表1,表2,解:1)設決策變量xij表示捷運公司在第i(i=1,2,3,4)個月初簽訂的租借期為j(j=1,2,3,4)個月的倉庫面積的合同(單位為100m2). 因5月份起該

6、公司不需要租借倉庫,故x24,x33,x34,x42,x43,x44均為零,2)目標函數:使總的租借費用最小,3)約束條件:每個月份所需倉庫面積的限制,s.t.,例5.合理下料問題,合理下料問題（Reasonably Cutting Problem）某型號的圓鋼8米長，需截取長2.5米、長2.0米、長1.3米的毛坯分別為100根、150根、200根。 問： 如何下料，才能既滿足需求，又使總用料最少 如何下料，才能既滿足需求，又使總余料最少,此型號的圓鋼8米長，截取的方案有：,四、線性規劃的一般形,線性規劃問題的數學模型有各種不同的形式，如 目標函數有極大化和極小化； 約束條件有“”、“”和“”

7、三種情況； 決策變量一般有非負性要求，有的則沒有。,為了求解方便，特規定一種線性規劃的標準形式，非標準型可以轉化為標準型。 標準形式為： 目標函數極大化， 約束條件為等式， 右端常數項bi0， 決策變量非負。,五、線性規劃問題的標準形式,標準形式為:,目標函數最大 約束條件等式 決策變量非負 右端常數非負,目標函數極小化問題 minZ=CX，只需將等式兩端乘以 -1 即變為極大化問題。 右端常數項非正 兩端同乘以 -1 約束條件為不等式 -當約束方程為“”時，左端加入一個非負的松弛變量； -當約束條件為“”時，左端減去一個非負的剩余變量。 決策變量xk無約束 令xk=xk-x k，xk，x k

8、 0，用xk、x k 取代模型中xk 決策變量xk0 令xk=-xk,顯然xk 0,非標準型向標準型轉化,例：目標函數 Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,化為標準型：目標函數 Max Z = 2x1 + 1x2 約束條件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,+0 x3+0 x4+0 x5,Max,例 2：,解 ：化為標準形為,作業：習題1.2中的（1）（2）,簡寫為,用矩陣表示,C價值向量 b資源向量 X決

9、策變量向量 A技術矩陣 P 技術向量,用向量表示,六、線性規劃的圖解法,由中學知識可知：y=ax+b是一條直線，同理：Z=2x1+x2x2=Z-2x1也是一條直線，以Z為參數的一族等值線。 5x2 15 x2 3 是直線 x2=3 下方的半平面。 所有約束的半平面的交集稱之為可行域，可行域內的任意一點，就是滿足所有約束條件的解，稱之為可行解。,例：目標函數 Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1、 x2 0,目標函數 Max Z = 2x1 + 1x2,可以先假設 2x1 + 1x2=4,再假設 2x1 + 1x2=6,2

10、x1 + 1x2=8,由圖中可知目標函數相交于Q2這一點上，由6x1 + 2x2 = 24 x1 + x2 = 5 聯合求解得到為（x1,x2)=(3.5,1.5),則目標函數為z=8.5,圖解法求解步驟,由全部約束條件作圖求出可行域； 作目標函數等值線，確定使目標函數最優的移動方向； 平移目標函數的等值線，平行線移出可行域之前的最后一個交點，就是最優點，算出最優值。,七、線性規劃問題求解的 幾種可能結果,1、唯一最優解（見上頁） 2、多重最優解：無窮多個最優解。若在兩個頂點同時得到最優解，則它們連線上的每一點都是最優解。,3、無界解：線性規劃問題的可行域無界，使目標函數無限增大而無界。（缺乏

11、必要的約束條件）,4、無解（或無可行解）：若約束條件相互矛盾，則可行域為空集。,圖解法的幾點結論:（由圖解法得到的啟示）,可行域是有界或無界的凸多邊形。 若線性規劃問題存在最優解，它一定可以在可行域的頂點得到。 若兩個頂點同時得到最優解，則其連線上的所有點都是最優解。 解題思路：找出凸集的頂點，計算其目標函數值，比較即得。,練習：用圖解法求解LP問題,圖解法 （練習）,圖解法 （練習）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,圖解法 （

12、練習）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40 x2 = 272,圖解法 （練習）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),圖解法 （練習）,x2,18 16 14 12 10 8 6 4 2 0,| 246810121

13、41618,x1,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,(0,6.8),最優解 (3,6),4x1+ 6x2=48 2x1+ 2x2 =18,1.3線性規劃解的概念及基本定理,可行解：滿足約束條件AX=b,X0的解。 最優解：使目標函數最優的可行解，稱為最優解。,基 mn，且m個方程線性無關，即矩陣A的秩為m；根據線性代數定理可知，nm，則方程組有多個解，這也正是線性規劃尋求最優解的余地所在。 若B是矩陣A中mm階非奇異子矩陣（B0），則B是線性規劃問題的一個基。不妨設：, j=1，2，,m 基向量。 ，j=1，2，,m 基變量。 , j=

14、m+1,n 非基變量。,線性方程組的增廣矩陣,例LP的標準型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,基矩陣： 系數矩陣A中任意m列所組成的m階非奇異子矩陣，稱為該線性規劃問題的一個基矩陣。 或稱為一個基，用B表示。 稱基矩陣的列為基向量，用Pj表示(j=1,2,m) 。,的基矩陣B，如下：,基變量： 與基向量Pj相對應的m個變量xj稱為基變量， 其余的n-m個變量為非基變量。 基解： 令所有非基變量等于零，對m個基變量所求的解， 對應一個

15、特定的基矩陣能求得一組唯一解，這個對應于基的解稱為基解。,基變量是x3, x4, x5 非基變量是x1, x2 令非基變量x1=x2=0，得到一個基解 x3=8，x4=12， x5=36,基可行解：滿足非負性約束的基解稱為基可行解。 可行基：對應于基可行解的基，稱為可行基。 最優基：最優解對應的基矩陣，稱為最優基。,非 可 行 解,可 行 解,基 解,例：求基解、基可行解、最優解。,最優解,解：,二、凸集及其頂點,凸集概念： 設D是n維線性空間Rn的一個點集，若D中的任意兩點x(1),x(2)的連線上的一切點x仍在D中，則稱D為凸集。 即：若D中的任意兩點x(1),x(2) D，存在01 使得

16、 x= x(1)+(1- )x(2) D,則稱D為凸集,頂點:若K是凸集，XK；若X不能用不同的兩點的線性組合表示為： 則X為頂點.,凸集,三、幾個基本定理的證明,證明:,定理1: 若線性規劃問題存在可行域, 則其可行域: 是凸集.,只要驗證X在D中即可,引理：可行解X為基可行解 X的正分量對應的列向量線性無關,定理3：若可行域有界，線性規劃 問題的目標函數一定可以在 其可行域的頂點上達到最優。,定理2：線性規劃問題的基可性解X 對應于可行域D的頂點。,幾點結論：,線性規劃問題的可行域是凸集。 基可行解與可行域的頂點一一對應，可行域有有限多個頂點。 最優解必在頂點上得到。,1.4單純形法的基本

17、原理,單純形法(Simplex Method)是美國人丹捷格 (G.Dantzig)1947年創建的 這種方法簡捷、規范，是舉世公認的解決線性規劃問題行之有效的方法。,例1的標準型 ： 目標函數 Max Z = 2x1 + 1x2+0 x3+0 x4+0 x5 約束條件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,LP的代數方法,定理1.線性規劃問題如果存在可行域，則其 可行域一定是一個凸集。 定理2.線性規劃問題的基可行解與凸集頂點是一一對應的。 定理3.線性規劃問題如果存在最優解，則一定存在一個基可

18、行解是最優解。（或者說最優解如果存在，一定出現在凸集的頂點上）。,線性規劃問題求最優解思路,step1.找到一個初始的基可行解。 step2.判斷是否最優。 如果最優，則結束。否則轉step3。 Step3.轉到與初始基可行解相鄰的下一個基可行解，轉化時應遵循目標函數值增大的原則。,1.確定初始基可行解,對標準型線性規劃問題 在約束中總存在一個單位矩陣 我們以這個單位矩陣為基矩陣，令非基變量都=0，得到一個初始基解 因為b=0，所以這個基解是一個基可行解。,標準形式為:,2.從一個基可行解轉換為相鄰的基可行解,定義：如果兩個基可行解之間的變換只需要變換一個基變量，則稱這兩個基可行解相鄰。,3.

19、最優性檢驗,將兩個基可行解分別帶入目標函數中得：,代入目標消去基變量，得到非基變量xj的檢驗數 j。,判斷最優（即規則） 會出現以下四種情況： （1）若對于一 切非基變量的解指數j均有j 0 則當前基本 可行解為最優解。 （2）若所有非基變量的檢測驗數 j 0，其中某個基變量的檢驗數 k=0，而該變量的系數列向量Pk中存在正分量，則說明該問題在兩個頂點上同時達到最優，該問題有無窮多最優解。,（3）若某個非基變量XK的檢驗數k 0，但其對應的列向量PK中，每一個元素aik(I=1,2,3m)均為非正數，這時該線性規劃問題無解。 （4）若存在非基變量檢驗數k 0，其對應的系數列向量Pk中，至少有一

20、個aik0,則問題還沒有得到最優解，應進行下步。,基變換,（1）換入變量的確定 以k對應的非基變量xk做為換入變量，當然任選也可以，或選取腳標最小的一個 （2）換出變量的確定 改進目標 換入變量xk原是非基變量，取值為0，現在將其作為基變量，取值為正。要保持除xk以外的原非基變量繼續為0，迫使某個原基變量為0，當xk取值超過任一bi/aik時，將使第i個基變量xBi0，就破壞了非負性約束條件。所以，比值i=bi/aik表示用xk去替換xBi時的取值限度，為保持解的可行性，取,即原其變量xl出基，為了表示清楚用Xbl表示換出變量，即規則 若不存在, 則Z，沒有有限最優解。,主元變換（迭代或旋轉變

21、換） xk進基， xl出基，其相應的系數列向量分別是,為了使Xk和XBl進行對換，須把Pk變為單位列向量，這可以通過系數矩陣的初等變換變來完成,1,alk,將上式中的第L行除以alk,得到,用第I行減去aik與上式的乘積，各行元素的變換關系式為,變換后新的增廣矩陣為：,這樣就進行了一次新的變換。另非基變量都為0，就會得到新的一組其可行解。,LP的表格法,表格單純形法，是對上節討論的方法步驟進行具體化、規范化、表格化的結果。,一、單純形法表,將線性規劃問題化成標準型。 找出或構造一個m階單位矩陣作為初始可行基，建立初始單純形表。 計算各非基變量xj的檢驗數j=Cj-CBB-1Pj ，若所有j0，

22、則問題已得到最優解，停止計算，否則轉入下步。 在大于0的檢驗數中，若某個k所對應的系數列向量Pk0，則此問題是無解，停止計算，否則轉入下步。 根據maxjj0=k原則，確定xk為換入變量(進基變量)，再按規則計算：=minbi/aik| aik0=bl/ alk 確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。 以alk為主元素進行迭代，把xk所對應的列向量變為單位列向量，即alk變為1，同列中其它元素為0，轉第 步。,二、單純形法的計算步驟,三、單純形法計算舉例,例：目標函數 Max Z = 2x1 + 1x2 約束條件 5x2 15 6x1 + 2x2 24 x

23、1 + x2 5 x1、 x2 0,化為標準型：目標函數 Max Z = 2x1 + 1x2+0 x3+0 x4+0 x5 約束條件 5x2 + x3 = 15 6x1 + 2x2 + x4 = 24 x1 + x2 + x5 =5 x1、 x2、x3、x4、x5 0,填入初始單純形表,最優解 :X*=(3.5,1.5,7.5,0,0)T，Z*=8.5,表準化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0,此時，檢驗數2=11 0，還沒有得到最優解。 確定x2進基，但x2所在列的系數向量元素非正，無界

24、 值不存在，有進基變量但無離基變量。,1.5人工變量問題,一、人工變量,用單純形法解題時，需要有一個單位陣作為初始基。 當約束條件都是“”時，加入松弛變量就形成了初始基。 但實際存在“”或“”型的約束，沒有現成的單位矩陣。,問題：線性規劃問題 化為標準形時，若約束 條件的系數矩陣中不存 在單位矩陣，如何構造 初始可行基？,采用人造基的辦法：人工構造單位矩陣 在沒有單位列向量的等式約束中加入人工變量，構成原線性規劃問題的伴隨問題，從而得到一個初始基。 人工變量是在等式中人為加進的，只有它等于0時，約束條件才是它本來的意義。,加入 人工變量,設線性規劃問題的標準型為：,系數矩陣為 單位矩陣， 可構

25、成初始 可行基。,約束條件已改變， 目標函數如何調整？,“懲罰” 人工變量！,（1）大M法 （2）兩階段法,一、大 M 法,人工變量在最大化的目標函數中的系數為 M（最小化的為+M）, 其中，M 為任意大的正數。,目標函數中添加“罰因子” 最大化-M（M是任意大的正數） 為人工變量系數，只要人 工變量0，則目標函數 不可能實現最優。,例: 求解線性規劃問題,加入松弛變量和剩余變量,化成標準型,加入人工變量構造初始可行基.,求解結果出現檢驗數非正 若基變量中含非零的人工變量， 則無可行解； 否則，有最優解。,用單純形法求解（見下頁）。,目標函數中添加“罰因子” -M為人工變量系數，只要人 工變量

26、0，則目標函數 不可能實現最優。,表1（初始單純形表）,主元,表2,主元,表3,主元,表4,最優解為 目標函數 值 z=2,檢驗數均非正，此為最終單純形表,M在計算機上處理困難。 分階段處理 先求初始基，再求解。,二、兩階段法,第一階段: 構造如下的線性規劃問題,加入人工變量 后的系數矩陣 為單位矩陣， 可構成初始 可行基。,目標函數僅含人工變量，并要求實現最小化。 若其最優解的目標函數值不為0，也即最優解的基變量中含有非零的人工變量，則原線性規劃問題無可行解。,用單純形法求解上述問題,若=0,進入第二階段,否則,原問題無可行解。 第二階段：去掉人工變量，還原目標函數系數，做出初始單純形表。

27、用單純形法求解即可。,下面舉例說明，仍用大M法的例。,例：,加入松弛變量和剩余變量,化成標準型,解：,構造第一階段問題并求解,注意，此時目標函數不滿足標準型條件，所以應將目標函數也化成標準型 用單純形法求解,（第一階段、求min ）,表1,主元,1 0 0 0 -1 1 0 0 0,0 -1 0,0 0 -1,x4 x5 x6,（第一階段、求min ）,表2,主元,1 -2 2 0 -1 1 0 0 0,0 0 -1,0 0 -1,x4 x5 x6,（第一階段、求min ）,表3：最終單純形表,進 入 第 二 階 段,不含人工變量且=0,第二階段,將去掉人工變量， 還原目標函數系數，做 出初始

28、單純形表。,1 0 0 0 -1,1/3 -2/3 0 -1 2/3 -4/3,0 0,x4 x5,第二階段,0 0 0 -1/3 -1/3,最優解為 目標函數 值 z=2,最優基,x3,x1,x2,最優基的逆,LP補遺,進基變量相持： 單純形法運算過程中，同時出現多個相同的j最大。 在符合要求的j(目標為max：j0，min：j0)中，選取下標最小的非基變量為換入變量；,離基變量相持： 單純形法運算過程中，同時出現多個相同的最小值。 繼續迭代，便有基變量為0，稱這種情況為退化解。 選取其中下標最大的基變量做為換出變量。,多重最優解： 最優單純形表中，存在非基變量的檢驗數j=0。 讓這個非基變

29、量進基，繼續迭代，得另一個最優解。,無界解： 在大于0的檢驗數中，若某個k所對應的系數列向量Pk0，則此問題是無界解。,無可行解： 最終表中存在人工變量是基變量。,1.6單純形法矩陣描述,為進一步加深對單純形法的理解以及為對偶理論和靈敏度分析打基礎，現在用矩陣形式描述單純形法的求解過程。前面講過線規劃標準型的矩陣表達式為,對于上式移項得,再左乘以B-1,代入目標函數得,單純形表的矩陣形式,例：,(1)、, 1 =C1 - CB B-1P1 =40 -(0 0 50) = 40 -(0,0,25) =40, A= C - CB B-1A=(40, 50, 0, 0, 0)- (0, 0, 50)

30、 =(40, 50, 0, 0, 0) -(0 0 25) = (40, 50, 0, 0, 0) -(0, 50, 0, 0, 25) = (40, 0, 0, 0, -25),1 2 1 0 0 3 2 0 1 0 0 2 0 0 1,1 2 1 0 0 3 2 0 1 0 0 2 0 0 1,B1-1,B2-1,B3-1,(1)、只須存貯原始數據A、B、C，每步需知B-1 。,(2)、每步必須計算的數據, 當某個 m+k 0時，需關鍵列：,1.6單純形法小結,基本概念,線性規劃模型 三個要素： 決策變量、目標函數、約束條件 線性性 線性規劃解的性質 線性規劃問題的可行域是凸集。,最優解必

31、在頂點上得到。 線性規劃求解方法 圖解法 單純形法,本次習題課內容,單純形法小結,一般線性規劃問題的標準化及初始單純形法表.,變量, 約束條件,目標函數,單純形法計算步驟框圖（下頁）,單純形法小結,LP的習題課,極小化線性規劃求解方法,極小化問題與極大化問題的解法，主要有一點區別，那就是進基變量的選取。由式 可知，若以極大化為目標，則當所有非基變量的檢驗數j0時，Z值達到最大。反之，若以極小化為目標，則當某個非基變量檢驗數j0時，若取xj0，將使Z值進一步變小，即使目標進一步優化；,當所有非基變量檢驗數j0時，若使任意非基變量xj0都會導致目標函數的增加從而偏離了極小化目標，于是可以認定此時的

32、解為最優解。 總而言之，極小化問題的判別準則是：j0 (j=1，2，n)時為最優，進基變量的選取是在負檢驗數中選取最小的一個k，它所對應的變量xk為換入變量。,舉例：,填入初始單純形表,所有的檢驗數大于0,得到最優解 X1=2/5 X2=38/5 Z=-30,一、已知某LP的初始單純形表和單純形法 迭代的表，求未知數al的值。,b=2,1 0,2,c/2=2 c=4,4,d/2=-1 d=-2,-2,-2a-1=-7 a=3,3,3,5,0,g=1 h=0,1=-1+e e=2,2,5,-3/2,解：,二、考慮LP問題 模型中 為參數，要求： （a）組成兩個新的約束(1)=(1)+(2), (

33、2)= (2)- 2(1) , 根據 (1),(2) ，以 為 基變量，列出初始單純形表；,（b）在表中，假定 ，則 為何值時， 為問題的最優基； （c）在表中，假定 ，則 為何值時， 為問題的最優基；,解：（a）兩個新的約束,以 為基變量，初始單純形表如下：,（b） 時， 最優基不變,（c） 時， 最優基不變,三、設線性規劃問題 （1）分別用圖解法和單純形法求解； （2）對照指出單純形表中的各基本可行 解對應圖解法中可行域的哪一頂點。,續,（3）若目標函數變為 討論c、d的值如何變化，使每個頂 點依次使目標函數達到最優。,解：化為標準型,1,2,2,1,最優解,10 5 0 0 0 9 3

34、4 1 0 0 8 5 2 0 1 10 5 0 0 0 21/5 0 14/5 1 -3/5 10 8/5 1 2/5 0 1/5 0 1 0 -2 5 3/2 0 1 5/14 -3/14 10 1 1 0 -1/7 2/7 0 0 -5/14 -25/14,O（0，0）,1,2,2,1,o,c d c/d 最優解的頂點 c/d5/2 Q1 c/d=5/2 Q1,Q2 0 0 3/40 不限 Q3 0 =0 - Q1 0 0 不限 Q1 0 0 不限 O,線性規劃的對偶理論與靈敏度分析,1.7線性規劃的對偶問題,一、對偶問題的提出 二、原問題與對偶問題的數學模型 三、原問題與對偶問題的對應

35、關系,對偶問題概念 任何一個線性規劃問題都有一個伴生的線性規劃問題，稱為其“對偶”問題。 對偶問題是對原問題從另一角度進行的描述，其最優解與原問題的最優解有著密切的聯系，在求得一個線性規劃最優解的同時也就得到對偶線性規劃的最優解，反之亦然。 對偶理論就是研究線性規劃及其對偶問題的理論，是線性規劃理論的重要內容之一。,一、對偶問題的提出,實例：某家電廠家利用現有資源生產兩種 產品， 有關數據如下表：,(1)如何組織生產,獲利最大 （2）如果外公司收購其資源，收購價格最低,如何安排生產， 使獲利最多？,設 產量 產量,設：設備A 元時 設備B 元時 調試工序 元時,付出的代價最小， 且對方能接受。

36、,出讓代價應不低于 用同等數量的資源 自己生產的利潤。,美佳能接受的條件： 收購方的意愿：,對 偶 問 題,原 問 題,廠 家,改寫成向量式,例2,例2,假設有客戶提出要求，購買工廠所擁有的工時和材料，為客戶加工別的產品，由客戶支付工時費和材料費。那么工廠給工時和材料制訂的最低價格應是多少，才值得出賣工時和材料 ?,出賣資源獲利應不少于生產產品的獲利; 約束 價格應該盡量低，這樣，才能有競爭力; 目標 價格應該是非負的,用y1和y2分別表示工時和材料的出售價格,總利潤最小 min W=3y1+9y2 保證A產品利潤 y1+y22 保證B產品利潤 y1+4y23 保證C產品利潤 y1+7y23

37、售價非負 y10 y20,min,max,3個約束 2個變量,2個約束 3個變量,一般規律,對偶問題對應表,例:,對偶問題為,寫出下面的線性規劃問題的對偶問題,對偶問題為：,對稱形式的對偶問題,對稱形式的對偶問題,對偶問題的特點 若原問題目標是求極大化，則對偶問題的目標是極小化，反之亦然 原問題的約束系數矩陣與對偶問題的約束系數矩陣互為轉置矩陣 極大化問題的每個約束對應于極小化問題的一個變量，其每個變量對應于對偶問題的一個約束。,一般線性規劃問題的對偶問題,1.8對偶問題的基本性質,對 偶 問 題,原 問 題,收 購,廠 家,引例,（ ）,原問題，最終單純形表：,對偶問題用兩階段法求解的最終的

38、單純形表,（ ）,（x1,x2）原問題 最優解,對偶問題 最優解,原問題與對偶問題對比，最終單純形表：,相反數！,兩個問題作一比較: 1.兩者的最優值相同 2.變量的解在兩個單純形表中互相包含 原問題最優解（決策變量） 對偶問題最優解（決策變量）,從引例中可見： 原問題與對偶問題在某種意義上來說，實質上是一樣的，因為第二個問題僅僅在第一個問題的另一種表達而已。,理論證明： 原問題與對偶問題解的關系,二、對偶問題的基本性質,（1）對稱定理： 定理： 對偶問題的對偶是原問題。,設原問題（1） 對偶問題（2）,（2）弱對偶性定理： 若 和 分別是原問題（1）及對偶問題（2）的可行解，則有,從弱對偶性

39、可得到以下重要結論： （1）極大化問題（原問題）的任一可行解所對應的目標函數值是對偶問題最優目標函數值的下界。極小化問題（對偶問題）的任一可行解所對應的目標函數值是原問題最優目標函數值的上界。 （2）若原問題可行，但其目標函數值無界（無上界），則對偶問題無可行解。 （3）若對偶問題可行，但其目標函數值無界（無下界），則原問題無可行解。 （4）若原問題有可行解而其對偶問題無可行解，則原問題目標函數值無界。 （5）對偶問題有可行解而其原問題無可行解，則對偶問題的目標函數值無界。,原問題,對偶問題,（3）最優性定理： 若 和 分別是（1）和（2）的 可行解，且有 則 分別是（1）和（2）的最優解 。

40、,則 為（1）的最優解， 反過來可知： 也是（2）的最優解。,證明：因為（1）的任一可行解 均滿足,（4）強對偶性定理 若原問題和對偶問題都有可行解，則兩者都有最優解，且最優解的目標函數值相等。,證明：設X*是原問題的最優解，則必有所有檢驗數0即,設Y=CBB-1，則,這表示Y*滿足對偶問題的約束條件。Y*是對偶問題的可行解，代入目標函數得,根據最優性，Y*是對偶問題的最優解，兩者最優值相等,（5）互補松弛性： 若 分別是原問題（1）與對偶問題（2）的可行解， 分別為（1）、（2）的松弛變量，則： 即：,為最優解,原問題第i條約束,A的第i行,說明：即如原始變量XJ*0 ，則與之相應的第J個對

41、偶約束方程為等式，即剩余變量YSJ=0；如果第J個對偶約束為嚴格不等式，即剩余變量YSJ0，則與之相對應的原始變量XJ*=0,另一方面：,對偶問題的第j條約束,證明：,充分性：設原問題為,對偶問題為：,原問題的目標函數可以變為,同理對偶目標函數可表示為：,互補松弛定理應用： （1）從已知的最優對偶解，求原問題最優解，反之亦然。 （2）證實原問題可行解是否為最優解。 （3）從不同假設來進行試算，從而研究原始、對偶問題最優解的一般性質。 （4）非線性的方面的應用。,以上性質同樣適用于非對稱形式。,例,化為標準型時：分別加上松馳變量X4，X5，X6構成標準型,化為標準型時：分別減去剩作變量y4，y5

42、，y6構成標準型,已知上例中對偶問題的最優解Y1*=0,Y2 * =8,Y3 * =2,利用互補松馳定理求原問題的最優解。,解： 將最優解Y1*=0,Y2 * =8,Y3 * =2代入對偶問題的數學模型，知Y40,Y5=0,Y6=0.剩余變量Y40，根據互補松馳性X*YS=0，則原始變量X1=0。 對偶變量Y1=0，而XSY*=0，則松馳變量X4=0,相應約束條件為不起作用約束。 同理，對偶變量Y2，Y30,則松馳變量X5=0，X6=0。 于是原問題約束條件為 2X1+X2=50 4X1+3X3=150 解之得X2=50，X3=50,當線性規劃原問題求得最優解 時，其對偶問題也得到最優解 ，且

43、代入各自的目標函數后有：,是線性規劃原問題約束條件的 右端項，它代表第 種資源的擁有量；,（3）,1.9影子價格,影子價格的定義,對偶變量 的意義代表在資源最優利用條件下對單位第 種資源的估價，這種估價不是資源的市場價格，而是根據資源在生產中作出的貢獻而作的估價，為區別起見，稱為影子價格（shadow price)。,影子價格的經濟意義,1資源的市場價格是已知數，相對比較穩定，而它的影子價格則有賴于資源的利用情況，是未知數。由于企業生產任務、產品結構等情況發生變化，資源的影子價格也隨之改變。,2影子價格是一種邊際價格。 在（3）式中， 。 說明 的值相當于在資源得到最優利用的生產條件下， 每增

44、加一個單位時目標函數 的增量。,（3）,幾何解釋,3資源的影子價格實際上又是一種機會成本. 在純市場經濟條件下,當第2種資源的市場價格低于1/4時，可以買進這種資源；相反當市場價格高于影子價格時，就會賣出這種資源。隨著資源的買進賣出，它的影子價格也將隨之發生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態。,4在對偶問題的互補松弛性質中有 這表明生產過程中如果某種資源 未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產中已耗費完畢。,5從影子價格的含義上考察單純形表的 檢驗數的經濟意義。,（4）,第j種產品的產值,生產第j中產品所消耗各項資源的

45、 影子價格的總和。（即隱含成本）,6一般說對線性規劃問題的求解是確定資源的最優分配方案，而對于對偶問題的求解則是確定對資源的恰當估價，這種估價直接涉及到資源的最有效利用。,經濟學研究如何管理 自己的稀缺資源,1.10對偶單純形法,一、對偶單純形法的基本思路 單純形法是在原問題為可行解(表格bi列0)、對偶問題為非可行解(部分檢驗數j0）的條件下，逐步進行變量替換，改善目標函數值，最終達到全部檢驗數j0，即對偶問題也是可行時，根據對偶問題性質3，原問題和對偶問題均得到最優解。 對偶單純形法是根據線性規劃問題的對偶性質設計的一種解題方法。其基本思路是：原問題不是可行解，保持對偶問題為可行解，逐步進

46、行變量替換，當原問題變為可行解時，即得到問題的最優解。,單純形法的基本思路： 原問題基可行解 最優解判斷,對偶問題的可行解,對偶問題 最優解判斷,對偶單純形法 基本思路,對偶單純形法的優點是可以從非可行解開始迭代，而不需添加人工變量去造基，這樣對一些特殊類型的線性規劃問題求解起來更加便捷。,對偶單純形法的解題步驟,根據線性規劃問題列出初始單純形表，表中所有檢驗數j0，b列中至少有一個分量為負。,確定換出變量，在b列的負分量中選出一個最小值（也可任選）bl，其對應的基變量xB1為出基變量。,對應基變量 為換出基的變量,例：用對偶單純形法求解線性規劃問題,初始可行基,初始可行基,使對偶問題基變量可

47、行,主元,主元,最優解,例2.12 用對偶單純形方法求解：,解: （1）引入松弛變量 x3 , x4 , x5 化為標準形，并在約束等式兩側同乘-1，得到,例2.13 用對偶單純形法求解下面線性規劃,解: 構造對偶單純形表進行迭代，,從最后的表可以看到，B-1b列元素中有-20，并且，-2所在行各元素皆非負，因此，原規劃沒有可行解。,用對偶單純形法求解線性規劃問題：,對偶單純形法的優點： 不需要人工變量； 在靈敏度分析中，有時需要用對偶單純形法處理簡化。 對偶單純形法缺點： 在初始單純形表中對偶問題是基可行解，這點對多數線性規劃問題很難做到。 因此，對偶單純形法一般不單獨使用。,1.11靈敏度

48、分析,在生產計劃問題的一般形式中，A代表企業的技術狀況，b代表企業的資源狀況，而C代表企業產品的市場狀況，這些因素不變時企業的最優生產計劃和最大利潤由線性規劃的最優解和最優值決定。 在實際生產過程中，上述三類因素均是在不斷變化的，如果按照初始的狀況制訂了最佳的生產計劃，而在計劃實施前或實施中上述狀況發生了改變，則決策者所關心的是目前所執行的計劃還是不是最優，如果不是應該如何修訂原來的最優計劃。更進一步，為了防止在各類狀況發生時，來不及隨時對其變化作出反應，即所謂“計劃不如變化快”，企業應當預先了解，當各項因素變化時，應當作出什么樣的反應。,當系數A，b，C發生改變時，目前最優基是否還最優？ 為

49、保持目前最優基還是最優，系數A，b，C的允許變化范圍是什么？ 假設每次只有一種系數變化 目標系數C變化 基變量系數發生變化； 非基變量系數發生變化； 右端常數b變化 增加一個變量 增加一個約束 技術系數A發生變化,列出初始單純形表,列出最終單純形表,Z0= CBB-1b, A = C - CBB-1 A N = CN - CBB-1 N j = Cj- CBB-1 Pj, b= B-1b, j = Cj- CBB-1 Pj,Z0= CBB-1b, b= B-1b,靈敏度分析只要滿足以下兩把尺子： j =Cj-CBB-1pj 0； b= B-1b 0,一、價值系數CJ的變化,（一）非基變量Xj的

50、價值系數Cj的改變,只要滿足：,（二）基變量Xbi的價值系數Cbi的變化 由j=Cj-CBB-1Pj看出：某一基變量價值系數CBi的變化將引起CB變化，CB變了則所有非基變量的檢驗數也隨之發生變化。基變量的檢驗數(CB+CB)-(CB+CB)B-1B0不受變動影響。非基變量的檢驗數變為,為確保所有 的允許變化范圍是,例：在第一章的美佳公司例子中， （1）若家電I的利潤降至1.5元/件，而家電II的利潤增至2元/件時，美佳公司最優生產計劃有何變化； （2）若家電I的利潤不變，家電II的利潤在什么范圍內變化時，則該公司的最優生產計劃將不發生變化。,6 14 -,即Z=(2,3,0,6,0),6 14 -,設家電II的利潤為（1+),為使表中為最優解則： -1/4+1/40, -1/2-3/2 0,解得：-1/3 1 即2/3 C2 2,二、右端資