【正文】 解：首先將問題化為標準型 添加人工變量 x6,x7,并建立輔助線性規(guī)劃如下： 121212212max Z = x + 2 xx x 2 x x 1 x 3 x ,x 0??????????? ???1 2 31 2 425j x x x 2 x x x 1 x x 3 x 0 , j 1 , 2 , 3 , 4 , 5???????????? ???671 2 3 61 2 4 725jm inZ = x + x x x x x 2 x x x x 1 x x 3 x 0, j 1, 2, 3, 4, 5, 6, 7? ? ???? ? ??????? ???由于輔助線性規(guī)劃的目標函數(shù)是極小化，因此最優(yōu)解的判別準則應為： N N Bσ = C C N 0? 0 1 1/2 1/2 0 1/2 1/2 3/2 X2 0 1 0 。 ? 求原問題的最優(yōu)解 。 如果輔助線性規(guī)劃存在一個基本可行解 ， 使目標函數(shù)的最小值等于零 ， 則所有人工變量都已經(jīng) “ 離基 ” 。 兩階段法的步驟： ? 求解一個輔助線性規(guī)劃 。 否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解 。 以后的計算與單純形表解法相同 ， Ｍ只需認定是一個很大的正數(shù)即可 。 為此可以在目標函數(shù)中賦予人工變量一個絕對值很大的負系數(shù) Ｍ 。 以單位矩陣為初始基 ， 即可求得一個初始的基本可行解 。 如果約束方程組中包含有一個單位矩陣 I， 那么已經(jīng)得到了一個初始可行基 。 此時可以把所有人工變量剔除 ， 開始正式進入求原線性規(guī)劃最優(yōu)解的過程 。 考慮線性規(guī)劃問題： 為了在約束方程組的系數(shù)矩陣中得到一個 m階單位矩陣作為 初始可行基 ， 在每個約束方程組的左端加上一個人工變量 可得到： njjj= 1ni j j ij= 1jm a xZ = c x a x =b ,i=1, 2, ... ,m x 0, j =1 ,2 ,.. .., n???? ????n + ix ( i = 1 , 2 , m )njjj= 1ni j j n + i ij= 1jm a xZ = c x a x + x = b ,i= 1, 2, ... ,m x 0, j=1 ,2 ,.. .., n+ m???? ???? ———————————————————————— 添加了 m個人工變量以后 ， 在系數(shù)矩陣中得到一個 m階單位矩陣 ，以該單位矩陣對應的人工變量 為基變量 ， 即可得到一個初始的基本可行解 這樣的基本可行解對原線性規(guī)劃沒有意義的 。 只有當基本可行解中所有人工變量都為取零值的非基變量時 ， 該基本可行解對原線性規(guī)劃才有意義 。 因為人工變量是在約束方程已為等式的基礎上 ， 人為的加上去的一個新變量 ， 因此 加入人工變量后的約束方程組與原約束方程組是不等價的 。= x1 2x2 x1 + x2 +x3 = 2 x1 +2x2 +x4= 6 x1 , …,x 4≥0 . XB CB B1b x1 x2 x3 x4 θ x3 0 2 1 1 1 0 不考慮 x4 0 6 [1] 2 0 1 6 σ 1 2 x3 0 8 0 3 1 1 x1 1 6 1 2 0 1 σ 0 4 0 1 ∴ X*=(6,0,8,0)T Z*= 6 x3 x1 x2 0 7 12 24 0 1 0 σ 20 1 0 0 84 0 0 1 0 0 0 σ σ θ x5 x4 x3 x2 x1 B1b CB XB x3 x4 x5 0 0 0 360 200 300 9 4 3 4 5 10 1 0 0 0 1 0 0 0 1 12 0 0 0 單純形表 : 7 90 40 30 x3 x4 x2 0 0 12 30 1 0 0 50 0 0 1 240 0 1 0 0 0 0 20 100 注：單純形表中的信息 ⑴每一列的含義： B1(b A)=(B1b, B1 P1,… ， B1 Pn) ⑵ 每個表中的 B和 B1的查找： B從初表中找； B1從當前表中找，對應于初表中的 I的位置。 檢驗數(shù)的公式是什么？ PBCc ????? ?在哪里？PB ? 列中的第 jAB 1 ???例 5：用單純形法求解例 1 ??????????????0,3001032022436049..21212121xxxxxxxxts21 127 xxMa x z ??將模型化為標準型：解：增加松弛變量 , 543 xxx ?????????????????0,3001032022436049..54321521421321xxxxxxxxxxxxxxts 21 127 xxMa x z ??問題：標準模型的 A中是否含 I？ —— 松弛變量系數(shù)恰好構(gòu)成 I。變換迭代計算的由此設計了基于初等行得。 三、單純形表 單純形表是基于單純形法的步驟設計的計算格式，是單純形法的具體實現(xiàn)。計算檢驗數(shù)均非正，當問題：當模型規(guī)模較大時，計算量很大。0, 0)( 20, 24, 84,( 84, 20, 24),103544912122XbBB ????????????? ?00。, PP 向量為再計算檢驗比確定出基量為計算檢驗數(shù)確定進基向（ 3）換基、計算下一個基可行解、再檢驗，直至最優(yōu) 。 （ 1）先將模型化為標準型 ?????????????????0,3001032022436049..54321521421321xxxxxxxxxxxxxxts 21 127 xxMa x z ??(2) 確定初始基可行解、檢驗 。對應的令進基；對應的方法：令PPBPBbBP???????????????0)()()(0111????m i nm a x稱作檢驗比。 （基變換） ?????? 0bBzz可行：改善：基變換的原則 ）變換的方法：（ PPPP , ???進基 出基 進基；對應的令保證“改善”進基 P0????? ?可決定出基。 1BbX= 0???????1 m + kB P 0?m +k 0? ?證：令 ，則得新的可行解 將上式代入 因為 , 故當 λ→+∞ 時， Z→+∞ 。 為保持解的可行性，可以按最小比值原則確定換出變量： 若 B 1 2 mX =( x , x , x ) T111im + k i 1 1m + k i m + k( B b)( B b)=m in |( B P ) 0 ,1 i m =( B P ) ( B P )ll? ? ?? ????? ??m+kx 1 1 1 1B N B m + k m + kX = B b B N X X = B b B P x?m+kP m+kxm+kx則選取對應的基變量 為換出變量。 現(xiàn)在需在 中確定一個基變量為換出變量。 1N N B=C C B N?m + 1m + 21B m + 1, m + 1, nnxxZ C B b+ ( σ σ σ )x????????????? 換入變量和換出變量的確定 ： ?換入變量的確定 — 最大增加原則 假設檢驗向量 ， 若其中有兩個以上的檢驗數(shù)為正，那么為了使目標函數(shù)值增加得快些，通常要用 “ 最大增加原則 ” ，即選取最大正檢驗數(shù)所對應的非基變量為換入變量，即若 則選取對應的 為換入變量， 由于 且為最大， 因此當 由零增至正值， 可使目標函數(shù)值 最大限度的增加。 具體做法是： ?先從檢驗數(shù)為正的非基變量中確定一個換入變量 ， 使它從非基變量變成基變量 （ 將它的值從零增至正值 ） ， ?再從原來的基變量中確定一個換出變量 ， 使它從基變量變成非基變量 （ 將它的值從正值減至零 ） 。 定理 2：無窮多最優(yōu)解判別定理 若 是一個基本可行解，所對應的檢驗向量 ，其中存在一個檢驗數(shù) σ m+k=0， 則線性規(guī)劃問題有無窮多最優(yōu)解。若 σ N的每一個檢驗數(shù)均小于等于 0，即 σ N≤0 ，那么現(xiàn)在的基本可行解就是最優(yōu)解。至少有某個檢驗數(shù) 0??? ??判斷現(xiàn)行的基本可行解是否最優(yōu) 假如已求得一個基本可行解 將這一基本可行解代入目標函數(shù)，可求得相應的目標函數(shù)值 其中 分別表示基變量和 非基變量所對應的價值系數(shù)子向量。時，當前基可行解為最，則當記 01 ??? ? ?? NBCC非最優(yōu)。,000 ????????????????? ? bbBX2. 最優(yōu)性檢驗 問題：用什么檢驗？ —— 目標。 方法： 若 A中含 I，則 B0=I； 若 A中不含 I，則可用人工變量法構(gòu) 造一個 I。 （ 3） 移至目標函數(shù)值有所改善的另一個基本可行解 ， 然后轉(zhuǎn)會到步驟 （ 2） 。 單純形法的一般步驟如下： （ 1） 尋找一個初始的基本可行解 。 二、單純形法的步驟 確定一個初始基可行解 檢驗這個基可行解是否最優(yōu) 尋找一個更好的基可行解 否 是 停止 Dantzig的單純形法把尋優(yōu)的目標集中在所有基本可行解 （ 即可行域頂點 ） 中 。 （ 2）線性規(guī)劃的最優(yōu)解（若存在的話）必能在可行 域的 角點 獲得。的基本解為相應于基 ,)3,1,0,0(XB ?,51573151525251,51525251,1221 112?????????????????????????????????????????????? ?? bBBB不是基本可行解。 稱非負的基本解為 基本可行解 （簡稱基可行解）?；兞繛槠湎鄳幕蛄繛????????????????2121212 2,1221xxXxxPPB問題：本例的 A中一共有幾個基？ （ 3）基本解與基本可行解 ? ? ? ?.0,0, ,1111?????????????????????????bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBA時，有當取即可表示為約束中的相應地）（列，則可記中的前表示取定后，不妨設中的基當