第二章 線性規(guī)劃的圖解法

1、第二章 線性規(guī)劃的圖解法一、線性規(guī)劃的概念一、線性規(guī)劃的概念二、線性規(guī)劃問題的提出二、線性規(guī)劃問題的提出三、線性規(guī)劃的數(shù)學(xué)模型三、線性規(guī)劃的數(shù)學(xué)模型四、線性規(guī)劃的圖解法四、線性規(guī)劃的圖解法五、線性規(guī)劃解的情況五、線性規(guī)劃解的情況六、六、LP圖解法的靈敏度分析圖解法的靈敏度分析一、線性規(guī)劃的概念線性規(guī)劃線性規(guī)劃Linear Programming 簡稱簡稱LP，是一，是一種解決在種解決在線性約束條件線性約束條件下追求最大或最小的下追求最大或最小的線性目標(biāo)函數(shù)線性目標(biāo)函數(shù)的方法。的方法。線性規(guī)劃的目標(biāo)和約束條件都可以表示成線線性規(guī)劃的目標(biāo)和約束條件都可以表示成線性的式子。性的式子。 例例1.1、勝

2、利家具廠生產(chǎn)桌子和椅子兩種家具，桌子售價、勝利家具廠生產(chǎn)桌子和椅子兩種家具，桌子售價50元元/張，椅子售價張，椅子售價30元元/張。生產(chǎn)一張桌子需要木工張。生產(chǎn)一張桌子需要木工4h，油漆，油漆工工2h，生產(chǎn)一張椅子需要木工，生產(chǎn)一張椅子需要木工3h，油漆工，油漆工1h。該廠每月可用。該廠每月可用木工工時木工工時120h，油漆工工時，油漆工工時50h。問該廠每月生產(chǎn)多少張桌。問該廠每月生產(chǎn)多少張桌子和椅子才能使每月的銷售收入最大？子和椅子才能使每月的銷售收入最大？ 解：解： 1、確定決策變量、確定決策變量 x1、x2每月生產(chǎn)桌子、椅子的數(shù)量；每月生產(chǎn)桌子、椅子的數(shù)量； 2、確定目標(biāo)函數(shù)、確定目標(biāo)

3、函數(shù)銷售收入最大銷售收入最大 Max s =50 x1+30 x2 3、確定約束條件、確定約束條件 s.t. 4x1+3x2 120 2x1+x2 50 4、變量非負(fù)限制、變量非負(fù)限制 x1 ,x2 0二、線性規(guī)劃問題的提出 線性規(guī)劃模型：線性規(guī)劃模型： Max s =50 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1 ,x2 0產(chǎn)品甲 產(chǎn)品乙 生產(chǎn)能力設(shè)備A設(shè)備B2111108單位利潤32承導(dǎo)入案例承導(dǎo)入案例設(shè)兩種產(chǎn)品產(chǎn)量為設(shè)兩種產(chǎn)品產(chǎn)量為x1,x2,則有則有:12121212max32210. .8,0zxxxxstxxx x總利潤表達(dá)式總利潤表達(dá)式最大化最

4、大化設(shè)備設(shè)備A臺時占用臺時占用設(shè)備設(shè)備B臺時占用臺時占用生產(chǎn)能力生產(chǎn)能力,不不允許超過允許超過產(chǎn)量非負(fù)產(chǎn)量非負(fù)決策變量決策變量（decision variable） 目標(biāo)函數(shù)目標(biāo)函數(shù)（objective function） 約束條件約束條件（subject to）三要素三要素當(dāng)目標(biāo)函數(shù)與約束條件均為決策變當(dāng)目標(biāo)函數(shù)與約束條件均為決策變量的線性函數(shù)，且變量取連續(xù)值時，量的線性函數(shù)，且變量取連續(xù)值時，稱為線性規(guī)劃稱為線性規(guī)劃LP；變量取整稱為整；變量取整稱為整數(shù)線性規(guī)劃數(shù)線性規(guī)劃ILP；變量取二進(jìn)制為；變量取二進(jìn)制為0-1規(guī)劃規(guī)劃BLP。例例1.2 某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件某工廠用

5、三種原料生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，試制訂總利潤最大的生產(chǎn)計劃如下表所示，試制訂總利潤最大的生產(chǎn)計劃單位產(chǎn)品所需原料數(shù)量單位產(chǎn)品所需原料數(shù)量（公斤）（公斤）產(chǎn)品產(chǎn)品Q1產(chǎn)品產(chǎn)品Q2產(chǎn)品產(chǎn)品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000單位產(chǎn)品的利潤（千元）單位產(chǎn)品的利潤（千元）354決策變量：每天生產(chǎn)三種產(chǎn)品的數(shù)量，分別決策變量：每天生產(chǎn)三種產(chǎn)品的數(shù)量，分別設(shè)為設(shè)為x1，x2，x3；目標(biāo)：每天的生產(chǎn)利潤最大目標(biāo)：每天的生產(chǎn)利潤最大目標(biāo)函數(shù)為目標(biāo)函數(shù)為Max s 3x15x24x3約束條件：每天原料的需求量不超過

6、可用量約束條件：每天原料的需求量不超過可用量原料原料P1 ： 2x13x20 x3 1500原料原料P2 ： 0 x12x24x3800原料原料P3 ： 3x12x25x32000隱含約束：產(chǎn)量為非負(fù)數(shù)隱含約束：產(chǎn)量為非負(fù)數(shù)x1 ，x2 ，x3 0 數(shù)學(xué)模型：數(shù)學(xué)模型：Max s = 3x15x24x3 s.t. 2x13x20 x3 1500 0 x12x24x3800 3x12x25x32000 x1 ，x2 ，x3 0從前面兩個例子中可以看出一般線性規(guī)劃問題從前面兩個例子中可以看出一般線性規(guī)劃問題的建模過程：的建模過程：A、理解要解決的問題，明確在什么條件下，、理解要解決的問題，明確在什

7、么條件下，要追求什么目標(biāo)；要追求什么目標(biāo)；B、定義決策變量；、定義決策變量；C、用決策變量的線性函數(shù)形式寫出所要追求、用決策變量的線性函數(shù)形式寫出所要追求的目標(biāo)，即目標(biāo)函數(shù)的目標(biāo)，即目標(biāo)函數(shù),按問題的不同，要求目按問題的不同，要求目標(biāo)函數(shù)實現(xiàn)最大化和最小化；標(biāo)函數(shù)實現(xiàn)最大化和最小化；D、用一組決策變量的等式或不等式來表示在、用一組決策變量的等式或不等式來表示在解決問題過程中所必須遵循的約束條件。解決問題過程中所必須遵循的約束條件。1、LP模型的一般形式模型的一般形式目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max(Min)z = c1x1 + c2x2 + + cnxn約束條件：約束條件： a11x1+a12x2+

8、a1nxn( =, )b1a21x1+a22x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bmx1 ，x2 ， ，xn ( ) 0 或無約束或無約束三、線性規(guī)劃的數(shù)學(xué)模型xj為待定的決策變量；為待定的決策變量；cj為目標(biāo)函數(shù)系數(shù)，或價值系數(shù)、費用系數(shù)；為目標(biāo)函數(shù)系數(shù)，或價值系數(shù)、費用系數(shù)；aij為技術(shù)系數(shù)；為技術(shù)系數(shù)；bj為資源常數(shù)，簡稱右端項；為資源常數(shù)，簡稱右端項；其中其中i1，2，m； j1，2，n可以看出，一般可以看出，一般LP模型的特點：模型的特點：A、決策變量、決策變量x1，x2，x3，xn表示要尋求表示要尋求的方案，每一組值就是一個

9、方案；的方案，每一組值就是一個方案；B、約束條件是用等式或不等式表述的限制、約束條件是用等式或不等式表述的限制條件；條件；C、一定有一個追求目標(biāo)，或希望最大或希、一定有一個追求目標(biāo)，或希望最大或希望最小；望最?。籇、所有函數(shù)都是線性的。、所有函數(shù)都是線性的。1 122maxnnzc xc xc x=+11 112211(0)nna xa xa xb+=()1 1220mmmnnma xaxaxb+=2、線性規(guī)劃模型的標(biāo)準(zhǔn)型：、線性規(guī)劃模型的標(biāo)準(zhǔn)型：x1 0， x2 0， xn 0s.t.標(biāo)準(zhǔn)形式的特點：標(biāo)準(zhǔn)形式的特點：A、目標(biāo)函數(shù)為、目標(biāo)函數(shù)為Max形式形式B、約束全為式、約束全為式C、所有決

10、策變量、所有決策變量xj 0，j 1，2，3， nD、所有、所有bi0，i1，2，3， m3、如何將一般、如何將一般LP問題化為標(biāo)準(zhǔn)形問題化為標(biāo)準(zhǔn)形式式A、極小化目標(biāo)函數(shù)問題轉(zhuǎn)化為極大化目標(biāo)、極小化目標(biāo)函數(shù)問題轉(zhuǎn)化為極大化目標(biāo)函數(shù)問題：函數(shù)問題： 若目標(biāo)函數(shù)為：若目標(biāo)函數(shù)為： Min f = c1x1 + c2x2 + + cnxn 則可令則可令z -f ，原目標(biāo)等同于：，原目標(biāo)等同于： Max z = -c1x1 - c2x2 - - cnxn 但須注意但須注意, f* z*B、約束條件不是等式的問題：約束條件不是等式的問題： 若約束條件為若約束條件為 ai1 x1+ai2 x2+ +ain

11、 xn bi 可以引進(jìn)一個新的變量可以引進(jìn)一個新的變量si ，使它等于約束右，使它等于約束右邊與左邊之差邊與左邊之差 si=bi(ai1 x1 + ai2 x2 + + ain xn ) 顯然，顯然，si 也具有非負(fù)約束，即也具有非負(fù)約束，即si0， 這時新的約束條件成為這時新的約束條件成為 ai1 x1+ai2 x2+ +ain xn+si = bi當(dāng)約束條件為當(dāng)約束條件為 ai1 x1+ai2 x2+ +ain xn bi時，類似地令時，類似地令 si= (ai1 x1 + ai2 x2 + + ain xn ) bi顯然，顯然，si也滿足非負(fù)約束，即也滿足非負(fù)約束，即si0，這時新，這時

12、新的約束條件成為的約束條件成為 ai1 x1+ai2 x2+ +ain xn-s = bi注意：注意：不同的約束不等式引入的變量也不同；不同的約束不等式引入的變量也不同；一般稱一般稱不等式中引入的變量為松弛變量，稱不等式中引入的變量為松弛變量，稱不等式中引入的變量為剩余變量。不等式中引入的變量為剩余變量。C、變量符號限制的問題：、變量符號限制的問題：當(dāng)某一個變量當(dāng)某一個變量xj 0時，可以令時，可以令 xj = -xj 則則xj0當(dāng)某一個變量當(dāng)某一個變量xj沒有非負(fù)約束時，可以令沒有非負(fù)約束時，可以令 xj = xj- xj”其中其中 xj0，xj”0D、右端項有負(fù)值的問題：、右端項有負(fù)值的問

13、題：如如 bi0S3=0剩余變量的值和意義請大家下去后閱讀教材請大家下去后閱讀教材1517頁例頁例2課堂練習(xí)：圖解法求解以下LP問題 目標(biāo)函數(shù)目標(biāo)函數(shù) Max z = 2500 x1 + 1500 x2 約束條件約束條件 s.t. 3x1+2x2 65 2x1+x2 40 3x2 75 x1 ,x2 0X1X2O3x1+2x265302010102030403x2752x1+x240（15，10）4050答案：答案：最優(yōu)解為：最優(yōu)解為： x1 15 ，x210最優(yōu)值為：最優(yōu)值為：z*250015+150010 52500五、線性規(guī)劃問題解的情況例例1.5的最優(yōu)解只有一個，這是線性規(guī)劃問題的最優(yōu)

14、解只有一個，這是線性規(guī)劃問題最一般的解的情況，但線性規(guī)劃問題解的情最一般的解的情況，但線性規(guī)劃問題解的情況還存在其它特殊的可能：無窮多最優(yōu)解、況還存在其它特殊的可能：無窮多最優(yōu)解、無界解或無可行解。無界解或無可行解。1、有唯一最優(yōu)解的情況例例1.5中即是，在此不再贅述。中即是，在此不再贅述。如果一個線性規(guī)劃問題有最優(yōu)解，則一定有如果一個線性規(guī)劃問題有最優(yōu)解，則一定有一個可行域的頂點對應(yīng)最優(yōu)解，唯一最優(yōu)解一個可行域的頂點對應(yīng)最優(yōu)解，唯一最優(yōu)解一定在可行域的頂點上取得。一定在可行域的頂點上取得。在例在例1. 5的線性規(guī)劃模型中的線性規(guī)劃模型中 目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max z= 50 x1+100

15、x2 約束條件：約束條件：x1+x2300 2x1+x2400 x2250 x1 0， x2 0 若目標(biāo)函數(shù)變?yōu)椋喝裟繕?biāo)函數(shù)變?yōu)椋?Max z= 50 x1+50 x2 2、無窮多最優(yōu)解的情況A(0,250)B(50,250)C(100,200)D(200,0)X1X2O300200100100200300400最優(yōu)情況下目標(biāo)函數(shù)最優(yōu)情況下目標(biāo)函數(shù)的等值線與直線的等值線與直線BC重重合。這時，最優(yōu)解有合。這時，最優(yōu)解有無窮多個，是從點無窮多個，是從點 B到點到點 C 線段上的所有線段上的所有點，最優(yōu)值為點，最優(yōu)值為15000。2、無窮多最優(yōu)解的情況、無窮多最優(yōu)解的情況3、無界解的情況若將例若將

16、例1.5的線性規(guī)劃模型中約束條件的線性規(guī)劃模型中約束條件1、2的的不等式符號改變，則線性規(guī)劃模型變?yōu)椋翰坏仁椒柛淖儯瑒t線性規(guī)劃模型變?yōu)椋?目標(biāo)函數(shù)：目標(biāo)函數(shù)：Max z= 50 x1+100 x2 約束條件：約束條件：x1+x2 300 2x1+x2 400 x2250 x1 0， x2 0X1X2可行域成為一個可行域成為一個無上界無上界的區(qū)域。這時，沒有有的區(qū)域。這時，沒有有限最優(yōu)解。限最優(yōu)解。3、無界解的情況4、無可行解的情況在例在例1.5的線性規(guī)劃模型中，如果增加約束條的線性規(guī)劃模型中，如果增加約束條件件x1 400，則模型變?yōu)椋海瑒t模型變?yōu)椋耗繕?biāo)函數(shù)：目標(biāo)函數(shù)：Max z= 50 x

17、1+100 x2 約束條件：約束條件：x1+x2300 2x1+x2400 x2250 x1 400 x1 0， x2 04、無可行解的情況可行域成為空的區(qū)域。這時，沒有可行域成為空的區(qū)域。這時，沒有可行解，顯然線性規(guī)劃問題無解?？尚薪?，顯然線性規(guī)劃問題無解。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400 x1400根據(jù)以上例題，進(jìn)一步分析可知線性規(guī)劃的可行域根據(jù)以上例題，進(jìn)一步分析可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況，簡圖如下：和最優(yōu)解有以下幾種可能的情況，簡圖如下：可行域有界可行域有界唯一最優(yōu)解唯一最優(yōu)解可行域有界可行域有界多

18、個最優(yōu)解多個最優(yōu)解可行域無界可行域無界唯一最優(yōu)解唯一最優(yōu)解可行域無界可行域無界無窮多最無窮多最優(yōu)解優(yōu)解可行域無界可行域無界目標(biāo)函數(shù)無界目標(biāo)函數(shù)無界可行域為空集可行域為空集無可行解無可行解課堂練習(xí)：用圖解法求解目標(biāo)函數(shù)目標(biāo)函數(shù) Max z = 3x1 + 9x2 約束條件約束條件 s.t. x1+3x2 22 -x1+x2 4 x26 2x1-5x2 0 x1 ,x2 0v答案：答案：v無窮多最優(yōu)解，最優(yōu)解在第一條直無窮多最優(yōu)解，最優(yōu)解在第一條直線確定的可行域邊界上，最優(yōu)值為線確定的可行域邊界上，最優(yōu)值為66。六、LP問題圖解法的靈敏度分析主要研究線性規(guī)劃模型中的一些系數(shù)主要研究線性規(guī)劃模型中的

19、一些系數(shù)cj，bi，aij變化時，對最優(yōu)解產(chǎn)生的影響。變化時，對最優(yōu)解產(chǎn)生的影響。1、目標(biāo)函數(shù)系數(shù)、目標(biāo)函數(shù)系數(shù)ci的靈敏度分析的靈敏度分析系數(shù)系數(shù)ci的變動直接的變動直接影響目標(biāo)函數(shù)等值影響目標(biāo)函數(shù)等值線的斜率線的斜率k。kBCkkAB時，最時，最優(yōu)解不變。優(yōu)解不變。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400BACC1150C175C1-100對于例對于例1.5，將目標(biāo)函數(shù)系數(shù)，將目標(biāo)函數(shù)系數(shù)c1，c2作為參數(shù)作為參數(shù)來討論，目標(biāo)函數(shù)為：來討論，目標(biāo)函數(shù)為：maxz c1 x1+ c2 x2要使最優(yōu)解在點要使最優(yōu)解在點B(50,250)

20、不變，必須保持目不變，必須保持目標(biāo)函數(shù)等值線的斜率在直線標(biāo)函數(shù)等值線的斜率在直線x1+x2300和和x2250之間。之間。即即-1- c1 / c2 0當(dāng)當(dāng)c150不變時，不變時， -1- 50 / c2 0即即c2的取值范圍為的取值范圍為c250；當(dāng)當(dāng)c2 100不變時，不變時， -1- c1 / 100 0即即c2的取值范圍為的取值范圍為100 c10課堂練習(xí)v分析以下模型中分析以下模型中c1的取值范圍和最優(yōu)解之間的取值范圍和最優(yōu)解之間的關(guān)系：的關(guān)系： Max z = c1 x1 + 9x2 s.t. x1+x2 6 x1+2x2 10 x1 ,x2 02、約束條件中右端常數(shù)、約束條件中右

21、端常數(shù)bi的靈敏度分析的靈敏度分析例例1.5中，當(dāng)設(shè)備臺時數(shù)中，當(dāng)設(shè)備臺時數(shù)增加增加10個單位時，第一個單位時，第一個約束條件變?yōu)椋簜€約束條件變?yōu)椋?x1+x2310，可行域發(fā)生，可行域發(fā)生變化。變化。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400 x1+x2310此時最優(yōu)解為：此時最優(yōu)解為：x160 ， x2250最優(yōu)值為最優(yōu)值為z*28000比原最優(yōu)值增加了比原最優(yōu)值增加了28000-27500500（元）（元）ABCDX1X2O300200100100200300400BC可見每增加一個臺時的設(shè)備就可以多獲得可見每增加一個臺時的設(shè)備就可

22、以多獲得500/1050元的利潤。元的利潤。資源常數(shù)每增加一個單位而使最優(yōu)目標(biāo)函數(shù)資源常數(shù)每增加一個單位而使最優(yōu)目標(biāo)函數(shù)值得到值得到改進(jìn)改進(jìn)的數(shù)量，稱為該資源的的數(shù)量，稱為該資源的對偶價格對偶價格。設(shè)備的對偶價格為設(shè)備的對偶價格為50元元/臺時。臺時。問題：一般情況下設(shè)備租價為問題：一般情況下設(shè)備租價為20元元/臺時，最臺時，最近設(shè)備緊張，要增加設(shè)備，出價高達(dá)近設(shè)備緊張，要增加設(shè)備，出價高達(dá)40元元/臺臺時。問是否應(yīng)該增加租用設(shè)備？時。問是否應(yīng)該增加租用設(shè)備？當(dāng)原料當(dāng)原料A的限制變?yōu)榈南拗谱優(yōu)?2x1+x2410時，可行域時，可行域會擴(kuò)大。會擴(kuò)大。但不會影響最優(yōu)解和最但不會影響最優(yōu)解和最優(yōu)值。

23、優(yōu)值。故原料故原料A的對偶價格為的對偶價格為0。ABCDX1X2O300200100100200300400例例1.5中，當(dāng)原材料中，當(dāng)原材料B增加增加10個單位時，第三個約束條件個單位時，第三個約束條件變?yōu)椋鹤優(yōu)椋簒2260，可行域發(fā)生，可行域發(fā)生變化。變化。最優(yōu)解變?yōu)樽顑?yōu)解變?yōu)镵(40,260)，最優(yōu)，最優(yōu)值變?yōu)橹底優(yōu)?8000。可見原材料。可見原材料B的對偶價格為的對偶價格為50。X1X2Ox1+x2300300200100100200300400 x22502x1+x2400 x2260K思考題：對于目標(biāo)函數(shù)思考題：對于目標(biāo)函數(shù)最小化最小化的的LP模型，模型，A、如果、如果i 約束條件中約束條件中bi的對偶價格為的對偶價格為30， bi增加增加2，則其最優(yōu)目標(biāo)函數(shù)值將，則其最優(yōu)目標(biāo)函數(shù)值將 ；B、如果、如果bi的對偶價格為的對偶價格為20， bi增加增加2，則，則其目標(biāo)函數(shù)值將會其目標(biāo)函數(shù)