第一章 線性規(guī)劃

1、(linear programming, lp)概概 述述 線性規(guī)劃問題的提出最早是線性規(guī)劃問題的提出最早是19391939年由前蘇聯(lián)數(shù)年由前蘇聯(lián)數(shù)學(xué)家康托洛維奇在研究鐵路運(yùn)輸?shù)慕M織問題、學(xué)家康托洛維奇在研究鐵路運(yùn)輸?shù)慕M織問題、工業(yè)生產(chǎn)的管理問題時提出來的。工業(yè)生產(chǎn)的管理問題時提出來的。 19471947年，美國學(xué)者丹西格（年，美國學(xué)者丹西格（g.b.dantzigg.b.dantzig）提）提出了線性規(guī)劃問題的單純形方法。出了線性規(guī)劃問題的單純形方法。 線性規(guī)劃理論最為成熟、應(yīng)用最為廣泛線性規(guī)劃理論最為成熟、應(yīng)用最為廣泛 第一節(jié) 線性規(guī)劃問題及其數(shù)學(xué)模型一、問題提出一、問題提出（生產(chǎn)計(jì)劃問題

2、）某企業(yè)利用（生產(chǎn)計(jì)劃問題）某企業(yè)利用a、b、c三種資源，三種資源，在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)在計(jì)劃期內(nèi)生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品資源的消耗、單位產(chǎn)品利潤等數(shù)據(jù)如下表，問如品資源的消耗、單位產(chǎn)品利潤等數(shù)據(jù)如下表，問如何安排生產(chǎn)計(jì)劃使企業(yè)利潤最大？何安排生產(chǎn)計(jì)劃使企業(yè)利潤最大？ 產(chǎn)產(chǎn) 品品資資 源源甲甲乙乙資源限制資源限制abc120111300kg400kg250kg單位產(chǎn)品利潤單位產(chǎn)品利潤(元元/件件)50100 決策變量決策變量：x1、x2分別代表甲、乙兩分別代表甲、乙兩種產(chǎn)品的生產(chǎn)數(shù)量。種產(chǎn)品的生產(chǎn)數(shù)量。目標(biāo)函數(shù)：目標(biāo)函數(shù)：max z=50 x1+100 x2

3、約束條件：約束條件： x1 + x2300 2x1 + x2400 x2250即有：即有： max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20稱之為上述問題的數(shù)學(xué)模型。稱之為上述問題的數(shù)學(xué)模型。 例例2 靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流靠近某河流有兩個化工廠，流經(jīng)第一化工廠的河流流量為每天流量為每天500萬萬m3，在兩個工廠之間有一條流量為，在兩個工廠之間有一條流量為200萬萬m3的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污的支流。兩化工廠每天排放某種有害物質(zhì)的工業(yè)污水分別為水分別為2萬萬m3和和1.4萬萬m3。從第一化工廠

4、排出的工業(yè)污。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有水流到第二化工廠以前，有20%可以自然凈化。環(huán)保要可以自然凈化。環(huán)保要求河流中工業(yè)污水含量不能大于求河流中工業(yè)污水含量不能大于0.2%。兩化工廠處理工。兩化工廠處理工業(yè)污水的成本分別為業(yè)污水的成本分別為1000元元/萬萬m3和和800元元/萬萬m3?，F(xiàn)在?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個工廠處理工業(yè)污水的費(fèi)用最小污水，使這兩個工廠處理工業(yè)污水的費(fèi)用最小.工廠工廠1工廠工廠2200萬萬m3500萬萬m3 決策變量決策變量：x1、x2分別代表工廠分別代表工

5、廠1和工廠和工廠2處處理污水的數(shù)量理污水的數(shù)量(萬萬m3)。 則目標(biāo)函數(shù)：則目標(biāo)函數(shù)：min z=1000 x1+800 x2 約束條件：約束條件：第一段河流（工廠第一段河流（工廠1工廠工廠2之間）：之間）： (2x1)/500 0.2%第二段河流：第二段河流： 0.8(2x1) +(1.4x2)/7000.2%此外有：此外有： x12； x21.4 化簡有：化簡有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20稱之為上述問題的數(shù)學(xué)模型。稱之為上述問題的數(shù)學(xué)模型。 從上述兩個例子，我們可以總結(jié)出線性規(guī)劃從上述兩個例子，我們

6、可以總結(jié)出線性規(guī)劃的數(shù)學(xué)模型的一般形式。的數(shù)學(xué)模型的一般形式。max(min) z=c1x1+c2x2+cnxn 目標(biāo)函數(shù)目標(biāo)函數(shù) a11x1+a12x2+a1nxn= (,) b1 a21x1+a22x2+a2nxn= (,) b2 約束條件約束條件 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 模型特點(diǎn)：目標(biāo)函數(shù)模型特點(diǎn)：目標(biāo)函數(shù)(objective function)與與約束條件約束條件(constraint)均為線性的；目標(biāo)函均為線性的；目標(biāo)函數(shù)實(shí)現(xiàn)極大化或極小化。數(shù)實(shí)現(xiàn)極大化或極小化。 第二節(jié)第二節(jié) 線性規(guī)劃圖解法線性規(guī)劃圖解法 (graphical sol

7、ution)一、基本概念一、基本概念 可行解可行解(feasible solution)任一滿足約束條任一滿足約束條件的一組決策變量的數(shù)值；件的一組決策變量的數(shù)值； 可行域可行域(feasible region)所有可行解組成所有可行解組成的集合，也稱為可行解集；的集合，也稱為可行解集； 目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線(objective function line)為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值；為于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值；二、圖解法步驟二、圖解法步驟(procedure)（1）畫出線性規(guī)劃問題的可行域；）畫出線性規(guī)劃問題的可行域；（2）畫出兩條目標(biāo)函數(shù)等值線；）畫出兩

8、條目標(biāo)函數(shù)等值線；（3）平行移動目標(biāo)函數(shù)等值線，使目標(biāo)函數(shù)在可）平行移動目標(biāo)函數(shù)等值線，使目標(biāo)函數(shù)在可行域范圍內(nèi)達(dá)到最優(yōu)。行域范圍內(nèi)達(dá)到最優(yōu)。三、圖解法舉例三、圖解法舉例例例1 max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z* =27500z1=50 x1+100 x2=0boacdz2=14000該問題有唯一最優(yōu)解該問題有唯一最優(yōu)解x1=50=50；x2=250=250 x1 + x23002x1 + x2400 x2250例例2 max z=50 x1+50 x2 x1 + x2300 2x1 + x2400 x22

9、50 x1、x20 x2x1z1=50 x1+50 x2=0b點(diǎn)和點(diǎn)和c點(diǎn)所代表的坐點(diǎn)所代表的坐標(biāo)同時為最優(yōu)解，即該標(biāo)同時為最優(yōu)解，即該問題有問題有無窮多最優(yōu)解無窮多最優(yōu)解boacdx1 + x23002x1 + x2400 x2250max z=50 x1+100 x2z* =27500z2=15000例例3 max z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 問題有無界解問題有無界解 (unbounded)例例4 min z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 有唯一最優(yōu)解有唯一最優(yōu)解111z=32z=5oa2x1xx1x2 1x1 + 2x

10、20例例4 max z =x1+x2 x1 + 2x21 x1 + x22 x1、x20 問題無可行解問題無可行解 (no feasible solution)直直 觀觀 結(jié)結(jié) 論論1) 可行域可以是個凸多邊形，可能無界，也可可行域可以是個凸多邊形，可能無界，也可能為空；能為空；2) 若線性規(guī)劃問題的最優(yōu)解存在，它一定可以若線性規(guī)劃問題的最優(yōu)解存在，它一定可以在可行域的某一個頂點(diǎn)上得到；在可行域的某一個頂點(diǎn)上得到；3) 若在兩個頂點(diǎn)上同時得到最優(yōu)解，則該兩點(diǎn)若在兩個頂點(diǎn)上同時得到最優(yōu)解，則該兩點(diǎn)連線上的所有點(diǎn)都是最優(yōu)解，即連線上的所有點(diǎn)都是最優(yōu)解，即lp有無窮多有無窮多最優(yōu)解；最優(yōu)解；4) 若

11、可行域非空有界，則一定有最優(yōu)解。若可行域非空有界，則一定有最優(yōu)解。四、線性規(guī)劃問題的標(biāo)準(zhǔn)形式四、線性規(guī)劃問題的標(biāo)準(zhǔn)形式(standard form) 規(guī)定如下形式的線性規(guī)劃數(shù)學(xué)模型為規(guī)定如下形式的線性規(guī)劃數(shù)學(xué)模型為lp標(biāo)準(zhǔn)形式。標(biāo)準(zhǔn)形式。max z=c1x1+c2x2+cnxn 目標(biāo)函數(shù)目標(biāo)函數(shù) a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 約束條件約束條件 am1x1+am2x2+amnxn= bm x1，x2，xn0 特點(diǎn)：特點(diǎn)：zmax；約束條件為等號；變量非負(fù)；約束條件為等號；變量非負(fù)；右端常數(shù)項(xiàng)大等于零。右端常數(shù)項(xiàng)大等于零。上述標(biāo)準(zhǔn)形式的線性

12、規(guī)劃模型還可寫成如下一些形式上述標(biāo)準(zhǔn)形式的線性規(guī)劃模型還可寫成如下一些形式: :(1) (2) njjj=1nijjij=1jmaxz =c xa x = bi = 1, . ,mx0 j = 1, . ,n0njjj=1jm axz = cxp x= bxj = 1, . ,n (3) (5)0njjj=1jmaxz = cxp x = bxj = 1, . ,nm axz = cxax = bx0xmaxz =cx r = x ax =b,x0r r (4) 五、化非標(biāo)準(zhǔn)形為標(biāo)準(zhǔn)形五、化非標(biāo)準(zhǔn)形為標(biāo)準(zhǔn)形（1）若）若min f=cx 此時可令：此時可令：z =f，則，則max z=min f

13、 =cx，這樣處理所得最優(yōu)解不變；這樣處理所得最優(yōu)解不變；舉例：舉例： min z =x1x2 2x1 + x22 x1 + x21 x1、x20 max f =x1+ x2z=-1/2f=0f=1/2z=0f=-z=8/3（1/3，4/3）(2)約束條件為約束條件為“”時，時，aijxjbi aijxj + xn+i = bi xn+i 松弛變量松弛變量(slack variable)；(3)約束條件為約束條件為“”時，時，aijxj bi aijxj xn+i = bi xn+i 過剩變量過剩變量(surplus variable)；這樣處理所得最優(yōu)解不變這樣處理所得最優(yōu)解不變；max z

14、 =x1+10 x2 x1 + 2x2100 x1、x20 max z =x1+10 x2 x1 + 2x2 + x3=100 x1、x200（4）若）若xk為無限制，為無限制， 則令則令xk=xk1xk2，其中其中xk1、xk20（5）若）若bi 0舉例舉例: 化下列線性規(guī)劃為標(biāo)準(zhǔn)形化下列線性規(guī)劃為標(biāo)準(zhǔn)形 max z=2x1+2x24x3 x1 + 3x23x3 30 x1 + 2x24x380 x1、x20，x3無限制無限制max z=2x1+2x24x3+4x3” x1 + 3x23x3+3x3” x4 = 30 x1 + 2x24x3+ 4x3” + x5 = 80 x1、x2 、x3

15、、x3” 、x4、x5 0第三節(jié)第三節(jié) 線性規(guī)劃問題解的性質(zhì)線性規(guī)劃問題解的性質(zhì) (properties of solution of lp) 一、線性規(guī)劃問題的基本概念一、線性規(guī)劃問題的基本概念(concepts)對于標(biāo)準(zhǔn)形式的線性規(guī)劃：對于標(biāo)準(zhǔn)形式的線性規(guī)劃： max z=cx （a） ax=b x0 （b）1.可行解可行解(feasible solution)滿足約束條件（滿足約束條件（b）的）的點(diǎn)點(diǎn)x=（x1，x2，xn）t稱為該稱為該lp的一個可行解；的一個可行解；2.最優(yōu)解最優(yōu)解(optimal solution)使目標(biāo)函數(shù)值達(dá)到最大使目標(biāo)函數(shù)值達(dá)到最大的可行解的可行解3基基、基變

16、量、非基變量、基變量、非基變量 (base, basic variable, nonbasic variable) 設(shè)約束方程的系數(shù)矩陣設(shè)約束方程的系數(shù)矩陣a中，有中，有m個線性無關(guān)的列向量，個線性無關(guān)的列向量， 且設(shè)且設(shè) b=（p1，p2，pm）線性無關(guān)，線性無關(guān)，則稱則稱b為為該該lp的一個基；的一個基； 相應(yīng)的相應(yīng)的 p1，p2，pm為基向量為基向量； 與之對應(yīng)的變量與之對應(yīng)的變量 x1，x2，xm基變量基變量，記為：，記為：xb= （x1，x2，xm）t ； 其余的向量為其余的向量為非基向量非基向量，記為：，記為：n=（pm+1，pm+2，pn）； 其余的變量為其余的變量為非基變量非基

17、變量 ，記為：，記為：xn=（xm+1，xm+2，xn）t；4 4基本解基本解 ( (basic solutionbasic solution) )將將ax=b改寫改寫 （b，n）（）（xb，xn）t=b有：有： bxb=bnxn令令 xn=0得到得到 bxb=b 線性方程組。線性方程組。由于由于b中各列向量線性無關(guān)，因此解此方程組有唯一解中各列向量線性無關(guān)，因此解此方程組有唯一解即：即： xb= （x10，x20，xm0）t于是得到于是得到ax=b的一個確定的解：的一個確定的解： x0=（xb，xn）t =（x10，x20，xm0，0，0，0）t稱稱x0為該線性規(guī)劃對應(yīng)與基為該線性規(guī)劃對應(yīng)與

18、基b的一個的一個基本解基本解。同樣，在同樣，在a中任選中任選m個線性無關(guān)的列向量都可以組成一個基，個線性無關(guān)的列向量都可以組成一個基，對應(yīng)基一個基本解。對于一個對應(yīng)基一個基本解。對于一個lp最多有多少呢？從最多有多少呢？從n個中個中選選m個進(jìn)行組合，即：個進(jìn)行組合，即：cnm=n！/（nm）?。?！m！因此，基本解是有限的。因此，基本解是有限的。舉例：找出下列舉例：找出下列l(wèi)p所有的基及其對應(yīng)的基本解所有的基及其對應(yīng)的基本解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化為標(biāo)準(zhǔn)型解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0 x3+0 x4 2

19、x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0abcdeox1x22x1+3x2 =1004x1 + 2x2 =120基本解如下表基本解如下表 基基基本解基本解可行可行否否目標(biāo)值目標(biāo)值對應(yīng)圖對應(yīng)圖中的點(diǎn)中的點(diǎn)b1=(p1，p2)b2=(p1，p3)b3=(p1，p4)b4=(p2，p3)b5=(p2，p4)b6=(p3，p4)x1=(20，20，0，0)tx2=(30，0，40，0)tx3=(50，0，0，80)tx4=(0，60，80，0)tx5=(0，100/3，0，160/3)tx6=(0，0，100，120)t 200180400

20、/30bcdeao二、線性規(guī)劃的基本定理二、線性規(guī)劃的基本定理(theorems)1.定義定義 凸集凸集設(shè)設(shè)k是是n維歐氏空間的一個點(diǎn)集，若任意兩點(diǎn)維歐氏空間的一個點(diǎn)集，若任意兩點(diǎn)x(1)k，x(2)k的連線上所有的點(diǎn)的連線上所有的點(diǎn)x=x（1）+（1）x（2）k，（01），則稱，則稱k為凸集。為凸集。2.定理定理1 若線性規(guī)劃存在可行域，則其可行域若線性規(guī)劃存在可行域，則其可行域r=x|ax=b，x0是凸集。是凸集。3.定理定理2 線性規(guī)劃問題的可行解線性規(guī)劃問題的可行解x=（x1，x2，xn）t為基可行為基可行解的充要條件是：解的充要條件是：x的非零分量所對應(yīng)的系數(shù)列向量是線性無關(guān)的非零分

21、量所對應(yīng)的系數(shù)列向量是線性無關(guān)的。的。4.定理定理3 如果線性規(guī)劃有可行解，則一定有基可行解。如果線性規(guī)劃有可行解，則一定有基可行解。5.定理定理4 線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點(diǎn)。線性規(guī)劃問題的基可行解對應(yīng)于可行域的頂點(diǎn)。6.定理定理5 若線性規(guī)劃問題的可行域非空有界，則線性規(guī)劃問題的最若線性規(guī)劃問題的可行域非空有界，則線性規(guī)劃問題的最優(yōu)解一定可以在其可行域的某個頂點(diǎn)上得到；優(yōu)解一定可以在其可行域的某個頂點(diǎn)上得到；第四節(jié)第四節(jié) 單純形法單純形法 (simplex method) 基本思想基本思想：在有限的基可行解中尋找最優(yōu)解。即，從初始基：在有限的基可行解中尋找最優(yōu)解。即，從初始基

22、可行解出發(fā)，轉(zhuǎn)換到另一個基可行解，使目標(biāo)值增大，直到達(dá)到可行解出發(fā)，轉(zhuǎn)換到另一個基可行解，使目標(biāo)值增大，直到達(dá)到最優(yōu)解，或判斷出無最優(yōu)解為止。最優(yōu)解，或判斷出無最優(yōu)解為止。一、引例一、引例 用單純形方法求解下列線性規(guī)劃用單純形方法求解下列線性規(guī)劃 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化為標(biāo)準(zhǔn)型解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0（1）找初始可行基：）找初始可行基：b1=（p3，p4）現(xiàn)成的初始可行基；現(xiàn)成

23、的初始可行基；此時，此時， xb=（x3，x4）t，xn=（x1，x2）t用用xn表示表示z和和xb有：有： max z=6x1+4x2 x3 =1002x13x2 +x4 =1204x12x2令令 xn=(0,0)t有有 xb=(100,120)t則有：則有： x（1）=（0，0，100，120）t為對應(yīng)于基為對應(yīng)于基b1的基可行解。的基可行解。問：問： x（1）是否最優(yōu)呢？是否最優(yōu)呢？否否因?yàn)椋阂驗(yàn)椋?x1和和x2在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)x1，z；x2，z。且：且： 稱非基變量在目標(biāo)函數(shù)中的系數(shù)為稱非基變量在目標(biāo)函數(shù)中的系數(shù)為檢驗(yàn)數(shù)檢驗(yàn)數(shù)。（2）尋找可行基）尋找

24、可行基b2，使其對應(yīng)的基可行解，使其對應(yīng)的基可行解x（2）能使目標(biāo)函數(shù)值增加。能使目標(biāo)函數(shù)值增加。選：選： x10則有：則有： x（2）=（x1，0，x3，x4）t要使為要使為x（2）基可行解，基可行解，x3，x4中必有一個為零，而另一個大等于零。中必有一個為零，而另一個大等于零。只要取只要取 x1=min100/2，120/4=30就有就有 x3=40，x4=0這樣這樣 x（2）=（30，0，40，0）t因?yàn)橐驗(yàn)?p1，p3線性無關(guān)，因此，線性無關(guān)，因此，b2=（p1，p3）為一個基為一個基而而 x（2）為對應(yīng)于為對應(yīng)于b2的基可行解的基可行解此時此時 xb=（x1，x3）t，xn=（x2，

25、x4）t用用xn表示表示z和和xb有：有： max z=180+2x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4問：問： x（2）是否最優(yōu)呢？是否最優(yōu)呢？否否因?yàn)椋阂驗(yàn)椋?x2在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)在目標(biāo)函數(shù)中的系數(shù)為正，當(dāng)x2，z。（3）尋找可行基）尋找可行基b3，使其對應(yīng)的基可行解，使其對應(yīng)的基可行解x（3）能使目標(biāo)函數(shù)值增加。能使目標(biāo)函數(shù)值增加。選：選： x20則有：則有： x（3）=（x1，x2，x3，0）t要使為要使為x（3）基可行解，基可行解，x1，x3中必有一個為零，而另一個大等于零。中必有一個為零，而另一個大等于零

26、。只要取只要取 x2=min30/（1/2），），40/2=20就有就有 x1=20，x3=0這樣這樣 x（3）=（20，20，0，0）t因?yàn)橐驗(yàn)?p1，p2線性無關(guān)，因此，線性無關(guān)，因此，b3=（p1，p2）為一個基為一個基而而 x（3）為對應(yīng)于為對應(yīng)于b3的基可行解的基可行解此時此時 xb=（x1，x2）t，xn=（x3，x4）t用用xn表示表示z和和xb有：有： max z=2001/2）x3（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4問：問： x（3）是否最優(yōu)呢？是否最優(yōu)呢？是，是，求解過程求解過程：從引例可以總結(jié)出求解

27、過程：（：從引例可以總結(jié)出求解過程：（1）找出初始基及其基可行）找出初始基及其基可行解；（解；（2）判斷是否為最優(yōu)解，是停止，否則轉(zhuǎn)下一步；（）判斷是否為最優(yōu)解，是停止，否則轉(zhuǎn)下一步；（3）轉(zhuǎn)換可）轉(zhuǎn)換可行基，并求出相應(yīng)的基可行解，使目標(biāo)函數(shù)值有所改進(jìn)，轉(zhuǎn)（行基，并求出相應(yīng)的基可行解，使目標(biāo)函數(shù)值有所改進(jìn)，轉(zhuǎn)（2）。）。二、單純形方法二、單純形方法 1檢驗(yàn)數(shù)檢驗(yàn)數(shù)( evaluation index)檢驗(yàn)數(shù)檢驗(yàn)數(shù)用非基變量表示目標(biāo)函數(shù)后，非基變量在目標(biāo)函數(shù)中的系數(shù)用非基變量表示目標(biāo)函數(shù)后，非基變量在目標(biāo)函數(shù)中的系數(shù) 設(shè)有標(biāo)準(zhǔn)形式的線性規(guī)劃問題：設(shè)有標(biāo)準(zhǔn)形式的線性規(guī)劃問題：max z=cx；ax

28、=b，x0； 現(xiàn)假定現(xiàn)假定 a中存在一可行基中存在一可行基b 又設(shè)又設(shè) b=（p1，p2，pm）；且；且b為單位陣為單位陣 這樣這樣 ax=b可以描述成如下形式，也就是用非基變量表示基變量可以描述成如下形式，也就是用非基變量表示基變量 x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm即即 從上述約束方程中可以得到對應(yīng)于基從上述約束方程中可以得到對應(yīng)于基b的基可行解的基可行解 x=（b1，b2，bm，0，0）tniiijjj=m+1x = b -a xi = 1,.,m 用

29、非基變量表示目標(biāo)函數(shù)有：用非基變量表示目標(biāo)函數(shù)有： 令令 有有 式中式中 j為基可行解為基可行解x的檢驗(yàn)數(shù)。的檢驗(yàn)數(shù)。更一般性：更一般性： nmnjjiijjj=1i=1j=m+1z=cx =cx +cxmnniiijjjji=1j=m+1j=m+1mnmiijiijji=1j=m+1i=1=c (b -a x )+c x=c b +(c -c a )xmm0iijjiiji=1i=1z =cb; =c -c an0jjj = m + 1z = z+x0iijjiijiiiiz =cb; =c -ca0jjjjz=z +x2 2最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn)(optimality testing) 判別

30、定理判別定理1：設(shè)：設(shè)x為線性規(guī)劃的一個基可行解，且為線性規(guī)劃的一個基可行解，且對于一切對于一切jj（j為非基變量的下標(biāo)集）有為非基變量的下標(biāo)集）有j0，則則x為線性規(guī)劃的最優(yōu)解；為線性規(guī)劃的最優(yōu)解； 判別定理判別定理2：設(shè)：設(shè)x為線性規(guī)劃的一個基可行解，且為線性規(guī)劃的一個基可行解，且對于一切對于一切jj（j為非基變量的下標(biāo)集）有為非基變量的下標(biāo)集）有j0，同時有某個非基變量的檢驗(yàn)數(shù)同時有某個非基變量的檢驗(yàn)數(shù)k=0（kj），則，則該線性規(guī)劃有無窮多最優(yōu)解；該線性規(guī)劃有無窮多最優(yōu)解； 判別定理判別定理3：設(shè)：設(shè)x為線性規(guī)劃的一個基可行解，若為線性規(guī)劃的一個基可行解，若有有k0（kj），且，且pk

31、0，則該線性規(guī)劃問題具，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。有無界解（無最優(yōu)解）。3 3 單純形表單純形表(simplex tableau)對于線性規(guī)劃：對于線性規(guī)劃：max z=z0 + m+1xm+1 + + nxn x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm x1，x2，xn0列如下單純形表：列如下單純形表：cjc1c2cmcm+1cnbcbxbx1x2xmxm+1xnc1x1100a1,m+1a1nb1c2x2010a2,m+1a2nb2cmxm001a

32、m,m+1amnbm -z0000m+1n-z0 單純形表的說明與功能：單純形表的說明與功能：（1）一個基對應(yīng)一個單純形表，且單純形表中必須有一個初始單位）一個基對應(yīng)一個單純形表，且單純形表中必須有一個初始單位基?；＃?）從單純表中，可立即得到一個基可行解，如上表中：）從單純表中，可立即得到一個基可行解，如上表中： x=（b1，b2，bm，0，0）t為基可行解。為基可行解。（3）很容易計(jì)算檢驗(yàn)數(shù)，并可判別上述基可行解是否為最優(yōu)解或線）很容易計(jì)算檢驗(yàn)數(shù)，并可判別上述基可行解是否為最優(yōu)解或線性規(guī)劃問題無最優(yōu)解。性規(guī)劃問題無最優(yōu)解。 4. 4. 單純形法計(jì)算步驟單純形法計(jì)算步驟（1）找出初始可行基

33、，建立初始單純形表；）找出初始可行基，建立初始單純形表；（2）計(jì)算檢驗(yàn)數(shù)，若對于一切）計(jì)算檢驗(yàn)數(shù)，若對于一切jj有有j0，則已得到線性規(guī)劃的最則已得到線性規(guī)劃的最優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)下一步；優(yōu)解，可停止計(jì)算，否則轉(zhuǎn)下一步；（3）若有）若有k0（kj），），且且pk0，則該線性規(guī)劃問題具有無界解，則該線性規(guī)劃問題具有無界解（無最優(yōu)解），停止計(jì)算，否則轉(zhuǎn)下一步；（無最優(yōu)解），停止計(jì)算，否則轉(zhuǎn)下一步；（4）根據(jù)）根據(jù)maxj|j0=k，確定確定xk為換入變量；為換入變量； 按按規(guī)則確定換出變量，即規(guī)則確定換出變量，即 =bi/aik|aik0=bs/ask，對應(yīng)的，對應(yīng)的xs為換出變量，轉(zhuǎn)下一步

34、；為換出變量，轉(zhuǎn)下一步；（5）以）以ask為主元素進(jìn)行迭代，得新的單純形表，轉(zhuǎn)（為主元素進(jìn)行迭代，得新的單純形表，轉(zhuǎn)（2）三、單純形法解題舉例三、單純形法解題舉例 例例1：用單純形法求解：用單純形法求解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化為標(biāo)準(zhǔn)型解：化為標(biāo)準(zhǔn)型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0找初始可行基：找初始可行基：b1=（p3，p4）現(xiàn)成的初始可行基；現(xiàn)成的初始可行基； 從表中有：從表中有：x（1）=（0

35、，0，100，120）t為對應(yīng)于為對應(yīng)于基基b1的基可行解，顯然不是最優(yōu)解；的基可行解，顯然不是最優(yōu)解； 根據(jù)根據(jù)maxj|j0=1，確定，確定x1為換入變量；為換入變量； 按按規(guī)則確定換出變量，即：規(guī)則確定換出變量，即：=bi/aik|aik0=120/4，對應(yīng)的，對應(yīng)的x4為換出變量；為換出變量；cj6 4 0 0b cbxbx1 x2 x3 x4 0 0 x3x4 2 3 1 04 2 0 1100120100/2120/4(min) z6 4 0 00 列初始單純形表列初始單純形表 以以4為主元素進(jìn)行迭代，得新的單純形表：為主元素進(jìn)行迭代，得新的單純形表： 從表中有：從表中有：x（2）

36、=（30，0，40，0）t為對應(yīng)于基為對應(yīng)于基b2的基可行解，顯然不是最優(yōu)解；的基可行解，顯然不是最優(yōu)解； 根據(jù)根據(jù)maxj|j0=2，確定確定x2為換入變量；為換入變量； 按按規(guī)則確定換出變量，即：規(guī)則確定換出變量，即：=bi/aik|aik0=40/2，對應(yīng)的，對應(yīng)的x3為換出變量；為換出變量； cj cb 0 6xbx3x1z6 x10104 x221/210 x31000 x4-1/21/4-3/8b 403018040/230/(1/2) 表中表中j0，j=1，4， 因此得最優(yōu)解：因此得最優(yōu)解：x*=（20，20，0，0）t，z*=200cj6400bcbxbx1x2x3x446x1

37、x2011/2-1/410-1/4 3/82020z00-1/2-5/4200以以2為主元素進(jìn)行迭代，得新的單純形表：為主元素進(jìn)行迭代，得新的單純形表：將上述計(jì)算列在一個表中為：將上述計(jì)算列在一個表中為： cj6400b cb xb x1x2x3x4 0 x3 2310100100/2 0 x4 4201120120/4(min) z 64000 0 x3021-1/24040/2(min) 6 x111/201/43030/(1/2) z 010-3/2180 4 x2011/2-1/420 6 x110-1/43/820 z00 -1/2-5/4200例例2：用單純形法求解：用單純形法求解

38、 max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20cj50100000b cbxb x1 x2x3x4x5 0 x311100300300/1 0 x421010400400/1 0 x501001250250/1(min) z501000000 0 x31010-15050/1(min) 0 x42001-1150150/2 100 x201001250 z50000-10025000 50 x11010-1500 0 x400-21150 100 x2010-01250 z00-500-5027500 例例3：用單純形法求解：用單

39、純形法求解 max z=2x1+x2 x1 + x25 2x15x210 x1、x20 2=6 0，且，且p20，故該線性規(guī)劃有無界解。，故該線性規(guī)劃有無界解。cj2100b cbxb x1x2x3x4 0 x3-11105100/2 0 x42-50110120/4(min) z21000 0 x30-3/211/21040/2(min) 2x11-5/201/2530/(1/2) z060-110 例例4：用單純形法求解：用單純形法求解 max z=6x1+2x2+10 x3+8x4 5x1 + 6x24x34x420 3x13x2 +2x3 + 8x425 4x12x2 + x3 + 3

40、x410 x1、x2、x3、x407=340, p70,故該故該lp有無解解有無解解cj62108000bcbxb x1x2x3x4x5x6x70 x556-4-4100200 x63-328010250 x74-21300110 z6210800000 x521-208104600 x6-510201-2510 x34-21300110 z-34220-2200-101000 x5110012120702x2-510201-2510 x3-601702-320 z7600-660-2234210四、極小化問題四、極小化問題(minimization problem) 若標(biāo)準(zhǔn)形式的線性規(guī)劃問題

41、的目標(biāo)函數(shù)是極小化形式，則問題若標(biāo)準(zhǔn)形式的線性規(guī)劃問題的目標(biāo)函數(shù)是極小化形式，則問題的判別準(zhǔn)則就會有所改變。這樣三個判別定理如下的判別準(zhǔn)則就會有所改變。這樣三個判別定理如下： 判別定理判別定理1：設(shè)：設(shè)x為線性規(guī)劃的一個基可行解，且對于一切為線性規(guī)劃的一個基可行解，且對于一切jj（j為非基變量的下標(biāo)集）有為非基變量的下標(biāo)集）有j 0，則，則x為線性規(guī)劃的最優(yōu)解；為線性規(guī)劃的最優(yōu)解； 判別定理判別定理2：設(shè)：設(shè)x為線性規(guī)劃的一個基可行解，且對于一切為線性規(guī)劃的一個基可行解，且對于一切jj（j為非基變量的下標(biāo)集）有為非基變量的下標(biāo)集）有j 0，同時有某個非基變量的檢，同時有某個非基變量的檢驗(yàn)數(shù)驗(yàn)數(shù)

42、k=0（kj），則該線性規(guī)劃有無窮多最優(yōu)解；，則該線性規(guī)劃有無窮多最優(yōu)解； 判別定理判別定理3：設(shè)：設(shè)x為線性規(guī)劃的一個基可行解，若有為線性規(guī)劃的一個基可行解，若有k 0（kj），且，且pk0，則該線性規(guī)劃問題具有無界解（無最優(yōu)，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。解）。上述單純形法的基礎(chǔ)是線性規(guī)劃問題有初始基可行上述單純形法的基礎(chǔ)是線性規(guī)劃問題有初始基可行解。有些線性規(guī)劃問題化為標(biāo)準(zhǔn)形式以后，就存在解。有些線性規(guī)劃問題化為標(biāo)準(zhǔn)形式以后，就存在初始可行基，如約束條件全部為初始可行基，如約束條件全部為“”的線性規(guī)劃的線性規(guī)劃問題。對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題，若約束方程問題。對于標(biāo)準(zhǔn)形式的線性

43、規(guī)劃問題，若約束方程系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則不能簡單系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則不能簡單的用上述單純形法，而通常采用所謂的人工變量法。的用上述單純形法，而通常采用所謂的人工變量法。人工變量法一般有大人工變量法一般有大m m法和兩階段法。法和兩階段法。五、人工變量法五、人工變量法(artificial variable method)（一）大（一）大m法法(big m method) 對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題a） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn=

44、b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入所謂的若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入所謂的人工變量xn+1，xn+m構(gòu)造如下形式的線性規(guī)劃問題（問題構(gòu)造如下形式的線性規(guī)劃問題（問題b） max z=c1x1+c2x2+cnxnmxn+1mxn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0 問題問題b中中m為任意大的正數(shù)。顯然問題

45、為任意大的正數(shù)。顯然問題b存在現(xiàn)成的單位基，存在現(xiàn)成的單位基，且初始基可行解中，以人工變量為基變量。且初始基可行解中，以人工變量為基變量。 關(guān)于問題關(guān)于問題b的幾點(diǎn)結(jié)論：的幾點(diǎn)結(jié)論： （1）問題）問題b要實(shí)現(xiàn)極大化，必須將人工變量從基變量中換出，要實(shí)現(xiàn)極大化，必須將人工變量從基變量中換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)極大化；否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)極大化； （2）若在求解問題）若在求解問題b的過程中，已將人工變量從基變量中換出，的過程中，已將人工變量從基變量中換出，則已得到問題則已得到問題a的一個基可行解，可繼續(xù)求解，以獲得問題的一個基可行解，可繼續(xù)求解，以獲得問題a的最優(yōu)解或判別問題的最優(yōu)解或判別問

46、題a無最優(yōu)解；無最優(yōu)解； （3）若求解問題）若求解問題b已得到最優(yōu)解，但最優(yōu)解的基變量中含有不已得到最優(yōu)解，但最優(yōu)解的基變量中含有不為零人工變量，則問題為零人工變量，則問題a無可行解；無可行解； （4）若求解問題）若求解問題b已得到最優(yōu)解，且最優(yōu)解的基變量中不含有已得到最優(yōu)解，且最優(yōu)解的基變量中不含有人工變量，則問題人工變量，則問題b的最優(yōu)解就是問題的最優(yōu)解就是問題a的最優(yōu)解。的最優(yōu)解。 例：用單純形法（大例：用單純形法（大m法）求解法）求解 max z=3x12x2x3 x1 2x2 + x3 11 4x1 + x2 +2x3 3 2x1 x3 = 1 x1、x2、x30 解：化為標(biāo)準(zhǔn)形式，

47、并引入人工變量，構(gòu)造如下模型：解：化為標(biāo)準(zhǔn)形式，并引入人工變量，構(gòu)造如下模型： max z=3x12x2x3mx6mx7 x12x2 + x3 + x4 = 11 4x1 + x2 +2x3 x5 + x6 = 3 2x1 x3 +x7 = 1 x1、x2、x30 列表計(jì)算：列表計(jì)算：cj3-1-100-m-mb cbxb x1 x2x3x4x5x6x70 x41-21100011-mx6-4120-1103-mx7-20100011 z3-6m-1+m-1+3m0-m00 0 x43-20100-110-mx60100-11-21-1x3-20100011 z1-1+m00-m0-3m+1

48、0 x43001-22-512-1x20100-11-21-1x3-20100011 z1000-1-m+1-m-1 3x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39 z000-1/3-1/3-m+1/3-m+2/32（二）兩階段法（二）兩階段法對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題對于標(biāo)準(zhǔn)形式的線性規(guī)劃問題（問題a） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入若其約束方程的系數(shù)矩陣中不存在現(xiàn)成的初始可行基，則引入所謂的人工變量所謂的人工變量xn+1，xn+m構(gòu)造如下輔助線性規(guī)劃問題構(gòu)造如下輔助線性規(guī)劃問題（問題（問題c） min w =xn+1 + + xn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0 關(guān)于問題