最新單純形法人工變量法

1、人工變量的引入及其解法人工變量的引入及其解法 當(dāng)約束條件為當(dāng)約束條件為“ ”型，引入剩余變量和人工變量型，引入剩余變量和人工變量 由于所添加的剩余變量的技術(shù)系數(shù)為由于所添加的剩余變量的技術(shù)系數(shù)為 1，不能作為初，不能作為初始可行基變量，為此引入一個(gè)人為的變量（注意，此始可行基變量，為此引入一個(gè)人為的變量（注意，此時(shí)約束條件已為時(shí)約束條件已為“=”型），以便取得初始基變量，故型），以便取得初始基變量，故稱為人工變量稱為人工變量 由于人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快由于人工變量在原問(wèn)題的解中是不能存在的，應(yīng)盡快被迭代出去，因此人工變量在目標(biāo)函數(shù)中對(duì)應(yīng)的價(jià)值被迭代出去，因此人工變量在目標(biāo)函

2、數(shù)中對(duì)應(yīng)的價(jià)值系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定法而定 兩種方法兩種方法 大大m法法 二階段法二階段法 標(biāo)準(zhǔn)型：標(biāo)準(zhǔn)型： max z =3 3x1- -x2- -x3 s.t. 01 23 2 411 2 513153214321x,xxxxxxxxxxx其中第其中第2、3個(gè)約束方程中無(wú)明顯基變量，分別加上人工變量個(gè)約束方程中無(wú)明顯基變量，分別加上人工變量x6, x7,約束方程為約束方程為“=”或或“=”的情形的情形（加人工變量） 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 這時(shí)，初始基和

3、初始基可行解很明顯。這時(shí)，初始基和初始基可行解很明顯。x(0)=(0，0，0，11，0，3，1)t不滿足原來(lái)的約束條件。如何使得可從不滿足原來(lái)的約束條件。如何使得可從x(0)開始，經(jīng)迭代逐步得到開始，經(jīng)迭代逐步得到x6=0，x7=0 的基可行解，的基可行解，從而求得問(wèn)題的最優(yōu)解，有兩種方法：從而求得問(wèn)題的最優(yōu)解，有兩種方法： 01 23 2411 2 71731653214321x,xxxxxxxxxxxxx 反之，若加了人工變量的問(wèn)題解后最優(yōu)解中仍含人工變量反之，若加了人工變量的問(wèn)題解后最優(yōu)解中仍含人工變量為基變量，便說(shuō)明原問(wèn)題無(wú)可行解。例的單純形表格為：為基變量，便說(shuō)明原問(wèn)題無(wú)可行解。例的

4、單純形表格為： 只要原問(wèn)題有可行解，隨著目標(biāo)函數(shù)向最大化方向的改善只要原問(wèn)題有可行解，隨著目標(biāo)函數(shù)向最大化方向的改善，人工變量一定會(huì)逐步換出基，從而得到原問(wèn)題的基可行解，人工變量一定會(huì)逐步換出基，從而得到原問(wèn)題的基可行解，進(jìn)而得到基最優(yōu)解。進(jìn)而得到基最優(yōu)解。大大m法法在目標(biāo)函數(shù)中加上懲罰項(xiàng)。在目標(biāo)函數(shù)中加上懲罰項(xiàng)。max =3 3x1- -x2- -x3- -mx6- -mx7其中其中m為充分大的正數(shù)。為充分大的正數(shù)。3- -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

5、 0 1 0 0 0 1 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 x* * = (4= (4，1 1，9 9，0 0，0)0)t t, z, z* * = 2= 2113/2 1 只要原問(wèn)題有可行解， 該最小化問(wèn)題的最優(yōu)目標(biāo)函數(shù)值就只要原問(wèn)題有可行解， 該最小化問(wèn)題的最優(yōu)目標(biāo)函數(shù)值就

6、是是 0，解得的最優(yōu)解，解得的最優(yōu)解 x6=0，x7=0，對(duì)應(yīng)原問(wèn)題一個(gè)基可行解。，對(duì)應(yīng)原問(wèn)題一個(gè)基可行解。反之若該問(wèn)題的最優(yōu)解目標(biāo)函數(shù)值大于零， 則說(shuō)明原問(wèn)題無(wú)可反之若該問(wèn)題的最優(yōu)解目標(biāo)函數(shù)值大于零， 則說(shuō)明原問(wèn)題無(wú)可行解。行解。 兩階段法兩階段法第一階段第一階段：以：以人工變量之和人工變量之和最小化為目標(biāo)函數(shù)。最小化為目標(biāo)函數(shù)。 min min = = x6+x7 第二階段第二階段：以第一階段的最優(yōu)解：以第一階段的最優(yōu)解(不含人工變量不含人工變量)為初始解，為初始解，以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。以原目標(biāo)函數(shù)為目標(biāo)函數(shù)。例例8 試用兩階段法求解線性規(guī)劃問(wèn)題試用兩階段法求解線性規(guī)劃問(wèn)題 min z

7、 =- -3 3x1+x2+x3 s.t. 01 23241123211321321x,x,xx xxxxxxx3 解：先在上述線性規(guī)劃問(wèn)題的約束方程中加入人工變量，解：先在上述線性規(guī)劃問(wèn)題的約束方程中加入人工變量，給出第一階段的數(shù)學(xué)模型為：給出第一階段的數(shù)學(xué)模型為： min min = = x6+x7 x1- -2 2x2+x3+x4 =11 - -4 4 x1+ x2+2x3 - -x5 + x6 =3 - -2 2x1 + x3 + x7 =1 x1， x7 0 第第一一階階段段的的單單純純形形表表如如下下： cj 0 0 0 0 0 0 0 1 1 cb xb b x1 x2 x3 x

8、4 x5 x6 x7 0 1 1 x4 x6 x7 11 3 1 1 - -4 - -2 2 - -2 2 1 0 1 2 1 1 0 0 0 0 - -1 1 0 0 1 0 0 0 1 11 3/2 1 6 - -1 - -3 3 0 1 1 0 0 0 0 1 0 x4 x6 x3 1 10 0 1 1 1 1 3 3 0 0 - -2 2 - -2 2 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 - -1 1 0 0 0 0 1 1 0 0 - -1 1 - -2 2 1 1 1 1 0 0 - -1 1 0 0 0 0 1 1 0 0 3 3 0 0 0 0 0

9、0 x4 x2 x3 1 12 2 1 1 1 1 3 3 0 0 - -2 2 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 - -2 2 - -1 1 0 0 2 2 1 1 0 0 - -5 5 - -2 2 0 0 4 4 0 0 0 0 0 1 1 1 第一階段求得的結(jié)果是一階段求得的結(jié)果是 = = 0, 0,最優(yōu)解是（最優(yōu)解是（0 0, ,1 1, ,1 1, ,1212, ,0 0, ,0 0, ,0 0）t t 因人工變量因人工變量 x6= x7=0，所以，所以(0,1,1,12,0)t是原線性規(guī)劃問(wèn)題的基可行解。是原線性規(guī)劃問(wèn)題的基可行解。 第二階段

10、運(yùn)算: 約束方程為約束方程為“=”或或“=”的情形的情形（加人工變量） 人工變量法（確定初始可行基）：0, 0,1111222121111111mnnnmmnnmnmnnnnnnxxxxbxxaxabxxaxabxxaxa原約束方程：ax=b加入人工變量：xn+1，xn+m人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，人工變量是虛擬變量，加入原方程中是作為臨時(shí)基變量，經(jīng)過(guò)基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得經(jīng)過(guò)基的旋轉(zhuǎn)變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中解是最優(yōu)解；若在最終表中檢驗(yàn)數(shù)小于零，而且基變量中還有某個(gè)非零的人工變量，原

11、問(wèn)題無(wú)可行解。還有某個(gè)非零的人工變量，原問(wèn)題無(wú)可行解。max z=2x1+ x 2+ x 3 s.t. 4x1+2x2+ 2x 34 2x1+4x2 20 4x1+8x2+ 2x 316 x1，x2，x 30 用兩階段法求下面線性規(guī)劃問(wèn)題的解用兩階段法求下面線性規(guī)劃問(wèn)題的解線性規(guī)劃問(wèn)題解的討論線性規(guī)劃問(wèn)題解的討論一、無(wú)可行解一、無(wú)可行解 max z=2x1+4x2 x1 +x2 10 2x1 +x2 40 x1 ,x2 0 x1x2cbxbbx3 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

12、 0 -1 -2 -1 110 1 1 1 0 0 cj-zj0 -1 -2 -1 0cj-zj2 1 0 -1 0 z0=-40z1=-20兩階段法兩階段法例例: max z=3x1+4x2 x1 +x2 40 2x1+x2 60 x1-x2 =0 x1 ,x2 0 x1x2 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

13、 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 -3/2 1 3 x1 20 1 0 1/2 0 三、三、 有無(wú)窮多最優(yōu)解的情況有無(wú)窮多最優(yōu)解的情況 最優(yōu)解中有最優(yōu)解中有非基變量的檢驗(yàn)數(shù)等于零非基變量的檢驗(yàn)數(shù)等于零的的情況。以這種非基變量作為換入變量，迭代可情況。以這種非基變量作為換入變量，迭代可求得另一基最優(yōu)解。求得另一基最優(yōu)解。 任一最優(yōu)解可表示為所有基最優(yōu)解的凸任一最

14、優(yōu)解可表示為所有基最優(yōu)解的凸組合組合。 例例 max z=3x1+5x2 3x1 +5x2 15 2x1 + x2 5 2x1+2x2 11 x1 ,x2 0。cbxbbx3 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 1 cj-zj 0 0 -1 0 0cj-zj3 5 0 0 0 z0=011 2 2 0 0 1z1=15x1x2四、無(wú)（有）界解四、無(wú)（有）界解 max z=x1+x2 -2x1+x2

15、4 x1- x2 2 -3x1+x2 3 x1 ,x2 0練習(xí)：寫出單純形表練習(xí)：寫出單純形表,分析檢驗(yàn)數(shù)分析檢驗(yàn)數(shù) 與系數(shù)關(guān)系并畫圖驗(yàn)證。與系數(shù)關(guān)系并畫圖驗(yàn)證。 線性規(guī)劃解除有線性規(guī)劃解除有唯一最優(yōu)解唯一最優(yōu)解的情況外，還的情況外，還有如下幾種情況有如下幾種情況人工人工變量變量不能不能從基從基底中底中換出換出基可行基可行解中非解中非零元素零元素個(gè)數(shù)小個(gè)數(shù)小于基變于基變量數(shù)量數(shù)檢驗(yàn)數(shù)檢驗(yàn)數(shù)中零的中零的個(gè)數(shù)多個(gè)數(shù)多于基變于基變量的個(gè)量的個(gè)數(shù)數(shù)檢驗(yàn)數(shù)大檢驗(yàn)數(shù)大于零，但于零，但對(duì)應(yīng)列元對(duì)應(yīng)列元素小于等素小于等于零，無(wú)于零，無(wú)換出變量換出變量單單純純形形法法小小結(jié)結(jié) 根根據(jù)據(jù)實(shí)實(shí)際際問(wèn)問(wèn)題題給給出出數(shù)數(shù)學(xué)學(xué)模模型型,列列出出初初始始單單純純形形表表,進(jìn)進(jìn)行行標(biāo)標(biāo)準(zhǔn)準(zhǔn)化化,見見表表 變變量量 x xj j0 0 x xj j0 0 x xj j無(wú)無(wú)約約束束 不不需需要要處處理理 令令xj=-xj; xj0 令令xj=xj-xj; ;xj, ,xj0 約約束束條條件件 b0 b 0 計(jì) 算計(jì) 算i i=bi/aik令令l=min=mini i 第第l l個(gè)基變量個(gè)基變量為換出變?yōu)閾Q出變量，量，alk為主元素為主元素 迭代運(yùn)算迭代運(yùn)算.用非基變量用非