運(yùn)籌(第一章線性規(guī)劃)

1、2022-3-171運(yùn)籌學(xué)運(yùn)籌學(xué)OPERATIONS RESEARCH2022-3-172第一章第一章 線性規(guī)劃及單純形法線性規(guī)劃及單純形法 (Linear Programming, LP)n線性規(guī)劃模型線性規(guī)劃模型n圖解法圖解法n單純形法原理單純形法原理n單純形法計(jì)算步驟單純形法計(jì)算步驟n單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論n數(shù)據(jù)包絡(luò)分析數(shù)據(jù)包絡(luò)分析2022-3-1731 1 一般線性規(guī)劃問題的數(shù)學(xué)模型一般線性規(guī)劃問題的數(shù)學(xué)模型1.1 1.1 引例引例 例例1 生產(chǎn)計(jì)劃問題生產(chǎn)計(jì)劃問題 能力能力 設(shè)備設(shè)備A 2 2 12 設(shè)備設(shè)備B 4 0 16 設(shè)備設(shè)備C 0 5 15 利潤利潤 2

2、3，各生產(chǎn)多少各生產(chǎn)多少, 可獲最大利潤可獲最大利潤?2022-3-174注意模型特點(diǎn)注意模型特點(diǎn)解解:設(shè)產(chǎn)品設(shè)產(chǎn)品, 產(chǎn)量分別為變量產(chǎn)量分別為變量 。21,xx2132maxxxZ0,1551641222.212121xxxxxxts2022-3-175線性規(guī)劃模型特點(diǎn)線性規(guī)劃模型特點(diǎn)n決策變量：向量決策變量：向量 決策人要考慮和決策人要考慮和 控制的因素，非負(fù)?？刂频囊蛩兀秦?fù)。n約束條件：關(guān)于約束條件：關(guān)于 的線性等式或不等式。的線性等式或不等式。n目標(biāo)函數(shù)：目標(biāo)函數(shù)： 為關(guān)于為關(guān)于 的線性函的線性函 數(shù)，求數(shù)，求Z Z極大或極小極大或極小TnxxxX）（,.,21X）（nxxxfZ,.

3、,21X2022-3-1761.2 1.2 線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃問題的數(shù)學(xué)模型線性規(guī)劃模型的三個組成要素：線性規(guī)劃模型的三個組成要素：1.1.決策變量決策變量: :是決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、是決策者為實(shí)現(xiàn)規(guī)劃目標(biāo)采取的方案、措施，是問題中要確定的未知量。措施，是問題中要確定的未知量。2.2.目標(biāo)函數(shù)目標(biāo)函數(shù): :指問題要達(dá)到的目的要求，表示為決指問題要達(dá)到的目的要求，表示為決策變量的函數(shù)。策變量的函數(shù)。3.3.約束條件約束條件: :指決策變量取值時受到的各種可用資指決策變量取值時受到的各種可用資源的限制，表示為含決策變量的等式或不等式。源的限制，表示為含決策變量的等式或不等式

4、。2022-3-177一般線性規(guī)劃問題的數(shù)學(xué)模型：一般線性規(guī)劃問題的數(shù)學(xué)模型：0 x,x,xb,xaxaxab,xaxaxab,xaxaxan21mnmn22m11m2nn22221211nn1212111）（或）（或）（或目標(biāo)函數(shù)：目標(biāo)函數(shù)：約束條件：約束條件：nn2211xcxcxczminmax）（或2022-3-178簡寫形式：簡寫形式：），（），（），（或）（或n1j0 xm1ibxaxczminmaxjin1jjijn1jjj 2022-3-179矩陣形式表示為：矩陣形式表示為：0minmaxXbAXCXz），（或）（或其中：其中：mnmmnnaaaaaaaaaA212222111

5、211ncccC,21TnxxxX,21Tmbbbb,212022-3-17101.3 1.3 線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式：），（），（n1j0 xm1ibxaxczmaxjin1jjijn1jjj 2022-3-1711標(biāo)準(zhǔn)形式特點(diǎn)：標(biāo)準(zhǔn)形式特點(diǎn)：4.4.決策變量取值非負(fù)。決策變量取值非負(fù)。1.1.目標(biāo)函數(shù)為求極大值；目標(biāo)函數(shù)為求極大值；2.2.約束條件全為等式；約束條件全為等式；3.3.約束條件右端常數(shù)項(xiàng)全為非負(fù)；約束條件右端常數(shù)項(xiàng)全為非負(fù)；2022-3-1712一般線性規(guī)劃問題如何化為標(biāo)準(zhǔn)型：一般線性規(guī)劃問題如何化為標(biāo)準(zhǔn)型：1.1.目標(biāo)函數(shù)求極小值：目

6、標(biāo)函數(shù)求極小值：njjjxcz1min令：令： ，即化為：，即化為：zznjjjnjjjxcxczzz11min)max(max2022-3-17132. 2. 約束條件為不等式：約束條件為不等式：（1 1）當(dāng)約束條件為）當(dāng)約束條件為“”“”時時如：如：122221 xx可令：可令： ， 顯然顯然1222321xxx03x（2 2）當(dāng)約束條件為）當(dāng)約束條件為“”“”時時如：如：18121021xx可令：可令： ，顯然，顯然04x181210421xxx 稱為稱為松弛變量。松弛變量。3x 稱為稱為剩余變量。剩余變量。4x2022-3-1714松弛變量和剩余變量統(tǒng)稱為松弛變量。松弛變量和剩余變量統(tǒng)

7、稱為松弛變量。（3 3）目標(biāo)函數(shù)中松弛變量的系數(shù)）目標(biāo)函數(shù)中松弛變量的系數(shù) 由于松弛變量和剩余變量分別表示未被充分利由于松弛變量和剩余變量分別表示未被充分利用的資源以及超用的資源，都沒有轉(zhuǎn)化為價值和利用的資源以及超用的資源，都沒有轉(zhuǎn)化為價值和利潤，因此潤，因此在目標(biāo)函數(shù)中系數(shù)為零在目標(biāo)函數(shù)中系數(shù)為零。2022-3-17153. 3. 取值無約束的變量取值無約束的變量xxx 其中：其中：00 xx，令令4. 變量變量 xj0jjxx，顯然，顯然0jx 如果變量如果變量 代表某產(chǎn)品當(dāng)年計(jì)劃數(shù)與上一年代表某產(chǎn)品當(dāng)年計(jì)劃數(shù)與上一年計(jì)劃數(shù)之差，顯然計(jì)劃數(shù)之差，顯然 的取值可能是正也可能是負(fù)，的取值可能是

8、正也可能是負(fù)，這時可令：這時可令：xx2022-3-1716例例. . 將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)型將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)型取值無約束321321321321321, 0, 06323 42 39 232minxxxxxxxxxxxxxxxz2022-3-1717解：令解：令，11xxzz00 33333 xxxxx，得標(biāo)準(zhǔn)形式為：得標(biāo)準(zhǔn)形式為： 06 33234 22 39 200332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxz，2022-3-1718求解線性規(guī)劃問題：求解線性規(guī)劃問題：就是從滿足約束方程組和約束不等式

9、的決策變量取就是從滿足約束方程組和約束不等式的決策變量取值中，找出使得目標(biāo)函數(shù)達(dá)到最大的值。值中，找出使得目標(biāo)函數(shù)達(dá)到最大的值。），（），（njxmibxaxczjinjjijnjjj1 01 max111.4 1.4 線性規(guī)劃問題的解的概念線性規(guī)劃問題的解的概念2022-3-1719 可行解：可行解：滿足約束條件的解稱為滿足約束條件的解稱為可行解可行解，可行解，可行解 的集合稱為的集合稱為可行域。可行域。最優(yōu)解：最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。使目標(biāo)函數(shù)達(dá)到最大值的可行解。 基：基：約束方程組的系數(shù)矩陣中的一個滿秩子矩陣稱約束方程組的系數(shù)矩陣中的一個滿秩子矩陣稱 為規(guī)劃問題的一個為規(guī)劃

10、問題的一個基基，基中的每一個列向量稱，基中的每一個列向量稱 為為基向量，基向量，與基向量對應(yīng)的變量稱為與基向量對應(yīng)的變量稱為基變量基變量， 其他變量稱為其他變量稱為非基變量。非基變量。 說明：基通常不唯一。說明：基通常不唯一。2022-3-1720 基解：基解：在約束方程組中，令所有非基變量為在約束方程組中，令所有非基變量為0 0，可以解，可以解 出基變量的唯一解，這組解與非基變量的出基變量的唯一解，這組解與非基變量的0 0共共 同構(gòu)成同構(gòu)成基解?；??；尚薪猓夯尚薪猓簼M足變量非負(fù)的基解稱為滿足變量非負(fù)的基解稱為基可行解?；尚薪??？尚谢嚎尚谢簩?yīng)于基可行解的基稱為對應(yīng)于基可行解的基稱

11、為可行基。可行基。2022-3-1721例：考察下述線性規(guī)劃問題：例：考察下述線性規(guī)劃問題：5,.2 , 1, 01551641222. .00032max524132154321ixxxxxxxxtsxxxxxzi2022-3-1722（1 1）可行解，如）可行解，如)15,16,12, 0 , 0()0 , 4 , 0 , 3 , 3(或或滿足約束條件，所以是可行解。滿足約束條件，所以是可行解。（2 2）基）基系數(shù)矩陣系數(shù)矩陣100500100400122A54321PPPPP其中其中 100010001),(5431PPPB或或 150004022),(5212PPPB都構(gòu)成基。而都構(gòu)成

12、基。而 )(431PPP不構(gòu)成基。不構(gòu)成基。2022-3-1723（3 3）基向量、基變量）基向量、基變量521,PPP是對應(yīng)于基是對應(yīng)于基的三個基向量，而的三個基向量，而2B521,xxx是對應(yīng)于這三個基向量的基變量。是對應(yīng)于這三個基向量的基變量。（4）基解、基可行解、可行基）基解、基可行解、可行基）（15,16,12, 0 , 0是對應(yīng)于基是對應(yīng)于基1B的基解、基可行解。的基解、基可行解。)5 ,0,0,2,4(是對應(yīng)于基是對應(yīng)于基2B的基解、基可行解。的基解、基可行解。21,BB均是可行基均是可行基 。練習(xí)：練習(xí)：P14P14， 例例4 42022-3-1724 為了便于建立為了便于建立

13、 n n 維空間中線性規(guī)劃問題的有關(guān)維空間中線性規(guī)劃問題的有關(guān)概念及便于理解求解一般線性規(guī)劃問題的單純形法的概念及便于理解求解一般線性規(guī)劃問題的單純形法的思路，先介紹圖解法。思路，先介紹圖解法。求解下述線性規(guī)劃問題：求解下述線性規(guī)劃問題：0,151641222212121xxxxxx 5 2132maxxxz2 2 線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法2022-3-1725畫出線性規(guī)劃問題的可行域：畫出線性規(guī)劃問題的可行域：122221 xx1641x1552x2x1xO1Q2Q3Q4Q342132xxZ目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線33212zxx2022-3-17261 1、可行域：、可

14、行域：約束條件所圍成的區(qū)域。約束條件所圍成的區(qū)域。2 2、基可行解、基可行解：對應(yīng)可行域的頂點(diǎn)。：對應(yīng)可行域的頂點(diǎn)。3 3、目標(biāo)函數(shù)等值線：、目標(biāo)函數(shù)等值線：332321221zxxxxZ4 4、目標(biāo)函數(shù)最優(yōu)值、目標(biāo)函數(shù)最優(yōu)值: : 最大截距所對應(yīng)的最大截距所對應(yīng)的 。 目標(biāo)函數(shù)等值線有無數(shù)條，且平行。（觀察規(guī)律目標(biāo)函數(shù)等值線有無數(shù)條，且平行。（觀察規(guī)律) )Z2022-3-1727解的幾種情況：解的幾種情況：( (2)2)無窮多最優(yōu)解：無窮多最優(yōu)解：若目標(biāo)函數(shù)改為若目標(biāo)函數(shù)改為( (1)1)唯一最優(yōu)解唯一最優(yōu)解2122maxxxz約束條件不變，則約束條件不變，則: :122221 xx164

15、1x1552x2x1xO1Q2Q3Q4Q342122xxZ目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線此時，線段此時，線段上所有點(diǎn)都是最優(yōu)上所有點(diǎn)都是最優(yōu)值點(diǎn)。值點(diǎn)。32QQ2022-3-1728( (4) 4) 無界解無界解( (3) 3) 無可行解：無可行解：當(dāng)可行域?yàn)榭占瘯r，無可行解當(dāng)可行域?yàn)榭占瘯r，無可行解。若目標(biāo)函數(shù)不變，將若目標(biāo)函數(shù)不變，將約束條件約束條件1和和3去掉，則可行去掉，則可行域及解的情況見下圖。域及解的情況見下圖。1641x2x1xO1Q2Q3Q4Q342122xxZ目標(biāo)函數(shù)等值線目標(biāo)函數(shù)等值線此時，目標(biāo)函數(shù)等此時，目標(biāo)函數(shù)等值線可以向上無窮值線可以向上無窮遠(yuǎn)處平移，遠(yuǎn)處平移，Z值無值

16、無界。界。2022-3-1729幾點(diǎn)說明：幾點(diǎn)說明：1、圖解法只能用來求解含有兩個決策變量的線、圖解法只能用來求解含有兩個決策變量的線 性規(guī)劃問題。性規(guī)劃問題。2、若最優(yōu)解存在，則必在可行域的某個頂點(diǎn)處、若最優(yōu)解存在，則必在可行域的某個頂點(diǎn)處 取得。取得。3、線性規(guī)劃問題的解可能是：唯一最優(yōu)解、無、線性規(guī)劃問題的解可能是：唯一最優(yōu)解、無 窮多最優(yōu)解、無最優(yōu)解、無界解。窮多最優(yōu)解、無最優(yōu)解、無界解。2022-3-17303 3單純形法原理單純形法原理上圖中（上圖中（1 1）（）（2 2）是凸集，（）是凸集，（3 3）（）（4 4）不是凸集）不是凸集3.1 3.1 預(yù)備知識預(yù)備知識 X凸集：凸集：

17、如果集合如果集合 中任意兩個點(diǎn)中任意兩個點(diǎn) ，其連線上的，其連線上的所有點(diǎn)也都是集合所有點(diǎn)也都是集合 中的點(diǎn)。中的點(diǎn)。21, XXCC頂點(diǎn)：頂點(diǎn)：如果對于凸集如果對于凸集 中的點(diǎn)中的點(diǎn) ，不存在，不存在 中的任意中的任意其它兩個不同的點(diǎn)其它兩個不同的點(diǎn) ，使得，使得 在它們的連線上，在它們的連線上，這時稱這時稱 為凸集的頂點(diǎn)。為凸集的頂點(diǎn)。21XX 、XXCC2022-3-17313.2 3.2 線性規(guī)劃問題基本定理線性規(guī)劃問題基本定理定理定理1:1:若線性規(guī)劃問題存在可行解，則問題的可行域若線性規(guī)劃問題存在可行解，則問題的可行域 是凸集。是凸集。證明證明: :設(shè)設(shè) 是線性規(guī)劃的任意兩個可行解

18、，則是線性規(guī)劃的任意兩個可行解，則21, XX0,0,2211XbAXXbAX于是對于任意的于是對于任意的 ， ，則則 ) 10( ,0)1 (21XXXbbbAXAXXXAAX)1 ()1 ()1 (2121所以所以 也是問題的可行解，即可行域也是問題的可行解，即可行域是凸集。是凸集。 21)1 (XXX2022-3-1732引理引理: : 線性規(guī)劃問題的可行解線性規(guī)劃問題的可行解 X X為基可行解的充要為基可行解的充要條件是條件是X X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。證明證明: :設(shè)設(shè) （1 1） 必要性顯然。必要性顯然。（2 2） 設(shè)設(shè) A A 的

19、秩為的秩為m m。可行解?？尚薪?X X 的前的前 k k 個分量個分量為正，且它們對應(yīng)的系數(shù)列向量為正，且它們對應(yīng)的系數(shù)列向量 線性無線性無關(guān)，則關(guān)，則 。 當(dāng)當(dāng) 時，時， 恰好構(gòu)成一組基，而恰好構(gòu)成一組基，而 恰是這組基對應(yīng)的基可行解。恰是這組基對應(yīng)的基可行解。 TnxxxX),.,(21)kPPP,.,21mk mk mPPP,.,21TmxxxX)0,.0 ,.,(212022-3-1733 當(dāng)當(dāng) 時，在時，在 基礎(chǔ)上從其余列向基礎(chǔ)上從其余列向量中可以找出量中可以找出 個線性無關(guān)的向量，恰好構(gòu)成一個線性無關(guān)的向量，恰好構(gòu)成一組基，而組基，而 X X 就是這組基對應(yīng)的基可行解。就是這組基

20、對應(yīng)的基可行解。 mk kPPP,.,21km2022-3-1734定理定理2:2: 線性規(guī)劃問題的基可行解線性規(guī)劃問題的基可行解 X X 對應(yīng)線性規(guī)劃對應(yīng)線性規(guī)劃問題可行域（凸集）的頂點(diǎn)。問題可行域（凸集）的頂點(diǎn)。證明證明: :問題即是要證明問題即是要證明: X: X是基可行解是基可行解 X X是可行域是可行域頂點(diǎn)，也即要證明其逆否命題：頂點(diǎn)，也即要證明其逆否命題： X X不是基可行解不是基可行解 X X不是可行域頂點(diǎn)不是可行域頂點(diǎn) 。（1 1）X X不是基可行解不是基可行解 X X不是可行域頂點(diǎn)。不是可行域頂點(diǎn)。假設(shè)假設(shè)X X是可行解，但不是基可行解，是可行解，但不是基可行解，X X的前的

21、前 k k個分量為個分量為正正, ,其余分量為其余分量為0 0，則有，則有) 1 (1kiiibxP又又X X不是基可行解，所以由引理知，正分量對應(yīng)不是基可行解，所以由引理知，正分量對應(yīng)列向量列向量 線性相關(guān)。即存在一組不全為線性相關(guān)。即存在一組不全為零的數(shù)零的數(shù) ，使得，使得用非零常數(shù)用非零常數(shù) 乘以上式得：乘以上式得：2022-3-1735ikPPP,.,21)2(01kiiiP)3(01kiiiP2022-3-1736（1）+（3）得：）得：（1）-（3）得：）得：令令選擇合適的選擇合適的 ，使得所有的，使得所有的于是于是 均是可行解，并且均是可行解，并且 ，所以，所以 X 不是可行域頂

22、點(diǎn)。不是可行域頂點(diǎn)。)4()(.)()(1111kikkkiiibPxPxPx)5()(.)()(1111kikkkiiibPxPxPx0,.,0),(),.,(112kkxxX0,.,0),(),.,(111kkxxX),.,2 , 1(, 0kixii21,XX212121XXX2022-3-1737（2 2）X X不是可行域頂點(diǎn)不是可行域頂點(diǎn) X X不是基可行解不是基可行解 。設(shè)設(shè) 不是可行域的頂點(diǎn)，因而不是可行域的頂點(diǎn)，因而可以找到可行域內(nèi)另兩個不同的點(diǎn)，可以找到可行域內(nèi)另兩個不同的點(diǎn)， 使得使得用分量表示即為：用分量表示即為： TkxxxX)0,.0 ,.,(210),.,(21Tn

23、yyyY0),.,(21TnzzzZ0)1 (ZYX),.,2 , 1, 10(, 0)1 (njzyxjjj易知，當(dāng)易知，當(dāng) ， 時，必有時，必有 0jx, 0jy),.,1( , 0nkjzj2022-3-1738所以所以,)0,.0 ,.,(21TkyyyY TkzzzZ)0,.0 ,.,(21所以所以) 1 (1kjjjbyP)2(1kjjjbzP于是（于是（1）-（2）得）得kjjjjPzy10)(而而 不全為零，于是知不全為零，于是知 線性相關(guān)，線性相關(guān)，X不是基可行解不是基可行解。 證畢。證畢。jjzy kPPP,.,212022-3-1739定理定理3: 若線性規(guī)劃問題有最優(yōu)解

24、，一定存在一個基若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解?？尚薪馐亲顑?yōu)解。引理：引理： 有界有界 凸集中的任何一點(diǎn)均可表示成頂點(diǎn)的凸凸集中的任何一點(diǎn)均可表示成頂點(diǎn)的凸組合。組合。證明證明: :假設(shè)假設(shè) 是可行域頂點(diǎn)，是可行域頂點(diǎn)， 不是可行不是可行域頂點(diǎn)域頂點(diǎn) ，且目標(biāo)函數(shù)在，且目標(biāo)函數(shù)在 處達(dá)到最優(yōu)，即處達(dá)到最優(yōu)，即 kXXX,.,210X0X0CXz 2022-3-1740由引理知：由引理知： 可表示為可表示為 的凸組合，的凸組合，即即0XkXXX,.,21kiiikkXXXX1221101, 0,.因此因此kikiiiiiCXXCCX110假設(shè)假設(shè) 是所有是所有 中最大者，則

25、中最大者，則mCXiCXkimmikiiiCXCXCXCX1102022-3-1741而而 是目標(biāo)函數(shù)的最大值，所以是目標(biāo)函數(shù)的最大值，所以 也是最大值，也即，目標(biāo)函數(shù)在可行域的某個頂點(diǎn)也是最大值，也即，目標(biāo)函數(shù)在可行域的某個頂點(diǎn)達(dá)到了最優(yōu)。達(dá)到了最優(yōu)。0CX0CXCXm從上述三個定理可以看出，要求線性規(guī)劃問題的最從上述三個定理可以看出，要求線性規(guī)劃問題的最優(yōu)解，只要比較可行域（凸集）各個頂點(diǎn)對應(yīng)的目優(yōu)解，只要比較可行域（凸集）各個頂點(diǎn)對應(yīng)的目標(biāo)函數(shù)值即可，最大的就是我們所要求的最優(yōu)解。標(biāo)函數(shù)值即可，最大的就是我們所要求的最優(yōu)解。2022-3-17423.3 3.3 確定初始基可行解確定初始基

26、可行解尋求最優(yōu)解的思路：尋求最優(yōu)解的思路：線性規(guī)劃問題的最優(yōu)解一定會在線性規(guī)劃問題的最優(yōu)解一定會在基可行解中取得，我們先找到一個初始基可行解。然基可行解中取得，我們先找到一個初始基可行解。然后設(shè)法轉(zhuǎn)換到另一個基可行解，并使得目標(biāo)函數(shù)值不后設(shè)法轉(zhuǎn)換到另一個基可行解，并使得目標(biāo)函數(shù)值不斷增大，直到找到最優(yōu)解為止。斷增大，直到找到最優(yōu)解為止。設(shè)給定線性規(guī)劃問題：設(shè)給定線性規(guī)劃問題：），（），（njxmibxaxczjinjjijnjjj101max11 2022-3-1743因此約束方程組的系數(shù)矩陣為：因此約束方程組的系數(shù)矩陣為：100010001212222111211mnmmnnaaaaaaaa

27、a添加松弛變量得其標(biāo)準(zhǔn)形為：添加松弛變量得其標(biāo)準(zhǔn)形為：），（），（njxmibxxaxxczjisinjjijmisinjjj1 01 0max1112022-3-1744由于該矩陣含有一個單位子矩陣，因此，這個單位陣由于該矩陣含有一個單位子矩陣，因此，這個單位陣就是一組基，就可以求出一個基可行解：就是一組基，就可以求出一個基可行解：TmbbX, 0 , 01說明：說明：如果約束條件不全是如果約束條件不全是 形式，如含所有形式，如含所有 形式，則無法找到一個單位陣作為一組基，這時需要形式，則無法找到一個單位陣作為一組基，這時需要添加人工變量，在后面的內(nèi)容介紹。添加人工變量，在后面的內(nèi)容介紹。,

28、稱其為稱其為初始基可行解初始基可行解。2022-3-17453.4 3.4 從初始基可行解轉(zhuǎn)換為另一個基可行解從初始基可行解轉(zhuǎn)換為另一個基可行解 思路：思路：對初始基可行解的系數(shù)矩陣進(jìn)行初等行變對初始基可行解的系數(shù)矩陣進(jìn)行初等行變換，構(gòu)造出一個新的單位矩陣，其各列所對應(yīng)的變換，構(gòu)造出一個新的單位矩陣，其各列所對應(yīng)的變量即為一組新的基變量，求出其數(shù)值，就是一個新量即為一組新的基變量，求出其數(shù)值，就是一個新的基可行解。的基可行解。 設(shè)有初始基可行解設(shè)有初始基可行解 ，并可設(shè)前并可設(shè)前 m m 個分量非零，即個分量非零，即 于是于是),.,()0()0(2)0(1)0(nxxxX)0,.,0 ,x,

29、.,x,x(X)0(m)0(2)0(1)0() 1 (1)0(miiibxP2022-3-1746 由構(gòu)造初始可行基的方法知前由構(gòu)造初始可行基的方法知前m m 個基向量恰好是個基向量恰好是一個單位陣，所以約束方程組的增廣矩陣為一個單位陣，所以約束方程組的增廣矩陣為mnmnnjmmmjmjmbbbaaaaaaaaa.1.00.0.100.0121, 2, 1,1, 21, 2, 11, 1bPPPPPPnjmm.1212022-3-1747由于由于任意系數(shù)列向量均可由基向量組線性表示任意系數(shù)列向量均可由基向量組線性表示，則，則非基向量中的非基向量中的 用基向量組線性表示為：用基向量組線性表示為：

30、jP),.,1(, 011nmjPaPPaPmiiijjmiiijj設(shè)有設(shè)有 ，則，則0)2(0)(1miiijjPaP（1 1）+ +（2 2）得：）得：) 3()()(1)0(11)0(bPPaxPaPxPjimiijimiiijjmiii2022-3-1748由此式可知，我們找到了滿足約束方程組的另一個由此式可知，我們找到了滿足約束方程組的另一個解解 ，)1(X) 0,.,0 ,.,()0(2)0(21)0(1) 1 (mjmjjaxaxaxX要使其要使其成為可行解成為可行解，只要對所有，只要對所有 i=1,2,m i=1,2,m ，下，下式成立式成立0)0(ijiax要使其要使其成為基

31、可行解成為基可行解，上面，上面m m個式中至少有一個取零。個式中至少有一個取零。（基可行解中非零分量的個數(shù)不超過（基可行解中非零分量的個數(shù)不超過m m 個。）個。）（與（與 比較）比較）)0,.,0 ,x,.,x,x(X)0(m)0(2)0(1)0(2022-3-1749只要取只要取ljlijijiaxaax)0()0(0min于是前于是前m m個分量中的第個分量中的第 個變?yōu)榱?，其余非?fù)，第個變?yōu)榱?，其余非?fù)，第個分量為正，于是非零分量的個數(shù)個分量為正，于是非零分量的個數(shù) ，并可證，并可證得得線性無關(guān)，所以線性無關(guān)，所以 是新的基可行解。是新的基可行解。jmllPPPPPP,.1121)1(

32、Xmlj2022-3-17503.4 3.4 最優(yōu)性檢驗(yàn)和解的判別最優(yōu)性檢驗(yàn)和解的判別設(shè)有基可行解設(shè)有基可行解TnxxxX00201)0(,) 0,.,0 ,.,()0(2)0(21)0(1) 1 (mjmjjaxaxaxX比較兩者對應(yīng)的目標(biāo)函數(shù)值，哪一個更優(yōu)？比較兩者對應(yīng)的目標(biāo)函數(shù)值，哪一個更優(yōu)？miiixcz10)0(miijijjijmiiiacczcaxcz1)0(10)1()()(2022-3-17512 2）若對所有的）若對所有的 ，則，則 ， 就是最優(yōu)解。就是最優(yōu)解。0)(1miijijjacc)0()1 (zz)0(zmiijijjacc1是判斷是否達(dá)到最優(yōu)解的標(biāo)是判斷是否達(dá)到

33、最優(yōu)解的標(biāo)準(zhǔn)，稱為準(zhǔn)，稱為檢驗(yàn)數(shù)。檢驗(yàn)數(shù)。1 1）當(dāng)）當(dāng) 時，時， ，目標(biāo)函數(shù)，目標(biāo)函數(shù)值得到了改進(jìn)，值得到了改進(jìn)， 不是最優(yōu)解，需要繼續(xù)迭代。不是最優(yōu)解，需要繼續(xù)迭代。0)(1miijijjacc)0()1(zz)0(z易知易知2022-3-1752當(dāng)所有當(dāng)所有 時，現(xiàn)有頂點(diǎn)對應(yīng)的基可行解即時，現(xiàn)有頂點(diǎn)對應(yīng)的基可行解即為最優(yōu)解。為最優(yōu)解。當(dāng)所有當(dāng)所有 時，又對某個非基變量時，又對某個非基變量 有有 則該線性規(guī)劃問題有無窮多最優(yōu)解。則該線性規(guī)劃問題有無窮多最優(yōu)解。如果存在某個如果存在某個 ，又，又 向量的所有分量向量的所有分量 ，對任意，對任意 ，恒有，恒有 ，則存在無界解。則存在無界解。kx

34、0j0j0k0jjP0ija000ijiax結(jié)論結(jié)論2022-3-17534 4 單純形法的計(jì)算步驟單純形法的計(jì)算步驟 設(shè)有線性規(guī)劃問題：設(shè)有線性規(guī)劃問題：nnxcxcxcZ.max(min)22110,.,.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa2022-3-1754(1)(1)找到初始可行基，建立初始單純形表找到初始可行基，建立初始單純形表. .(4)(4) 重復(fù)二、三兩步，直至找到最優(yōu)解重復(fù)二、三兩步，直至找到最優(yōu)解。單純形法的計(jì)算步驟單純形法的計(jì)算步驟 (2)(2)進(jìn)行最優(yōu)性檢驗(yàn)。進(jìn)行最優(yōu)性檢驗(yàn)。計(jì)算檢驗(yàn)數(shù)，若

35、所有計(jì)算檢驗(yàn)數(shù)，若所有 0 0 則得最優(yōu)解，結(jié)束則得最優(yōu)解，結(jié)束. .否否則轉(zhuǎn)下步則轉(zhuǎn)下步. .若某若某 0 0 而而 0 0 ，則最優(yōu)解無界，則最優(yōu)解無界，結(jié)束結(jié)束. .否則轉(zhuǎn)下步否則轉(zhuǎn)下步. .kkPj(3)(3)從一個可行解轉(zhuǎn)換到另一個目標(biāo)函數(shù)值更大的從一個可行解轉(zhuǎn)換到另一個目標(biāo)函數(shù)值更大的基可行解?；尚薪?。由最大增加原則確定進(jìn)基變量；由最小比值原則選由最大增加原則確定進(jìn)基變量；由最小比值原則選擇出基變量；以擇出基變量；以 為主元素進(jìn)行換基迭代。為主元素進(jìn)行換基迭代。lka2022-3-1755001(1)(1)找到初始可行基，建立初始單純形表找到初始可行基，建立初始單純形表. .0C

36、BCBXbZbCBmccc21mxxx21mbbb21mcc.1mxx.1nmxxj1x. m 21miijijacc1100nmccj1c. mjjjaaa211,1, 21, 1mmmmaaamnnnaaa21miininacc1mimiimacc11,10mlPPPP.21是初始基。是初始基。2022-3-1756(2)(2)進(jìn)行最優(yōu)性檢驗(yàn)進(jìn)行最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，若所有計(jì)算檢驗(yàn)數(shù)，若所有 0 0 則得最優(yōu)解，結(jié)束則得最優(yōu)解，結(jié)束. .否否則轉(zhuǎn)下步則轉(zhuǎn)下步. .若某若某 0 0 而而 0 0 ，則最優(yōu)解無界，結(jié)束，則最優(yōu)解無界，結(jié)束. .否否則轉(zhuǎn)下步則轉(zhuǎn)下步. .kkPjmiijijja

37、cc1檢驗(yàn)數(shù)的計(jì)算方法：檢驗(yàn)數(shù)的計(jì)算方法：基變量的檢驗(yàn)數(shù)一定為基變量的檢驗(yàn)數(shù)一定為0 0。判斷是否達(dá)到最優(yōu)時，。判斷是否達(dá)到最優(yōu)時，只要考慮非基變量檢驗(yàn)數(shù)。只要考慮非基變量檢驗(yàn)數(shù)。2022-3-1757(3)(3)從一個可行解轉(zhuǎn)換到另一個目標(biāo)函數(shù)值更大的從一個可行解轉(zhuǎn)換到另一個目標(biāo)函數(shù)值更大的 基可行解。基可行解。kjjjkx0max進(jìn)基變量進(jìn)基變量由最大增加原則確定進(jìn)基變量：由最大增加原則確定進(jìn)基變量：當(dāng)某些非基變量的檢驗(yàn)數(shù)當(dāng)某些非基變量的檢驗(yàn)數(shù) 時，為使目標(biāo)函時，為使目標(biāo)函數(shù)值增加地更快，一般選擇正檢驗(yàn)數(shù)中最大者對數(shù)值增加地更快，一般選擇正檢驗(yàn)數(shù)中最大者對應(yīng)的非基變量進(jìn)基應(yīng)的非基變量進(jìn)基

38、，成為新的基變量。，成為新的基變量。 0j由最小比值原則選擇出基變量；由最小比值原則選擇出基變量；為確保新的基可行解的非零分量非負(fù)，按下述規(guī)為確保新的基可行解的非零分量非負(fù)，按下述規(guī)則求得最小比值則求得最小比值 ，其所對應(yīng)的原基變量中的，其所對應(yīng)的原基變量中的 出基。出基。lx2022-3-1758lklikikiiabaab/0/min于是，新的一組基是：于是，新的一組基是：kmllPPPPPP,.1121以以 為主元素進(jìn)行換基迭代：為主元素進(jìn)行換基迭代：即利用初等行變換將進(jìn)基變量即利用初等行變換將進(jìn)基變量 所在的系數(shù)列所在的系數(shù)列變?yōu)閱挝涣邢蛄?，而變?yōu)閱挝涣邢蛄?，?變?yōu)樽優(yōu)? 1。這樣原

39、來基矩。這樣原來基矩陣中的陣中的 就不再是單位向量，取而代之的就不再是單位向量，取而代之的是是 ，這樣就找到了一組新的基。，這樣就找到了一組新的基。lkakxlkalPkP(4)(4) 重復(fù)二、三兩步，直至找到最優(yōu)解重復(fù)二、三兩步，直至找到最優(yōu)解。2022-3-1759說明：說明：若目標(biāo)函數(shù)是若目標(biāo)函數(shù)是求最小求最小，可以不必將其轉(zhuǎn)變?yōu)榍?，可以不必將其轉(zhuǎn)變?yōu)榍?最大，但在使用單純形法求解時，確定進(jìn)基變最大，但在使用單純形法求解時，確定進(jìn)基變 量，應(yīng)找量，應(yīng)找負(fù)檢驗(yàn)數(shù)中最小者負(fù)檢驗(yàn)數(shù)中最小者，并應(yīng)以并應(yīng)以檢驗(yàn)數(shù)檢驗(yàn)數(shù) 全部為正全部為正作為判別最優(yōu)的條件。作為判別最優(yōu)的條件。2022-3-1760

40、解解 將模型標(biāo)準(zhǔn)化將模型標(biāo)準(zhǔn)化2132maxxxZ例例1 1 求解下面的線性規(guī)劃問題求解下面的線性規(guī)劃問題2132maxxxZ0,1551641222.212121xxxxxxts0,1551641222.544215241321xxxxxxxxxxxxts230000122210012/201640010-0150500115/5230001xjcbBcj5x4x3xBx2x3x4x5x檢驗(yàn)數(shù)最大檢驗(yàn)數(shù)最大比值最小比值最小miijijjacc1lklikikiiabaab/0/min列單純形表，進(jìn)行迭代計(jì)算列單純形表，進(jìn)行迭代計(jì)算612022-3-1723000062010-2/56/201

41、64001016/43301001/52000-3/51xjcbBcj2x4x3xBx2x3x4x5x檢驗(yàn)數(shù)最大檢驗(yàn)數(shù)最大比值最小比值最小miijijjacc1lklikikiiabaab/0/min622022-3-172300023101/20-1/50400-214/53301001/500-10-1/51xjcbBcj2x4x1xBx2x3x4x5x0,4,0,3,354321xxxxx15maxZZ所有檢驗(yàn)數(shù)均已非正，已得到最優(yōu)解，最優(yōu)解即為所有檢驗(yàn)數(shù)均已非正，已得到最優(yōu)解，最優(yōu)解即為632022-3-172022-3-1764解解 將模型標(biāo)準(zhǔn)化將模型標(biāo)準(zhǔn)化2153maxxxZ0,3

42、6431228.212121xxxxxxts例例2 2 求解下面的線性規(guī)劃問題求解下面的線性規(guī)劃問題2153maxxxZ0,36431228.543215214231xxxxxxxxxxxxts350000810100-0120201012/20363400136/4350001xjcbBcj5x4x3xBx2x3x4x5x檢驗(yàn)數(shù)最大檢驗(yàn)數(shù)最大比值最小比值最小miijijjacc1lklikikiiabaab/0/min列單純形表，進(jìn)行迭代計(jì)算列單純形表，進(jìn)行迭代計(jì)算652022-3-173500008101008/1560101/20-012300-2112/3300-5/201xjcbBc

43、j5x2x3xBx2x3x4x5x檢驗(yàn)數(shù)最大檢驗(yàn)數(shù)最大比值最小比值最小miijijjacc1lklikikiiabaab/0/min列單純形表，進(jìn)行迭代計(jì)算列單純形表，進(jìn)行迭代計(jì)算662022-3-1735000040012/3-1/3560101/2034100-2/31/3000-1/2-11xjcbBcj1x2x3xBx2x3x4x5x列單純形表，進(jìn)行迭代計(jì)算列單純形表，進(jìn)行迭代計(jì)算672022-3-1742,0 , 0 , 4 , 6 , 4Zx）（所有檢驗(yàn)數(shù)均已非正，已得到最優(yōu)解，最優(yōu)解即為所有檢驗(yàn)數(shù)均已非正，已得到最優(yōu)解，最優(yōu)解即為2022-3-1768特殊情況：特殊情況：（1 1

44、）出現(xiàn)兩個或兩個以上相同的最大）出現(xiàn)兩個或兩個以上相同的最大 ，此，此時可任選一個時可任選一個 所對應(yīng)的變量作為進(jìn)基變量。所對應(yīng)的變量作為進(jìn)基變量。 （2 2）利用）利用 規(guī)則決定出基變量時，出現(xiàn)兩個或規(guī)則決定出基變量時，出現(xiàn)兩個或兩個以上的最小比值兩個以上的最小比值 ，則迭代后，會出現(xiàn)一，則迭代后，會出現(xiàn)一個或幾個基變量等于零的情況，我們稱此為退個或幾個基變量等于零的情況，我們稱此為退化現(xiàn)象。進(jìn)而可能會出現(xiàn)迭代過程的循環(huán)，致化現(xiàn)象。進(jìn)而可能會出現(xiàn)迭代過程的循環(huán)，致使永遠(yuǎn)達(dá)不到最優(yōu)解。使永遠(yuǎn)達(dá)不到最優(yōu)解。出現(xiàn)退化現(xiàn)象時，可考慮采用出現(xiàn)退化現(xiàn)象時，可考慮采用“勃蘭特勃蘭特”規(guī)則規(guī)則決定進(jìn)基變量和

45、出基變量的選擇。決定進(jìn)基變量和出基變量的選擇。jj2022-3-17695.1 5.1 人工變量人工變量 n用單純形法解題時，需要有一個單位陣作為初始基。用單純形法解題時，需要有一個單位陣作為初始基。n當(dāng)約束條件都是當(dāng)約束條件都是“”“”時，加入松弛變量就形成了時，加入松弛變量就形成了初始基。初始基。n但實(shí)際存在但實(shí)際存在“”“”或或“”型的約束，沒有現(xiàn)成的型的約束，沒有現(xiàn)成的單位矩陣。單位矩陣。n采用人造基的辦法：添加采用人造基的辦法：添加5 5 單純形法的進(jìn)一步討論單純形法的進(jìn)一步討論 2022-3-1770人工單位矩陣的構(gòu)造方法人工單位矩陣的構(gòu)造方法 （1 1）在）在“ ”“ ”的不等式

46、約束中減去一個剩余變量的不等式約束中減去一個剩余變量后可變?yōu)榈仁郊s束，但此剩余變量的系數(shù)是后可變?yōu)榈仁郊s束，但此剩余變量的系數(shù)是 -1-1，所以再加入一個人工變量，其系數(shù)是所以再加入一個人工變量，其系數(shù)是 +1+1，因而在，因而在系數(shù)矩陣中可得到一個相應(yīng)的單位向量，以便構(gòu)系數(shù)矩陣中可得到一個相應(yīng)的單位向量，以便構(gòu)成初始單位陣，即初始基矩陣。成初始單位陣，即初始基矩陣。（2 2）在原本就是）在原本就是“ “ = ”= ”的約束中可直接添加一個的約束中可直接添加一個人工變量，以便得到初始基矩陣。人工變量，以便得到初始基矩陣。注意：人工變量是在等式中人為加進(jìn)的，只有它等注意：人工變量是在等式中人為加

47、進(jìn)的，只有它等于于0 0時，約束條件才是它本來的意義。時，約束條件才是它本來的意義。2022-3-17715.2 5.2 大大M M法法 n沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量人工變量 。n人工變量最終必須等于人工變量最終必須等于0才能保持原問題性質(zhì)不變。才能保持原問題性質(zhì)不變。為保證人工變量為為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為（，在目標(biāo)函數(shù)中令其系數(shù)為（-M）。）。求最小值問題中，人工變量系數(shù)取求最小值問題中，人工變量系數(shù)取MnM為無限大的正數(shù)，這是一個懲罰項(xiàng)，倘若人工變?yōu)闊o限大的正數(shù)，這是一個懲罰項(xiàng)，倘若人工變量不為零，則

48、目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去。須將人工變量逐步從基變量中替換出去。n如若到最終表中人工變量仍沒有置換出去，那么這如若到最終表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當(dāng)然亦無最優(yōu)解。個問題就沒有可行解，當(dāng)然亦無最優(yōu)解。2022-3-1772例例3解線性規(guī)劃解線性規(guī)劃0,93124.3max3213232132131xxxxxxxxxxxtsxxZ解解 化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型0,93124.3max54321325321432131xxxxxxxxxxxxxxxtsxxZ此時無單位矩陣作此時無單位矩陣作為初

49、始基。為初始基。2022-3-1773添加人工變量，構(gòu)造初始基：添加人工變量，構(gòu)造初始基：0,.,93124.3max717326532143217631xxxxxxxxxxxxxxtsMxMxxxZ（求最小值問題中，人工變量系數(shù)需?。ㄇ笞钚≈祮栴}中，人工變量系數(shù)需取M M）2022-3-1774-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始單純形表：初始單純形表：jCCBXBb0 x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10 x430 x21-Mx76-3+6M01

50、+4M03M-3M02022-3-1775-30100-M-Mx1x2x3x4x5x6x7jCCBXBb00303/2-M-3/2-M+1/2-93/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60 x400 x23-3x11-3/2000-3/4-M+3/4-M-1/40 x400 x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/42022-3-1776此時人工變量全部出基，并已達(dá)最優(yōu)條件。此時人工變量全部出基，并已達(dá)最優(yōu)條件。最優(yōu)解為最優(yōu)解為)25,25, 0(X，最優(yōu)值為，最優(yōu)值為

51、25Z注意：注意：計(jì)算機(jī)上使用大計(jì)算機(jī)上使用大M M法時，需要用機(jī)器最大字法時，需要用機(jī)器最大字 長的數(shù)字代替長的數(shù)字代替M M，但當(dāng)某些系數(shù)與之較接近時，還，但當(dāng)某些系數(shù)與之較接近時，還是可能會出錯。是可能會出錯。另外一種求解帶人工變量的線性規(guī)劃問題的方法不另外一種求解帶人工變量的線性規(guī)劃問題的方法不會出現(xiàn)這種問題會出現(xiàn)這種問題-兩階段法兩階段法。2022-3-1777例解線性規(guī)劃例解線性規(guī)劃解按大解按大M M法構(gòu)造人造基，引入人工變量的輔助問法構(gòu)造人造基，引入人工變量的輔助問題如下：題如下：32123maxxxxZ0,426323.321321321xxxxxxxxxts5432123ma

52、xMxMxxxxZ0,426323.5432153214321xxxxxxxxxxxxxts3-1-2-M-M-M632-3106/3-M41-21014/13+4M-1-2-M003212/3-11/30-M20-8/32-1/3110-3-8M/31+2M-1-4M/301xjcbBcj5x4xBx2x3x4x5x列單純形表，進(jìn)行迭代計(jì)算列單純形表，進(jìn)行迭代計(jì)算782022-3-175x1xj3-1-2-M-M331-2/301/61/2-210-4/31-1/61/20-5/30-M-5/6-M-1/21xjcbBcj3x1xBx2x3x4x5x列單純形表，進(jìn)行迭代計(jì)算列單純形表，進(jìn)行迭

53、代計(jì)算792022-3-1771 ,0 , 3Zx），（所有檢驗(yàn)數(shù)均已非正，且人工變量都已出基，已得所有檢驗(yàn)數(shù)均已非正，且人工變量都已出基，已得到最優(yōu)解，最優(yōu)解即為到最優(yōu)解，最優(yōu)解即為2022-3-17805.3 5.3 兩階段法兩階段法 第一階段：第一階段：構(gòu)造目標(biāo)函數(shù)只含人工變量的線構(gòu)造目標(biāo)函數(shù)只含人工變量的線 性規(guī)劃問題，求解后判斷原線性性規(guī)劃問題，求解后判斷原線性 規(guī)劃問題是否有基本可行解，若規(guī)劃問題是否有基本可行解，若 有，則進(jìn)行第二階段有，則進(jìn)行第二階段 ；第二階段：第二階段：將第一階段的最終單純形表所對將第一階段的最終單純形表所對 應(yīng)的解，去掉人工變量，作為第應(yīng)的解，去掉人工變量

54、，作為第 二階段的初始單純形表的初始基二階段的初始單純形表的初始基 可行解，進(jìn)行單純形法的迭代。可行解，進(jìn)行單純形法的迭代。2022-3-1781 解解（1 1）化標(biāo)準(zhǔn)型、并添加人工變量得：化標(biāo)準(zhǔn)型、并添加人工變量得： 例：例：目標(biāo)函數(shù)目標(biāo)函數(shù)： 約束條件：約束條件： 0,6002125350.32min212112121xxxxxxxtsxxf0.,6002125350.32min721521741632121xxxxxxxxxxxxxtsxxf，2022-3-1782（2 2）構(gòu)造第一階段問題：）構(gòu)造第一階段問題： 說明：說明：原問題目標(biāo)函數(shù)無論是求原問題目標(biāo)函數(shù)無論是求MAXMAX還是求

55、還是求MINMIN，構(gòu)造的構(gòu)造的第一階段問題目標(biāo)函數(shù)第一階段問題目標(biāo)函數(shù)都是都是求最小求最小MINMIN。0.,6002125350.min721521741632176xxxxxxxxxxxxxtsxxz，2022-3-1783求解第一階段問題：求解第一階段問題：2022-3-1784此時所得可行解目標(biāo)函數(shù)值為此時所得可行解目標(biāo)函數(shù)值為0 0，故原規(guī)劃問題有，故原規(guī)劃問題有基可行解。轉(zhuǎn)入第二步?；尚薪狻＾D(zhuǎn)入第二步。2022-3-1785（3 3）去掉人工變量，得到第二階段的單純形表，）去掉人工變量，得到第二階段的單純形表，在此基礎(chǔ)上繼續(xù)求解。在此基礎(chǔ)上繼續(xù)求解。最優(yōu)解為：最優(yōu)解為：125,

56、100,250421xxx2022-3-17865.4 5.4 關(guān)于解的不同情況的判別關(guān)于解的不同情況的判別 1 1、無窮多最優(yōu)解、無窮多最優(yōu)解例：例：0,15 5 16 41222212121xxxxxx2133maxxxz解：將問題化解：將問題化 為標(biāo)準(zhǔn)型：為標(biāo)準(zhǔn)型： 0.,15x 5 16x 41222515241321xxxxxxx2133maxxxz2022-3-17872022-3-1788從上表中可知，已達(dá)最優(yōu)解，為從上表中可知，已達(dá)最優(yōu)解，為 ，而而 ，若將，若將 選為進(jìn)基變量迭代后，可得選為進(jìn)基變量迭代后，可得另一最優(yōu)解另一最優(yōu)解 。 )5 , 0 , 0 , 2 , 4(1

57、Z044x)0 , 4 , 0 , 3 , 3(2Z上述兩最優(yōu)解分別對應(yīng)兩個頂點(diǎn)，而兩點(diǎn)連線上上述兩最優(yōu)解分別對應(yīng)兩個頂點(diǎn)，而兩點(diǎn)連線上的點(diǎn)均是最優(yōu)解，故有無窮多最優(yōu)解。的點(diǎn)均是最優(yōu)解，故有無窮多最優(yōu)解。 判別無窮多最優(yōu)解的方法：判別無窮多最優(yōu)解的方法：單純形表的檢驗(yàn)數(shù)行已單純形表的檢驗(yàn)數(shù)行已達(dá)最有性條件（全部小于或等于零），且有一個非達(dá)最有性條件（全部小于或等于零），且有一個非基變量的檢驗(yàn)數(shù)為零，此時有無窮多最優(yōu)解。基變量的檢驗(yàn)數(shù)為零，此時有無窮多最優(yōu)解。 2022-3-1789 . 0,40,30,1501033020max212112121xxxxxxxxxz2 2、無可行解、無可行解

58、例例 用單純形表求解下列線性規(guī)劃問題用單純形表求解下列線性規(guī)劃問題121121121231121231max2030310150,30,40, ,0.zxxMaxxsxsxxsax x s s s a目標(biāo)函數(shù)約束條件解解 化為標(biāo)準(zhǔn)型：化為標(biāo)準(zhǔn)型：2022-3-1790單純形表求解線性規(guī)劃問題單純形表求解線性規(guī)劃問題2022-3-1791所有檢驗(yàn)數(shù)均為非正，但單純形法的最終表里所有檢驗(yàn)數(shù)均為非正，但單純形法的最終表里有人工有人工變量大于零變量大于零，則此線性規(guī)劃，則此線性規(guī)劃無可行解。無可行解。2022-3-1792 NoImage3 3、無界解、無界解例例 用單純形表求解下面線性規(guī)劃問題。用單

59、純形表求解下面線性規(guī)劃問題。12121212max1,326,0.zxxxxxxxx目 標(biāo) 函 數(shù)約 束 條 件121211221212max1,326,0.zxxxxsxxsx x s s目標(biāo)函數(shù)約束條件解解2022-3-1793單純形表求解線性規(guī)劃問題單純形表求解線性規(guī)劃問題此時此時 的檢驗(yàn)數(shù)仍為正，但系數(shù)列全為負(fù)，的檢驗(yàn)數(shù)仍為正，但系數(shù)列全為負(fù)，此時可判斷這個線性規(guī)劃問題是無界的，即目此時可判斷這個線性規(guī)劃問題是無界的，即目標(biāo)函數(shù)值可以取得無限大。標(biāo)函數(shù)值可以取得無限大。2x2022-3-1794練習(xí)：用大練習(xí)：用大M M法求解下列線性規(guī)劃問題法求解下列線性規(guī)劃問題0,162842042

60、4224.232132121321321xxxxxxxxxxxtsxxxZMax1 1、2022-3-1795解解1 1：將模型化為標(biāo)準(zhǔn)型得：將模型化為標(biāo)準(zhǔn)型得：0,1628420424224.276543217321621543215321xxxxxxxxxxxxxxxxxxxtsMxxxxZMax建立單純形表并計(jì)算如下建立單純形表并計(jì)算如下2022-3-1796顯然，檢驗(yàn)數(shù)已全部非正，已達(dá)最優(yōu)解，但非基變顯然，檢驗(yàn)數(shù)已全部非正，已達(dá)最優(yōu)解，但非基變量量X X2 2的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為0 0，故知此問題有無窮多最優(yōu)解。，故知此問題有無窮多最優(yōu)解。2022-3-1797練習(xí)：用大練習(xí)：用大M