1、.表格法解線性規劃問題【教學目標】知識目標： 理解用表格法解線性規劃問題的方法和步驟.能力目標：通過例子詳細地介紹了表格法解線性規劃問題的過程，并引入了線性規劃標準型的概念，歸納總結了表格法解線性規劃問題的步驟.【教學重點】 理解用表格法解線性規劃問題的方法和步驟 . 【教學難點】 理解用表格法解線性規劃問題的方法和步驟 . 【教學設計】1、 表格法也稱 單純形法 ，是解線性規劃問題的常用方法，使用該方法時，首先要將一般的線性規劃問題化為標準型 .在教材中給出了化標準型的方法 .講解時一定要注意 b0 以及變量的非負性 .2、表格法解線性規劃問題的過程，教材中歸納為五個步驟，這實際上是一個算法

2、，可以利用前面介紹過的算法知識來學習.3、初始表格中初始解組的確定是關鍵，一般可取松弛變量 ，但當標準型中沒有這樣的變量滿足初始解組的要求時，通常要通過添加人工變量 來解決，本教材沒有就這方面的問題進行深入討論（一般的運籌學教材中都可找到該容）.4、表格在轉換時（通常稱為轉軸） ，教材中提到用 加減消元法 來轉軸.教師可就這部分容作適當的講解.5、由于通常的表格轉換要進行多次，而表頭部分是不變的，因此可以將多表格合并起來，具體樣式可參見5.5 節表 5-16.Word 資料.【教學過程】線性規劃問題的標準形式求線性規劃問題的圖解法雖然直觀簡便，但對多于兩個變量的情況就不能適用了， 對于多于兩個

3、決策變量的線性規劃問題，可以用什么方法呢？下面介紹一種用表格的方法來求解線性規劃問題的解.表格法是根據 單純形法 而專門設計的一種計算表格.單純形法（Simple Method ）是求解線性規劃問題的主要方法， 該法由丹賽（ Dantzig ）于 1947 年提出，后經過多次改進而成，是求解線性規劃問題的實用算法 .由上節的敘述可知，如果線性規劃問題的最優解存在，則必定可以在其可行解集合的頂點（極點）中找到因此，尋求一個最優解就是在其可行域的各個極點中搜索最優點 .單純形法實質上是一個迭代過程， 該迭代即是從可行域的一個極點移到另一個近鄰的極點，直到判定某一極點為最優解為止 .為使用表格法，首

4、先介紹線性規劃問題的標準形式.一般的線性規劃問題中目標函數可能是求最大 (或最小 )值，而線性約束條件中可能是線性方程， 也可能是線性不等式， 約束條件中約束方程（或不等式）的個數也未必就比決策變量的個數少，這些問題對于線性規劃的求解，帶來極大的不便，為此，引入下述標準形式：求目標函數最大值max Z c1 x1 c2 x2 c3 x3 . cn xnn(用和式表示為 max Zc j x j )j 1Word 資料.a11 x1a12 x2.a1n xnb1a21 x1a22 x2.a2n xnb2滿足.am1 x1am2 x2.amn xnbmx1 0, x20,., xn0n用和式表示為

5、滿足aijxibi, (i1,2,3, , m)j1xj0,( j1,2,3, n)其中， 各 aij , bi , c j (i1,2,3, m; j1,2, n) 都是確定的常數，x j ( j1,2, n) 是決策變量 ，Z 是目標函數 ， aij 叫做技術系數， bi 0（ i1,2,m) 叫做資源系數 ， c j 叫做目標函數系數 .特點：1、目標函數為極大化；2、除決策變量的非負約束外， 所有的約束條件都是等式， 且右端常數均為非負；3、所有決策變量均非負如果根據實際問題建立起來的線性規劃模型不是標準型的，可以用下述方法將它化為標準型 .（1）若目標函數是 min Z c1 x1

6、c2 x2 c3 x3. cn xn可令 zz' , 將目標函數轉化為 max Z '(c1 x1 c2 x2 c3 x3 . cn xn )（2）若約束條件不等式中是 “”,可在不等式左邊加上非負變量，將不等式轉化為方程 .如 6x1 2x2 180 可轉化為 6x1 2x2 x3 180, 其中 x3 0.這里的 x3 叫做松弛變量 . 表示沒有用完的資源 .（3）若約束條件不等式是“”，可在不等式左邊減去非負變量，將Word 資料.不等式轉化為等式方程，如 2x1 2x2 10 可轉化為 2x12x2 x4 10 ，其中， x4 0.這里的 x4 叫做多余變量 ，表示不存

7、在的資源 .一般地，松弛變量和多余變量的目標函數系數為0.（4）若有一個變量 xk 沒有非負約束（叫做自由變量 ），可令 xkxlxs ，其中 xl 0， xs 0.知識鞏固例 1 將 5.1 節問題 1 中的線性規劃問題化為標準型6x12x2180約束條件求目標函數最大值4 x110x24003x15x2210x10, x20max Z31x122 x2解分別對前三個約束條件引入松弛變量x3 , x4 , x5 ，得標準型：約束條件求目標函數最大值6x12x2x31804x110x2x44003x15x2x5210x j 0, j1,2,3, 5.max Z31x1 22 x2表格法下面我們

8、通過實例來介紹表格法.首先要列出初始表格為了得到初始表格，我們分幾步來說明：先把標準型中的約束條件方程轉換成表格（表5.4）的形式如:5.1 問題 1 轉化的結果為：Word 資料.6x12x2x30x40x51804x110x20x3x40x5400列成表格為：3x15x20x30x4x5210x j0, j1,2,5.表 5.4x1x2x3x4x5bi6210041001040035001210(表格中的列數為變量個數加1，行數為方程個數加1)從約束方程中，很容易得到，當 x1 0 ，x20 時，x3 180 ，x4 400 ，x5 210 ，顯然這是一組可行解（我們把它叫作初始解組 ），

9、將其中三個取非 0 值的變量 x3 , x4 , x5 列成一列對應地加在上表的最左側，然后再在所得表的左側添加一列對應于該初始解組變量的目標函數系數，在表的上側添加一行對應于各變量的目標函數系數，得如下表：Word 資料.其中在初始解組中的變量必須滿足在對應行的約束條件方程中系數為 1，而同列其他系數為0，（如果約束條件方程中不滿足這要求，可以通過對線性約束條件方程作加減消元法而得到.）再在上表的基礎上，增加1 行(叫做檢驗數行j )和 1 列(叫做比值列 i )得下面形式：按下面的計算公式在表中依次填上檢驗數行j和比值列 i ,其中m檢驗數計算公式jc jci aij , 例如 j 31

10、，即為 x1所在列的目標函i1數系數行中的 c1值減去該列系數與第一列初始解組的目標函數系數的對應乘積和，131 (06 0403)31.選取檢驗數最大的正數所在列(記作 k 列，表中用 表示 )然后計算比值 i 比值的計算公式bi, aik 0,180.i，例如 1aik6選取最小的 i 值，記所在行為i 行(表中用 表示 )，如下表 (i 1 ）Word 資料.最后填上目標函數Z 值一格，其中目標函數Z 為第一列 C B 與 b 所在列對應乘積和得下表：表 5.7可行解比值c j3122000CBX Bx1x2x3x4x5bii0x3(6)2100300x44100104001000x53

11、500121070j31220000檢驗數目標函數 Z這樣我們得到了初始表格（表5.7）顯然，前面的初始解組并不能產生最優目標函數值，因此，必須要對初始解組中的變量進行替換，以求更好的解.通常，我們按下述方法進行變量的替換：根據上面所選的第k 列第 i 行(如上表中 x3 所在行和 x1 所在列，我們將兩者的交叉點用 ( )表示 )，對初始解組作調整，將變量xk 換入，替代第 i 行中的初始變量 (即表中換入 x1 ，換出 x3 )，根據表格法的要求，必須同時將換入變量xk 在( )中的系數通過加減消元法化為1，且同列其他系數為 0，而初始解組中其他未換出變量所在列的系數不變，通常可用加減消元

12、法來求得Word 資料.下面我們具體來說明表格的轉換框中 <A> 行除以 6 得<A / > 行；<B> 行減 <A / > ×4 得<B / > 行；<C>行減 <A / > ×3 得<C / > 行(表 5.8 轉換到表 5.9)表 5.8c j3122000CBXBx1x2x3x4x5bii0x3(6)2100<A>0x4410010400<B>0x535001210<C>表 5.9c j3122000BX Bx1x2x3x4x5biCi

13、31x11110030<A />360x40262330x50(4)1210280<B/>01120<C />再依次填上檢驗數行j 和比值列i ，得下表 (表 5.10)Word 資料.表 5.10c j3322000CBX Bx1x2x3x4x5bii31x1111003090360x402621028042033130x50(4）101120302j035310093036如果檢驗數全為非正數，那么，所得解就是最優解否則，繼續按前方法修改可行解， 直至不能繼續為止 顯然，上表中 x2 換入，變量 x5 換出轉下表 (表 5.11)表 5.11c j312

14、0002CBX Bx1x2x3x4x5bii31x1105012024120x40051132012622x2011013084j008903512802412因為所有的檢驗數j 0，故當前可行解 x120，x230，x30 ，x40 ， x50 為最優解，刪去松弛變量，即得原線性規劃最優解為x120， x230，Word 資料.最優值為Z=1280 通過上面的例子，可以歸納一般的表格法的計算步驟如下：第一步：建立初始表格第二步：檢查：若所有的j 0，則當前可行解即為最優解；否則轉入(3)第三步：檢查：若存在k>0, 且aik0，(i=1,2,m)，則無最優解；否則轉入 (4) 第四步：

15、選取檢驗數行中最大的正數所在的列，(記作 k 列，表中用表示 )然后計算比值 i，比值的計算公式 bi,aik 0 iaik選取最小的 i 值，記所在行為 i 行(表中用 表示 )，確定 x ，將kxk 換入，將松弛變量xh 換出，用加減消元法化xk 的系數 aik 為 1，且同列其他系數為 0以 xk 取代 xh 得新表，轉入 (2).鞏固知識典型例題例 2 用表格法解 5.1 節中的例 1：某工廠用鋼與橡膠生產 3 種產品 A、B、C,有關資料如表 5.3 所示 .已知每天可獲得 100 單位的鋼和 120 單位的橡膠，問每天應按排生產 A、B、C 三種產品各多少，能使總利潤最大？試寫出問

16、題的線性約束條件和目標函數.表 5.3產品單位產品鋼消耗量單位產品橡膠消耗量單位產品利潤A2340B3345Word 資料C122x13x2x3100則可得約束條件3x13x22x3120x10, x20, x3 0目標函數為 max Z40x1 45x224 x3解引入松弛變量 x4 , x5 ，得標準型：max Z40 x1 45x2 24x32x13x2x3x4100滿足3x13x22 x3x5120x j0, j1,2,3,5列初始表格 (表 5.12)表 5.12c j40452400C BX Bx1x2x3x4x50x42(3)1100x533201j40452400因為2為最大正數，轉下表 (表 5.13)表 5.13c j40452400C BX Bx1x2x3x4x545x2211103330x5(1)0111.24bii100 1