單純形法-人工變量法

1、人工變量的引入及其解法 當(dāng)約束條件為“”型，引入剩余變量和人工變量由于所添加的剩余變量的技術(shù)系數(shù)為1，不能作為初始可行基變量，為此引入一個(gè)人為的變量（注意，此時(shí)約束條件已為“=”型），以便取得初始基變量，故稱(chēng)為人工變量由于人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對(duì)應(yīng)的價(jià)值系數(shù)應(yīng)具有懲罰性，稱(chēng)為罰系數(shù)。罰系數(shù)的取值視解法而定兩種方法大M法二階段法1其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變量x6, x7,約束方程為“=”或“=”的情形（加人工變量）2這時(shí)，初始基和初始基可行解很明顯。X(0)=(0，0，0，11，0，3，1)T不滿(mǎn)足原來(lái)的約束條件。

2、如何使得可從X(0)開(kāi)始，經(jīng)迭代逐步得到x6=0，x7=0 的基可行解，從而求得問(wèn)題的最優(yōu)解，有兩種方法：3 反之，若加了人工變量的問(wèn)題解后最優(yōu)解中仍含人工變量為基變量，便說(shuō)明原問(wèn)題無(wú)可行解。例的單純形表格為： 只要原問(wèn)題有可行解，隨著目標(biāo)函數(shù)向最大化方向的改善，人工變量一定會(huì)逐步換出基，從而得到原問(wèn)題的基可行解，進(jìn)而得到基最優(yōu)解。大M法在目標(biāo)函數(shù)中加上懲罰項(xiàng)。max =3x1-x2-x3-Mx6-Mx7其中M為充分大的正數(shù)。43-6M M-13M-1 0-M 0 0 0 x4 10 3 -2 0 1 0 0 -1 -M x6 1 0 1 0 0 -1 1 -2 1 -1 x3 1 -2 0

3、1 0 0 0 1 1 -1+M 0 0-M 0 -3M+1 0 x4 12 3 0 0 1 -2 -1 x2 1 0 1 0 0 -1 4 -1 x3 1 -2 0 1 0 0 1 0 0 0 -13 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 -2 0 0 0 -1/3 -1/3X* = (4，1，9，0，0)T, z* = 2113/2 1 5兩階段法第一階段：以人工變量之和最小化為目標(biāo)函數(shù)。 min = x6+x7 第二階段：以第一階段的最優(yōu)解(不含人工變量)為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。6 約束方程為

4、“=”或“=”的情形（加人工變量） 人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，xn+m人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過(guò)基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原問(wèn)題無(wú)可行解。7Max Z=2x1+ x 2+ x 3 s.t. 4x1+2x2+ 2x 34 2x1+4x2 20 4x1+8x2+ 2x 316 x1，x2，x 30 用兩階段法求下面線(xiàn)性規(guī)劃問(wèn)題的解8線(xiàn)性規(guī)劃問(wèn)題解的討論一、無(wú)可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 4

5、0 x1 ,x2 0人工變量不能從基底換出，此時(shí)原線(xiàn)性規(guī)劃問(wèn)題無(wú)可行解。x1x2CBXBbX3 x5 0-1 0 0 0 0 -1 x1 x2 x3 x4 x540 2 1 0 -1 110 1 1 1 0 0cj1040/2x1 x5 0-1 20 0 -1 -2 -1 110 1 1 1 0 0cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 Z0=-40Z1=-20兩階段法9例: max z=3x1+4x2 x1 +x2 40 2x1+x260 x1-x2 =0 x1 ,x2 0此題初始解是退化的。最優(yōu)解也是退化解。退化解迭代中，當(dāng)換入變量取零值時(shí)目標(biāo)函數(shù)值沒(méi)有改進(jìn)，x1

6、x2 0 x3 40 1 1 1 0 0 0 x4 60 2 1 0 1 -1 -M x5 0 1 -1 0 0 1 0 x3 40 0 2 1 0 0 x4 60 0 3 0 1 3 x1 0 1 -1 0 0 3+M 4-M 0 0 0 zj- cj 0 0 0 -7/3 zj- cj 0 x3 0 0 0 1 -1/3 4 x2 20 0 1 0 1/3 3 x1 20 1 0 0 1/3 cj 3 4 0 0 -M CB XB b x5 x1 x2 x3 x4 0 7 0 0 zj- cj 0 0 -3.5 0 zj- cj 4 x2 20 0 1 1/2 0 0 x4 0 0 0 -

7、3/2 1 3 x1 20 1 0 1/2 0 10 例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0如果將x1換入基底，得另一解，由可行域凸性易知，有兩個(gè)最優(yōu)解必有無(wú)窮多組最優(yōu)解當(dāng)非基底變量的檢驗(yàn)數(shù)中有取零值，或檢驗(yàn)數(shù)中零的個(gè)數(shù)大于基變量個(gè)數(shù)時(shí)，有無(wú)窮多解。CBXBbx3 x4x5 000 3 5 0 0 0 x1 x2 x3 x4 x5 5 2 1 0 1 015 3 5 1 0 035 11/2x2 x4x5 5003 3/5 1 1/5 0 02 7/5 0 -1/5 1 0 5 4/5 0 -2/5 0 1cj-zj

8、 0 0 -1 0 0cj-zj3 5 0 0 0 Z0=011 2 2 0 0 1Z1=15x1x211四、無(wú)（有）界解 max z=x1+x2 -2x1+x2 4 x1- x2 2 -3x1+x23 x1 ,x2 0若檢驗(yàn)數(shù)有大于0，而對(duì)應(yīng)系數(shù)列中元素全部小于或等于零（無(wú)換出變量）則原問(wèn)題有無(wú)界解。練習(xí)：寫(xiě)出單純形表,分析檢驗(yàn)數(shù) 與系數(shù)關(guān)系并畫(huà)圖驗(yàn)證。12 線(xiàn)性規(guī)劃解除有唯一最優(yōu)解的情況外，還有如下幾種情況 無(wú)可行解 退化 無(wú)窮多解 無(wú)界解人工變量不能從基底中換出基可行解中非零元素個(gè)數(shù)小于基變量數(shù)檢驗(yàn)數(shù)中零的個(gè)數(shù)多于基變量的個(gè)數(shù)檢驗(yàn)數(shù)大于零，但對(duì)應(yīng)列元素小于等于零，無(wú)換出變量13唯一最優(yōu)解 否 否否 是是是添加松弛變量、人工變量 列出初始單純形表計(jì)算非基變量各列的檢驗(yàn)數(shù)j所有j0基變量中有非零的人工變量某非基變量檢驗(yàn)數(shù)為零無(wú)可行解無(wú)窮多最優(yōu)解對(duì)任一j0有aik0無(wú)界解令k=maxjxk為換入變量對(duì)所有aik0計(jì)算i=bi/aik令l=mini第l個(gè)基變量為換出變量，alk為主元素 迭代運(yùn)算.用非基變量xk替換換出變量 .對(duì)主元素行(第l行