王家榮-運(yùn)籌學(xué)(編輯修改稿)

　

【文章內(nèi)容簡(jiǎn)介】 過(guò)求基礎(chǔ)可行解的線(xiàn)性代數(shù)的方法來(lái)得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。 。這個(gè)線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式的約束條件為：x1+x2+x3=3x2+x4=1x1,x2,x3,x4≥0系數(shù)矩陣 A矩陣包含以下六個(gè)22的子矩陣： 其中 其行列式det B2=0，因而B(niǎo)2不是線(xiàn)性規(guī)劃的一個(gè)基。其余均為非奇異方陣，因此該問(wèn)題共有5個(gè)基。對(duì)于基B1=[a1，a2]，基變量為x1，x2，非基變量為x3，x4。令非基變量x3，x4等于0，求解線(xiàn)性方程組x1+x2=3x2=1得到基變量的值 x1=2，x2=1基變量全為非負(fù)，因而B(niǎo)1是可行基。 （x1，x2，x3，x4）=（2，1，0，0） 為對(duì)應(yīng)于基B1的一個(gè)基礎(chǔ)解。由于這個(gè)基礎(chǔ)解的各變量均為非負(fù)，故這是一個(gè)基礎(chǔ)可行解，因而對(duì)應(yīng)于一個(gè)極點(diǎn)。對(duì)于基B3=[a1，a4]，基變量為x1，x4，非基變量為x2，x3。令非基變量x2，x3等于0，求解線(xiàn)性方程組x1=3x4=1得到基變量的值 x1=3，x4=1基變量全為非負(fù)，因而B(niǎo)1是可行基。 （x1，x2，x3，x4）=（3，0，0，1） 為對(duì)應(yīng)于基B3的一個(gè)基礎(chǔ)解。由于這個(gè)基礎(chǔ)解的各變量均為非負(fù)，故這是一個(gè)基礎(chǔ)可行解，因而對(duì)應(yīng)于一個(gè)極點(diǎn)。對(duì)于基B4=[a2，a3]，基變量為x2，x3，非基變量為x1，x4。令非基變量x1，x4等于0，求解線(xiàn)性方程組x2+x3=3x2=1得到基變量的值 x2=1，x3=2基變量全為非負(fù)，因而B(niǎo)1是可行基。 （x1，x2，x3，x4）=（0，1，2，0） 為對(duì)應(yīng)于基B4的一個(gè)基礎(chǔ)解。由于這個(gè)基礎(chǔ)解的各變量均為非負(fù)，故這是一個(gè)基礎(chǔ)可行解，因而對(duì)應(yīng)于一個(gè)極點(diǎn)。對(duì)于基B5=[a2，a4]，基變量為x2，x4，非基變量為x1，x3。令非基變量x1，x3等于0，求解線(xiàn)性方程組x2=3x2+x4=1得到基變量的值 x2=3，x4=2基變量出現(xiàn)負(fù)數(shù)，因而B(niǎo)5不是可行基。 （x1，x2，x3，x4）=（0，3，0，2） 為對(duì)應(yīng)于基B5的一個(gè)基礎(chǔ)解，但不是基礎(chǔ)可行解，不是極點(diǎn)，而是約束直線(xiàn)的一個(gè)交點(diǎn)。對(duì)于基B6=[a3，a4]，基變量為x3，x4，非基變量為x1，x2。令非基變量x1，x2等于0，求解線(xiàn)性方程組x3=3x4=1得到基變量的值 x3=2，x4=1基變量全為非負(fù)，因而B(niǎo)1是可行基。 （x1，x2，x3，x4）=（0，0，3，1） 為對(duì)應(yīng)于基B6的一個(gè)基礎(chǔ)解。由于這個(gè)基礎(chǔ)解的各變量均為非負(fù)，故這是一個(gè)基礎(chǔ)可行解，因而對(duì)應(yīng)于一個(gè)極點(diǎn)。，只要將這四個(gè)極點(diǎn)的坐標(biāo)分別代入目標(biāo)函數(shù)，比較相應(yīng)目標(biāo)函數(shù)值的大小，就可以得到線(xiàn)性規(guī)劃的最優(yōu)解。，這就是先確定線(xiàn)性規(guī)劃問(wèn)題的基，如果是可行基，則計(jì)算相應(yīng)的基礎(chǔ)可行解以及相應(yīng)解的目標(biāo)函數(shù)值。由于基的個(gè)數(shù)是有限的（最多個(gè)），因此必定可以從有限個(gè)基礎(chǔ)可行解中找到使目標(biāo)函數(shù)為最優(yōu)（極大或極小）的解。不幸的是線(xiàn)性規(guī)劃的基的個(gè)數(shù)是隨著問(wèn)題規(guī)模的增大而很快增加，以至實(shí)際上成為不可窮盡的。舉例來(lái)說(shuō)，一個(gè)有50個(gè)變量，20個(gè)約束等式的線(xiàn)性規(guī)劃問(wèn)題。其最多可能有 個(gè)基。為了說(shuō)明計(jì)算所有基礎(chǔ)可行解的計(jì)算量有多大，我們假定計(jì)算一個(gè)基礎(chǔ)可行解（即求解一個(gè)2020的線(xiàn)性方程組！）只需要一秒鐘，那么計(jì)算以上所有的基礎(chǔ)可行解需要 年，即約150萬(wàn)年。很顯然，那怕是規(guī)模不大的問(wèn)題，也是不可能的。而下一章介紹的一種算法——單純形法，可以極為有效地解決大規(guī)模的線(xiàn)性規(guī)劃問(wèn)題。167。 單純形法原理 用消元法描述單純形法原理為了避免搜索可行域的所有極點(diǎn)，我們采用以下搜索策略（見(jiàn)示意圖）：首先找到可行域的一個(gè)極點(diǎn)A。以這個(gè)極點(diǎn)作為起點(diǎn)，檢查與這個(gè)極點(diǎn)相鄰的極點(diǎn)。判斷可行解從初始極點(diǎn)到一個(gè)相鄰的極點(diǎn)移動(dòng)，目標(biāo)函數(shù)是否減小。如果目標(biāo)函數(shù)減小，就將可行解移動(dòng)到新的極點(diǎn)B上。繼續(xù)判斷可行解從極點(diǎn)B向與它相鄰的極點(diǎn)移動(dòng)時(shí)，目標(biāo)函數(shù)是否減小。如果是，繼續(xù)移動(dòng)。依次進(jìn)行。當(dāng)可行解移動(dòng)到某一個(gè)極點(diǎn)D，發(fā)現(xiàn)從D點(diǎn)向與它相鄰的所有極點(diǎn)移動(dòng)時(shí)，目標(biāo)函數(shù)都不會(huì)減小，這個(gè)最后到達(dá)的極點(diǎn)D就是線(xiàn)性規(guī)劃的最優(yōu)解。這樣的搜索策略可以極大地減少訪(fǎng)問(wèn)極點(diǎn)的數(shù)量。這就是單純形法的基本思想。單純形法是描述可行解從可行域的一個(gè)極點(diǎn)沿著可行域的邊界移到另一個(gè)相鄰的極點(diǎn)時(shí)，目標(biāo)函數(shù)和基變量隨之變化的方法。由上一節(jié)的討論可以知道，對(duì)于線(xiàn)性規(guī)劃的一個(gè)基，當(dāng)非基變量確定以后，基變量和目標(biāo)函數(shù)的值也隨之確定。因此，可行解從一個(gè)極點(diǎn)到相鄰極點(diǎn)的移動(dòng)，以及移動(dòng)時(shí)基變量和目標(biāo)函數(shù)值的變化可以分別由基變量和目標(biāo)函數(shù)用非基變量的表達(dá)式來(lái)表示。同時(shí)，當(dāng)可行解從可行域的一個(gè)極點(diǎn)沿著可行域的邊界移動(dòng)到一個(gè)相鄰的極點(diǎn)的過(guò)程中，所有非基變量中只有一個(gè)變量的值從0開(kāi)始增加，而其他非基變量的值都保持0不變。 maxz=x1+2x2.x1+x2≤3x2≤1x1,x2≥0首先將以上問(wèn)題轉(zhuǎn)換成標(biāo)準(zhǔn)形式。將目標(biāo)函數(shù)轉(zhuǎn)換成極小化，并在約束中增加松弛變量x3，x4：minz’=x12x2.x1+x2+x3=3x2+x4=1x1,x2,x3,x4≥0第一次疊代：圖 OABCDx1x23210123x3=0x4=0x1=0x2=0步驟取初始可行基，x3，x4為基變量，x1，x2為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表出：z’=x12x2x3=3x1x2x4=1x2當(dāng)非基變量x1，x2=0時(shí)，相應(yīng)的基變量和目標(biāo)函數(shù)值為x3=3，x4=1，z’=0，得到當(dāng)前的基礎(chǔ)可行解(x1，x2，x3，x4)=(0，0，3，1)z’=0初始可行解位于極點(diǎn)O。圖中的兩個(gè)箭頭分別（定性地）表示當(dāng)前基變量x3和x4的大小。步驟選擇進(jìn)基變量。在目標(biāo)函數(shù)z’=x12x2中，非基變量x1，x2的系數(shù)都是負(fù)數(shù)，因此x1，x2進(jìn)基都可以使目標(biāo)函數(shù)z’減小，但x2的系數(shù)為2，絕對(duì)值比x1的系數(shù)1大，因此x2進(jìn)基可以使目標(biāo)函數(shù)z’減少更快。選擇x2進(jìn)基，使x2的值從0開(kāi)始增加，另一個(gè)非基變量x1=0保持不變。可行解從極點(diǎn)O向極點(diǎn)C移動(dòng)。步驟確定離基變量。在約束條件z’=x12x2x3=3x1x2x4=1x2中，由于進(jìn)基變量x2在兩個(gè)約束條件中的系數(shù)都是負(fù)數(shù)，當(dāng)x2的值從0開(kāi)始增加時(shí)，基變量x3，x4的值分別從當(dāng)前的值3和1開(kāi)始減少，當(dāng)x2增加到1時(shí)，x4首先下降為0成為非基變量。這時(shí)，新的基變量為x3，x2，新的非基變量為x1，x4，當(dāng)前的基礎(chǔ)可行解和目標(biāo)函數(shù)值為：(x1，x2，x3，x4)=(0，1，2，0)，z’=2可行解移到極點(diǎn)C。第二次疊代：圖 OABCDx1x23210123x3=0x4=0x1=0x2=0步驟將當(dāng)前的基變量x3，x2用當(dāng)前的非基變量x1，x4表示：x2+x3=3x1x2=1x4消去第一個(gè)約束中的基變量x2，得到x3=2x1+x4x2=1x4圖中的兩個(gè)箭頭分別（定性地）表示當(dāng)前的基變量x2和x3的大小。將第二個(gè)約束x2=1x4代入目標(biāo)函數(shù)z’=x12x2，得到目標(biāo)函數(shù)用當(dāng)前非基變量表示的形式：z’=x12(1x4)=2x1+2x4步驟選擇進(jìn)基變量。在目標(biāo)函數(shù)z’=2x1+2x4中，只有非基變量x1的值增加可以使目標(biāo)函數(shù)z’減少，選擇非基變量x1進(jìn)基，另一個(gè)非基變量x4=0保持不變。可行解從C向B移動(dòng)。步驟確定離基變量。從約束條件x3=2x1+x4x2=1x4可以看出，當(dāng)進(jìn)基變量x1從0開(kāi)始增加時(shí)，基變量x3的值從2開(kāi)始減少，另一個(gè)基變量x2的值不隨x1變化。當(dāng)x1=2時(shí)，基變量x3=0離基，這時(shí)新的基變量為x1，x2，新的非基變量為x3，x4。當(dāng)前的基礎(chǔ)可行解為：(x1，x2，x3，x4)=(2，1，0，0)，z’=4這個(gè)解對(duì)應(yīng)于極點(diǎn)B。圖 OABCDx1x23210123x3=0x4=0x1=0x2=0第三次疊代：步驟將基變量x1，x2和目標(biāo)函數(shù)z’分別用非基變量x3，x4表示：x1+x2=3x3x2=1x4消去第一個(gè)約束條件中的x2，得到x1=2x3+x4x2=1x4圖中的兩個(gè)箭頭分別表示當(dāng)前的基變量x1和x2的大小。將以上兩個(gè)基變量x1，x2代入目標(biāo)函數(shù)z’=x12x2，得到目標(biāo)函數(shù)用當(dāng)前非基變量表出的形式：z’=(2x3+x4)2(1x4)=4+x3+x4步驟選擇進(jìn)基變量。由于目標(biāo)函數(shù)中非基變量x3，x4的系數(shù)都是正數(shù)，因此任何一個(gè)進(jìn)基都不能使目標(biāo)函數(shù)減少，而只會(huì)使目標(biāo)函數(shù)增大。已經(jīng)達(dá)到最優(yōu)解。最優(yōu)解為：(x1，x2，x3，x4)=(2，1，0，0)，min z’=4。原問(wèn)題的最優(yōu)解為：(x1，x2)=(2，1)，max z=4。根據(jù)以上討論，（目標(biāo)函數(shù)極小化問(wèn)題）單純形法的步驟可描述如下：步驟0（初始步驟）：找到一個(gè)初始的基和相應(yīng)基礎(chǔ)可行解（極點(diǎn)），確定相應(yīng)的基變量、非基變量（全部等于0）以及目標(biāo)函數(shù)的值，并將目標(biāo)函數(shù)和基變量分別用非基變量表示。步驟根據(jù)目標(biāo)函數(shù)用非基變量表出的表達(dá)式中非基變量的系數(shù)，選擇一個(gè)非基變量，使它的值從當(dāng)前值0開(kāi)始增加時(shí)，目標(biāo)函數(shù)值隨之減少。這個(gè)選定的非基變量稱(chēng)為“進(jìn)基變量”。如果任何一個(gè)非基變量的值增加都不能使目標(biāo)函數(shù)值減少，則當(dāng)前的基礎(chǔ)可行解就是最優(yōu)解。步驟在基變量用非基變量表出的表達(dá)式中，觀(guān)察進(jìn)基變量增加時(shí)各基變量變化情況，確定基變量的值在進(jìn)基變量增加過(guò)程中首先減少到0的變量，這個(gè)基變量稱(chēng)為“離基變量”。當(dāng)進(jìn)基變量的值增加到使離基變量的值降為0時(shí)，可行解移動(dòng)到相鄰的極點(diǎn)。如果進(jìn)基變量的值增加時(shí)，所有基變量的值都不減少，則表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無(wú)限減少。步驟將進(jìn)基變量作為新的基變量，離基變量作為新的非基變量，確定新的基、新的基礎(chǔ)可行解和新的目標(biāo)函數(shù)值。返回步驟1。 用單純形法求解以下線(xiàn)性規(guī)劃問(wèn)題maxz=x1+3x2.x1+x2≤6x1+2x2≤8x1,x2≥0圖 z=0z=3z=6z=9z=12z=0 1 2 3 4 5 68 7 6 5 4 3 2 1654321x1x2這個(gè)問(wèn)題的圖解如下圖所示。標(biāo)準(zhǔn)化，得到minz’=x13x2.x1+x2+x3=6x1+2x2+x4=8x1,x2,x3,x4≥0第一次疊代步驟1：初始非基變量x1=x2=0，基變量x3=6，x4=8，初始基礎(chǔ)可行解為(x1，x2，x3，x4)=(0，0，6，8)，z’=0，對(duì)應(yīng)于極點(diǎn)O。基變量和目標(biāo)函數(shù)用非基變量表示z’=x13x2x3=6x1x2x4=8+x12x2步驟2：選擇進(jìn)基變量。x2進(jìn)基，另一個(gè)非基變量x1=0不變。步驟確定離基變量。min{，}=4，當(dāng)x2=4時(shí)，x4=0離基。新的基礎(chǔ)可行解為：(x1，x2，x3，x4)=(0，4，2，0)，z’=12，對(duì)應(yīng)于極點(diǎn)C。第二次疊代步驟1：基變量和目標(biāo)函數(shù)用非基變量表示x2+x3=6x12x2=8+x1x4將第二個(gè)約束兩邊同除以2，得到x2+x3=6x1x2=4+x1x4兩式相減，消去第一式中的基變量x2，得到x3=2x1+x4x2=4+x1x4將基變量x2=4＋x1－x4代入目標(biāo)函數(shù)z’=x13x2，消去目標(biāo)函數(shù)中的基變量x2z’=x13(4+x1x4)=12x1+x4x3=2x1+x4x2=4+x1x4步驟2：選擇進(jìn)基變量。x1進(jìn)基，另一個(gè)非基變量x4=0保持不變。步驟3：確定離基變量。min{2/，}=，當(dāng)x1=時(shí)，x3=0離基。這時(shí)新的基礎(chǔ)可行解為：(x1，x2，x3，x4)=(，0，0)，z’=，對(duì)應(yīng)于極點(diǎn)B。第三次疊代步驟1：基變量和目標(biāo)函數(shù)用非基變量表示x1+x2=6x3x1+2x2=8x4兩式相加，消去第二式中的基變量x1，得到x1+x2=6x33x2=14x3x4將第二個(gè)約束兩邊同除以3，得到x1+x2=6x3x2=x3x4兩式相減，消去第一式中的基變量x2，得到x1=x3+