運(yùn)籌學(xué)05-單純形法

1、第五章第五章 單純形法單純形法5.1 5.1 線性規(guī)劃問(wèn)題的基本解線性規(guī)劃問(wèn)題的基本解5.2 5.2 單純形法單純形法5.3 5.3 求初始基的人工變量法求初始基的人工變量法5.1 5.1 線性規(guī)劃問(wèn)題的基本解線性規(guī)劃問(wèn)題的基本解 302.1XbAXtsCXZMax(1) 解的基本概念解的基本概念定義定義 在線性規(guī)劃問(wèn)題中，約束方程組在線性規(guī)劃問(wèn)題中，約束方程組(2)(2)的系的系數(shù)矩陣數(shù)矩陣A(A(假定假定 ) )的任意一個(gè)的任意一個(gè) 階的非奇階的非奇異異( (可逆可逆) )的子方陣的子方陣B(B(即即 ) )，稱為線性規(guī)劃，稱為線性規(guī)劃問(wèn)題的一個(gè)問(wèn)題的一個(gè)基陣基陣或或基基。mm0Bnm m

2、nmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaA212122212222211211111211mmmmmmaaaaaaaaaB212222111211mnmmmmnmmnmmaaaaaaaaaN212221212111基陣基陣非基陣非基陣TmBxxxX21TnmmNxxxX21基基向向量量非非基基向向量量基變量基變量非基變量非基變量NBANBXXXbAX bXXNBNBbNXBXNBNBNXbBXNBNXBbBX11NBXXXNNXNXBbBX11令令0NX則則01bBX定義定義 在約束方程組在約束方程組(2) 中，對(duì)于中，對(duì)于一個(gè)選定的基一個(gè)選定的基B，令所有的非基

3、變，令所有的非基變量為零得到的解，稱為相應(yīng)于基量為零得到的解，稱為相應(yīng)于基B的基本解。的基本解。定義定義 在基本解中，若該基本解滿足非負(fù)約束，在基本解中，若該基本解滿足非負(fù)約束，即即 ，則稱此基本解為，則稱此基本解為基本可行解基本可行解，簡(jiǎn)稱簡(jiǎn)稱基可行解基可行解；對(duì)應(yīng)的基；對(duì)應(yīng)的基B稱為稱為可行基可行基。01bBXB定義定義 在線性規(guī)劃問(wèn)題的一個(gè)基本可行解中，如果在線性規(guī)劃問(wèn)題的一個(gè)基本可行解中，如果所有的基變量都取正值，則稱它為所有的基變量都取正值，則稱它為非退化解非退化解，如，如果所有的基本可行解都是非退化解。稱該問(wèn)題為果所有的基本可行解都是非退化解。稱該問(wèn)題為非退化的線性規(guī)劃問(wèn)題非退化的

4、線性規(guī)劃問(wèn)題；若基本可行解中，有基；若基本可行解中，有基變量為零，則稱為變量為零，則稱為退化解退化解，該問(wèn)題稱為，該問(wèn)題稱為退化的線退化的線性規(guī)劃問(wèn)題性規(guī)劃問(wèn)題。基本解中最多有基本解中最多有m個(gè)非零分量。個(gè)非零分量。基本解的數(shù)目不超過(guò)基本解的數(shù)目不超過(guò) 個(gè)。個(gè)。!mnmnCmn例例 現(xiàn)有線性規(guī)劃問(wèn)題現(xiàn)有線性規(guī)劃問(wèn)題0,24261553.221212121xxxxxxtsxxZMax試求其基本解、基本可行解并判斷是否為退試求其基本解、基本可行解并判斷是否為退化解?；?。解解: (1)首先將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型首先將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型 引入松弛變量引入松弛變量x3和和x40,2402615053.2

5、43214321432121xxxxxxxxxxxxtsxxZMax(2) 求基本解求基本解由上式得由上式得10260153A2415b可能的基陣可能的基陣10260153A265312B061313B160314B021523B120524B100134B612121234!24! 2! 424C 由于所有由于所有|B| 0，所以有所以有6個(gè)基陣和個(gè)基陣和6個(gè)基本解。個(gè)基本解。242615532121xxxx對(duì)于基陣對(duì)于基陣265312B令令03x04x則則TX0043415246153131xxx對(duì)于基陣對(duì)于基陣令令02x04x則則TX0304061313B為基本可行解，為基本可行解，B1

6、3為可行基為可行基為基本可行解，為基本可行解，B12為可行基為可行基246153411xxx對(duì)于基陣對(duì)于基陣令令02x03x則則TX6005242155232xxx對(duì)于基陣對(duì)于基陣令令01x04x則則TX045120160314B021523B242155422xxx對(duì)于基陣對(duì)于基陣令令01x03x則則Tx對(duì)于基陣對(duì)于基陣令令01x02x則則TX241500120524B100134B為基本可行解，為基本可行解，B24為可行基為可行基為基本可行解，為基本可行解，B34為可行基為可行基0ABCDETX0043415TX0304TX6005TX241500TX18030T

7、X045120所以，本問(wèn)所以，本問(wèn)題存在題存在6個(gè)基個(gè)基本解，其中本解，其中4個(gè)為基可行個(gè)為基可行解解,無(wú)退化解無(wú)退化解.例例2 現(xiàn)有線性規(guī)劃問(wèn)題現(xiàn)有線性規(guī)劃問(wèn)題0,05.221212121xxxxxxtsxxZMax試求其基本解、基本可行解并判斷是否為退試求其基本解、基本可行解并判斷是否為退化解。化解。解解: (1)首先將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型首先將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型 引入松弛變量引入松弛變量x3和和x4(2) 求基本解求基本解由上式得由上式得10110111A05b0,0050.243214321432121xxxxxxxxxxxxtsxxZMax可能的基陣可能的基陣111112B011113

8、B110114B011123B110124B100134B612121234!24! 2! 424C 由于所有由于所有|B| 0，所以有所以有6個(gè)基陣和個(gè)基陣和6個(gè)基本解。個(gè)基本解。10110111A對(duì)于基陣對(duì)于基陣令令03x04x則則TX002525對(duì)于基陣對(duì)于基陣令令02x04x則則TX0500為基本可行解，為基本可行解，B12為可行基為可行基為基本可行解，為基本可行解，B13為可行基為可行基,為退化解為退化解111112B052121xxxx011113B05131xxx對(duì)于基陣對(duì)于基陣令令02x03x則則TX5005對(duì)于基陣對(duì)于基陣令令01x04x則則TX0500為基本可行解，為基本可

9、行解，B23為可行基為可行基,為退化解為退化解05411xxx05232xxx110114B011123B對(duì)于基陣對(duì)于基陣令令01x03x則則TX5050對(duì)于基陣對(duì)于基陣令令01x02x則則TX0500為基本可行解，為基本可行解，B24為可行基為可行基為基本可行解，為基本可行解，B34為可行基為可行基,為退化解為退化解05422xxx0543xx110124B100134B0ABCTX002525TX0500TX5005TX5050(2) 解的基本性質(zhì)解的基本性質(zhì)判別可行解為基可行解的準(zhǔn)則判別可行解為基可行解的準(zhǔn)則定理定理1 線性規(guī)劃問(wèn)題的可行解是基可行解的充要線性規(guī)劃問(wèn)題的可行解是基可行解的

10、充要條件是它的非零向量所對(duì)應(yīng)的列向量線性無(wú)關(guān)條件是它的非零向量所對(duì)應(yīng)的列向量線性無(wú)關(guān).線性規(guī)劃問(wèn)題的基本定理線性規(guī)劃問(wèn)題的基本定理:定理定理2和定理和定理3定理定理2 線性規(guī)劃問(wèn)題有可行解線性規(guī)劃問(wèn)題有可行解,則它必有基可行解則它必有基可行解.定理定理3 若線性規(guī)劃問(wèn)題有最優(yōu)解若線性規(guī)劃問(wèn)題有最優(yōu)解,則一定存在一個(gè)則一定存在一個(gè)基可行解是它的最優(yōu)解基可行解是它的最優(yōu)解.定理定理2 線性規(guī)劃問(wèn)題有可行解線性規(guī)劃問(wèn)題有可行解,則它必有基可行解則它必有基可行解.證證:設(shè)設(shè) 為線性規(guī)劃問(wèn)題的一個(gè)可行解為線性規(guī)劃問(wèn)題的一個(gè)可行解. 若若 ,則它是一個(gè)基可行解則它是一個(gè)基可行解,定理成立定理成立; 若若

11、,則令則令 的前的前k個(gè)分量為非零分量：個(gè)分量為非零分量： 0X 0X 00X 00X mkkjxxxxXjTk, 2 , 1, 0000002010若上述分量所對(duì)應(yīng)的列向量若上述分量所對(duì)應(yīng)的列向量 線性無(wú)關(guān)線性無(wú)關(guān),則它是一個(gè)基可行解則它是一個(gè)基可行解,定理成立定理成立;若若 線性相關(guān)，從線性相關(guān)，從 出發(fā)，出發(fā)，必可找到線性規(guī)劃問(wèn)題的一個(gè)基可行解。必可找到線性規(guī)劃問(wèn)題的一個(gè)基可行解。kPPP21kPPP21 0X由于由于 線性相關(guān)，則存在一組不全為零線性相關(guān)，則存在一組不全為零的數(shù)的數(shù) ， 使得使得kPPP21k21kjjjP10假定假定0i令令 0min0iiix若若0i令令 01XX(

12、若若0i令令 01XX)(*)0021k njxxjjj, 2 , 1001由由(*)可知可知即即 01X njnjjjjjnjjjjnjjjbPPxPxPxAX11010111 0X與與 相比，相比， 的非零分量減少的非零分量減少1個(gè)，若對(duì)應(yīng)的個(gè)，若對(duì)應(yīng)的k-1個(gè)個(gè)列向量線性無(wú)關(guān)，則即為基可行解；否則繼續(xù)上述步列向量線性無(wú)關(guān)，則即為基可行解；否則繼續(xù)上述步驟，直至剩下的非零變量對(duì)應(yīng)的列向量線性無(wú)關(guān)。驟，直至剩下的非零變量對(duì)應(yīng)的列向量線性無(wú)關(guān)。 1X幾點(diǎn)結(jié)論幾點(diǎn)結(jié)論v若線性規(guī)劃問(wèn)題有可行解若線性規(guī)劃問(wèn)題有可行解,則可行域是一個(gè)凸多邊形或則可行域是一個(gè)凸多邊形或凸多面體凸多面體(凸集凸集),且僅

13、有有限個(gè)頂點(diǎn)且僅有有限個(gè)頂點(diǎn)(極點(diǎn)極點(diǎn));v線性規(guī)劃問(wèn)題的每一個(gè)基可行解都對(duì)應(yīng)于可行域上的一線性規(guī)劃問(wèn)題的每一個(gè)基可行解都對(duì)應(yīng)于可行域上的一個(gè)頂點(diǎn)個(gè)頂點(diǎn)(極點(diǎn)極點(diǎn));v若線性規(guī)劃問(wèn)題有最優(yōu)解若線性規(guī)劃問(wèn)題有最優(yōu)解,則最優(yōu)解必可在基可行解則最優(yōu)解必可在基可行解(極極點(diǎn)點(diǎn))上達(dá)到上達(dá)到;v線性規(guī)劃問(wèn)題的基可行解線性規(guī)劃問(wèn)題的基可行解(極點(diǎn)極點(diǎn))的個(gè)數(shù)是有限的的個(gè)數(shù)是有限的,不會(huì)超不會(huì)超過(guò)過(guò) 個(gè)個(gè).mnC上述結(jié)論說(shuō)明上述結(jié)論說(shuō)明:線性規(guī)劃的最優(yōu)解可通過(guò)有限次運(yùn)算在基可行解中獲得線性規(guī)劃的最優(yōu)解可通過(guò)有限次運(yùn)算在基可行解中獲得.5.2 5.2 單純形法單純形法l基本思路和原理：基本思路和原理：l從可行

14、域的某個(gè)頂點(diǎn)出發(fā)，判斷是否最優(yōu)。如不從可行域的某個(gè)頂點(diǎn)出發(fā)，判斷是否最優(yōu)。如不是，再找另一個(gè)使得目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)（迭是，再找另一個(gè)使得目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)（迭代）。再判斷是否最優(yōu)，直到找到一個(gè)頂點(diǎn)為其代）。再判斷是否最優(yōu)，直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，或判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。最優(yōu)解，或判斷出線性規(guī)劃問(wèn)題無(wú)最優(yōu)解為止。l單純型法解題步驟：?jiǎn)渭冃头ń忸}步驟：l1 1、找出一個(gè)初始基本可行解、找出一個(gè)初始基本可行解l2 2、最優(yōu)性檢驗(yàn)、最優(yōu)性檢驗(yàn)l3 3、基變換、基變換(1)單純形法的引入單純形法的引入5.2 5.2 單純形法單純形法l例例1 1Max Z=40X1 +50X2 X1 +

15、2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0 0(1)單純形法的引入單純形法的引入解：解：(1)(1)、確定初始可行解、確定初始可行解B = ( P3 P4 P5 ) = IZ = 0 + 40X1 + 50X2X3 = 30 - ( X1 + 2X2 )X4= 60 - ( 3X1 + 2X2 )X5 = 24 - 2 X2令令X1 = X2 =0X(1) =(0, 0, 30, 60, 24)TZ(1) =0(2)(2)、判定解是否最優(yōu)、判定解是否最優(yōu)Z=0+40X1+50X2當(dāng)當(dāng) X1 從從 0 或或 X2 從從 0 Z 從從 0 X

16、X(1) (1) 不是最優(yōu)解不是最優(yōu)解(3)(3)、由一個(gè)基可行解、由一個(gè)基可行解另一個(gè)基可行解。另一個(gè)基可行解。 50 40 選選 X2 從從 0，X1 =0X3 = 30 - 2X2 0 0 X2 30/2 X4 = 60 - 2X2 0 0 X2 60/2 X5 = 24 - 2 X2 0 0 X2 24/2 X2 = min ( 30/2 , 60/2 , 24/2 ) =12X2 ：進(jìn)基變量進(jìn)基變量， X5 ：出基變量出基變量。B B2 2=( P3 P4 P2 )Z= 0 + 40 X1 + 50 X2 X3 + 2X2 = 30 - X1 X4 + 2X2 = 60 - 3X1

17、2X2 = 24 - X5 1/2 ， 代入代入 式，式， ，Z = 600 + 40X1 - 25X5X3 = 6 - X1 + X5 X4 = 36 - 3X1 + X5 X2 = 12 -1/2X5令令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )T Z(2) = 600(2)(2) 判斷判斷 400 X(2)不是最優(yōu)解不是最優(yōu)解。(3) 選選X1從從0 ， X5 =0 X3= 6- X1 0 0 X4= 36-3X1 0 0 X2=12 0 0 X1=min( 6/1 , 36/3 , 12 /0) =6X1進(jìn)基，進(jìn)基， X3出基。出基。B3 =(P1

18、P4 P2 )Z=840-40X3+15X5X1=6 - X3 + X5 X4= 18+3X3 - 2X5X2=12 -1/2X5令令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)TZ(3) =840(2) 150 X(3)不是不是(3) 選選X5從從0 ， X3 =0 X1=6 +X5 0 X4= 18 -2X5 0 X2=12-1/2 X5 0 X5=min( 18/2 , 12/1/2 ) =9X5進(jìn)基，進(jìn)基， X4出基。出基。B4=(P1 P5 P2 )Z=975- 35/2X3 - 15/2X4X1= 15 + 1/2X3 - 1/2X4X5= 9 + 3/2X3

19、 - 1/2X4X2= 15/2 -3/4X3 + 1/4X4令令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =9750(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)X(3)X(4)X(1)X(2)X(3)Z=40X1+50X2初始基本可行解初始基本可行解是否最優(yōu)解或是否最優(yōu)解或無(wú)限最優(yōu)解無(wú)限最優(yōu)解? ?結(jié)束結(jié)束沿邊界找新沿邊界找新的基本可行解的基本可行解N NY Y(2) 線性規(guī)劃的典則形式線性規(guī)劃的典則形式0XbAXt . sCXZMaxNBA NBXXXNBCCC 標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型bAX bXX

20、NBNBbNXBXNBN11BNXBbBXN1BN1 -BNNN1 -B1 -BNNN11BNNBBNBNBXNBCCbBCXCNXBCbBCXCNXBbBCXCXCXXCCCXZ0X, 0XbBNXBXt . sXNBCCbBCZMaxNB1N1BN1BN1B上式稱為線性規(guī)劃問(wèn)題對(duì)應(yīng)于基上式稱為線性規(guī)劃問(wèn)題對(duì)應(yīng)于基B的的典則形式典則形式，簡(jiǎn)稱簡(jiǎn)稱典式典式。1.約束方程組的系數(shù)矩陣中含有一個(gè)單位矩約束方程組的系數(shù)矩陣中含有一個(gè)單位矩陣，并以其為基；陣，并以其為基；2.目標(biāo)函數(shù)中不含基變量，只有非基變量。目標(biāo)函數(shù)中不含基變量，只有非基變量。 NBCC0NBCCBBCCNBBCCCABCC1BN1

21、BN1BB1BNB1B檢檢驗(yàn)驗(yàn)數(shù)數(shù)(3) 最優(yōu)性判別定理最優(yōu)性判別定理在線性規(guī)劃問(wèn)題的典式中，設(shè)在線性規(guī)劃問(wèn)題的典式中，設(shè) X(0)=(x1,x2,xm,0,0)為對(duì)應(yīng)于基為對(duì)應(yīng)于基B 的一個(gè)基可行解，若有的一個(gè)基可行解，若有 j 0 ( j = m+1 , m+2 , , n )則則X(0)是線性規(guī)劃問(wèn)題的是線性規(guī)劃問(wèn)題的最優(yōu)解最優(yōu)解，基，基B為為最優(yōu)基最優(yōu)基。證：設(shè)證：設(shè)X為線性規(guī)劃問(wèn)題的一個(gè)可行解，必有為線性規(guī)劃問(wèn)題的一個(gè)可行解，必有 X 0 ，當(dāng)，當(dāng) j 0， 則則 X 0 Z*=CX(0) = Z(0) Z(0) + X =CX 故故X(0)為線性規(guī)劃問(wèn)題的最優(yōu)解為線性規(guī)劃問(wèn)題的最優(yōu)

22、解。在線性規(guī)劃問(wèn)題的典式中，設(shè)在線性規(guī)劃問(wèn)題的典式中，設(shè) X(0)=(x1,x2,xm,0,0)為對(duì)應(yīng)于基為對(duì)應(yīng)于基B 的一個(gè)基可行解，若有的一個(gè)基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 且且 j+k = 0 則則線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解。線性規(guī)劃問(wèn)題有無(wú)窮多個(gè)最優(yōu)解。無(wú)窮多最優(yōu)解判別定理無(wú)窮多最優(yōu)解判別定理在線性規(guī)劃問(wèn)題的典式中，設(shè)在線性規(guī)劃問(wèn)題的典式中，設(shè)X(0) 為對(duì)應(yīng)于基為對(duì)應(yīng)于基B 的一個(gè)的一個(gè)基可行解，若某一非基變量基可行解，若某一非基變量xj+k的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) j+k 0 且對(duì)應(yīng)的列向量且對(duì)應(yīng)的列向量 Pm+k=(a1,m+k,a2,m+k,a

23、m,m+k) 0 則則線性規(guī)劃問(wèn)題具有無(wú)界解。線性規(guī)劃問(wèn)題具有無(wú)界解。無(wú)界解判別定理無(wú)界解判別定理(4) 基可行解改進(jìn)定理基可行解改進(jìn)定理在線性規(guī)劃問(wèn)題的典式中，設(shè)在線性規(guī)劃問(wèn)題的典式中，設(shè) X(0)=(x1,x2,xm,0,0)為對(duì)應(yīng)于基為對(duì)應(yīng)于基B 的一個(gè)基可行解，若滿足以下條件：的一個(gè)基可行解，若滿足以下條件：1) 某個(gè)非基變量的檢驗(yàn)數(shù)某個(gè)非基變量的檢驗(yàn)數(shù) k 0 ( m+1 k n );2) aik ( i = 1,2,m )不全小于或等于零，即至少有一個(gè)不全小于或等于零，即至少有一個(gè) aik 0 ( 1 k m );3) bi 0( I = 1 , 2,m ),即即X(0)為非退化的

24、基可行解。為非退化的基可行解。則從則從X(0)出發(fā)，一定能找到一個(gè)新的基可行解出發(fā)，一定能找到一個(gè)新的基可行解X(1)，使得，使得 CX(1) CX(0) 。(5) 單純形表單純形表00,XXbBNXBXs.tXNBCCbBCZMaxNB1N1BN1BN1B將線性規(guī)劃問(wèn)題典式中的數(shù)據(jù)按一定規(guī)則列入表將線性規(guī)劃問(wèn)題典式中的數(shù)據(jù)按一定規(guī)則列入表中，該表即為中，該表即為單純形表單純形表。CCBCNCBXBbXBXNCBXBB-1bIB-1NZCB B-1b0CN-CB B-1NC2100CBXBbX1X2X3X40X31535100X4246201Z02100C2100CBXBbX1X2X3X40X

25、33041-1/22X1411/301/6Z801/30-1/3(1)、確定初始基域初始基本可行解、確定初始基域初始基本可行解,列出初始單列出初始單純形表純形表(3)、若有、若有 j 0，Pj 全全 0，停止，停止， 沒(méi)有有限最優(yōu)解；沒(méi)有有限最優(yōu)解； 否則轉(zhuǎn)否則轉(zhuǎn) (4)(2)、對(duì)應(yīng)于非基變量檢驗(yàn)數(shù)、對(duì)應(yīng)于非基變量檢驗(yàn)數(shù) j全小于全小于零零。 若是，停止，得到最優(yōu)解；若是，停止，得到最優(yōu)解； 若否，轉(zhuǎn)若否，轉(zhuǎn)(3)。(6) (6) 單純形單純形法的迭代步驟單純形單純形法的迭代步驟= = min aim+k 0 =0 =biaim+kbrarm+k定定Xr為出基變量，為出基變量，arm+k為為主

26、元。主元。由最小由最小比值法求：比值法求：Max j = m+kXm+k 進(jìn)基變量進(jìn)基變量 j 0 0(4)、轉(zhuǎn)轉(zhuǎn)(2) (2) a1m+k 0a2m+k 0ar,m+k 1amm+k 0初等行變換初等行變換Pm+k =(5)、以、以arm+k為中心，換基迭代為中心，換基迭代從步驟從步驟(2)-(5)(2)-(5)的每一個(gè)循環(huán)，稱為一次的每一個(gè)循環(huán)，稱為一次單純形迭代單純形迭代。例例1、Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.t X1+2X2 +X3 = 303X1+2X2 +X4 =60 2X2 +X5 = 24 X1

27、 X5 0 0s.tC4050000CBXBBX1X2X3X4X50X33012100150X46032010300X5240200112Z04050000 CBXBBX1X2X3X4X50X33012100 0X46032010 50X22402001 Z CBXBBX1X2X3X4X50X361010-160X4363001-11250X21201001/2 Z60040000-25 C4050000CBXBBX1X2X3X4X540X161010-10X41800-312950X21201001/224Z84000-40015 CBXBBX1X2X3X4X540X11510-1/21/2

28、0 0X5900-3/21/21 50X215/2975013/4-1/40 Z 0 0-35/2-15/2 0 例例1、Max Z=40X1+ 80X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.t X1+2X2 +X3 = 303X1+2X2 +X4 =60 2X2 +X5 = 24 X1 X5 0 0s.tC4080000CBXBBX1X2X3X4X50X33012100150X46032010300X5240200112Z04080000 CBXBBX1X2X3X4X50X361010-1 60X4363001-112 80X21201001/2

29、Z 960 40 0 0 0 -40 CBXBBX1X2X3X4X540X161010-10X41800-312980X21201001/2 24Z120000-4000 C4050000CBXBBX1X2X3X4X540X115101/2-1/20 0X59003/2-1/20 80X215/2120001-3/41/41 Z 0 0 -200 0 5.3 5.3 求初始基的人工變量法求初始基的人工變量法求解線性規(guī)劃問(wèn)題的單純形法第一步就是要找求解線性規(guī)劃問(wèn)題的單純形法第一步就是要找到一個(gè)初始可行基并求出初始基可行解，以它到一個(gè)初始可行基并求出初始基可行解，以它作為迭代的起點(diǎn)。作為迭代的起點(diǎn)

30、。獲得初始可行基及初始基可行解的途徑主要有：獲得初始可行基及初始基可行解的途徑主要有：(1) 試算法；試算法；(2) 人工變量法。人工變量法。在約束方程組中的每一個(gè)沒(méi)有單位向量的約束在約束方程組中的每一個(gè)沒(méi)有單位向量的約束方程中人為加入一個(gè)變量，使系數(shù)矩陣中湊成方程中人為加入一個(gè)變量，使系數(shù)矩陣中湊成一個(gè)單位方陣，以形成一個(gè)初始可行基陣。一個(gè)單位方陣，以形成一個(gè)初始可行基陣。約束條件約束條件： a11x1 + a12x2 + + a1nxn +xn+1= b1 a21x1 + a22x2 + + a2nxn +xn+2 = b2 . . . am1x1 + am2x2 + + amnxn +x

31、n+m = bm x1 ，x2 ， ，xn , xn+1 , , xn+m 0s.t0,.MMXXbIXAXts人工變量人工變量人工基人工基0.XbAXtsCXZMax0,.MMXXbIXAXtsCXZMax等價(jià)否？等價(jià)否？0.XbAXtsCXZMax0,.MMXXbIXAXtsCXZMax0MX0.XbAXtsCXZMax0,.MMMXXbIXAXtsMXCXZMax0.XbAXtsCXZMax0,.MMMXXbIXAXtsIXZMax大大M法法兩階段法兩階段法(1) 大大M法法例例3、 Max Z=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0s.t2X1+X2-X

32、3 =8-2X1+X2 +X4= 2X1 X4 0s.tMax Z=2X1+ 4X2 MX52X1+X2-X3 +X5 =8-2X1+X2 +X4= 2X1 X5 0s.tC2400-MCBXBbX1X2X3X4X5-MX5821-10140X42-21010 Z-8M2+2M4+M-M00 2X1411/2-1/201/280X41002-1115Z80310-1 2X1610-1-11 4X2501-1/21/21/2 Z320040-4 例例4、 Max Z=3X1+2X2 -X1 -X2 1X1 , X2 0s.t-X1 -X2 X3 =1X1 , X2 0s.tMax Z=3X1+2

33、X2 MX4-X1 -X2 X3 +X4 =1X1 X4 0s.tC320-MCBXBbX1X2X3X4-MX41-1-1-11 Z-M3+M2+MM0 0,10527.532321321321321XXXXXXXXXtsXXXZMax010527.)(5326165321432164321XXXXXXXXXXXtsXXMXXXZMaxC23-5-M0-MCBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115Z-17M2+3M3-4M2M-50-M0 -MX4207/21/211/2-1/24/72X151-5/21/20-1/21/2 Z2M-1003M/2+8M/