第2章線性規(guī)劃

1、i iiiii每周可使用量每周可使用量a a（千克）（千克）1 12 25 5b b（噸）（噸）2 21 14 4c c（百工時(shí)）（百工時(shí)）4 43 39 9單位產(chǎn)品利潤單位產(chǎn)品利潤（萬元）（萬元）3 32 2問：該公司每周應(yīng)生產(chǎn)產(chǎn)品問：該公司每周應(yīng)生產(chǎn)產(chǎn)品i i與產(chǎn)品與產(chǎn)品iiii各多少單位，各多少單位，才能使每周的獲利達(dá)到最大？才能使每周的獲利達(dá)到最大？1、線性規(guī)劃數(shù)學(xué)模型例例1 1、 穗羊公司例子穗羊公司例子（1 1）提出、分析問題）提出、分析問題1、線性規(guī)劃數(shù)學(xué)模型 x x1 1+2x+2x2 2 55 2x 2x1 1+ x+ x2 2 44 4x 4x1 1+3x+3x2 2 99

2、 x x1 1 ,x,x2 2 0 0 （2 2）根據(jù)已知條件建立數(shù)學(xué)模型）根據(jù)已知條件建立數(shù)學(xué)模型 確定變量：確定變量：需要做哪些決策需要做哪些決策設(shè)：每周生產(chǎn)產(chǎn)品設(shè)：每周生產(chǎn)產(chǎn)品xx1 1件，產(chǎn)品件，產(chǎn)品xx2 2件，總利潤件，總利潤z z元元max z=3xmax z=3x1 1+2x+2x2 2stst. .目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件1、線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃數(shù)學(xué)模型資源資源單位活動對資源的使用量單位活動對資源的使用量資源可資源可利用量利用量b1b2bna1a11a12a1na1a2a21a22a2na2 amam1am2amnam對對z的貢獻(xiàn)的貢獻(xiàn)c1c2cn生產(chǎn)計(jì)劃問題（

3、產(chǎn)品組合問題）生產(chǎn)計(jì)劃問題（產(chǎn)品組合問題）1、線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃數(shù)學(xué)模型max z= cmax z= c1 1x x1 1+c+c2 2x x2 2+ + +c cn nx xn n a a1111x x1 1+a+a1212x x2 2+ +a+a1n1nx xn na a1 1 a a2121x x1 1+a+a2222x x2 2+ +a+a2n2nx xn na a2 2 a am1m1x x1 1+a+am2m2x x2 2+ + +a amnmnx xn na am m x x1 1,x,x2 2, , ,x xn n 00st生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型：生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型

4、：設(shè)設(shè)xj（j=1,2, ,n）代表第）代表第j種產(chǎn)品的生產(chǎn)數(shù)量種產(chǎn)品的生產(chǎn)數(shù)量例例2 2 設(shè)有一批規(guī)格為設(shè)有一批規(guī)格為1010米長的圓鋼筋，將它截成分米長的圓鋼筋，將它截成分別為別為3 3米，米，4 4米長的預(yù)制構(gòu)件的短鋼筋各米長的預(yù)制構(gòu)件的短鋼筋各100100根，問怎根，問怎樣截取最省料？樣截取最省料？ 因?yàn)?，因?yàn)椋?010米長的鋼筋截為米長的鋼筋截為3 3米或米或4 4米長，共有三種截米長，共有三種截法：法：截法截法：3 3 3 1 3 3 3 1 米米截法截法：3 3 4 0 3 3 4 0 米米截法截法：4 4 0 2 4 4 0 2 米米設(shè)：按截法設(shè)：按截法，各截取各截取1010米

5、長的鋼筋分別為米長的鋼筋分別為x x1 1, x, x2 2, x, x3 3根，鋼筋總用量為根，鋼筋總用量為w w1、線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃數(shù)學(xué)模型0,10021003.min3213221321xxxxxxxtsxxxw例例2 2 中的問題常稱為中的問題常稱為下料問題下料問題1、線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃數(shù)學(xué)模型數(shù)學(xué)模型：數(shù)學(xué)模型： 下料問題的數(shù)學(xué)模型下料問題的數(shù)學(xué)模型：1、線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃數(shù)學(xué)模型min w = cmin w = c1 1x x1 1+c+c2 2x x2 2+ + +c cn nx xn n a a1111x x1 1+a+a1212x x2 2+ +a+

6、a1n1nx xn n a a1 1 a a2121x x1 1+a+a2222x x2 2+ +a+a2n2nx xn n a a2 2 a am1m1x x1 1+a+am2m2x x2 2+ + +a amnmnx xn n a am m x x1 1,x,x2 2, ,x,xn n00st（2 2）線性規(guī)劃模型必須滿足如下兩個(gè)要求：）線性規(guī)劃模型必須滿足如下兩個(gè)要求：目標(biāo)函數(shù)必須是決策變量的線性函數(shù)；目標(biāo)函數(shù)必須是決策變量的線性函數(shù)；約束條件必須是含決策變量的線性等式或不約束條件必須是含決策變量的線性等式或不等式。等式。1、線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃數(shù)學(xué)模型（1）線性規(guī)劃數(shù)學(xué)模型的三個(gè)

7、要素：）線性規(guī)劃數(shù)學(xué)模型的三個(gè)要素：決策變量、目標(biāo)函數(shù)、約束條件決策變量、目標(biāo)函數(shù)、約束條件maxz = 3x1+2x2 x1 +2x25 2x1+ x24 4x1+3x29x1 0, x20目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線最優(yōu)解最優(yōu)解0 x1x2st.可行域可行域x1+2x2=52x1+x2=44x1 +3x2=912x,231x21623*21xxz可行解：可行解：將滿足線性規(guī)劃問題的所有約束條件的變將滿足線性規(guī)劃問題的所有約束條件的變量量x x1 1和和x x2 2的一組取值稱為線性規(guī)劃問題的一個(gè)可行解。的一組取值稱為線性規(guī)劃問題的一個(gè)可行解。通常用通常用x x表示。表示?？尚杏颍嚎尚杏颍嚎?/p>

8、行解的集合稱為可行域。可行解的集合稱為可行域。最優(yōu)解：最優(yōu)解：求解線性規(guī)劃問題，就是要求使得目標(biāo)函求解線性規(guī)劃問題，就是要求使得目標(biāo)函數(shù)取最優(yōu)值（對例數(shù)取最優(yōu)值（對例1 1，就是取最大值）的可行解，這，就是取最大值）的可行解，這樣的可行解就稱為線性規(guī)劃問題的最優(yōu)解。樣的可行解就稱為線性規(guī)劃問題的最優(yōu)解。 通常用通常用x x* *表示。表示。最優(yōu)值：最優(yōu)值：通常用通常用z z* *表示表示0 x1x22x1+x2=44x1 +3x2=9x1+2x2=5l 有唯一的最優(yōu)解有唯一的最優(yōu)解l 有無窮多最優(yōu)解有無窮多最優(yōu)解（將目標(biāo)函數(shù)改為將目標(biāo)函數(shù)改為z=4xz=4x1 1+3x+3x2 2）0,934

9、425234max2121212121xxxxxxxxs.t.xxzl 無界解無界解 指線性規(guī)劃問題有可行解，但是在可行域，目指線性規(guī)劃問題有可行解，但是在可行域，目標(biāo)函數(shù)值是無界的，因而達(dá)不到有限最優(yōu)值。因此標(biāo)函數(shù)值是無界的，因而達(dá)不到有限最優(yōu)值。因此線性規(guī)劃問題不存在最優(yōu)解。線性規(guī)劃問題不存在最優(yōu)解。0,1212332max21212121xxxxxxxxzx1x2o-3x1+2x2=1x1-2x2=10,22232422max2121212121xxxxxxxxxxzl 無可行解無可行解 指找不到一組變量能滿足線性規(guī)劃的所有約束指找不到一組變量能滿足線性規(guī)劃的所有約束條件的情況，也就是線

10、性規(guī)劃問題不存在可行解，條件的情況，也就是線性規(guī)劃問題不存在可行解，或者說可行域是空集。或者說可行域是空集。x1x2o2x1-3x2=2-x1+2x2=42x1+x2=2定理定理2.1 2.1 線性規(guī)劃問題的可行域如果不是空線性規(guī)劃問題的可行域如果不是空集，就一定是凸集。集，就一定是凸集。凸集凸集非凸集非凸集x2x1x1x2x2x1x2x1x1x2x1x2凸集凸集頂點(diǎn)線性規(guī)劃的最優(yōu)解若存在，就一定在其可線性規(guī)劃的最優(yōu)解若存在，就一定在其可行域的頂點(diǎn)上行域的頂點(diǎn)上圖解法求解線性規(guī)劃問題，指出問題是哪一圖解法求解線性規(guī)劃問題，指出問題是哪一類解。類解。0,42266432min21212121xx

11、xxxxxxz一般形式：一般形式：或無約束，或或，或或，或或或0)(,.,)()()(. .min)max(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz), 1(0)(), 1(),(. .max(min)11njxmibxatsxczjnjijijnjjj或無約束其中：其中：cj價(jià)值系數(shù)；價(jià)值系數(shù)； bi限定系數(shù)；限定系數(shù)； aij工藝系數(shù)、技術(shù)系數(shù)工藝系數(shù)、技術(shù)系數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式的其他表示方式：線性規(guī)劃數(shù)學(xué)模型的一般形式的其他表示方式：（1 1）用和號）用和號“ ”“ ”表示：表

12、示：（2 2）用向量表示：）用向量表示： 或無約束，或或或0)()(.min)max(1xbpcxnjjjxtszmmjjjjnnbbbaaacccxxx21212121,bpcx其中其中（3）用矩陣表示：）用矩陣表示：或無約束0)(),(. .max(min)xbaxtscxzn21xxxxm21bbbb),(21nccccmnmmnnaaaaaaaaaa2122221112110,.,.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz特點(diǎn)：特點(diǎn)：a、目標(biāo)函數(shù)：、目標(biāo)函數(shù)：maxb、約束條件

13、：等式、約束條件：等式c、決策變量、決策變量00d d、b bi i003、如何將線性規(guī)劃數(shù)學(xué)模型的一般形式轉(zhuǎn)化、如何將線性規(guī)劃數(shù)學(xué)模型的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式為標(biāo)準(zhǔn)形式a、目標(biāo)函數(shù)：、目標(biāo)函數(shù)：max “min” 令令 z = - z max z = - cxb、約束條件：等式、約束條件：等式 “” + xs 松弛變量松弛變量 “” - xs 剩余變量剩余變量c、決策變量、決策變量0 “x0” 設(shè)設(shè) x=-x 則則x0 “x 無約束無約束” 設(shè)設(shè) x- x=xd、bi0 “bi0” 乘乘“-1” ， -bi0543,xxx其中其中 就是分別對第一、第二、第三個(gè)約束就是分別對第一、第二、第三個(gè)

14、約束條件中添加的松弛變量。條件中添加的松弛變量。 maxz = 3x1+2x2 x1 +2x25 2x1+ x24 4x1+3x29x1 0, x20st.0,934425223max5432152142132121xxxxxxxxxxxxxxxxz（2 2）變量）變量 無約束，因此取兩個(gè)變量無約束，因此取兩個(gè)變量 使得使得 。在模型中，所有的。在模型中，所有的 都用都用 代替。代替。（1 1）變量）變量 是非正的，所以要將模型中的所有是非正的，所以要將模型中的所有 都都用用 代替，其中代替，其中例例3 3 化如下的線性規(guī)劃問題模型為標(biāo)準(zhǔn)形式化如下的線性規(guī)劃問題模型為標(biāo)準(zhǔn)形式0, 022322

15、3223min321321321321xxxxxxxxxxxxz無約束1x1x1x011xx2x0, 022 xx222xxx 2x22xx (5)(5)約束條件約束條件2 2是是“”型的，因此需要在左邊加上一型的，因此需要在左邊加上一個(gè)松弛變量個(gè)松弛變量 化為等式：化為等式： 也也就是就是(4)(4)約束條件約束條件1 1是是“”型的，并且右端的常數(shù)小于零。型的，并且右端的常數(shù)小于零。因此先將其左邊減去一個(gè)剩余變量因此先將其左邊減去一個(gè)剩余變量 化為等式，即化為等式，即然后再兩端然后再兩端-1-1得，得， 也就是也就是(3)(3)目標(biāo)函數(shù)是求最小值的，因此令目標(biāo)函數(shù)是求最小值的，因此令 ，即

16、，即zz32232132122323)23(xxxxxxxxxxz 4x2324321xxxx2324321xxxx232243221 xxxxx5x22325321xxxx2233253221 xxxxx。 0,223322322223max54322153221432213221xxxxxxxxxxxxxxxxxxxxz從而得到模型的標(biāo)準(zhǔn)形式為從而得到模型的標(biāo)準(zhǔn)形式為:練習(xí)題：將線性規(guī)劃數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式練習(xí)題：將線性規(guī)劃數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式1、min z= -x1+2x2-3x3 x1+2x2+3x3 7 -x1+ x2 - x3 -2 -3x1+ x2+2x3 =5 x1 , x

17、3 0 x2 無約束無約束2、min z= 2x1-2x2+3x3 -x1+ x2+ x3 = 4 -2x1+ x2 - x36 x1 0, x2 0 ，x3無約束無約束答案：答案：1、max z= x1 2 x2+ 2 x2”+ 3x3 x1 + 2 x2 2x2” +3x3 +x4 = 7 x1 x2 + x2” + x3 x5= 2 -3x1 + x2 x2” +2x3 = 5 x1 , x2 , x2” , x3 , x4 , x5 02、max z= 2x1+2x2 3x3+ 3x3” x1+ x2 + x3 x3” = 4 2x1+ x2 x3+ x3” + x4 = 6 x1,

18、x2 , x3, x3”, x4 00,.,. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz線性規(guī)劃：線性規(guī)劃： max z = cx ax = b x 0 可行解：滿足條件可行解：滿足條件、的解的解x ； 可行域：可行解的集合；可行域：可行解的集合； 最優(yōu)解：滿足條件最優(yōu)解：滿足條件使目標(biāo)函數(shù)最大的可行解；使目標(biāo)函數(shù)最大的可行解； 可行解可行解、最優(yōu)解最優(yōu)解a a稱為線性規(guī)劃問題的系數(shù)矩陣，并且總假定其秩稱為線性規(guī)劃問題的系數(shù)矩陣，并且總假定其秩等于其行數(shù)：等于其行數(shù)： 這意味著系數(shù)矩

19、陣這意味著系數(shù)矩陣a a的各的各行是線性無關(guān)的，這也表明約束方程中的各個(gè)方程行是線性無關(guān)的，這也表明約束方程中的各個(gè)方程式相互獨(dú)立的。式相互獨(dú)立的。0. .maxxbaxtscxz用矩陣形式表示線性規(guī)劃數(shù)學(xué)模型用矩陣形式表示線性規(guī)劃數(shù)學(xué)模型mnmmnnaaaaaaaaa212222111211amrank)(a線性規(guī)劃的線性規(guī)劃的基矩陣基矩陣(基基)、基變量基變量、非基變量非基變量例：對于線性規(guī)劃問題例：對于線性規(guī)劃問題 0,6323523632max432143214214321xxxxxxxxxxxxxxxz其系數(shù)矩陣為：其系數(shù)矩陣為： 31125023基矩陣（基）：基矩陣（基）：1223

20、3152和和還能找出其它基嗎？線性規(guī)劃的線性規(guī)劃的基矩陣基矩陣(基基)、基變量基變量、非基變量非基變量基變量：基變量：就是由就是由m m個(gè)變量構(gòu)成的一組變量，其系數(shù)構(gòu)個(gè)變量構(gòu)成的一組變量，其系數(shù)構(gòu)成的行列式不等于零；反之滿足系數(shù)行列式不等于成的行列式不等于零；反之滿足系數(shù)行列式不等于零的一組零的一組m m個(gè)變量，就是基變量。個(gè)變量，就是基變量。非基變量：非基變量：線性規(guī)劃中不是基變量的變量就是非基線性規(guī)劃中不是基變量的變量就是非基變量。變量?；猓夯猓毫罘腔兞康扔诹罘腔兞康扔? 0的解。的解。基可行解：基可行解：基解基解 + + 可行解可行解 線性規(guī)劃的線性規(guī)劃的基矩陣基矩陣(基基)、基

21、變量基變量、非基變量非基變量可行解可行解基可行解基可行解非可行解非可行解基解基解解之得解之得 。故我們得到基解。故我們得到基解注意到這個(gè)基解還是一個(gè)可行解。注意到這個(gè)基解還是一個(gè)可行解。 例如，對于上面的線性規(guī)劃問題，如果取例如，對于上面的線性規(guī)劃問題，如果取x x1 1，x x2 2為為基變量，則令非基變量基變量，則令非基變量x x3 3，x x4 4為零，約束方程組為為零，約束方程組為 623232121xxxx712,71521xx0, 0,712,7154321xxxx是否所有的基解都是基可行是否所有的基解都是基可行解？（選解？（選x x1 1,x,x3 3作為基變量）作為基變量）線性

22、規(guī)劃的線性規(guī)劃的基矩陣基矩陣(基基)、基變量基變量、非基變量非基變量選擇：選擇：標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其可行解是標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其可行解是 基基可行解，最優(yōu)解可行解，最優(yōu)解 是可行解，最優(yōu)解是可行解，最優(yōu)解 能能在可行域某一個(gè)頂點(diǎn)達(dá)到。在可行域某一個(gè)頂點(diǎn)達(dá)到。a a、一定、一定 b b、不一定、不一定 c c、一定不、一定不線性規(guī)劃的線性規(guī)劃的基矩陣基矩陣(基基)、基變量基變量、非基變量非基變量=目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件行列式行列式0基矩陣基矩陣右邊常數(shù)右邊常數(shù) 定理定理2.22.2： 線性規(guī)劃問題的基可行解是線性規(guī)劃問題的基可行解是其可行域的頂點(diǎn)。其可行域的頂點(diǎn)。 定理定理

23、2.32.3： 線性規(guī)劃問題的最優(yōu)解如果線性規(guī)劃問題的最優(yōu)解如果存在，則一定有一個(gè)基可行解是最優(yōu)解。存在，則一定有一個(gè)基可行解是最優(yōu)解。 對于一般的線性規(guī)劃問題（系數(shù)矩陣對于一般的線性規(guī)劃問題（系數(shù)矩陣a am mn n），基解的個(gè)數(shù)最多為），基解的個(gè)數(shù)最多為c cn nm m個(gè)，從而基可個(gè)，從而基可行解的個(gè)數(shù)總是有限的。行解的個(gè)數(shù)總是有限的。例：例：maxz = 3x1+2x2 x1 +2x25 2x1+ x24 4x1+3x29x1 0, x20st.0,934425223max5432152142132121xxxxxxxxxxxxxxxxz基變量基變量x x1 1、x x2 2、x x

24、3 3，非基變量，非基變量x x4 4、x x5 5基解為（基解為（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3/23/2，1 1，3/23/2，0 0，0 0）是基）是基可行解，表示可行域的一個(gè)頂點(diǎn)?？尚薪?，表示可行域的一個(gè)頂點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=z=13/213/2基變量基變量x x1 1、x x2 2、x x4 4，非基變量，非基變量x x3 3、x x5 5基解為（基解為（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3/53/5，11/511/5，0 0，3/53/5，0 0）是基可行解，表示可行域的一

25、個(gè)頂點(diǎn)。是基可行解，表示可行域的一個(gè)頂點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=z=31/531/5基變量基變量x x1 1、x x2 2、x x5 5，非基變量，非基變量x x3 3、x x4 4基解為（基解為（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（1 1，2 2，0 0，0 0，-1-1）是基解，）是基解，但不是可行解，不是可行域的一個(gè)頂點(diǎn)。但不是可行解，不是可行域的一個(gè)頂點(diǎn)。基變量基變量x x2 2、x x3 3、x x4 4，非基變量，非基變量x x1 1、x x5 5基解為（基解為（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5

26、）= =（0 0，3 3，-1-1，1 1，0 0）是基解，）是基解，但不是可行解，不是可行域的一個(gè)頂點(diǎn)但不是可行解，不是可行域的一個(gè)頂點(diǎn)基變量基變量x x2 2、x x3 3、x x4 4，非基變量，非基變量x x1 1、x x5 5基解為（基解為（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（0 0，4 4，-5-5，0 0，-3-3）是基）是基解，但不是可行解，不是可行域的一個(gè)頂點(diǎn)解，但不是可行解，不是可行域的一個(gè)頂點(diǎn)( x1, x2, x3) ( x1, x2, x4)( x1, x2, x5)( x1, x3, x4)( x1, x3, x5)( x1

27、, x4, x5)( x2, x3, x4)( x2, x3, x5)( x2, x4, x5)( x3, x4, x5)( 3/2, 1 3/2 ) z = 13/2( 3/5, 11/5, 3/5 ) z = 31/5( 1, 2, -1)( 9/4, 11/4, -1/2 )( 2, 3, 1) z = 6( 5, -6, -11 )( 3, -1, -1 )( 4, -5, -3 )( 5/2, 3/2, 3/2 ) z = 5( 5, 4, 9 ) z = 012x,231x21623*21xxz0 x1x2a(2,0)b(3/2,1)c(3/5,11/5)d(0,5/2)幾何概念幾

28、何概念代數(shù)概念代數(shù)概念約束直線約束直線滿足一個(gè)等式約束的解滿足一個(gè)等式約束的解約束半平面約束半平面滿足一個(gè)不等式約束的解滿足一個(gè)不等式約束的解約束半平面的交約束半平面的交集：凸多邊形集：凸多邊形滿足一組不等式約束滿足一組不等式約束的解的解約束直線的交點(diǎn)約束直線的交點(diǎn)基解基解可行域的頂點(diǎn)可行域的頂點(diǎn)基可行解基可行解目標(biāo)函數(shù)等值線：目標(biāo)函數(shù)等值線：一組平行線一組平行線 目標(biāo)函數(shù)值等于一個(gè)目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解常數(shù)的解=目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件基矩陣基矩陣右邊常數(shù)右邊常數(shù)=基變量基變量=換入變量換入變量換出變量換出變量目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件右邊常數(shù)右邊常數(shù)=目標(biāo)函數(shù)目標(biāo)函數(shù)約束

29、條件約束條件新的基矩陣新的基矩陣右邊常數(shù)右邊常數(shù)=換入變量換入變量換出變量換出變量目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件基矩陣基矩陣=目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件新的基矩陣新的基矩陣右邊常數(shù)右邊常數(shù)=基本思路：基本思路：l首先求出初始基可行解首先求出初始基可行解l判斷其是否為最優(yōu)解判斷其是否為最優(yōu)解l如果不是最優(yōu)，則迭代到其相鄰的基本如果不是最優(yōu)，則迭代到其相鄰的基本可行解，并再次檢驗(yàn)可行解，并再次檢驗(yàn)求解線性規(guī)劃求解線性規(guī)劃0,934425223max2121212121xxxxxxxxs.t.xxz0,934425223max5432152142132121xxxxxxxxxxxxxxxxz

30、首先轉(zhuǎn)化為標(biāo)準(zhǔn)形式首先轉(zhuǎn)化為標(biāo)準(zhǔn)形式 基解與基可行解的性質(zhì)：基解與基可行解的性質(zhì)： 每個(gè)變量不是基變量就是非基變量每個(gè)變量不是基變量就是非基變量 基變量個(gè)數(shù)基變量個(gè)數(shù) = = 方程個(gè)數(shù)方程個(gè)數(shù) 令非基變量令非基變量 = 0= 0 求解方程組可得基變量值求解方程組可得基變量值 若基解滿足若基解滿足x xj j0 0 ，則基解就是一個(gè)基可行解，則基解就是一個(gè)基可行解1 1、確定初始基可行解：、確定初始基可行解：100340101200121基變量為：基變量為： x3 ，x4 ，x5 非基變量為：非基變量為： x1，x2（0）z = 3x1 + 2x2（1） x1 +2x2 + x3 = 5（2）

31、2x1 + x2 + x4 = 4（3） 4x1+ 3x2 + x5 = 9初始初始基可行解基可行解x(0)=（0，0，5，4，9） z(0) = 0 2 2、最優(yōu)性檢測：、最優(yōu)性檢測：檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：j j 0 0 時(shí)，基可行解為最優(yōu)解時(shí)，基可行解為最優(yōu)解 z = 3x1 + 2x2 + 0 x3 + 0 x4 + 0 x5 x(0)非最優(yōu)解非最優(yōu)解2 2、基可行解的轉(zhuǎn)換：、基可行解的轉(zhuǎn)換：換入變量：換入變量：max j 0 （0） z = 3x1 +2x2 + 0 x3 + 0 x4 + 0 x5 x1 為換入變量為換入變量換出變量：換出變量： （1） x1+2x2 + x3 = 5（2）

32、 2x1+ x2 + x4 = 4（3） 4x1+ 3x2 +x5 = 9（1 1）尋找換入、換出變量）尋找換入、換出變量x1 = 5 x3 x1 = 4/2 1/2x4x1 = 9/4 1/4 x5 x1 5 x1 4/2 x1 9/4 x1+ x3 = 5 2x1 + x4 = 4 4x1 +x5 = 9（2 2）代換，求新基可行解）代換，求新基可行解 基變量為：基變量為： x3 ，x1 ，x5 非基變量為：非基變量為： x2，x4rkrikikiiabm21i0aab),(min （0）z = 3 x1 + 2x2 （1） x1+ 2x2+ x3 = 5（2） 2x1+ x2 + x4

33、= 4（3） 4x1 +3x2 + x5 = 9（0）z = 3x1 + 2x2 （1） x3 = 3 3/2x2 +1/2x4（2） x1 = 2 1/2x2 1/2x4 （3） x5 = 1 x2 + 2 x4 基可行解基可行解x(1)=（2，0，3，0，1） z(1) = 6（0） z = 6 + 1/2x2 3/2x4 （1） 3/2x2 + x3 1/2x4 = 3（2） x1+ 1/2x2 + 1/2x4 = 2（3） x2 2x4 + x5 = 1 x x4 4 為換出變量為換出變量 最小比值原則最小比值原則: : =4/2=4/23 3、再最優(yōu)性檢測：、再最優(yōu)性檢測： （0）

34、z =6+ 1/2x2 3/2x4 檢驗(yàn)數(shù)：檢驗(yàn)數(shù)： 2 2= 1/20 = 1/20 x(1)非最優(yōu)解非最優(yōu)解4 4、基可行解的轉(zhuǎn)換、基可行解的轉(zhuǎn)換換入變量：換入變量： 2 2= 1/2= 1/2 x2 為換入變量為換入變量換出變量：換出變量： = 2 = 4 = 1 x5 為換出變量為換出變量（1） 3/2x2 + x3 1/2x4 = 3（2）x1+ 1/2x2 +1/2x4 = 2（3） x2 2x4 + x5 = 1（0） z = 6 + 1/2x2 3/2x4 （1） 3/2x2 + x3 1/2x4 = 3（2） x1+ 1/2x2 + 1/2x4 = 2（3） x2 2x4 +

35、 x5 = 1 基變量為：基變量為： x3 ，x1 ，x2 非基變量為：非基變量為： x4，x5基可行解基可行解x(2)=（3/2，1，3/2，0，0） z(2) = 6.5 檢測：檢測：（0）z = 6.5 1/2x4 1/2 x5 檢驗(yàn)數(shù)檢驗(yàn)數(shù) 0 0 x(2)是最優(yōu)解是最優(yōu)解 最優(yōu)解最優(yōu)解 x x* *= =（3/23/2，1 1，3/23/2，0 0，0 0） 最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值 z z* *=6.5=6.5（0） z = 6 +1/2x2 3/2 x5（1） x3 = 3/2 5/2 x4 +3/2 x5（2） x1 = 3/2 3/2 x4 + 1/2 x5（3） x2

36、= 1 + 2 x4 x5 （0）z =6.5 1/2x4 1/2 x5（1） x3 +5/2 x4 3/2 x5 = 3/2（2） x1 +3/2 x4 1/2 x5 = 3/2（3） x2 2 x4 + x5 = 1100340101200121基變量為：基變量為： x3 ，x4 ，x5 非基變量為：非基變量為： x1，x2單純型表：將一般形式變?yōu)闃?biāo)準(zhǔn)形式單純型表：將一般形式變?yōu)闃?biāo)準(zhǔn)形式1、列出初始單純形表、列出初始單純形表 59/44/2主元主元x 4換出變量換出變量x 1換入變量換入變量基可行解基可行解（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（0

37、0，0 0，5 5，4 4，9 9）檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：1 1 2 2 0 0 非最優(yōu)解非最優(yōu)解2 2、尋找換入變量，換出變量、尋找換入變量，換出變量max max j j 0 ; min0 0 ; min0 3、尋找新的基矩陣和基可行解、尋找新的基矩陣和基可行解x13211/201/20303/21-1/201010-2101/20-3/20 x3x500迭代的目標(biāo)就是把主元迭代的目標(biāo)就是把主元化為化為1，然后把主元所，然后把主元所在列其他系數(shù)化為在列其他系數(shù)化為03、尋找新的基矩陣和基可行解、尋找新的基矩陣和基可行解1x5換出變量換出變量x2換入變量換入變量24基可行解基可行解（x x1 1,

38、x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3 3，0 0，2 2，0 0，1 1）檢驗(yàn)數(shù)：檢驗(yàn)數(shù)：2 2 0 0 非最優(yōu)解非最優(yōu)解4 4、尋找換入變量，換出變量、尋找換入變量，換出變量max max j j 0 ; min0 0 ; min0 x133/21003/2 -1/23/20015/2 -3/21010-21000-1/2 -1/2x3x202檢驗(yàn)：所有的檢驗(yàn)：所有的j j0 0 得到最優(yōu)解，最優(yōu)解為：得到最優(yōu)解，最優(yōu)解為：（x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5）= =（3/23/2，1 1，3/23/2，0 0，0 0，），）

39、max z=6.5max z=6.5合并的單純形表合并的單純形表32000cbxbx1x2x3x4x5b 000 x3x4x51242131000100015495/14/29/4320000030 x3x1x50103/21/21100-1/21/2-200132124101/20-3/206032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/20,.,832625223min61654254324215321xxxxxxxxxxxxxxxxxz注意該問題已經(jīng)滿足標(biāo)準(zhǔn)形式的要求，而且可注意該問題已經(jīng)滿足標(biāo)準(zhǔn)形式的要求，而且可以找到初

40、始基變量以找到初始基變量x x1 1、x x3 3、x x6 6，只是他們在目，只是他們在目標(biāo)函數(shù)中的系數(shù)不為標(biāo)函數(shù)中的系數(shù)不為0 0。單純形法的進(jìn)一步討論1-110-30cbxbx1x2x3x4x5x6b1x1120-20051x3011-12063.00 0 x602013182.67 0-403-50111x1120-20052.51x30- 1/31- 5/30-2/32/3-3x502/301/311/38/340-2/3014/305/3-7/3-1x21/210-1005/21x31/601-20-2/33/2-3x5-1/300111/311/300405/3-4例：考慮如何求

41、解下列線性規(guī)劃問題例：考慮如何求解下列線性規(guī)劃問題0,4222212232max321321321321321xxxxxxxxxxxxxxxz系數(shù)矩陣：系數(shù)矩陣：0,4222212232max654321632153214321321xxxxxxxxxxxxxxxxxxxxxz化為標(biāo)準(zhǔn)形式：化為標(biāo)準(zhǔn)形式：添加人工變量：添加人工變量：x7 ，x8數(shù)學(xué)模型變?yōu)椋簲?shù)學(xué)模型變?yōu)椋?,4222212200032max6543216321853217432187654321xxxxxxxxxxxxxxxxxxxxmxmxxxxxxxz-231000-m-mcbxbx1x2x3x4x5x6x7x8b-mx7

42、2-12-100101-mx82210-100120 x6-121001004-2+4m3+m1+3m-m-m000-2x11-1/21- 1/2001/201/2-mx803-11-10-1110 x603/22-1/2011/209/202+3m3-m-1+m-m01-m0-2x1105/6-1/3-1/601/31/62/33x201-1/31/3-1/30-1/31/31/30 x6005/2-11/211-1/24008/3-5/32/30-m+5/3-m-2/31、人工變量法（大、人工變量法（大m法）法）-231000-m-mcbxbx1x2x3x4x5x6x7x8b1x36/50

43、1-2/5-1/502/51/54/53x22/5101/5-2/50-1/52/53/50 x6-3000110-12-22/500-1/57/50-m+1/5-m-3/51x33/501-2/501/52/506/53x2-4/5101/502/5-1/507/50 x5-3000110-12-1/500-1/50-7/5-m+1/5-m27/5。為了減少計(jì)算工作量，為了減少計(jì)算工作量，紅色陰影部分可以不寫紅色陰影部分可以不寫0, 0, 0, 2, 0, 2 . 1, 4 . 1, 087654321xxxxxxxx4 . 5527*z因此最優(yōu)解為因此最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為最優(yōu)目標(biāo)函數(shù)值

44、為注意：注意：如果在用大如果在用大m m法求解線性規(guī)劃問題時(shí)，最法求解線性規(guī)劃問題時(shí)，最終表的基變量中還含有人工變量，那么這個(gè)最終終表的基變量中還含有人工變量，那么這個(gè)最終表并沒有給出原來問題的基可行解，從而沒有給表并沒有給出原來問題的基可行解，從而沒有給出原來的線性規(guī)劃問題最優(yōu)解。這時(shí)原來線性規(guī)出原來的線性規(guī)劃問題最優(yōu)解。這時(shí)原來線性規(guī)劃問題為劃問題為無可行解無可行解。0,4222212232max321321321321321xxxxxxxxxxxxxxxz 由于由于m m不是一個(gè)確定的數(shù)，所以大不是一個(gè)確定的數(shù)，所以大m m法適宜于手工法適宜于手工計(jì)算，而不適合計(jì)算機(jī)求解。計(jì)算，而不適合

45、計(jì)算機(jī)求解。0,42222122min876543216321853217432187xxxxxxxxxxxxxxxxxxxxxxxxz第一階段：求解輔第一階段：求解輔助的線性規(guī)劃問題助的線性規(guī)劃問題00000011cbxbx1x2x3x4x5x6x7x8b1x72-12-1001011x82210-100120 x6-121001004 -4-1-3110000 x11 -1/21 -1/20 0 1/20 1x80 3 -1 1 -1 0 -1 1 1/2 1 0 x60 3/22 -1/20 1 1/20 9/20-31-110200 x11 0 5/6-1/3-1/60 1/31/62

46、/30 x20 1 -1/31/3-1/30 -1/31/31/30 x60 0 5/2-1 1/21 1 -1/24 000000110第一階段第一階段第二階段（去掉人工變量，換為原來的目標(biāo)函數(shù)）第二階段（去掉人工變量，換為原來的目標(biāo)函數(shù)）-231000cbxbx1x2x3x4x5x6b-2x11 0 5/6-1/3-1/60 2/33x20 1 -1/31/3-1/30 1/30 x60 0 5/2-1 1/21 4 0 0 11/3-5/32/30 1x36/50 1 -2/5-1/50 4/53x22/51 0 1/5-2/50 3/50 x6-3 0 0 0 1 1 2 -22/50 0 -1/57/50 1x33/50 1 -2/50 1/56