【文章內容簡介】 BB 所以 有 ?????????0011BCABCCBB BC B 1?稱為單純形乘子，若令BC BY 1?? ，則有0, ?? YCYA成立。 單純形法計算的矩陣描述 基于矩陣描述單純形法求解線性規(guī)劃問題的一般計算步驟為： （ 1 ） 根據(jù)給出的線性規(guī)劃問題，在加入松馳變量或人工變量后，得到初始基變量，求初始基矩陣 B 的逆陣 1?B 。求出初始解： ??????????????01bBXXNB （ 2 ） 計算非基變量NX的檢驗數(shù)N? ， NBCC BNN 1???? ，若0?N?已得到最優(yōu)解，停止計算，若還存在Njj ?? ,0? ，轉入下一步。 （ 3 ） 根據(jù)? ? kjjj??? ?? 0|m ax ，所對應的非基變量kX 為換入變量，計算kPB1? ，若01 ?? kPB 那問題無解，停止計算，否則進行下一步。 （ 4 ） 根據(jù) ?規(guī)則，求出：? ?11111( ) ( )m in 0( ) ( )ilkiilB b B bBPB P B Pkk??????????? ? ??????? 它對應的基變量lX 為換出變量，于是可給出一組新的基變量以及新的基矩陣1B 。 （ 5 ） 計算新的基矩陣的逆矩陣11?B ，求出bB 11? ，重復（ 2 ）至（ 5 ）。 ?人工變量法 ?人工變量法的基本思路是： 若原線性規(guī)劃問題的系數(shù)矩陣中沒有 單位向量 ，則在每個約束方程中加入一個人工變量便可在系數(shù)矩陣中形成一個單位向量。 線性規(guī)劃求解的人工變量法 對于如下線性規(guī)劃問題 m a x z =c1 x1+ c2 x2+ …+ cn xn a11 x1+ a12 x2+ …+ a1nxn = b1 a21 x1+ a22 x2+ …+ a2nxn = b2 … … am1 x1+ am2 x2+ …+ amnxn = bm x1, x2,…, xn ≥ 0 線性規(guī)劃求解的人工變量法 分別對每個約束方程中加入一個人工變量 x n + 1 … , x n + m 得到 m a x z = c 1 x 1 + c 2 x 2 + … + c n x n a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 由于單位陣可以作為基陣，因此，可選加入的人工變量為基變量。然后，再通過基變換，使得基變量中不含非零的人工變量。如果在最終單純形表中還存在 非零的人工變量 ，這表示無可行解。 大 M法 兩階段法 m a x z = c 1 x 1 + c 2 x 2 + … + c n x n a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 ?為了使加入人工變量后線性規(guī)劃問題的最優(yōu)目標函數(shù)值不受影響，我們賦予人工變量一個很大的負價值系數(shù) M (M為任意大的正數(shù) )。 線性規(guī)劃求解的大 M法 線性規(guī)劃求解的大 M法 max z = c 1 x 1 + c 2 x 2 + … + c n x n M ( x n + 1 + … + x n + m ) a 11 x 1 + a 12 x 2 + … + a 1n x n + x n + 1 = b 1 a 21 x 1 + a 22 x 2 + … + a 2n x n + x n + 2 = b 2 … … a m1 x 1 + a m2 x 2 + … + a mn x n + x n + m = b m x 1 , x 2 , … , x n , x n + 1 … , x n + m ≥ 0 ?由于人工變量對目標函數(shù)有很大的負影響，單純形法的尋優(yōu)機制會自動將人工變量趕到基外，從而找到原問題的一個可行基。 ?這種方法我們通常稱其為大 M法。 【 例 7】 用大 M法解 下列線性規(guī)劃 ???????????????????????012210243423m a x321321321321321xxxxxxxxxxxxxxxZ、線性規(guī)劃求解的大 M法舉例 【 解 】 首先將數(shù)學模型化為標準形式 ????????????????????????5,2,1,012210243423m a x32153214321321?jxxxxxxxxxxxxxxxZj式中 x4為剩余變量 ， x5為松弛變量 ， x5可作為一個基變量 ， 第一 、三約束中分別加入人工變量 xx7， 目標函數(shù)中加入 ―M x6―M x7一項 ， 得到人工變量單純形法數(shù)學模型 用前面介紹的單純形法求解，見下表。 ???????????????????????????7,2,1,012210243423m a x732153216432176321?jxxxxxxxxxxxxxxMxMxxxxZj－Cj 3 2 － 1 0 0 － M － M b CB XB x1 x2 x3 x4 x5 x6 x7 － M 0 － M x6 x5 x7 － 4 1 2 3 － 1 － 2 1 2 [1] － 1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λj 32M 2+M 1+2M↑ － M 0 0 0 － M 0 － 1 x6 x5 x3 － 6 － 3 2 [5] 3 － 2 0 0 1 － 1 0 0 0 1 0 1 0 0 3→ 8 1 λj 56M 5M↑ 0 － M 0 0 2 0 － 1 x2 x5 x3 － 6/5 [3/5] － 2/5 1 0 0 0 0 1 － 1/5 3/5 － 2/5 0 1 0 3/5 31/5→11/5 λj 5↑ 0 0 0 0 2 3 － 1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 5/3 2/3 13 31/3 19/3 λj 0 0 0 － 5 25/3 最優(yōu)解 X＝（ 31/3， 13， 19/3， 0， 0)T；最優(yōu)值 Z＝ 152/3 注意： ?M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值； 【 例 8】 1212122 2 1 2. . 2 1 4,0xxs t x xxx???????? ??12m a x 2 3z x x??線性規(guī)劃求解的兩階段法 兩階段法的基本思路是： 第一階段 ，首先不考慮原問題是否存在基可行解 ， 先求解一個目標函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標函數(shù)中其他變量的系數(shù)取零，人工變量的系數(shù)取某個正的常數(shù) ( 一般取 1) ，在保持原問題約束條件不變的情況下求這個目標函數(shù)極小化時的解。也就是，給原問題加入人工變量，構造僅含人工變量的目標函數(shù)，并要求最小化。 我們可以構造如下輔助問題 m in w = xn +1+ … + xn + m+0 x1+ … +0 xn a11 x1+ a12 x2+ … + a1 nxn+ xn +1 = b1 a21 x1+ a22 x2+ … + a2 nxn + xn +2= b2 … … am 1 x1+ am 2 x2+ … + amnxn+ xn + m = bm x1, x2, … , xn , xn +1, … , xn+ m≥ 0 ?????????線性規(guī)劃求解的兩階段法 然后用單純形法求解所構造的新模型，若得到 w=0，這時，若基變量中不含人工變量，則說明原問題存在基可行解，可進行第二步計算； 否則，原問題無可行解，應停止計算。 第二階段 ，單純形法求解原問題 第一階段計算得到的最終單純形表中除去人工變量，將目標函數(shù)行的系數(shù)，換成原問題的目標函數(shù)后，作為第二階段計算的初始表，繼續(xù)求解。 【 例 】 用兩階段單純形法求解例 【 7】 的線性規(guī)劃 。 ???????????????????????012210243423m a x321321321321321xxxxxxxxxxxxxxxZ、 【 解 】 標準型為 ????????????????????????5,2,1,012210243423m ax32153214321321?jxxxxxxxxxxxxxxxZj在第一 、 三約束方程中加入人工變量 x x7后 ， 第一階段問題為 ?????????????????????????7,