1、1第第3 3章章線性規劃問題的線性規劃問題的對偶與靈敏度分析對偶與靈敏度分析2本章內容重點本章內容重點 線性規劃的對偶問題的概線性規劃的對偶問題的概念、理論及經濟意義念、理論及經濟意義 線性規劃的對偶單純形法線性規劃的對偶單純形法 線性規劃的靈敏度分析線性規劃的靈敏度分析33.1.1 對偶問題的提出：對偶問題的提出： 若第二章例若第二章例2.1問題的設備都用于問題的設備都用于外協加工，工廠收取加工費。試問：外協加工，工廠收取加工費。試問：設備設備 A、B、C 每工時各如何收費每工時各如何收費才最有競爭力？才最有競爭力？ 設設 y1 ，y2 ，y3 分別為每工時設備分別為每工時設備 A、B、C

2、的收取費用。的收取費用。3.1 3.1 線性規劃對偶問題線性規劃對偶問題3.1 線性規劃對偶問題線性規劃對偶問題例例2.1:某工廠擁有某工廠擁有A、B、C三種類型的設備，三種類型的設備，生產甲、乙兩種產品。每件產品在生產中生產甲、乙兩種產品。每件產品在生產中需要占用的設備機時數，每件產品可以獲需要占用的設備機時數，每件產品可以獲得的利潤以及三種設備可利用的時數如下得的利潤以及三種設備可利用的時數如下表所示。求獲最大利潤的方案。表所示。求獲最大利潤的方案。產品甲產品乙設備能力（h）設備A3 32 26565設備B2 21 14040設備C0 03 37575利潤/（元/件/p>

3、025005Max z = 1500 x1 + 2500 x2 原問題原問題s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 , x2 0Min f = 65y1+ 40y2 + 75y3 對偶問題對偶問題s.t. 3y1+2y2 1500 （不少于甲產品的利潤）（不少于甲產品的利潤） 2y1+y2+3y3 2500（不少于乙產品的利潤）（不少于乙產品的利潤） y1, y2 , y3 063.1.2 對偶規劃的形式對偶規劃的形式 有有對稱形式對稱形式和和非對稱形式非對稱形式。 對稱形式對稱形式的對偶規劃之間具有下面的的對偶規劃之間具有下面的對應關系：對應關系： (

4、1) 若一個模型為目標求若一個模型為目標求“極大極大”，約，約束為束為“小于等于小于等于”的不等式，則它的的不等式，則它的對偶模型為目標求對偶模型為目標求“極小極小”，約束是，約束是“大于等于大于等于”的不等式。即的不等式。即 “max，” 和和 “min，” 相對應。相對應。7(2) 從約束系數矩陣看：一個模型中從約束系數矩陣看：一個模型中為為，則另一個模型中為，則另一個模型中為AT。一個。一個模型是模型是m個約束，個約束，n個變量，則它的個變量，則它的對偶模型為對偶模型為n個約束，個約束，m個變量。個變量。(3) 從數據從數據b、C的位置看：在兩個規的位置看：在兩個規劃模型中，劃模型中，b

5、和和C的位置對換。的位置對換。(4) 兩個規劃模型中的變量皆非負。兩個規劃模型中的變量皆非負。8 對稱形式：對稱形式： 互為對偶互為對偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”9 非對稱形式非對稱形式的對偶規劃的對偶規劃: :對非對稱形式，對非對稱形式，可以按照下面的對應關系直接給出其對偶規劃可以按照下面的對應關系直接給出其對偶規劃(1) 將模型統一為將模型統一為“max，”或或“min，” 的形式，對于其中的等式約束按的形式，對于其中的等式約束按下面下面(2)、(3)

6、中的方法處理；中的方法處理；(2) 若原規劃的某個約束條件為等式約若原規劃的某個約束條件為等式約束，則在對偶規劃中與此約束對應的束，則在對偶規劃中與此約束對應的那個變量取值沒有非負限制；那個變量取值沒有非負限制；(3) 若原規劃的某個變量的值沒有非負若原規劃的某個變量的值沒有非負限制，則在對偶問題中與此變量對應限制，則在對偶問題中與此變量對應的那個約束為等式。的那個約束為等式。10 下面對關系下面對關系(2)作一說明。對于關系作一說明。對于關系(3)可以給出類似的解釋：可以給出類似的解釋： 設原規劃中第一個約束為等式：設原規劃中第一個約束為等式： a11x1 + + a1nxn = b1 那么

7、，它與下面兩個不等式等價那么，它與下面兩個不等式等價1111111111.bxaxabxaxannnn 11 mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn,2, 1,0max11111111111111原規劃模型可以寫成原規劃模型可以寫成12 這里，把這里，把y1看作是看作是 y1 =y1 - y1，于是于是y1沒有非負限制。沒有非負限制。 沒有非負限制沒有非負限制121111112211211211111111221111, 0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm轉化為對稱形式，直接寫出對偶規

8、劃轉化為對稱形式，直接寫出對偶規劃13例例 寫出下面線性規劃的對偶規劃模型寫出下面線性規劃的對偶規劃模型 沒沒有有非非負負限限制制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ14解解 先將約束條件變形為先將約束條件變形為“”形式形式 沒沒有有非非負負限限制制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx15根據非對稱形式的對應關系，直接寫根據非對稱形式的對應關系，直接寫出對偶規劃出對偶規劃 0,725472123122510306025min543215

9、4213213132154321yyyyyyyyyyyyyyyyyyyyyyf沒有非負限制沒有非負限制16定理定理3-1 (弱對偶定理）弱對偶定理） 若若X和和Y分別為原規劃（分別為原規劃（P）和對偶規劃（和對偶規劃（D）的可行解，那）的可行解，那么么cTx bTy。推論推論1 設設X0和和Y0分別為原規劃分別為原規劃（P）和對偶規劃（）和對偶規劃（D）的可行解，）的可行解，當當CTX0=bTY0時，時，X0、Y0分別是分別是兩個問題的最優解。兩個問題的最優解。3.1.3 3.1.3 線性規劃對偶問題線性規劃對偶問題17推論推論2 若規劃（若規劃（P）有可行解，則（）有可行解，則（P）有最優解

10、的充分必要條件是規劃（有最優解的充分必要條件是規劃（D）有可行解。有可行解。推論推論3 若規劃（若規劃（D）有可行解，則（）有可行解，則（D）有最優解的充分必要條件是規劃（有最優解的充分必要條件是規劃（P）有可行解。有可行解。定理定理 3.2 若原規劃（若原規劃（P）有最優解，則）有最優解，則對偶規劃（對偶規劃（D）也有最優解，反之亦）也有最優解，反之亦然。并且兩者的然。并且兩者的目標函數值相等目標函數值相等若（若（P）、）、(D)都有可行解都有可行解 二者二者都有最優解。都有最優解。（P）(D)其中之一有最優解其中之一有最優解 另另一個也有最優解。一個也有最優解。一個有可行解，一個無可行解一

11、個有可行解，一個無可行解 二者都無最優解。二者都無最優解。19例例 求解下面線性規劃問題，并根求解下面線性規劃問題，并根據最優單純形表中的檢驗數，給據最優單純形表中的檢驗數，給出其對偶問題的最優解。出其對偶問題的最優解。 0,1003310022734max321321321321xxxxxxxxxxxxz20解得最優單純形表解得最優單純形表 最優解為最優解為(0, 25, 25)T，最優值為，最優值為250。表中松弛變量的檢驗數分別為表中松弛變量的檢驗數分別為-0.5，-2，可以驗證可以驗證(0.5, 2)T為對偶規劃的最優解。為對偶規劃的最優解。 x1x2x3x4x5-0.75100.75

12、-0.51.2501-0.250.5-2.500-0.5-2cBxB3x2257x325-z-2504370021 可以用下面方法驗證的對偶最優性。可以用下面方法驗證的對偶最優性。原規劃的對偶規劃為原規劃的對偶規劃為 0,7323243.100100min2121212121yyyyyyyytsyyf(1/2,2)T為對偶可行解，并且目標值為為對偶可行解，并且目標值為f =250由定理由定理3.1的推論的推論1可以判斷可以判斷(1/2,2)T為對偶問為對偶問題的最優解。題的最優解。22 從本例的結論可以看到，對從本例的結論可以看到，對偶規劃的最優解可以在原規劃的偶規劃的最優解可以在原規劃的最優

13、解的檢驗數中得到，最優解的檢驗數中得到，原規劃原規劃最優解的檢驗數最優解的檢驗數 的后的后m個分量個分量（松弛變量對應的檢驗數）的負（松弛變量對應的檢驗數）的負值，為對偶規劃的最優解值，為對偶規劃的最優解。對偶規劃的最優解又稱對偶規劃的最優解又稱231 1影子價格的概念影子價格的概念考慮互為對偶的線性規劃考慮互為對偶的線性規劃(P)(P)，(D)(D)設設y*=（y1*,，ym*)T為對偶規劃為對偶規劃(D)(D)的最優解，的最優解，則則yi* *稱為規劃稱為規劃(P)(P)第第i個個約束對應的影子價格約束對應的影子價格( (shadow Price) )。3.1.4 影子價格影子價格24影子

14、價格的經濟含義影子價格的經濟含義(1) 影子價格是對現有資源實現最大效影子價格是對現有資源實現最大效益時的一種估價益時的一種估價 企業可以根據現有資源的影子價格，企業可以根據現有資源的影子價格，對資源的使用有兩種考慮：第一，是否將對資源的使用有兩種考慮：第一，是否將設備用于外加工或出租，若租費高于設備設備用于外加工或出租，若租費高于設備的影子價格，可考慮出租設備，否則不宜的影子價格，可考慮出租設備，否則不宜出租。第二，是否將投資用于購買設備，出租。第二，是否將投資用于購買設備，以擴大生產能力，若市價低于某設備的影以擴大生產能力，若市價低于某設備的影子價格，可考慮買進該設備，否則不宜買子價格，可

15、考慮買進該設備，否則不宜買進進。253.1.4 3.1.4 影子價格影子價格 (2) 影子價格表明資源增加對總效益產影子價格表明資源增加對總效益產生的影響。生的影響。 根據推論，在最優解的根據推論，在最優解的情況下，有情況下，有 因此，可以將因此，可以將z* *看作是看作是bi的函數，的函數，對對bi求偏導數可得到求偏導數可得到 這說明，如果右端常數增加一個這說明，如果右端常數增加一個單位，則目標函數值的增量將是單位，則目標函數值的增量將是y* *. .*22*11*mmybybybfz miybzii, 2 , 1,* 26 影子價格反映了不同的局部影子價格反映了不同的局部或個體的增量可以獲

16、得不同的整或個體的增量可以獲得不同的整體經濟效益。如果為了擴大生產體經濟效益。如果為了擴大生產能力，能力，考慮增加設備，就應該從考慮增加設備，就應該從影子價格高的設備入手。影子價格高的設備入手。這樣可這樣可以用較少的局部努力，獲得較大以用較少的局部努力，獲得較大的整體效益。的整體效益。 需要指出，影子價格不是固定不變需要指出，影子價格不是固定不變的，當約束條件、產品利潤等發生變化的，當約束條件、產品利潤等發生變化時，有可能使影子價格發生變化。另外，時，有可能使影子價格發生變化。另外，影子價格的經濟含義是指資源在一定范影子價格的經濟含義是指資源在一定范圍內增加時的情況圍內增加時的情況，當某種資源

17、的增加，當某種資源的增加超過了這個超過了這個“一定的范圍一定的范圍”時，總利潤時，總利潤的增加量則不是按照影子價格給出的數的增加量則不是按照影子價格給出的數值線性地增加。這個問題還將在靈敏度值線性地增加。這個問題還將在靈敏度分析一節中討論。分析一節中討論。283.2 對偶單純形法對偶單純形法3.2.1 3.2.1 對偶單純形法的基本思想對偶單純形法的基本思想 從原規劃的一個從原規劃的一個對偶可行基本對偶可行基本解解（檢驗數非正）出發，然后檢驗（檢驗數非正）出發，然后檢驗原規劃的原規劃的基本解基本解是否可行，即是否是否可行，即是否非負。如果有小于零的分量，則進非負。如果有小于零的分量，則進行迭代

18、，求另一個行迭代，求另一個基本解基本解（保持檢（保持檢驗數非正）。驗數非正）。偶單純形法的適用范圍偶單純形法的適用范圍 對偶單純形法適合于解如下形式的線對偶單純形法適合于解如下形式的線性規劃問題：性規劃問題：njxmibxacxcfjnjijijnjjjj, 2 , 1, 0, 2 , 10min11301. 建立初始對偶單純形表建立初始對偶單純形表, 對應一個基本解對應一個基本解,所有檢驗數均非正所有檢驗數均非正, 轉轉2；2. 若若 b0, 則得到最優解則得到最優解, 停止停止;否則否則, 若有若有bk0, 則選則選k行的基變量為出基變量行的基變量為出基變量, 轉轉33. 若所有若所有ak

19、j0( j = 1,2,n )，則原問題無可，則原問題無可行解行解, 停止停止; 否則否則, 若有若有akj0, 則選則選 =min j / akjakj0= r/akr那么那么, xr為進基變量為進基變量,轉轉4；4. 以以akr為轉軸元為轉軸元, 作矩陣行變換使其變為作矩陣行變換使其變為1, 該列其他元變為該列其他元變為0, 轉轉2。3.2.2 對偶單純形法主要步驟：對偶單純形法主要步驟：31例例 求解線性規劃問題：求解線性規劃問題： Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0解：解

20、： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1- 2x2-x3+x4 = -3 -2x1+x2-3x3 +x5= -4 x1,x2,x3,x4,x5 0表格對偶單純形法表格對偶單純形法最優解為最優解為: x = ( 2.2, 0.4, 0, 0, 0 )T , z = -5.6最優值最優值 f = 5.6無可行解情況無可行解情況 線性規劃問題可能出現不存在可線性規劃問題可能出現不存在可行解的情況，這時，在對偶單純形表行解的情況，這時，在對偶單純形表中顯示矛盾方程。中顯示矛盾方程。例例 Max z = x1 3x2 2x3 s.t. x1 + 2x2 + 3x3 + x

21、4 = -10 2x1 + x2 + 5x3 + x5 = 20 3x1 + 2x2 - x3 + x6 = -12 x1 , x2 , x3 , x4 , x5 , x6 0對偶單純形表對偶單純形表表中第表中第1行反映了一個矛盾約束：行反映了一個矛盾約束： x1 + 2x2 + 3x3 + x4 = -10 即，若所有即，若所有akj0( j = 1,n )，則原問，則原問題無可行解題無可行解,停止停止;是是是是是是是是否否否否否否否否所有所有所有所有得到得到最優解最優解計算計算計算計算典式對應原規劃的典式對應原規劃的基本解是可行的基本解是可行的典式對應原規劃的基典式對應原規劃的基本解的檢驗

22、數本解的檢驗數所有所有所有所有計算計算計算計算以為中心元素進行迭代以為中心元素進行迭代以為中心元素進行迭代以為中心元素進行迭代停停沒沒有有最最優優解解沒沒有有最最優優解解單純形法單純形法對偶單純形法對偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min比較比較0 csMin j/asj asj0 br Min-bi/air air050上例最優單純形表如下上例最優單純形表如下 例例51 0 1/4 0 0 1/4 0 這里這里 B B-1 -1 = -2 1/2 1 = -2 1/2 1 1/2 -1/8 0 1

23、/2 -1/8 0 各列分別對應各列分別對應 b1、b2、b3 的單一變化的單一變化因此，設因此，設 b1 增加增加 4，則，則 x1 , x5 , x2分別變為：分別變為：4+04=4, 4+(-2)4=-40, 2+ 1/21/2 4=4用對偶單純形法進一步求解，可得：用對偶單純形法進一步求解，可得：52于是，于是，x* = ( 4, 3, 2, 0, 0 )T f* = 1753 討論保持最優基不變的前提下，討論保持最優基不變的前提下， b2的允許變化范圍的允許變化范圍 4 + b2 0.25 0 b2 -16 4 + b2 0.5 0 b2 -8 2 + b2 (- 0.125) 0

24、b2 16于是于是 -8 b2 16例題：例題：某廠生產甲、乙、丙三種產品，分別經過某廠生產甲、乙、丙三種產品，分別經過、三種設備加工。已知生產單位產品所需的、三種設備加工。已知生產單位產品所需的設備臺時數、設備的現有加工能力及每件產品的利設備臺時數、設備的現有加工能力及每件產品的利潤見下頁表，求：潤見下頁表，求：(1) (1) 產品丙利潤增加到多大時才值得安排生產？如產品丙利潤增加到多大時才值得安排生產？如產品丙每件的利潤增加到產品丙每件的利潤增加到50/6 50/6 ，求最優生產計劃，求最優生產計劃。(2) (2) 產品甲的利潤在多大范圍內變化時，原最優計產品甲的利潤在多大范圍內變化時，原

25、最優計劃保持不變？劃保持不變？(3) (3) 設備設備A A的能力如為的能力如為100+10100+10 ，確定保持原最優，確定保持原最優基不變的基不變的 的變化范圍。的變化范圍。(4) (4) 如有一種新產品丁，加工一件需設備如有一種新產品丁，加工一件需設備A A、B B、C C的臺時各為的臺時各為1 1、4 4、3 3小時，預期每件的利潤為小時，預期每件的利潤為8 8元，元，是否值得安排生產？是否值得安排生產？(5) (5) 如合同規定該廠至少生產如合同規定該廠至少生產1010件產品丙，試確定件產品丙，試確定最優計劃的變化。最優計劃的變化。 甲甲乙乙丙丙設備能力（設備能力（臺時）臺時）10

26、100100600600300300單位產品利單位產品利潤（元）潤（元）10最優單純形表最優單純形表1064000cBxBx1x2x3x4x5x66x2200/3015/65/3-1/6010 x1100/3101/6-2/31/600 x6100004-01-zj-2200/300-8/3 -10/3 -2/30參考解答參考解答(1) 3 = -8/3 +c30, 故故c38/3，即當產品丙即當產品丙的利潤大于的利潤大于20/3（48/3）時，值得安排生產；）時，值得安排生產； 如產品丙每件的利潤增加到如產品丙每件的利潤增加到50/650/6，則，則最優生產計劃最優生產計劃 x* = 175

27、/6, 275/6, 25。(2) - 4 c1 5，即，即產品甲的利潤產品甲的利潤 6 c1 1 5時，原最優計劃保持不變。時，原最優計劃保持不變。(3) 當當 - 4 5，保持原最優基不變。保持原最優基不變。(4) 新產品丁值得安排生產。新產品丁值得安排生產。(5) 如合同規定該廠至少生產如合同規定該廠至少生產1010件產品丙，則件產品丙，則最優計劃為最優計劃為 x* = 95/3, 175/3, 10 。 59增加變量增加變量 xn+1, 相應有相應有pn+1, cn+1 。 可計算出可計算出 B-1pn+1, n+1=cn+1-cri ari n+1 填入最優單純形表：填入最優單純形表

28、： 若若 n+1 0 則則 最優解不變；最優解不變； 否則，進一步用單純形法求解。否則，進一步用單純形法求解。3.3.4 增加新變量分析增加新變量分析60例例 對前例，增加對前例，增加x6 , p6=( 2, 6, 3 )T, c6=5用單純形法進一步求解，可得：用單純形法進一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5666616pcc,pBpTB 61 首先，應把最優解代入新的約束首先，應把最優解代入新的約束 若滿足，則最優解不變，停止；若滿足，則最優解不變，停止； 否則，引入一個新的非負變量（否則，引入一個新的非負變量（原約原約束若是束若是小于等于形式

29、可引入非負松弛變量，否則引小于等于形式可引入非負松弛變量，否則引入非負人工變量入非負人工變量），填入最優單純形表作），填入最優單純形表作為新的一行，并通過矩陣行變換把為新的一行，并通過矩陣行變換把對應對應基中的列向量變為單位向量基中的列向量變為單位向量。 進一步用對偶單純形法求解。進一步用對偶單純形法求解。3.3.5 增加一個約束條件增加一個約束條件62例例 上例增加上例增加 3x1+ 2x2 15，原最優解不，原最優解不滿足這個約束。于是滿足這個約束。于是 對表中新的一行利用矩陣初等行變對表中新的一行利用矩陣初等行變換進行處理，可得新的對偶單純形表：換進行處理，可得新的對偶單純形表：63經對

30、偶單純形法一步，可得最優解為經對偶單純形法一步，可得最優解為（3.5, 2.25, 0, 0, 3, 2 )T，最優值為最優值為 13. 75 64(只討論只討論 N 中某一列變化情況）中某一列變化情況） 與增加變量與增加變量 xn+1 的情況類似，的情況類似，假設假設 pj 變化變化 。那么，重新計算出。那么，重新計算出 pj=B-1pj j = cj - cri ari j 填入最優單純形表，若填入最優單純形表，若 j 0 則最則最 優解不變；否則，進一步用單純形優解不變；否則，進一步用單純形法求解。（例子從略）法求解。（例子從略）3.3.6 A中元素發生變化中元素發生變化 作業作業P80

31、-3.1(3); P81-3.7(1);P82- 3.10線性規劃應用與線性規劃應用與計算機解題計算機解題6667線性規劃的計算機求解線性規劃的計算機求解介紹小型的運籌學教學軟件：介紹小型的運籌學教學軟件： MS60用用ExcelExcel求解線性規劃求解線性規劃68線性規劃問題的計算機求解線性規劃問題的計算機求解(Excel)決策變量決策變量 x1 x2 1 1目標函數目標函數 c1 c2 f 50 100 150約束矩陣約束矩陣 Aij sum b 1 1 2 300 2 1 3 400 0 1 1 25069線性規劃問題的計算機求解線性規劃問題的計算機求解(Excel)(Excel)運算

32、結果報告運算結果報告目標單元格目標單元格 ( (最大值最大值) ) 單元格單元格 名字名字 初值初值 終值終值 $E$5 f 150 27500可變單元格可變單元格 單元格單元格 名字名字 初值初值 終值終值 $B$2 x1 1 50 $C$2 x2 1 250約束約束 單元格單元格 名字名字 單元格值單元格值 公式公式 狀態狀態 型數值型數值 $D$8 sum 300 $D$8=$E$8 $D$8 sum 300 $D$8=$E$8 到達限制值到達限制值 0 0 $D$9 sum 350 $D$9=$E$9 $D$9 sum 350 $D$9=$E$9 未到限制值未到限制值 5050 $D$

33、10 sum 250 $D$10=$E$10 $D$10 sum 250 $D$10=0 $B$2 x1 50 $B$2=0 未到限制值未到限制值 5050 $C$2 x2 250 $C$2=0 $C$2 x2 250 $C$2=0 未到限制值未到限制值 25025070線性規劃問題的計算機求解線性規劃問題的計算機求解(Excel)敏感性報告敏感性報告可變單元格可變單元格單元格單元格 名字名字 終值終值 遞減成本遞減成本 目標式系數目標式系數 允許的增量允許的增量 允許的減量允許的減量$B$2 x1 50 0 50 50 50$B$2 x1 50 0 50 50 50$C$2 x2 250 0

34、 100 1E+30 50$C$2 x2 250 0 100 1E+30 50約束約束單元格單元格 名字名字 終值終值 陰影約束陰影約束 約束限制值約束限制值 允許的增量允許的增量 允許的減量允許的減量$D$8 sum 300 50 300 25 50$D$8 sum 300 50 300 25 50$D$9 sum 350 0 400 1E+30 50$D$9 sum 350 0 400 1E+30 50$D$10 sum 250 50 250 50 50$D$10 sum 250 50 250 50 5071結果考察：結果考察：1、當目標函數的系數、當目標函數的系數 ci 單一變化時，單一

35、變化時，只要不超過其上、下限，基不變，即只要不超過其上、下限，基不變，即最優解不變；最優解不變；2、當約束條件中右邊系數、當約束條件中右邊系數 bj 變化時，變化時，當其不超過上、下限，基不變，即對當其不超過上、下限，基不變，即對偶價格不變解；偶價格不變解； 3、當有多個系數變化時，需要進一步、當有多個系數變化時，需要進一步討論。討論。72百分之一百法則百分之一百法則 對于所有變化的目標函數決策對于所有變化的目標函數決策系數（約束條件右邊常數值），當系數（約束條件右邊常數值），當其所有允許增加的百分比與允許減其所有允許增加的百分比與允許減少的百分比之和不超過少的百分比之和不超過100%100%

36、時，最時，最優解不變（對偶價格不變），即最優解不變（對偶價格不變），即最優基不變。優基不變。73 允許增加量允許增加量 = 上限上限 - 現在值現在值 例例 c1 的允許增加量為的允許增加量為 100 - 50 = 50 b1 的允許增加量為的允許增加量為 325 - 300 = 25 允許減少量允許減少量 = 現在值現在值 - 下限下限 例例 c2 的允許減少量為的允許減少量為 100 - 50 = 50 b3 的允許減少量為的允許減少量為 250 - 200 = 50 允許增加的百分比允許增加的百分比 = 增加量增加量 / 允許增加量允許增加量 允許減少的百分比允許減少的百分比 = 減少量

37、減少量 / 允許減少量允許減少量 示例說明示例說明74示例說明示例說明-續續 c1 變為變為 74 , c2 變為變為 78, 則則 (74 - 50)/50 + (100 - 78 )/50 = 92%，故最優解不變。故最優解不變。 b1 變為變為 315 , b3 變為變為 240, 則則 (315-300)/25+(250-240)/50 = 80%，故對偶價格不變故對偶價格不變（最優基不變）（最優基不變）。751）當允許增加量（允許減少量）為無窮）當允許增加量（允許減少量）為無窮大時，則對任意增加量（減少量），其允大時，則對任意增加量（減少量），其允許增加（減少）百分比均看作許增加（減

38、少）百分比均看作0；2）百分之一百法則是充分條件，但非必）百分之一百法則是充分條件，但非必要條件；要條件；3）百分之一百法則不能用于目標函數決）百分之一百法則不能用于目標函數決策變量系數和約束條件右邊常數值同時變策變量系數和約束條件右邊常數值同時變化的情況。這種情況下，只有重新求解。化的情況。這種情況下，只有重新求解。百分之一百法則的要點：百分之一百法則的要點：762.2 線性規劃應用線性規劃應用 線性規劃應用很廣，有線性規劃應用很廣，有一些典型的問題可歸類為線一些典型的問題可歸類為線性規劃性規劃問題：問題： 某企業生產某企業生產 3種產品甲、乙、丙，種產品甲、乙、丙，生產受到的約束為原料生產受到的約束為原料A、B、C、D的的限制，分別為限制，分別為 630 噸、噸、600 噸、噸、728 噸、噸、270 噸。生產每噸產品對各原料噸。生產每噸產品對各原料 A、B、C、D的消耗噸數為：的