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