運(yùn)籌學(xué)第二章 線性規(guī)劃2.1-2

1、第章線性規(guī)劃第章線性規(guī)劃2.1線性規(guī)劃的模型與圖解法線性規(guī)劃的模型與圖解法2.2單純形法單純形法2.1 線性規(guī)劃的模型與圖解法線性規(guī)劃的模型與圖解法2.1.1問(wèn)題的引入問(wèn)題的引入l如何合理使用有限的人力，物力和資金，如何合理使用有限的人力，物力和資金，使得收到最好的經(jīng)濟(jì)效益。使得收到最好的經(jīng)濟(jì)效益。 某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源?，F(xiàn)將有關(guān)數(shù)據(jù)列表如下：油三種資源。現(xiàn)將有關(guān)數(shù)據(jù)列表如下： 試擬訂使總收入最大的生產(chǎn)方案。試擬訂使總收入最大的生產(chǎn)方案。資源單耗產(chǎn)品資源單耗產(chǎn)品 資源資源甲甲 乙乙資源限量資源限量煤煤電電油油9 44 5

2、 3 10360200300單位產(chǎn)品價(jià)格單位產(chǎn)品價(jià)格 7 12121212121212xx kgmaxZ7x12x9x4x3604x5x2003x10 x300 x ,x0設(shè)甲乙產(chǎn)品產(chǎn)量分別為 和決策變量則目標(biāo)函數(shù)約束條件 甲甲 乙乙 資源限量資源限量 煤煤(t) 9 4 360 電（電（kwh) 4 5 200 油（油（t） 3 10 300 單價(jià)（萬(wàn)元）單價(jià)（萬(wàn)元） 7 12l如何合理地搭配（混合）材料，以最經(jīng)如何合理地搭配（混合）材料，以最經(jīng)濟(jì)的方式，達(dá)到配比要求。濟(jì)的方式，達(dá)到配比要求。（3 3）下料問(wèn)題）下料問(wèn)題l如何截取原材料，在達(dá)到截取要求的情如何截取原材料，在達(dá)到截取要求的情況

3、下，使廢料最少?zèng)r下，使廢料最少料長(zhǎng)料長(zhǎng)7.47.4米，截成米，截成2.92.9、2.12.1、1.51.5米各米各200200根。根。如何截取余料最少？如何截取余料最少？ 方案方案料型料型 1 2 3 4 5 2.9米米 2.1米米 1.5米米 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 合計(jì)合計(jì) 殘料殘料 7.4 7.3 7.2 7.1 6.6 0 0.1 0.2 0.3 0.8(j(j=1,2,3,4,5)=1,2,3,4,5)+0.8x+0.8x5 5 練習(xí)練習(xí)1 1：某畜牧廠每日要為牲畜購(gòu)買(mǎi)飼料以使其獲取某畜牧廠每日要為牲畜購(gòu)買(mǎi)飼料以使其獲取A、B、C、D四種養(yǎng)分。市場(chǎng)

4、上可選擇的飼料有四種養(yǎng)分。市場(chǎng)上可選擇的飼料有M、N兩種。兩種。有關(guān)數(shù)據(jù)如下：有關(guān)數(shù)據(jù)如下：試決定買(mǎi)試決定買(mǎi)M與與N二種飼料各多少公斤而使支出的總費(fèi)用二種飼料各多少公斤而使支出的總費(fèi)用為最少？為最少？410售價(jià) 0.4 0.6 2.0 1.7牲畜每日每頭需要量 0 0.1 0.2 0.1N 0.1 0 0.1 0.2 M每公斤含營(yíng)養(yǎng)成分 A B C D飼料解：設(shè)購(gòu)買(mǎi)M、N飼料各為 ，則 12104min zxx12121212120.100.400.10.60.10.22.00.20.11.7,0 xxxxxxxxx x21,xx2.1.2 線性規(guī)劃的一般模型與標(biāo)準(zhǔn)型線性規(guī)劃的一般模型與標(biāo)準(zhǔn)型

5、一、一般模型一、一般模型規(guī)劃問(wèn)題的數(shù)學(xué)模型包含三個(gè)組成要素：規(guī)劃問(wèn)題的數(shù)學(xué)模型包含三個(gè)組成要素：（1）決策變量）決策變量：指決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)：指決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案措施，是問(wèn)題中要確定的未采取的方案措施，是問(wèn)題中要確定的未知量。知量。（2）目標(biāo)函數(shù)：）目標(biāo)函數(shù)：指問(wèn)題要達(dá)到的目的要求，指問(wèn)題要達(dá)到的目的要求，表示為決策變量的函數(shù)。表示為決策變量的函數(shù)。（3）約束條件：）約束條件：指決策變量取值時(shí)受到的指決策變量取值時(shí)受到的各種可用資源的限制，表示為含決策變各種可用資源的限制，表示為含決策變量的等式或不等式。量的等式或不等式。 1 12211 11221121 1222221 12

6、212max(min)( , )( , )( , ),( )0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xa xa xbx xx 一般地，線性規(guī)劃模型一般地，線性規(guī)劃模型： 簡(jiǎn)記為：簡(jiǎn)記為：11max(min)( , ) 1,2,( )0 1,2,njjjnijjijjZc xa xbimxjn 矩陣表示為：矩陣表示為： 12121211121212221212max(min)()( )( ,)( ,)( ,)( ,.,) nTnTmnnnmmmnZc ccx xxb bbaaaaaaP PPaaa CXAXbX0CXbA其中：價(jià)值系數(shù)向量決策變

7、量向量資源向量技術(shù)系數(shù)矩陣?yán)?：123123123123123123123min425742410,0min(4, 2,1)5714124100Zxxxxxxxxxx x xxZxxxxxxxx矩陣表示為：二、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式二、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式要求：標(biāo)準(zhǔn)形式要求：（1）目標(biāo)最大化（）目標(biāo)最大化（max）（2）約束是）約束是“=”約束約束（3）右端項(xiàng)非負(fù)）右端項(xiàng)非負(fù)（4）所有變量非負(fù)）所有變量非負(fù)標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型0)0(maxXbbAXCXZ化標(biāo)準(zhǔn)型：化標(biāo)準(zhǔn)型：(1)minZ=2x1+4x2 (令令Z=-Z) maxZ=-2x1-4x2(2)-x1+x2+4x32 (引入松弛變

8、量引入松弛變量x4) -x1+x2+4x3+x4=2 松弛變量的意義：未被充分利用的資源（松弛變量的意義：未被充分利用的資源（c4=0）(3)-x1+x2+4x32 (引入剩余變量引入剩余變量x5) -x1+x2+4x3-x5=2 剩余變量的意義：超用的資源（剩余變量的意義：超用的資源（c5=0） (4)xj0 (令令xj=-xj) xj0(5)xj為自由變量為自由變量 (令令xj=xj-xj) xj0,xj0例例2：將下面的線性規(guī)劃模型化為標(biāo)準(zhǔn)型：將下面的線性規(guī)劃模型化為標(biāo)準(zhǔn)型為自由變量321321321321321, 0, 06454273273minxxxxxxxxxxxxxxxZ ,:

9、33311xxxxxZZ令解引入松弛變量x4,剩余變量x5思考題：思考題：1、松弛變量、松弛變量(剩余變量剩余變量)的實(shí)際意義是什么？的實(shí)際意義是什么？2、松弛變量、松弛變量(剩余變量剩余變量)在目標(biāo)函數(shù)中的系數(shù)是多少？在目標(biāo)函數(shù)中的系數(shù)是多少？為自由變量321321321321321, 0, 06454273273minxxxxxxxxxxxxxxxZ0, , , 6 4454 27 33200 773max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ則：練習(xí)：將下面的線性規(guī)劃模型化為標(biāo)準(zhǔn)型練習(xí)：將下面的線性規(guī)劃模型化為標(biāo)準(zhǔn)型0,

10、 0894232515579min321321321321321xxxxxxxxxxxxxxxZ為自由變量0, , , ,89 423 225155 77009 max54322153221322143221543221xxxxxxxxxxxxxxxxxxxxxxxxxxZ ,:22233xxxxxZZ令解0, 0894232515579min321321321321321xxxxxxxxxxxxxxxZ為自由變量x1,x2,x3為實(shí)際變量x4為剩余變量x5為松弛變量廣義松弛變量引入剩余變量x4,松弛變量x52.1.3 線性規(guī)劃模型的圖解法（適用于線性規(guī)劃模型的圖解法（適用于2個(gè)變個(gè)變量的一般

11、型）量的一般型）一、線性規(guī)劃問(wèn)題的解的概念一、線性規(guī)劃問(wèn)題的解的概念 設(shè)線性規(guī)劃問(wèn)題的一般型為設(shè)線性規(guī)劃問(wèn)題的一般型為0)(),(max(min)XbAXCXZ（1）可行解：滿(mǎn)足全部約束條件的決策變量）可行解：滿(mǎn)足全部約束條件的決策變量X為可行解；全為可行解；全 部可行解的集合部可行解的集合R稱(chēng)為可行解域。稱(chēng)為可行解域。（2）最優(yōu)解：使目標(biāo)函數(shù)為最大（或最?。┑目尚薪猓┳顑?yōu)解：使目標(biāo)函數(shù)為最大（或最小）的可行解X*。二、線性規(guī)劃的圖解法二、線性規(guī)劃的圖解法圖解法步驟：圖解法步驟：（1）根據(jù)約束條件畫(huà)出可行解域；）根據(jù)約束條件畫(huà)出可行解域；（2）畫(huà)出目標(biāo)函數(shù)的等值線；）畫(huà)出目標(biāo)函數(shù)的等值線；（3

12、）求出最優(yōu)解。）求出最優(yōu)解。x1x209040405030100Dl1l2l30,3001032005436049127max) 1 (2121212121xxxxxxxxxxZ例例3 用圖解法求解下列線性規(guī)劃問(wèn)題用圖解法求解下列線性規(guī)劃問(wèn)題可行域可行域目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線A有唯一最優(yōu)解（頂點(diǎn)有唯一最優(yōu)解（頂點(diǎn)D）解直線解直線l2,l3組成的線性方程組成的線性方程組得：組得：X*=(20,24)T最優(yōu)生產(chǎn)最優(yōu)生產(chǎn)方案方案Z*=720+1224=428最大收入最大收入(2)在模型在模型(1)中，目標(biāo)函中，目標(biāo)函數(shù)改為數(shù)改為 maxZ=3x1+10 x2，其，其他不變。他不變。 易知，目標(biāo)

13、函數(shù)等值易知，目標(biāo)函數(shù)等值線與直線線與直線l3平行，平行， 故線段故線段AD上的點(diǎn)均為上的點(diǎn)均為最優(yōu)解。最優(yōu)解。 有無(wú)窮多最優(yōu)解有無(wú)窮多最優(yōu)解 x209040405030100Dl1l2l3AX10,164127max)3(21121xxxxxZx1x204可行域無(wú)界，在可行域可行域無(wú)界，在可行域上沒(méi)有使目標(biāo)函數(shù)值為上沒(méi)有使目標(biāo)函數(shù)值為有限的最優(yōu)解。有限的最優(yōu)解。無(wú)有限最優(yōu)解（無(wú)界解）無(wú)有限最優(yōu)解（無(wú)界解）0,2212max)4(21212121xxxxxxxxZ1x2012x1-1不存在所有約束條件的不存在所有約束條件的公共范圍公共范圍無(wú)可行解無(wú)可行解小結(jié)：（1）線性規(guī)劃問(wèn)題解的情況在可行域

14、某條邊上達(dá)到多重在可行域某頂點(diǎn)處達(dá)到唯一有最優(yōu)解有限最優(yōu)解可行域無(wú)界，且達(dá)不到無(wú)界解無(wú)最優(yōu)解可行解公共范圍不存在所有約束條件的無(wú)可行解: )(:（2）線性規(guī)劃問(wèn)題解的線性規(guī)劃問(wèn)題解的兩個(gè)重要結(jié)論兩個(gè)重要結(jié)論l 線性規(guī)劃的可行域是凸多面體線性規(guī)劃的可行域是凸多面體l 線性規(guī)劃的最優(yōu)解在可行域的頂點(diǎn)上線性規(guī)劃的最優(yōu)解在可行域的頂點(diǎn)上凸多面體凸多面體凹多面體極點(diǎn)（頂點(diǎn)）u思考題思考題:約束條件不等式的幾何意義是什么？約束條件不等式的幾何意義是什么？怎樣做圖？怎樣做圖？2.2單純形法（適用于多個(gè)變量的標(biāo)準(zhǔn)型）單純形法（適用于多個(gè)變量的標(biāo)準(zhǔn)型）2.2.1單純形法的原理與基本概念單純形法的原理與基本概念一

15、一.原理原理 單純形法是一種迭代算法，它利用線性單純形法是一種迭代算法，它利用線性規(guī)劃最優(yōu)解在可行域頂點(diǎn)上達(dá)到這一結(jié)論。規(guī)劃最優(yōu)解在可行域頂點(diǎn)上達(dá)到這一結(jié)論。首先確定一個(gè)初始頂點(diǎn)，用某種方法判別它首先確定一個(gè)初始頂點(diǎn)，用某種方法判別它是否最優(yōu)解，若不是最優(yōu)解，則設(shè)法去尋找是否最優(yōu)解，若不是最優(yōu)解，則設(shè)法去尋找一個(gè)更好的頂點(diǎn)。由于頂點(diǎn)個(gè)數(shù)是有限的，一個(gè)更好的頂點(diǎn)。由于頂點(diǎn)個(gè)數(shù)是有限的，經(jīng)過(guò)有限次迭代后，必達(dá)到最優(yōu)點(diǎn)。經(jīng)過(guò)有限次迭代后，必達(dá)到最優(yōu)點(diǎn)。0maxXbAXCXZ為：設(shè)線性規(guī)劃的標(biāo)準(zhǔn)形式mARmnPPPaaaaaaaaaAnmnmmnn)()(),.,(.21212222111211二二.

16、基本概念基本概念1.基與基變量基與基變量基基( (又稱(chēng)基矩陣又稱(chēng)基矩陣):):A A中的中的m m階可逆子陣，記為階可逆子陣，記為B(|B|0)B(|B|0)其余部分稱(chēng)作非基，記為其余部分稱(chēng)作非基，記為N N基向量基向量: :基基B B中的列中的列P Pj j非基向量非基向量: :非基非基N N中的列中的列p pj j基變量基變量: :與基向量同下標(biāo)的變量與基向量同下標(biāo)的變量x xj j，記作，記作X XB B( (有有m m個(gè)分量個(gè)分量) )非基變量非基變量: :與非基向量同下標(biāo)的變量，記作與非基向量同下標(biāo)的變量，記作X XN N( (有有n-mn-m個(gè)個(gè)分量分量) )2.基本解與基本可行解

17、基本解與基本可行解基本解：基本解：令非基變量為令非基變量為0，所得到的解，稱(chēng)為基本解。，所得到的解，稱(chēng)為基本解?；究尚薪猓夯究尚薪猓悍秦?fù)的基本解稱(chēng)為基本可行解，它所非負(fù)的基本解稱(chēng)為基本可行解，它所 對(duì)應(yīng)的基為可行基對(duì)應(yīng)的基為可行基。=目標(biāo)函數(shù)約束條件行列式0基矩陣右邊常數(shù))4 , 3 , 2 , 1(032124421321jxxxxxxxj：某線性規(guī)劃約束例),(10120121A4321pppp系數(shù)矩陣1221N1001B11非基可取基21 43P,P P,P非基向量：基向量：T21NT43B2143)x,(xX )x,(xXx,x x,x非基變量：基變量：思考題：一個(gè)思考題：一個(gè)mn

18、階系數(shù)陣階系數(shù)陣A中基的個(gè)數(shù)最多為多少？中基的個(gè)數(shù)最多為多少？例例5：某線性規(guī)劃約束中：某線性規(guī)劃約束中11112131213122(1)1122,1211112,121( ,)230,211(3, 1,0)TBNTAbBNXx xXxxxxxxxxX 如取基非基基變量，非基變量令則方程組變?yōu)榛窘?2213221312313(2)2121,112( ,)2200,11(0,0,1),BTBNTBNXx xXxxxxxxxxX 如取基非基基變量，非基變量令則方程組變?yōu)榛究尚薪鉃榭尚谢?x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1 +3x2 +x3 +x4 =1

19、5 2x1 +3x2 -x3 +x5 =18 x1 -x2 +x3 +x6 =3 基變量基變量x1、x2、x3，非基變量，非基變量x4、x5、x6基本解為（基本解為（x1，x2，x3，x4，x5，x6）T=（5，3，1，0，0，0）T是基本可行解，表示可行域的一個(gè)極點(diǎn)。是基本可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=20 x1+3x2+x4=152x1+3x2=18x1-x2=3基變量基變量x1、x2、x4，非基變量，非基變量x3、x5、x6基本解為基本解為（x1，x2，x3，x4，x5，x6）T=（27/5，12/5，0，2/5，0，0）T是基本可行解，表示可行域的一個(gè)極

20、點(diǎn)。是基本可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=18x1+3x2=152x1+3x2+x5=18x1-x2=3基變量基變量x1、x2、x5，非基變量，非基變量x3、x4、x6基本解為（基本解為（x1，x2，x3，x4，x5，x6）T=（6，3，0，0，-3，0）T是基本解，但不是可行解，不是一個(gè)極點(diǎn)。是基本解，但不是可行解，不是一個(gè)極點(diǎn)。x1+3x2=152x1+3x2=18x1-x2+x6=3基變量基變量x1、x2、x6，非基變量，非基變量x3、x4、x5基本解為（基本解為（x1，x2，x3，x4，x5，x6）T=（3，4，0，0，0，4）T是基本可行解，表示可行域的

21、一個(gè)極點(diǎn)。是基本可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基變量基變量x2、x3、x4，非基變量，非基變量x1、x5、x6基本解為基本解為（x1，x2，x3，x4，x5，x6）T=（0，21/2，27/2，-30，0，0）T是基本解，但不是可行解是基本解，但不是可行解。3x2+x3=153x2-x3+x5=18-x2+x3=3基變量基變量x1、x2、x3，非基變量，非基變量x4、x5、x6基本解為（基本解為（x1，x2，x3，x4，x5，x6）T=（0，3，6，0，15，0）T是基本

22、可行解，表示可行域的一個(gè)極點(diǎn)。是基本可行解，表示可行域的一個(gè)極點(diǎn)。目標(biāo)函數(shù)值為：目標(biāo)函數(shù)值為：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基變量基變量x1、x2、x3，非基變量，非基變量x4、x5、x6基本解為基本解為（x1，x2，x3，x4，x5，x6）T=（0，11/2，-3/2，0，0，10）T是基本解但不是可行解。是基本解但不是可行解。三三.兩個(gè)重要結(jié)論：兩個(gè)重要結(jié)論：（1）可行域的頂點(diǎn)一定是基本可行解）可行域的頂點(diǎn)一定是基本可行解（2）最優(yōu)解存在，一定在基本可行解處達(dá)到）最優(yōu)

23、解存在，一定在基本可行解處達(dá)到思考題：四個(gè)重要結(jié)論有何重要意義？思考題：四個(gè)重要結(jié)論有何重要意義？幾何概念幾何概念代數(shù)概念代數(shù)概念約束直線約束直線滿(mǎn)足一個(gè)等式約束的解滿(mǎn)足一個(gè)等式約束的解約束半平面約束半平面滿(mǎn)足一個(gè)不等式約束的解滿(mǎn)足一個(gè)不等式約束的解約束半平面的交集約束半平面的交集(凸多邊形凸多邊形)滿(mǎn)足一組不等式約束的解滿(mǎn)足一組不等式約束的解約束直線的交點(diǎn)約束直線的交點(diǎn)基本解基本解可行域的極點(diǎn)可行域的極點(diǎn)基本可行解基本可行解目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線(一組平行線一組平行線) 目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解2.2.2單純形法的步驟單純形法的步驟枚舉法枚舉法:找出所有基本

24、可行解找出所有基本可行解比較其目標(biāo)函數(shù)值比較其目標(biāo)函數(shù)值最大者最大者 最優(yōu)最優(yōu)單純形法單純形法: :找出一個(gè)基本可行解找出一個(gè)基本可行解檢驗(yàn)其是否最優(yōu)檢驗(yàn)其是否最優(yōu)是是停止停止 否否 再找一個(gè)更好的基本可行解再找一個(gè)更好的基本可行解1.1.確定一個(gè)初始基本可行解確定一個(gè)初始基本可行解 法大位陣，仍取中不含單位陣，人造單中含單位陣，取取初始可行基MIBAIBAB000與與B0對(duì)應(yīng)的解稱(chēng)之為初始基本可行解。對(duì)應(yīng)的解稱(chēng)之為初始基本可行解。2.檢驗(yàn)一個(gè)基本可行解是否最優(yōu)檢驗(yàn)一個(gè)基本可行解是否最優(yōu) 不妨取可行基為不妨取可行基為B=(P1,P2,Pm) 則則N=(Pm+1,Pm+2,Pn) 系數(shù)陣：系數(shù)陣

25、：A=(B,N)TNBXXX),(可行解非基變量基變量TnmNTmBXxXxxX),.,(),.,(11),(NBCCC 價(jià)值系數(shù)),.,(),.,(11nmNmBccCccCbAX 由bXXN)(B,NB則bBNXBX-1N-1BN-1-1BNXB-bBX bNXXNB BNNBBNBNBXCXCXXCCZ),(則CXZ 由NNNXCNXBbBC)(11BNBNBXNBCCbBCz)(11),.,(11nmBNNNBCC記),.,1(1nmjPBCCjBjj-非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)-第j個(gè)非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)最最優(yōu)優(yōu)0 0b bB BX X可可行行解解當(dāng)當(dāng)前前基基此此時(shí)

26、時(shí), ,可可使使Z Z最最大大，0 0時(shí)時(shí), ,0 0時(shí)時(shí)，只只有有當(dāng)當(dāng)X X若若1 1N NN N本1BNNZC B bX1BCbAXB兩邊左乘以進(jìn)一步地，將bBCAX-1B1BCB則A)XBC-(Cb-1B1BCBAX)BC-b(-1B1BCCXCXZB),.,(ABC-C21-1Bn記變量變量X的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)),.,2 , 1(PBC-C-1Bjnjjj第第j個(gè)變量個(gè)變量xj的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)當(dāng)當(dāng)j j0 0時(shí)時(shí), ,基本可行解基本可行解X=(BX=(B-1-1b,0)b,0)T T達(dá)到最優(yōu)達(dá)到最優(yōu)解解, ,否則將尋找一個(gè)更好的基本可行解否則將尋找一個(gè)更好的基本可行解.3.尋找一個(gè)更好的

27、基本可行解尋找一個(gè)更好的基本可行解(1)原理原理 基變換基變換設(shè)設(shè)A=(p1,pl,pm, pm+1,pm+2,pk,pn) x1,xl,xm, xm+1,xm+2, ,xk, xn 當(dāng)前基當(dāng)前基 換基方式換基方式:換基原則換基原則: 解仍可行（解仍可行（XB0）換出原則換出原則當(dāng)前非基當(dāng)前非基先先換入一列換入一列pk 相應(yīng)的相應(yīng)的xk稱(chēng)為進(jìn)基變量稱(chēng)為進(jìn)基變量后換出一列換出一列pl 相應(yīng)的相應(yīng)的xl稱(chēng)為出基變量稱(chēng)為出基變量改善改善Z新新比比Z舊舊好好換入原則換入原則(2)基變換法基變換法進(jìn)基對(duì)應(yīng)的時(shí)，取求kjkpZ0maxmax 保證目標(biāo)函數(shù)增加更快保證目標(biāo)函數(shù)增加更快檢驗(yàn)數(shù)的意義：非基變量每

28、增加一個(gè)單位，目標(biāo)函數(shù)增加的量。檢驗(yàn)數(shù)的意義：非基變量每增加一個(gè)單位，目標(biāo)函數(shù)增加的量。出基對(duì)應(yīng)的取likikiilppBpBbB0)( |)()(min111保證保證XB0得新基后轉(zhuǎn)入第二步。得新基后轉(zhuǎn)入第二步。=目標(biāo)函數(shù)約束條件基矩陣右邊常數(shù)=基變量圖示：=進(jìn)基變量離基變量目標(biāo)函數(shù)約束條件右邊常數(shù)=目標(biāo)函數(shù)約束條件新的基矩陣右邊常數(shù)=進(jìn)基變量離基變量目標(biāo)函數(shù)約束條件基矩陣=目標(biāo)函數(shù)約束條件新的基矩陣右邊常數(shù)=思考題：思考題：1.最優(yōu)性用什么來(lái)檢驗(yàn)？檢驗(yàn)數(shù)公式最優(yōu)性用什么來(lái)檢驗(yàn)？檢驗(yàn)數(shù)公式? 2.檢驗(yàn)數(shù)的意義是什么？檢驗(yàn)數(shù)的意義是什么？2.2.3 單純形表單純形表 對(duì)每個(gè)確定的可行基對(duì)每個(gè)確

29、定的可行基B，單純形表的結(jié)構(gòu)為：，單純形表的結(jié)構(gòu)為： CjC1 C2 CnCB XB B-1bx1 x2 xnCB XB bP1 P2 Pn j1 2 n其中其中:CB基變量所對(duì)應(yīng)的價(jià)值系數(shù)基變量所對(duì)應(yīng)的價(jià)值系數(shù) XB基變量基變量 b=B-1b Pj=B-1Pj j=Cj-CBB-1Pj(j=1,2,.,n) B=0基變量的檢驗(yàn)數(shù)基變量的檢驗(yàn)數(shù)0,3212max121212121xxxxxxxxZ）（例例7 用單純形法求解下列線性規(guī)劃問(wèn)題用單純形法求解下列線性規(guī)劃問(wèn)題0,321200max43214213214321xxxxxxxxxxxxxxZ解：化為標(biāo)準(zhǔn)型初始單純形表為：初始單純形表為：0

30、) 3 , 1 , 0 , 0(1001),()0()0(10104300ZXCpBCCbbBPPBTjjBjjX2進(jìn)基32103021321222242304213211xxxxxxxxxxxxx(2=10),相應(yīng)的系數(shù)列為主元列2為主元素為主元素X3出基用消元法得到新的單純型表用消元法得到新的單純型表單純型表的簡(jiǎn)化計(jì)算單純型表的簡(jiǎn)化計(jì)算 -對(duì)角法則對(duì)角法則272) 1(13252) 1(12212) 1(10對(duì)角法則的解釋?zhuān)旱趉列第j列第l行blalkaij第i行biaikaljbl/alk0alj/alkbi-blaik/alk1aij-aikalj/alkaikalkaljaijaij

31、=aij-aikalj/alk Cj -1 1 0 0 CB XB B-1b X1 X2 X3 X4 0 X3 1 1 2 1 0 0 X4 3 2 -1 0 1 j -1 1 0 0 2/1)27, 0 ,21, 0(272131121021121021,1102),()1()1(111421ZXbBbBPPBTTZX2/1)27, 0 ,21, 0(*最終單純形表N00中最大者所對(duì)應(yīng)的變量先進(jìn)基，未必是最快中最大者所對(duì)應(yīng)的變量先進(jìn)基，未必是最快的。的。X*0 x1x2用單純形法求解線性規(guī)劃問(wèn)題用單純形法求解線性規(guī)劃問(wèn)題適用條件適用條件:典則式模型典則式模型0maxXbAXCXZ基本步驟基本

32、步驟:一一.化標(biāo)準(zhǔn)型化標(biāo)準(zhǔn)型二二.填寫(xiě)初始單純型表填寫(xiě)初始單純型表三三.判斷當(dāng)前基本可行解是否最優(yōu)判斷當(dāng)前基本可行解是否最優(yōu)判別條件判別條件:j0(j=1,2,n)或或N0若存在某若存在某k0,則確定進(jìn)基變量則確定進(jìn)基變量方法方法:取正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的變量為進(jìn)取正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的變量為進(jìn)基變量基變量.四四.確定出基變量確定出基變量方法方法:采用最小比值判別法采用最小比值判別法用用B-1b中的元素除以主元列中正的系數(shù)取最中的元素除以主元列中正的系數(shù)取最小比值小比值,其對(duì)應(yīng)的變量作為出基變量其對(duì)應(yīng)的變量作為出基變量.五五.用初等行變換法將主元列中的主元素化用初等行變換法將主元列中的主元素化

33、為為1,其余元素化為其余元素化為0,得到新單純型表得到新單純型表.六六.重復(fù)第重復(fù)第3步步,直到直到j(luò)0為止為止.0,102515535 . 2max221212121xxxxxxxxZ）（0,10251553005 . 2max43214213214321xxxxxxxxxxxxxxZ解：化為標(biāo)準(zhǔn)型 Cj 2.5 1 0 0 CB XB B-1b X1 X2 X3 X4 0 X3 15 3 5 1 0 0 X4 10 5 2 0 1 j 2.5 1 0 0 TZX5)0,9 ,0,2(*最優(yōu)解為N0, 有最優(yōu)解 Cj 2.5 1 0 0 CB XB B-1b X1 X2 X3 X4 0 X3

34、 9 0 19/5 1 -3/5 2.5 X1 2 1 2/5 0 1/5 j 0 0 0 -1/2 進(jìn)一步，讓進(jìn)一步，讓x2進(jìn)基，進(jìn)基，x3出基出基 Cj 2.5 1 0 0 CB XB B-1b X1 X2 X3 X4 1 X2 45/19 0 1 5/19 -3/19 2.5 X1 20/19 1 0 -2/19 5/19 j 0 0 0 -1/2 N0, 有最優(yōu)解TZX5)0 , 0 ,19/45,19/20(*最優(yōu)解為N0且N中至少有一個(gè)為0，有無(wú)窮多最優(yōu)解0,42122max321212121xxxxxxxxZ）（0,4210022max43214213214321xxxxxxxx

35、xxxxxxZ解：化為標(biāo)準(zhǔn)型 Cj 2 2 0 0 CB XB B-1b X1 X2 X3 X4 0 X3 1 -1 1 1 0 0 X4 4 -1 2 0 1 j 2 2 0 0 1 10,0,但相應(yīng)列上的系數(shù)但相應(yīng)列上的系數(shù)P P1 1=(-1,-1)=(-1,-1)T T0,0,0,但相應(yīng)列上的系數(shù)但相應(yīng)列上的系數(shù)P Pk k0,0,有無(wú)界有無(wú)界解解線性規(guī)劃的矩陣表示0,. .,maxNBNBNBNBXXbXXNBtsXXCCz0. .maxXbAXtsCXz=0,. .)(max1111NBNBNTNBBXXNXBbBXt sXCNBCbBCz=0,. .maxNBNBNNBBXXbN

36、XBXtsXCXCz=0,. .max11NBNBNNBBXXNXBbBXtsXCXCz0.maxXbAXtsXCz0,. .maxNBNBNNBBXXbNXBXtsXCXCz0,. .max11NBNBNNBBXXNXBbBXtsXCXCz0,. .)(max1111NBNBNBNBXXNXBbBXt sXNBCCbBCzcj-CBB-1Pj=cj-zj 稱(chēng)為非基變量的檢驗(yàn)數(shù)（Reduced Cost）B-1Pj=pj， B-1b= b ，CBB-1b=z02.2.4大大M法法原理原理: 如線性規(guī)劃問(wèn)題系數(shù)矩陣中，不存在單位如線性規(guī)劃問(wèn)題系數(shù)矩陣中，不存在單位陣作為初始可行基，此時(shí)，需要通過(guò)

37、填加人工陣作為初始可行基，此時(shí)，需要通過(guò)填加人工變量給出單位初始可行基。變量給出單位初始可行基。)5 , 4 , 3 , 2 , 1(0242822234min3153214321321jxxxxxxxxxxxxxxZj)3 , 2 , 1(0242822234min. 831321321321jxxxxxxxxxxxxZj例)7 , 6 , 5 , 4 , 3 , 2 , 1(0242822)(00234min7316532143217654321jxxxxxxxxxxxxxMMxMxxxxxxZj為任意大的正數(shù))5 , 4 , 3 , 2 , 1(0242822234min31532143

38、21321jxxxxxxxxxxxxxxZjx1,x2,x3實(shí)際變量實(shí)際變量x4 松弛變量松弛變量x5 剩余變量剩余變量x6,x7人工變量人工變量100010001,7640PPPB例例9.用大用大M法求解下面線性規(guī)劃問(wèn)題法求解下面線性規(guī)劃問(wèn)題)41(010234210854235max) 1 (432143214321jxxxxxxxxxxxxxZj解解:引入人工變量引入人工變量x5,x6)6 , 5 , 4 , 3 , 2 , 1(010234210854235max6432154321654321jxxxxxxxxxxxMxMxxxxxZj得：最優(yōu)解為：3400 , 0 ,35,35*Z

39、XT)51(052151565935121510max)2(321321321321jxxxxxxxxxxxxxZj解解:增加松弛變量增加松弛變量x4,x5，剩余變量，剩余變量x6，人工變量，人工變量x7)71(052151565935000121510max76321532143217654321jxxxxxxxxxxxxxxMxxxxxxxZj得： Cj 10 15 12 0 0 0 -M CB XB B-1b X1 X2 X3 X4 X5 X6 X7 0 X4 9 5 3 1 1 0 0 0 0 -M X5 X7 15 5 -5 2 6 1 15 1 0 0 1 0 0 -1 0 1 j

40、 10+2M 15+M 12+M 0 0 -M 0 Cj 10 15 12 0 0 0 -M CB XB B-1b X1 X2 X3 X4 X5 X6 X7 10 X1 9/5 1 3/5 1/5 1/5 0 0 0 0 -M X5 X7 24 7/5 0 0 9 -1/5 16 3/5 1 -2/5 1 0 0 -1 0 1 j 0 9-1/5M 10+3/5M -2/5M 0 -M 0 人工變量人工變量x7=1/20，所以原問(wèn)題無(wú)可行解。，所以原問(wèn)題無(wú)可行解。（補(bǔ)充）兩階段法（補(bǔ)充）兩階段法(大大M法的補(bǔ)充）法的補(bǔ)充）求解問(wèn)題：求解問(wèn)題： max z=-3x1+x3 x1+ x2+x34

41、-2x1+ x2-x31 3x2+x3=9 xj0(j=1,2,3)化標(biāo)準(zhǔn)型化標(biāo)準(zhǔn)型: max z=-3x1+0 x2+x3+0 x4+0 x5 x1+ x2+x3+x4 =4 -2x1+ x2-x3 -x5 =1 3x2+x3 =9 xj0(j=1,2,5)min w=x6+x7 x1+ x2+x3+x4 =4 -2x1+ x2-x3 -x5+x6 =1 3x2+x3 +x7=9 xj0(j=1,2,7) X*=(0,5/2,3/2,0,0,0,0)T W*=0 max z=-3x1+x3+0 x4+0 x5 x1+ x2+x3+x4 =4 -2x1+ x2- x3 -x5 =1 3x2+x3 =9 xj0(j=1,2,7) X=(0,5/2,3/2,0,0)Tmin w=x6+x7 max z=-3x1+x3+0 x4+0 x5 x1+ x2+