北郵運(yùn)籌學(xué)ch16 人工變量法

1、 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實(shí)際問(wèn)題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法?！纠?.15】用大M法解 下列線性規(guī)劃7/25/2022【解】首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式式中x4，x5為松弛變量，x5可作為一個(gè)基變量，第一、三約束中分別加入人工變量，x6、，x7，目標(biāo)函數(shù)中加入MR6MR7一項(xiàng)，得到人工變量單純形法數(shù)學(xué)模型再用前面介紹的單純形法求解，見(jiàn)下表。 7/25

2、/2022 Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j32M2+M1+2MM000M01x6x5x3632532001100010001381j56M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j000525/37/25/2022（1）初始表中的檢驗(yàn)數(shù)有兩種算法，第一種算法是利用第一、三約束將x6、x7的表達(dá)式代入目標(biāo)涵數(shù)消去x6和x7，得到用非基變量表達(dá)的目標(biāo)函

3、數(shù)，其系數(shù)就是檢驗(yàn)數(shù)；第二種算法是利用公式計(jì)算，如(參看第二章第一節(jié))；（2）M是一個(gè)很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個(gè)確定數(shù)值；（3）在第二張中x7已出基，故沒(méi)有計(jì)算第七列的數(shù)值，同理，第三、四張表中x6、x7都已出基，故第六、七列沒(méi)有計(jì)算；（4）第三、四張表中的基變量沒(méi)有人工變量x6、x7，因而檢驗(yàn)數(shù)中不含M；（5）可以看出，人工變量是幫助我們尋求原問(wèn)題的可行基，第三張表就找到了原問(wèn)題的一組基變量x2、x5、x3，此時(shí)人工變量就可以從模型中退出，也說(shuō)明原規(guī)劃有可行解，但不能肯定有最優(yōu)解。7/25/2022【例1.16】求解線性規(guī)劃 【解】加入松馳變量x3

4、、x4化為標(biāo)準(zhǔn)型在第二個(gè)方程中加入人工變量x5，目標(biāo)函數(shù)中加上M x5一項(xiàng)，得到 7/25/2022用單純形法計(jì)算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM07/25/2022表中j0，j=1，2，5，從而得到最優(yōu)解X=（2，0，0，0，2）， Z=10+2M。但最優(yōu)解中含有人工變量x50說(shuō)明這個(gè)解是偽最優(yōu)解，是不可行的，因此原問(wèn)題無(wú)可行解。解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗(yàn)數(shù)非零,則線 規(guī)劃具有唯一最優(yōu)解 多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解. 無(wú)界解的判斷: 某個(gè)k0且aik（i=1，2,m）則線性規(guī)劃具有無(wú)界解退化基本可行解的判斷:存在某個(gè)基變量為零的基本可行解。無(wú)可行解的判斷：當(dāng)用大M單純形法計(jì)算得到最優(yōu)解并且存