資源描述：
《單純形法-人工變量法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、人工變量的引入及其解法當(dāng)約束條件為“?”型，引入剩余變量和人工變量由于所添加的剩余變量的技術(shù)系數(shù)為?1，不能作為初始可行基變量，為此引入一個人為的變量（注意，此時約束條件已為“=”型），以便取得初始基變量，故稱為人工變量由于人工變量在原問題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對應(yīng)的價值系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定兩種方法大M法二階段法其中第2、3個約束方程中無明顯基變量，分別加上人工變量x6,x7,約束方程為“>=”或“=”的情形（加人工變量）這時，初始基和初始基可行解很明
2、顯。X(0)=(0，0，0，11，0，3，1)T不滿足原來的約束條件。如何使得可從X(0)開始，經(jīng)迭代逐步得到x6=0，x7=0的基可行解，從而求得問題的最優(yōu)解，有兩種方法：反之，若加了人工變量的問題解后最優(yōu)解中仍含人工變量為基變量，便說明原問題無可行解。例的單純形表格為：只要原問題有可行解，隨著目標(biāo)函數(shù)向最大化方向的改善，人工變量一定會逐步換出基，從而得到原問題的基可行解，進而得到基最優(yōu)解。大M法在目標(biāo)函數(shù)中加上懲罰項。max=3x1-x2-x3-Mx6-Mx7其中M為充分大的正數(shù)。3-6MM-13M-10-M000x4
3、103-20100-1-Mx610[1]00-11-21-1x31-20100011-1+M00-M0-3M+10x412[3]001-2-1x210100-14-1x31-201001000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3-2000-1/3-1/3X*=(4，1，9，0，0)T,z*=2113/21〔〕兩階段法第一階段：以人工變量之和最小化為目標(biāo)函數(shù)。min?=x6+x7第二階段：以第一階段的最優(yōu)解(不含人工變量)為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。約束方程為“>=”或“
4、=”的情形（加人工變量）人工變量法（確定初始可行基）：原約束方程：AX=b加入人工變量：xn+1，?，xn+m人工變量是虛擬變量，加入原方程中是作為臨時基變量，經(jīng)過基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗數(shù)小于零，而且基變量中還有某個非零的人工變量，原問題無可行解。MaxZ=2x1+x2+x3s.t.4x1+2x2+2x3≥42x1+4x2≤204x1+8x2+2x3≤16x1，x2，x3≥0用兩階段法求下面線性規(guī)劃問題的解線性規(guī)劃問題解的討論一、無可行解maxz=2x1+4x2x1+x2
5、?102x1+x2?40x1,x2?0人工變量不能從基底換出，此時原線性規(guī)劃問題無可行解。x1x2?CBXBbX3x50-10000-1x1x2x3x4x540210-1110[1]1100cj?1040/2x1x50-1200-1-2-111011100cj-zj0-1-2-10cj-zj210-10Z0=-40Z1=-20兩階段法例:maxz=3x1+4x2x1+x2?402x1+x2?60x1-x2=0x1,x2?0此題初始解是退化的。最優(yōu)解也是退化解。退化解迭代中，當(dāng)換入變量取零值時目標(biāo)函數(shù)值沒有改進，x1x20x
6、340111000x4602101-1-Mx50[1]-10010x3400[2]100x46003013x101-1003+M4-M000zj-cj000-7/3zj-cj0x30001-1/34x2200101/33x1201001/3cj→3400-MCBXBbx5θx1x2x3x40700zj-cj00-3.50zj-cj4x220011/200x4000-3/213x120101/20例maxz=3x1+5x23x1+5x2?152x1+x2?52x1+2x2?11x1,x2?0如果將x1換入基底，得另一解，由可
7、行域凸性易知，有兩個最優(yōu)解必有無窮多組最優(yōu)解當(dāng)非基底變量的檢驗數(shù)中有取零值，或檢驗數(shù)中零的個數(shù)大于基變量個數(shù)時，有無窮多解。?CBXBbx3x4x500035000x1x2x3x4x5521010153[5]1003511/2x2x4x550033/511/50027/50-1/51054/50-2/501cj-zj00-100cj-zj35000Z0=01122001Z1=15x1x2四、無（有）界解maxz=x1+x2-2x1+x2?4x1-x2?2-3x1+x2?3x1,x2?0若檢驗數(shù)有大于0，而對應(yīng)系數(shù)列中元素全
8、部小于或等于零（無換出變量）則原問題有無界解。練習(xí)：寫出單純形表,分析檢驗數(shù)與系數(shù)關(guān)系并畫圖驗證。線性規(guī)劃解除有唯一最優(yōu)解的情況外，還有如下幾種情況無可行解退化無窮多解無界解人工變量不能從基底中換出基可行解中非零元素個數(shù)小于基變量數(shù)檢驗數(shù)中零的個數(shù)多于基變量的個數(shù)檢驗數(shù)大于零，但對應(yīng)列元素小于等于零，無
