【正文】 步驟3：確定離基變量。第二次疊代步驟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：選擇進基變量。min{，}=4，當x2=4時，x4=0離基。x2進基，另一個非基變量x1=0不變。標準化，得到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，對應于極點O。返回步驟1。如果進基變量的值增加時，所有基變量的值都不減少，則表示可行域是不封閉的，且目標函數(shù)值隨進基變量的增加可以無限減少。步驟在基變量用非基變量表出的表達式中，觀察進基變量增加時各基變量變化情況，確定基變量的值在進基變量增加過程中首先減少到0的變量，這個基變量稱為“離基變量”。這個選定的非基變量稱為“進基變量”。根據(jù)以上討論，（目標函數(shù)極小化問題）單純形法的步驟可描述如下：步驟0（初始步驟）：找到一個初始的基和相應基礎(chǔ)可行解（極點），確定相應的基變量、非基變量（全部等于0）以及目標函數(shù)的值，并將目標函數(shù)和基變量分別用非基變量表示。最優(yōu)解為：(x1，x2，x3，x4)=(2，1，0，0)，min z’=4。由于目標函數(shù)中非基變量x3，x4的系數(shù)都是正數(shù)，因此任何一個進基都不能使目標函數(shù)減少，而只會使目標函數(shù)增大。圖 OABCDx1x23210123x3=0x4=0x1=0x2=0第三次疊代：步驟將基變量x1，x2和目標函數(shù)z’分別用非基變量x3，x4表示：x1+x2=3x3x2=1x4消去第一個約束條件中的x2，得到x1=2x3+x4x2=1x4圖中的兩個箭頭分別表示當前的基變量x1和x2的大小。當x1=2時，基變量x3=0離基，這時新的基變量為x1，x2，新的非基變量為x3，x4。步驟確定離基變量。在目標函數(shù)z’=2x1+2x4中，只有非基變量x1的值增加可以使目標函數(shù)z’減少，選擇非基變量x1進基，另一個非基變量x4=0保持不變。第二次疊代：圖 OABCDx1x23210123x3=0x4=0x1=0x2=0步驟將當前的基變量x3，x2用當前的非基變量x1，x4表示：x2+x3=3x1x2=1x4消去第一個約束中的基變量x2，得到x3=2x1+x4x2=1x4圖中的兩個箭頭分別（定性地）表示當前的基變量x2和x3的大小。在約束條件z’=x12x2x3=3x1x2x4=1x2中，由于進基變量x2在兩個約束條件中的系數(shù)都是負數(shù)，當x2的值從0開始增加時，基變量x3，x4的值分別從當前的值3和1開始減少，當x2增加到1時，x4首先下降為0成為非基變量。可行解從極點O向極點C移動。在目標函數(shù)z’=x12x2中，非基變量x1，x2的系數(shù)都是負數(shù)，因此x1，x2進基都可以使目標函數(shù)z’減小，但x2的系數(shù)為2，絕對值比x1的系數(shù)1大，因此x2進基可以使目標函數(shù)z’減少更快。圖中的兩個箭頭分別（定性地）表示當前基變量x3和x4的大小。將目標函數(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為非基變量。同時，當可行解從可行域的一個極點沿著可行域的邊界移動到一個相鄰的極點的過程中，所有非基變量中只有一個變量的值從0開始增加，而其他非基變量的值都保持0不變。由上一節(jié)的討論可以知道，對于線性規(guī)劃的一個基，當非基變量確定以后，基變量和目標函數(shù)的值也隨之確定。這就是單純形法的基本思想。當可行解移動到某一個極點D，發(fā)現(xiàn)從D點向與它相鄰的所有極點移動時，目標函數(shù)都不會減小，這個最后到達的極點D就是線性規(guī)劃的最優(yōu)解。如果是，繼續(xù)移動。如果目標函數(shù)減小，就將可行解移動到新的極點B上。以這個極點作為起點，檢查與這個極點相鄰的極點。167。很顯然，那怕是規(guī)模不大的問題，也是不可能的。其最多可能有 個基。不幸的是線性規(guī)劃的基的個數(shù)是隨著問題規(guī)模的增大而很快增加，以至實際上成為不可窮盡的。，這就是先確定線性規(guī)劃問題的基，如果是可行基，則計算相應的基礎(chǔ)可行解以及相應解的目標函數(shù)值。由于這個基礎(chǔ)解的各變量均為非負，故這是一個基礎(chǔ)可行解，因而對應于一個極點。令非基變量x1，x2等于0，求解線性方程組x3=3x4=1得到基變量的值 x3=2，x4=1基變量全為非負，因而B1是可行基。 （x1，x2，x3，x4）=（0，3，0，2） 為對應于基B5的一個基礎(chǔ)解，但不是基礎(chǔ)可行解，不是極點，而是約束直線的一個交點。對于基B5=[a2，a4]，基變量為x2，x4，非基變量為x1，x3。 （x1，x2，x3，x4）=（0，1，2，0） 為對應于基B4的一個基礎(chǔ)解。對于基B4=[a2，a3]，基變量為x2，x3，非基變量為x1，x4。 （x1，x2，x3，x4）=（3，0，0，1） 為對應于基B3的一個基礎(chǔ)解。對于基B3=[a1，a4]，基變量為x1，x4，非基變量為x2，x3。 （x1，x2，x3，x4）=（2，1，0，0） 為對應于基B1的一個基礎(chǔ)解。對于基B1=[a1，a2]，基變量為x1，x2，非基變量為x3，x4。這個線性規(guī)劃問題的標準形式的約束條件為：x1+x2+x3=3x2+x4=1x1,x2,x3,x4≥0系數(shù)矩陣 A矩陣包含以下六個22的子矩陣： 其中 其行列式det B2=0，因而B2不是線性規(guī)劃的一個基。這個定理是線性規(guī)劃的基本定理，它的重要性在于把可行域的極點這一幾何概念與基礎(chǔ)可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基礎(chǔ)可行解的線性代數(shù)的方法來得到可行域的一切極點，從而有可能進一步獲得最優(yōu)極點。如果一個基對應的基礎(chǔ)解是可行解，這個基稱為可行基。這樣得到的n個變量的一個解成為基礎(chǔ)解。 線性規(guī)劃問題的基礎(chǔ)解、基礎(chǔ)可行解和可行基對于線性規(guī)劃的一個基（mm階矩陣），n個變量劃分為m個基變量、nm個非基變量。矩陣中的一個非奇異的mm子矩陣稱為線性規(guī)劃的一個基。當這n個變量的值都是非負時，這個交點就是線性規(guī)劃可行域的一個極點。在約束等式中，令X=(x1，x2，…，xn)T中nm個變量為零，如果剩下的m個變量在線性方程組中的系數(shù)矩陣是非奇異的，這m個變量有唯一解。這是由于對應的直線x2=0和x4=0平行，沒有交點的緣故。而D點對應于x1=0，x3=0，x2=3，x4=2，x4的值小于0，因而不是極點。同樣，A點對應于x2=0，x3=0，x1=3，x4=1；B點對應于x3=0，x4=0，x1=2，x2=1；C點對應于x1=0，x4=0，x2=1，x3=2。即O點對應于極點X=(x1，x2，x3，x4)T=(0，0，3，1)T。由此可見，上圖中約束直線的交點O，A，B，C和D可以由以下方法得到：在標準化的等式約束中，令其中某兩個變量為零，得到其他變量的唯一解，這個解就是相應交點的坐標，如果某一交點的坐標（x1，x2，x3，x4）全為非負，則該交點就對應于線性規(guī)劃可行域的一個極點（如點A，B，C和O）；如果某一交點的坐標中至少有一個分量為負值（如點D），則該交點不是可行域的極點。BC以上半平面中的點，滿足x40。直線AD右上側(cè)半平面上的點滿足約束條件x1+x23，即該半平面上的點，滿足x30，而直線AD上的點，相應的x3=0。0，問題變成為標準形式maxz=x1+2x2.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3x4179。maxz=x1+2x2.x1+x2≤3(1)x2≤1(2)x1,x2≥0。 線性規(guī)劃的基、基礎(chǔ)可行解由于圖解法無法解決三個變量以上的線性規(guī)劃問題，我們必須用代數(shù)方法來求得可行域的極點?？尚杏驗榭占蚨鴽]有可行解。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況。若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個極點上。對于0l1，若 X=lX1+(1l)X2則必定有X=X1=X2，則稱X為S的一個極點。S，X2206。 設(shè)S為一凸集，且X206。在n維空間中，我們稱這樣的點為極點（Extreme Point）。x1x2x2x1x1x2x1x2x1x2x1x2 (a)凸集 (b)凸集 (c)凸集 (d)非凸集 (e)非凸集 (f)非凸集，線性規(guī)劃如果有最優(yōu)解，其最優(yōu)解必定位于可行域邊界的某些點上。點X稱為點X1和X2的凸組合。1），有 X=lX1+(1l)X2206。X2，以及任意實數(shù)l（0163。S，X2206。 設(shè)S是n維空間中的一個點集。容易想象，在一般的n維空間中，n個變量，m個約束的線性規(guī)劃問題的可行域也應具備這一性質(zhì)。運用矩陣記號，n維空間中的多面體也可記為 AX≤（或≥）b每一個變量非負約束xi≥0（i=1，2，…，n）也都是半空間，其相應的超平面就是相應的坐標平面xi=0。 滿足條件 ai1x1+ai2x2+…+ainxn≤（或≥）bi的點集 X=(x1，x2，…，xn)T稱為n維空間中的一個半空間。給出了z=0，z=3，z=6，…，z=，對于目標函數(shù)極大化問題，這一組目標函數(shù)等值線沿目標函數(shù)增大而平行移動的方向（即目標函數(shù)梯度方向）就是目標函數(shù)的系數(shù)向量C=(c1,c2,…,…,)T；對于極小化問題，目標函數(shù)則沿C方向平行移動。為了在圖上表示目標函數(shù)，令z=z0為某一確定的目標函數(shù)值，取一組不同的z0值，在圖上得到一組相應的平行線，稱為目標函數(shù)等值線。我們稱滿足線性規(guī)劃問題所有約束條件（包括變量非負約束）的向量 X=(x1，x2，…，xn)T為線性規(guī)劃的可行解（Feasible Solution），稱可行解的集合為可行域（Feasible Region）。而變量x1，x2的非負約束表明滿足約束條件的點同時應位于第一象限內(nèi)。maxz=x1+3x2.x1+x2≤6(1)x1+2x2≤8(2)x1,x2≥0其中滿足約束(1)的點位于坐標平面上直線x1+x2=6靠近原點的一側(cè)。167。2+2x3x5= 6x1x39。2+x3.2x14x39。2+2x3≥ 6x1≥0x39。2+x3.2x14x39。2，x39。,x3,x4,x5≥0 變量小于等于零的問題在一些實際問題中，變量不允許為正數(shù)，這樣的問題也不是標準問題。,x239。39。x3x5=5x1+x239。3x239。39。x3.x1x239。3x239。39。其中x239。x239。當一個變量xj沒有非負約束時，可以令 xj=xj’xj”其中 xj’≥0，xj”≥0即用兩個非負變量之差來表示一個無符號限制的變量，當xj的符號取決于xj’和xj”的大小。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標準形式時，必須對各個約束引進不同的松弛變量。 極大化目標函數(shù)的問題設(shè)目標函數(shù)為 令z’＝－z，則以上極大化問題和以下極小化問題有相同的最優(yōu)解。0記向量和矩陣 ，則線性規(guī)劃問題可由向量和矩陣表示 max(min) z＝C