【正文】 2,x3,x4≥0這是一個典型的成本最小化的問題。設xij為從供應地 Ai 運往需求地 Bj 的物資數(shù)量（i=1,2；j=1,2,3），z為總運費，則總運費最小的線性規(guī)劃模型為：minz=2x11+3x12+5x13+4x21+7x22+8x23.x11+x12+x13=35(1)x21+x22+x23=25(2)x11+x21=10(3)x12+x22=30(4)x13+x23=20(5) xij≥0以上約束條件（1）、（2）稱為供應地約束，（3）、（4）、（5）稱為需求地約束。設xij（i=1, 2, 3, 4；j=1, 2, 3, 4）為第i個教師是否教第j門課，xij只能取值0或1，其意義如下：變量xij與教師 i 以及課程 j 的關系如下：表 16 i j語文數(shù)學物理化學張x11x12x13x14王x21x22x23x24李x31x32x33x34趙x41x42x43x44這個指派問題的線性規(guī)劃模型為：max z= 92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44. x11+x12+x13+x14=1 （1）x21+x22+x23+x24=1 （2）x31+x32+x33+x34=1 （3）x41+x42+x43+x44=1 （4）x11+x21+x31+x41=1 （5）x12+x22+x32+x42=1 （6）x13+x23+x33+x43=1 （7）x14+x24+x34+x44=1 （8）xij=0, 1這個問題的變量只能取值0或1，這樣的線性規(guī)劃問題成為0－1規(guī)劃。例如以下的問題就不是線性規(guī)劃問題：max z=5x1x2+2x3. 2x12+3x2163。 將以下線性規(guī)劃問題轉化為標準形式maxz=3x12x2+x3.x1+2x2x3≤5(1)4x1+3x3≥8(2)x1+x2+x3=6(3)x1,x2,x3≥0將目標函數(shù)轉換成極小化，并分別對約束（1）、（2）引進松弛變量x4，x5，得到以下標準形式的線性規(guī)劃問題minz’=3x1+2x2x3.x1+2x2x3+x4=54x1+3x3x5=8x1+x2+x3=6x1,x2,x3,x4,x5≥0 變量無符號限制的問題在標準形式中，每一個變量都有非負約束?！?得到以下等價的標準形式minz’=2x1+3x239。39。例如：minz=3x15x2+x3.2x1+4x2+x3≤15x13x2+2x3≥ 6x1≥0x2≤0x3≥0令x2=x39。2+x3+x4=15x1+3x39。這樣，以上幾個區(qū)域的交集就是滿足以上所有約束條件的點的全體。 有限個半空間的交集，即同時滿足以下條件的非空點集 a11x1+a12x2+…+a1nxn≤（或≥）b1 a21x1+a22x2+…+a2nxn≤（或≥）b2 ……… am1x1+am2x2+…+amnxn≤（或≥）bm稱為n維空間中的一個多面體。S，且X1185。在平面多邊形中，這些點就是多邊形的頂點。運用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質：若線性規(guī)劃的可行域非空，則可行域必定為一凸集。先從以下的例子來看。另外，OA上的點滿足x2=0，OD上的點滿足x1=0。同時，我們也注意到，如在等式約束中令x2=0，x4=0，由于線性方程組的系數(shù)行列式等于0，因而xx3無解。與基矩陣對應的變量稱為基變量，其余的變量稱為非基變量。 。令非基變量x2，x3等于0，求解線性方程組x1=3x4=1得到基變量的值 x1=3，x4=1基變量全為非負，因而B1是可行基。令非基變量x1，x3等于0，求解線性方程組x2=3x2+x4=1得到基變量的值 x2=3，x4=2基變量出現(xiàn)負數(shù)，因而B5不是可行基。由于基的個數(shù)是有限的（最多個），因此必定可以從有限個基礎可行解中找到使目標函數(shù)為最優(yōu)（極大或極?。┑慕狻?單純形法原理 用消元法描述單純形法原理為了避免搜索可行域的所有極點，我們采用以下搜索策略（見示意圖）：首先找到可行域的一個極點A。這樣的搜索策略可以極大地減少訪問極點的數(shù)量。將基變量和目標函數(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，x2，新的非基變量為x1，x4，當前的基礎可行解和目標函數(shù)值為：(x1，x2，x3，x4)=(0，1，2，0)，z’=2可行解移到極點C。當前的基礎可行解為：(x1，x2，x3，x4)=(2，1，0，0)，z’=4這個解對應于極點B。步驟根據(jù)目標函數(shù)用非基變量表出的表達式中非基變量的系數(shù)，選擇一個非基變量，使它的值從當前值0開始增加時，目標函數(shù)值隨之減少。 用單純形法求解以下線性規(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這個問題的圖解如下圖所示。x1進基，另一個非基變量x4=0保持不變。(x1，x2，x3，x4)=(，0，0)，min z’=原問題的解為：(x1，x2，x3，x4)=(，0，0)，max z=。這時，新的基變量為x2，x4，新的非基變量為x1，x3，當前的基礎可行解和目標函數(shù)值為：(x1，x2，x3，x4)=(0，1，0，1)，z=2對應于極點C。由于目標函數(shù)中非基變量x3系數(shù)是負數(shù)，因此選取x3為進基變量。0寫出系數(shù)矩陣表，容易看出，這就是以xx4為基的單純形表。1，X=lX1+(1l)X2都是最優(yōu)解，并且有相同的目標函數(shù)值： z=CTX=CT[lX1+(1l)X2]=lCTX1+(1l)CTX2=lz0+(1l)z0=z0 多個最優(yōu)解的問題。3x1,x2,x3179。24 x1x2x3≥0目標函數(shù)轉化為極小化，引進松弛變量，使約束條件轉變?yōu)榈仁剑簃inz’=x12x2x3 .x1+x2+x3+x3=12 2x1+3x2+x3+x4=18 x1+x2+x3+x5=24 x1x2x3x4x5x6≥0列出單純形表zx1x2x3x4x5x6RHSz11210000x401111001212/1x502[3]10101818/3x601110012424/1x2進基，x5離基z’x1x2x3x4x5x6RHSz’11/301/302/3012x401/30[2/3]11/3066/2/3x202/311/301/3066/1/3x605/302/301/311818/2/3x3進基，x4離基z’x1x2x3x4x5x6RHSz’11/2001/21/2015x301/2013/21/209x201/2101/21/203x6020010112最優(yōu)解為x1=0，x2=3，x3=9，x4=0，x5=0，x6=12，min z’=15，max z=15167。當標準形式問題的A矩陣中不含有單位矩陣或雖含有單位矩陣但b不全為非負時，無法獲得一個初始的可行基。()的基礎可行解(X, Xa)T中的X要滿足()，當且僅當()的基全部包含在A矩陣中，即Xa=0全部成為非基變量。 求解以下線性規(guī)劃問題minz=x12x2.x1+x2≥2x1+x2≥1x2≤3x1,x2≥0引進松弛變量x3，x4，x5179。D，基疊代經(jīng)過的路線如上圖所示。 退化和循環(huán) 退化的基礎可行解 設B是線性規(guī)劃的一個可行基， XB=B1b=(xB1,xB2,…,xBi,…,xBm)T是這個基礎解中的基變量。在十分特殊的情況下，退化會出現(xiàn)基的循環(huán)，一旦出現(xiàn)這樣的情況，單純形疊代將永遠停留在同一極點上，因而無法求得最優(yōu)解。OABC069312457836退化的結構對單純形疊代會有不利的影響。C，C174。這個問題求解的兩個階段前后經(jīng)歷5個基O，A，B，C，D，經(jīng)過4次基變換O174。轉第二階段。對于不能直接獲得初始可行基的問題，可以用引進人工變量（Artificial Variables）的方法構造一個人工基作為初始可行基。當用系統(tǒng)的初始可行解方法不能求得任何初始基礎可行解時，就可以得出線性規(guī)劃問題無解的結論。 用單純形表求以下線性規(guī)劃問題的最優(yōu)解。 用單純形表求以下線性規(guī)劃問題的最優(yōu)解。在最優(yōu)單純形表中，在獲得一個最優(yōu)基以及相應的最優(yōu)解后，我們還可以從非基變量xj的檢驗數(shù)zjcj中是否有等于判斷這個最優(yōu)解是否是唯一的最優(yōu)解。即()和()兩式。從約束條件x2=1+x1x3x4=1x1+x3可以看出，當進基變量x1從0開始增加時，基變量x4的值從1開始減少，另一個基變量x2的值隨x1變化而增加。在目標函數(shù)z=x12x2中，非基變量x1，x2的系數(shù)都是負數(shù)，因此x1，x2進基都可以使目標函數(shù)z減小，但x2的系數(shù)為2，絕對值比x1的系數(shù)1大，因此x2進基可以使目標函數(shù)z減少更快。第三次疊代步驟1：基變量和目標函數(shù)用非基變量表示x1+x2=6x3x1+2x2=8x4兩式相加，消去第二式中的基變量x1，得到x1+x2=6x33x2=14x3x4將第二個約束兩邊同除以3，得到x1+x2=6x3x2=x3x4兩式相減，消去第一式中的基變量x2，得到x1=x3+x4x2=x3x4將以上基變量x1，x2代入目標函數(shù)z’=x13x2，消去目標函數(shù)中的基變量x1，x2z’=(x3+x4)3180。步驟確定離基變量。當進基變量的值增加到使離基變量的值降為0時，可行解移動到相鄰的極點。已經(jīng)達到最優(yōu)解?？尚薪鈴腃向B移動。選擇x2進基，使x2的值從0開始增加，另一個非基變量x1=0保持不變。因此，可行解從一個極點到相鄰極點的移動，以及移動時基變量和目標函數(shù)值的變化可以分別由基變量和目標函數(shù)用非基變量的表達式來表示。繼續(xù)判斷可行解從極點B向與它相鄰的極點移動時，目標函數(shù)是否減小。為了說明計算所有基礎可行解的計算量有多大，我們假定計算一個基礎可行解（即求解一個2020的線性方程組?。┲恍枰幻腌?，那么計算以上所有的基礎可行解需要 年，即約150萬年。 （x1，x2，x3，x4）=（0，0，3，1） 為對應于基B6的一個基礎解。令非基變量x1，x4等于0，求解線性方程組x2+x3=3x2=1得到基變量的值 x2=1，x3=2基變量全為非負，因而B1是可行基。令非基變量x3，x4等于0，求解線性方