第二章線性規(guī)劃的圖解法一、線性規(guī)劃的概念二、線性規(guī)劃問(wèn)題的提出三、線性規(guī)劃的數(shù)學(xué)模型四、線性規(guī)劃的圖解法五、線性規(guī)劃解的情況六、LP圖解法的靈敏度分析一、線性規(guī)劃的概念線性規(guī)劃LinearProgramming簡(jiǎn)稱(chēng)LP，是一種解決在線性約束條件下追求最大或最小的線性目標(biāo)函數(shù)的方法。線性規(guī)劃的目標(biāo)和約束條件都可以表示成線性的式子。例1.1、勝利家具廠生產(chǎn)桌子和椅子兩種家具，桌子售價(jià)50元/張，椅子售價(jià)30元/張。生產(chǎn)一張桌子需要木工4h，油漆工2h，生產(chǎn)一張椅子需要木工3h，油漆工1h。該廠每月可用木工工時(shí)120h，油漆工工時(shí)50h。問(wèn)該廠每月生產(chǎn)多少?gòu)堊雷雍鸵巫硬拍苁姑吭碌匿N(xiāo)售收入最大？解：1、確定決策變量

x1、x2——每月生產(chǎn)桌子、椅子的數(shù)量；

2、確定目標(biāo)函數(shù)——銷(xiāo)售收入最大

Maxs=50x1+30x23、確定約束條件s.t.

4x1+3x2≤1202x1+x2≤504、變量非負(fù)限制x1,x2≥0二、線性規(guī)劃問(wèn)題的提出

線性規(guī)劃模型：

Maxs=50x1+30x2

s.t.

4x1+3x2≤1202x1+x2≤50x1,x2≥0例1.2某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如下表所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃單位產(chǎn)品所需原料數(shù)量（公斤）產(chǎn)品Q(chēng)1產(chǎn)品Q(chēng)2產(chǎn)品Q(chēng)3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000單位產(chǎn)品的利潤(rùn)（千元）354決策變量：每天生產(chǎn)三種產(chǎn)品的數(shù)量，分別設(shè)為x1，x2，x3；目標(biāo)：每天的生產(chǎn)利潤(rùn)最大目標(biāo)函數(shù)為Maxs＝3x1＋5x2＋4x3約束條件：每天原料的需求量不超過(guò)可用量原料P1

：2x1＋3x2＋0x3≤1500原料P2

：0x1＋2x2＋4x3≤800原料P3

：3x1＋2x2＋5x3≤2000隱含約束：產(chǎn)量為非負(fù)數(shù)x1

，x2，x3≥0數(shù)學(xué)模型：Maxs=3x1＋5x2＋4x3

s.t.

2x1＋3x2＋0x3≤15000x1＋2x2＋4x3≤8003x1＋2x2＋5x3≤2000x1

，x2，x3≥0從前面兩個(gè)例子中可以看出一般線性規(guī)劃問(wèn)題的建模過(guò)程：A、理解要解決的問(wèn)題，明確在什么條件下，要追求什么目標(biāo)；B、定義決策變量；C、用決策變量的線性函數(shù)形式寫(xiě)出所要追求的目標(biāo)，即目標(biāo)函數(shù)；D、用一組決策變量的等式或不等式來(lái)表示在解決問(wèn)題過(guò)程中所必須遵循的約束條件。1、LP模型的一般形式目標(biāo)函數(shù)：Max(Min)z=c1x1+c2x2+…+cnxn約束條件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2

...am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥(≤)0或無(wú)約束三、線性規(guī)劃的數(shù)學(xué)模型xj為待定的決策變量；cj為目標(biāo)函數(shù)系數(shù)，或價(jià)值系數(shù)、費(fèi)用系數(shù)；aij為技術(shù)系數(shù)；bj為資源常數(shù)，簡(jiǎn)稱(chēng)右端項(xiàng)；其中i＝1，2，…m；j＝1，2，…n可以看出，一般LP模型的特點(diǎn)：A、決策變量x1，x2，x3，……xn表示要尋求的方案，每一組值就是一個(gè)方案；B、約束條件是用等式或不等式表述的限制條件；C、一定有一個(gè)追求目標(biāo)，或希望最大或希望最小；D、所有函數(shù)都是線性的。2、線性規(guī)劃模型的標(biāo)準(zhǔn)型：x1≥0，x2≥0，…，xn≥0s.t.標(biāo)準(zhǔn)形式的特點(diǎn)：A、目標(biāo)函數(shù)為Max形式B、約束全為＝式C、所有決策變量xj≥0，j＝1，2，3，…nD、所有bi≥0，i＝1，2，3，……m3、如何將一般LP問(wèn)題化為標(biāo)準(zhǔn)形式A、極小化目標(biāo)函數(shù)問(wèn)題轉(zhuǎn)化為極大化目標(biāo)函數(shù)問(wèn)題：若目標(biāo)函數(shù)為：

Minf=c1x1+c2x2+…+cnxn

則可令z＝-f，原目標(biāo)等同于：

Maxz=-c1x1-c2x2-…-cnxn

但須注意,f*＝–z*B、約束條件不是等式的問(wèn)題：若約束條件為

ai1x1+ai2x2+…+ain

xn≤bi

可以引進(jìn)一個(gè)新的變量si

，使它等于約束右邊與左邊之差

si=bi–(ai1x1+ai2x2+…+ain

xn)

顯然，si

也具有非負(fù)約束，即si≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ain

xn+si=bi當(dāng)約束條件為

ai1x1+ai2x2+…+ain

xn

≥bi時(shí)，類(lèi)似地令

si=(ai1x1+ai2x2+…+ain

xn)–bi顯然，si也滿(mǎn)足非負(fù)約束，即si≥0，這時(shí)新的約束條件成為

ai1x1+ai2x2+…+ain

xn-s=bi注意：不同的約束不等式引入的變量也不同；一般稱(chēng)≤不等式中引入的變量為松弛變量，稱(chēng)≥不等式中引入的變量為剩余變量。C、變量符號(hào)限制的問(wèn)題：當(dāng)某一個(gè)變量xj

≤0時(shí)，可以令

xj=-xj’

則xj’≥0當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，可以令

xj=xj’-xj”其中xj’≥0，xj”≥0D、右端項(xiàng)有負(fù)值的問(wèn)題：如bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：-ai1x1-ai2x2-…-ain

xn=-bi

。例1.3：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x3≤15.74.1x1+3.3x3≥8.9x1+x2+x3=38x1,x2,x3≥0解：首先，將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z=-f=-3.6x1+5.2x2-1.8x3

其次考慮約束，有2個(gè)不等式約束，引進(jìn)松弛變量x4

，x5≥0。于是，我們可以得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：Maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3–x5=8.9x1+x2+x3=38x1,x2,x3,x4,x5≥0例1.4將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式minf=x1+2x2+3x3s.t.x1-x2+x3≤4x1+2x3≥8x1+x2+x3≥2x1≥0,x2≤0答案：標(biāo)準(zhǔn)型為maxz=-x1+2x2’-3x3’+3x3’’s.t.x1+x2’+x3’－

x3’’+s1=4x1+2x3’－2x3’’–s2＝8x1-x2

’+x3’－

x3’’–s3

＝2x1

，x2’

，x3’，

x3’’，

s1，s2，s3≥0（注：其中z＝-f，x2’

=-x2

，

x3’－x3’’

＝x3

）對(duì)于只有兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以在二維直角坐標(biāo)平面上作圖表示線性規(guī)劃問(wèn)題的有關(guān)概念，并求解。四、線性規(guī)劃的圖解法例1.5某工廠在計(jì)劃期內(nèi)要安排Ⅰ，Ⅱ兩種產(chǎn)品的生產(chǎn)，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗以及資源的限制如表所示：產(chǎn)品ⅠⅡ資源限制設(shè)備11300臺(tái)時(shí)原料A21400kg原料B01250kg工廠每生產(chǎn)一單位產(chǎn)品Ⅰ可以獲利50元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利100元，問(wèn)工廠應(yīng)分別生產(chǎn)多少單位產(chǎn)品Ⅰ和產(chǎn)品Ⅱ才能使獲利最多？問(wèn)題的線性規(guī)劃模型：目標(biāo)函數(shù)：maxz=50x1+100x2

約束條件：x1+x2≤300

2x1+x2≤400

x2≤250

x1≥0，x2≥0第一步：確定可行域X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400可行域第二步：作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的點(diǎn)X1X2OZ＝10000300200100100200300400等值線法線z＝0(50,250)Z＝27500等值線最優(yōu)解最優(yōu)值故原問(wèn)題最優(yōu)解為：x1＝50，x2＝250最優(yōu)值為27500。圖解法求解線性規(guī)劃問(wèn)題的步驟：

1、建立直角坐標(biāo)系。

2、畫(huà)出可行域。

3、作目標(biāo)函數(shù)的等值線

4、找出最優(yōu)解。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400最優(yōu)解：x1＝50x2＝250非可行解：x1＝200x2＝300可行解：x1＝100x2＝100可行域線性規(guī)劃中解的概念線性規(guī)劃中幾個(gè)的概念1、解：決策變量的任意一組取值；2、可行解：滿(mǎn)足約束條件（包括非負(fù)條件）的一組決策變量值，稱(chēng)可行解；3、可行域：所有可行解的集合；4、最優(yōu)解：使目標(biāo)函數(shù)值最優(yōu)（即使最大化目標(biāo)函數(shù)值最大，使最小化目標(biāo)函數(shù)最小）的可行解；5、最優(yōu)值：最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值。松弛變量的值和意義例1.5的線性規(guī)劃模型化為標(biāo)準(zhǔn)型：目標(biāo)函數(shù)：maxz=50x1+100x2

約束條件：x1+x2+s1＝300

2x1+x2+s2＝400

x2+s3＝250

x1,x2,s1,s2,s3≥0引入的松弛變量常常表示未被充分利用的資源條件。松弛變量的值和意義對(duì)最優(yōu)解x1＝50，x2＝250來(lái)說(shuō)，各松弛變量的值如下表所示：約束條件松弛變量的值設(shè)備臺(tái)時(shí)數(shù)S1=0原料AS2=50原料BS3=0松弛變量的值也可以從圖解法中獲得一些信息：X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400最優(yōu)解：x1＝50x2＝250S1=0S2>0S3=0剩余變量的值和意義請(qǐng)大家下去后閱讀教材15－17頁(yè)例2課堂練習(xí)：圖解法求解以下LP問(wèn)題目標(biāo)函數(shù)

Maxz=2500x1+1500x2

約束條件

s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0X1X2O3x1+2x2＝65302010102030403x2＝752x1+x2＝40（15，10）4050答案：最優(yōu)解為：x1＝15，x2＝10最優(yōu)值為：z*＝2500×15+1500×10

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

約束條件：x1+x2≤300

2x1+x2≤400

x2≤250

x1≥0，x2≥0

若目標(biāo)函數(shù)變?yōu)椋篗axz=50x1+50x2

2、無(wú)窮多最優(yōu)解的情況A(0,250)B(50,250)C(100,200)D(200,0)X1X2O300200100100200300400最優(yōu)情況下目標(biāo)函數(shù)的等值線與直線BC重合。這時(shí)，最優(yōu)解有無(wú)窮多個(gè)，是從點(diǎn)B到點(diǎn)C線段上的所有點(diǎn)，最優(yōu)值為15000。2、無(wú)窮多最優(yōu)解的情況3、無(wú)界解的情況若將例1.5的線性規(guī)劃模型中約束條件1、2的不等式符號(hào)改變，則線性規(guī)劃模型變?yōu)椋耗繕?biāo)函數(shù)：Maxz=50x1+100x2

約束條件：x1+x2≥

300

2x1+x2≥

400

x2≤250

x1≥0，x2≥0X1X2可行域成為一個(gè)無(wú)上界的區(qū)域。這時(shí)，沒(méi)有有限最優(yōu)解。3、無(wú)界解的情況4、無(wú)可行解的情況在例1.5的線性規(guī)劃模型中，如果增加約束條件x1≥400，則模型變?yōu)椋耗繕?biāo)函數(shù)：Maxz=50x1+100x2

約束條件：x1+x2≤300

2x1+x2≤400

x2≤250

x1≥400x1≥0，x2≥04、無(wú)可行解的情況可行域成為空的區(qū)域。這時(shí)，沒(méi)有可行解，顯然線性規(guī)劃問(wèn)題無(wú)解。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400x1＝400根據(jù)以上例題，進(jìn)一步分析可知線性規(guī)劃的可行域和最優(yōu)解有以下幾種可能的情況，簡(jiǎn)圖如下：可行域有界—唯一最優(yōu)解可行域有界—多個(gè)最優(yōu)解可行域無(wú)界—唯一最優(yōu)解可行域無(wú)界—無(wú)窮多最優(yōu)解可行域無(wú)界—目標(biāo)函數(shù)無(wú)界可行域?yàn)榭占獰o(wú)可行解課堂練習(xí)：用圖解法求解目標(biāo)函數(shù)

Maxz=3x1+9x2

約束條件

s.t.x1+3x2≤22-x1+x2≤4x2≤62x1-5x2≤0x1,x2≥0答案：無(wú)窮多最優(yōu)解，最優(yōu)解在第一條直線確定的可行域邊界上，最優(yōu)值為66。六、LP問(wèn)題圖解法的靈敏度分析主要研究線性規(guī)劃模型中的一些系數(shù)cj，bi，aij變化時(shí)，對(duì)最優(yōu)解產(chǎn)生的影響。1、目標(biāo)函數(shù)系數(shù)ci的靈敏度分析系數(shù)ci的變動(dòng)直接影響目標(biāo)函數(shù)等值線的斜率k。kBC≤k≤kAB時(shí)，最優(yōu)解不變。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400BACC1＝150C1＝75C1＝-100對(duì)于例1.5，將目標(biāo)函數(shù)系數(shù)c1，c2作為參數(shù)來(lái)討論，目標(biāo)函數(shù)為：maxz＝c1x1+c2x2要使最優(yōu)解在點(diǎn)B(50,250)不變，必須保持目標(biāo)函數(shù)等值線的斜率在直線x1+x2＝300和x2＝250之間。即-1≤-c1/c2≤0當(dāng)c1＝50不變時(shí)，-1≤-50/c2≤0即c2的取值范圍為c2≥50；當(dāng)c2＝100不變時(shí)，-1≤-c1/100≤0即c2的取值范圍為100≥c1≥0課堂練習(xí)分析以下模型中c1的取值范圍和最優(yōu)解之間的關(guān)系：

Maxz=c1x1+9x2

s.t.x1+x2≤6x1+2x2≤10x1,x2≥02、約束條件中右端常數(shù)bi的靈敏度分析例1.5中，當(dāng)設(shè)備臺(tái)時(shí)數(shù)增加10個(gè)單位時(shí)，第一個(gè)約束條件變?yōu)椋簒1+x2≤310，可行域發(fā)生變化。X1X2Ox1+x2＝300300200100100200300400x2＝2502x1+x2＝400x1+x2＝310此時(shí)最優(yōu)解為：x1＝60，x2＝250最優(yōu)值為z*＝28000比原最優(yōu)值增加了28000-27500＝500（元）ABCDX1X2O300200100100200300400B’C’可見(jiàn)每增加一個(gè)臺(tái)時(shí)的設(shè)備就可以多獲得500/10＝50元的利潤(rùn)。資源常數(shù)每增加一個(gè)單位而使最優(yōu)目標(biāo)函數(shù)值得到改進(jìn)的數(shù)量，稱(chēng)為該資源的對(duì)偶價(jià)格。設(shè)備的對(duì)偶價(jià)格為50元/臺(tái)時(shí)。問(wèn)題：一般情況下設(shè)備租價(jià)為20元/臺(tái)時(shí)，最近設(shè)備緊張，要增加設(shè)備，出價(jià)高達(dá)40元/臺(tái)時(shí)。問(wèn)是否應(yīng)該增加租用設(shè)備？當(dāng)原料A的限制變?yōu)?/p>

2x1+x2≤410時(shí)，可行域會(huì)擴(kuò)大。但不會(huì)影響最優(yōu)解和最優(yōu)值。故原料A的對(duì)偶價(jià)格為0。ABCDX1X2O300200100100200300