CHAPTER3線性規(guī)劃一圖解法與單形法課件

1、線性規(guī)劃（linear programming，LP）是協(xié)助企業(yè)決策者將有限的資源做最有效率使用，以達到利潤極大化或成本極小化目標的重要數(shù)學工具。線性規(guī)劃（linear programming，LP）是協(xié)助3.1線性規(guī)劃的意義與假設一、意義線性規(guī)劃（linear programming，LP）為一種數(shù)學工具，當企業(yè)決策者面臨有限資源的配置問題時，以線性數(shù)學模式加以描述，並尋求最佳的解決方案，以達成利潤極大化或成本極小化的企業(yè)目標。3.1線性規(guī)劃的意義與假設一、意義3.1線性規(guī)劃的意義與假設有關線性規(guī)劃的解有幾個重要名詞，說明如下：(1)可行解（feasible solution）：指可以滿足所

2、有限制式的解。(2)可行區(qū)域（feasible region）：指所有可行解所形成的集合。(3) 最佳解（optimal solution）：指在可行區(qū)內(nèi)，能使目標函數(shù)達到極大化或最小化的解。3.1線性規(guī)劃的意義與假設有關線性規(guī)劃的解有幾個重要名詞，3.1線性規(guī)劃的意義與假設二、線性規(guī)劃的假設企業(yè)決策者在運用線性規(guī)劃時，必須注意數(shù)學模式背後所隱含的假設，分述如下：1. 線性2. 可加性3. 比例性4. 可分割性5. 確定性6. 非負性3.1線性規(guī)劃的意義與假設二、線性規(guī)劃的假設3.1線性規(guī)劃的意義與假設三、典型的線性規(guī)劃依據(jù)目標函數(shù)的不同，典型的線性規(guī)劃分為兩大類：1. 極大化問題2.極小化問

3、題兩者的最重要的差異為：前者目標式為極大值，限制式的不等式方向為 ；後者目標式為極小值，限制式的不等式方向為。相同點的決策變數(shù)均需滿足均含非負限制式。3.1線性規(guī)劃的意義與假設三、典型的線性規(guī)劃3.1線性規(guī)劃的意義與假設四、求解的方法線性規(guī)劃可透過圖解法、單形法與電腦軟體三種方法求解。1. 圖解法：只能適用於兩個決策變數(shù)的情境，此方法的優(yōu)點是有助於對於線性規(guī)劃相關經(jīng)濟意義的解釋。2. 單形法：是透過表格計算方式求解，可用於 3 個以上決策變數(shù)的情境，但是當變數(shù)太多時，則計算較為繁複。3. 電腦軟體：是最便利的方法，一旦模式的重要參數(shù)設定妥當，即可快速計算之答案。3.1線性規(guī)劃的意義與假設四、求

4、解的方法3.2圖解法圖解法最重要的關鍵原理在於：最佳解必定出現(xiàn)於可行區(qū)的邊角，稱為邊角解（coner solution）。利用此性質(zhì)，決策分析者只要藉由比較所有邊角解的目標值大小，即可找出目標函數(shù)的最佳解。3.2圖解法圖解法最重要的關鍵原理在於：最佳解必定出現(xiàn)於可3.2圖解法圖解法的步驟：步驟 1：在座標平面繪製每一個限制條件的可行區(qū)。步驟 2：求解所有可行區(qū)邊界直線相交點的座標，此即所謂的邊角解。步驟 3：將各個邊角解代入目標函數(shù)，比較目標值的大小。步驟 4： 若目標為求極大值時，以目標值最大的邊角解為最佳解；若目標為求極小值時，以目標值最小的邊角解為最佳解。3.2圖解法圖解法的步驟：3.3

5、單形法（一）：極大值單形法（Simplex method）是由 G. B. Dantzig 於1947 為解決線性規(guī)劃問題所發(fā)展出來的方法。單形法求解極大值之的步驟：步驟 1：先將原模式轉(zhuǎn)化為標準式。將目標函數(shù)轉(zhuǎn)化為：Z 12X1 16X2 = 0將限制式轉(zhuǎn)換為標準等式，規(guī)則如下：小於或等於（）限制式：將不等式加入差額變數(shù)（slack variable）。等式限制條件為：在等式限制式中加入人工變數(shù)（artifi cal variable）。大於或等於（）限制式：將不等式減去差額變數(shù)並加上人工變數(shù)。3.3單形法（一）：極大值單形法（Simplex meth3.3單形法（一）：極大值步驟 2：依據(jù)

6、目標函數(shù)與限制式標準化後，依據(jù)相關係數(shù)與常數(shù)，建立單形法的起始表（注意：係數(shù)應對齊），如表3.1所示。其中表頭（Z、X1、X2、S1、S2）為相關變數(shù)，RHS（Right-hand Side）為目標式與限制式等號右邊常數(shù)項，中間部分為限制條件中相關係數(shù)。此時表格左方的 S1 與S2 稱為基本變數(shù)（bacic variable, BV）。3.3單形法（一）：極大值步驟 2：依據(jù)目標函數(shù)與限制式標3.3單形法（一）：極大值步驟 3：選擇進入變數(shù)（enter variable）：選擇對利潤目標貢獻最多的非基本變數(shù)，作為進入變數(shù)以取代基本變數(shù)。進入變數(shù)所在的行稱為基準行（pilot column）。3

7、.3單形法（一）：極大值步驟 3：選擇進入變數(shù)（ente3.3單形法（一）：極大值步驟 4：選擇離去變數(shù)（leaving variable）。找出在基準行中係數(shù)為正值的 aij 並計算 ri 值， 。比較每個 ri，並以最小的 ri 所在的列數(shù)作為基準列（pilot row）。以基準列對應的變數(shù)作為離去變數(shù)。3.3單形法（一）：極大值步驟 4：選擇離去變數(shù)（leav3.3單形法（一）：極大值步驟 5：決定基準元素。利用基準列與基準行的交集元素，作為基準元素。步驟 6：修正單形表：將基準行化為單位向量。3.3單形法（一）：極大值步驟 5：決定基準元素。3.3單形法（一）：極大值步驟 7：檢查最佳

8、解條件。若目標列係數(shù)均為正值或零（即不存在負的係數(shù)），表示現(xiàn)有的解為最佳解並計算目標值。若目標列係數(shù)仍存在負的係數(shù)，則重回步驟 37，直到上一條件成立為止。由於修正後，表3.4目標列中 X1 的係數(shù)值為 4，小於 0。所以，重回37的步驟找出基準行與基準列與基準元數(shù)，結果如下表：3.3單形法（一）：極大值步驟 7：檢查最佳解條件。3.3單形法（一）：極大值由上表可知，此時新的進入變數(shù)為 X1 ，離去變數(shù)為 S2。由於基準元素為 5，故：(1) 將限制式第 2 列所有係數(shù)除以（5），使基準元 數(shù)化為 1。(2) 將新限制式第 2 列所有係數(shù)乘上（1/2）加到第 1 列係數(shù)。3.3單形法（一）：極

9、大值由上表可知，此時新的進入變數(shù)為 3.3單形法（一）：極大值(3) 將新限制式的第 1 列所有係數(shù)乘上（4）加到目 標列。(4) 基本變數(shù)中以 X1 取代 S2，修正後的單形表如表 3.6：3.3單形法（一）：極大值(3) 將新限制式的第 1 列3.3單形法（一）：極大值將上述過程彙整後，如表3.7：3.3單形法（一）：極大值將上述過程彙整後，如表3.7：3.4單形法（二）：極小值線性規(guī)劃求解極小值之單形法，一般又稱為大M法。例題：廠商追求成本極小化的要素組合問題為例。Min C = 240Y1 + 480Y2S.T. 2Y1 + 6Y2 124Y1 + 2Y2 16Y1, Y2 0(1)

10、先將原模式目標函數(shù)乘上（1）轉(zhuǎn)化為極大值Z = C = 240Y1 480Y2 移項後成為：Z + 240Y 1 + 480Y2= 03.4單形法（二）：極小值線性規(guī)劃求解極小值之單形法，一般3.4單形法（二）：極小值(2) 由於兩個限制式均含，因此，兩個限制式均同時減去差額變數(shù)，並加上人工變數(shù)。修正如下：2Y1 + 6Y2 S1 + A1 =124Y1 + 2Y2 S2 + A2 =16(3) 由於存在人工變數(shù)，將新的目標函數(shù)中人工變數(shù)的係數(shù)設定為（M），其中M為無窮大的正數(shù)。本例的目標函數(shù)再修正為：Z = 240Y1 480Y2 M * A1 M * A2 移項後成為：Z + 240Y1

11、+ 480Y2 + M * A1 + M * A2 = 03.4單形法（二）：極小值(2) 由於兩個限制式均含3.4單形法（二）：極小值(4) 依據(jù)目標函數(shù)與限制式的係數(shù)，建立單形法起始表，如表3.8所示：3.4單形法（二）：極小值(4) 依據(jù)目標函數(shù)與限制式的係3.4單形法（二）：極小值(5) 將人工變數(shù)所在的行向量化為單位向量，亦即將目標列中的人工變數(shù)係數(shù) M 化為 0。本例中將第1 列限制式所有係數(shù)乘上（M）加到目標列；接著，將第 2 列限制式所有係數(shù)乘上（M）加到目標列。修正完成後，如表 3.9 所示：3.4單形法（二）：極小值(5) 將人工變數(shù)所在的行向量化3.4單形法（二）：極小值

12、本例的單形法計算表格，如表3.10所示：3.4單形法（二）：極小值本例的單形法計算表格，如表3.13.5Excel求解線性規(guī)劃問題一、啟動線性規(guī)劃功能Excel 為一般常用的商用計算軟體，它也提供了求解線性規(guī)劃的工具。當線性規(guī)劃模型包含了 3 個以上的決策變數(shù)時，圖解法便不適用，即使採用單形法求解，過程亦相當繁複。此時，可利用 Excel 軟體所提供的求解工具。3.5Excel求解線性規(guī)劃問題一、啟動線性規(guī)劃功能3.5Excel求解線性規(guī)劃問題在使用 Excel 2003 求解之前，需先喚醒 Excel 內(nèi)線性規(guī)劃的計算功能。步驟如圖 3.4及圖 3.5。圖3.4Excel求解的準備動作圖3.

13、5啟動規(guī)劃求解功能3.5Excel求解線性規(guī)劃問題在使用 Excel 23.5Excel求解線性規(guī)劃問題二、Excel的求解步驟步驟1：開啟Excel，依據(jù)線性規(guī)劃模型中的目標函數(shù)與每個限制式的相關係數(shù)、變數(shù)以及資源限制式計算公式輸入到 Excel 。步驟2：點選工具規(guī)劃求解（V）。 （在Excel 2007 中可點選資料、分析、 規(guī)劃求解開始參數(shù)對話。）3.5Excel求解線性規(guī)劃問題二、Excel的求解步驟3.5Excel求解線性規(guī)劃問題步驟3：進入?yún)?shù)對話方塊。(1) 設定目標儲存格選項：設定儲存儲存目標函數(shù)的座標位置。(2) 等於選項；點選極大值。(3) 推測選項：取一個目標函數(shù)的初始

14、值，如 0。(4) 變數(shù)儲存格選項：設定決策變數(shù)儲存格的座標位置。圖3.6參數(shù)設定的對話方塊3.5Excel求解線性規(guī)劃問題步驟3：進入?yún)?shù)對話方塊。3.5Excel求解線性規(guī)劃問題步驟4：限制式選項：點選新增到新增限制式 的對話：(1) 儲存格參照位址：設定勞動與資本需求量加總公式的位置（一次可同時設定兩條方程式）。(2) 選擇限制式的類型：選=（可視問題 或 或選擇）。(3) 限制值：設定勞動與資本供給量數(shù)值的座標位址。完成後如圖 3.7 所示。(4) 按確定即完成限制式設定。圖3.7限制條件的對話方塊（一）3.5Excel求解線性規(guī)劃問題步驟4：限制式選項：點3.5Excel求解線性規(guī)劃

15、問題步驟5：設定選項。(1) 完成參數(shù)設定後的對話畫面，如圖3.8所示。圖3.8限制條件的對話方塊（二）3.5Excel求解線性規(guī)劃問題步驟5：設定選項。圖3.83.5Excel求解線性規(guī)劃問題(2) 點選選項。(3) 勾選採用線性模式與採用非負值，按確定。圖3.9設定選項的對話方塊3.5Excel求解線性規(guī)劃問題(2) 點選選項。圖33.5Excel求解線性規(guī)劃問題步驟6：點選求解。圖3.10對話方塊3.5Excel求解線性規(guī)劃問題步驟6：點選求解。圖33.5Excel求解線性規(guī)劃問題步驟7：點選保存運算結果 按確定。圖3.11求解結果的設定3.5Excel求解線性規(guī)劃問題步驟7：點選保存運

16、算結果 3.5Excel求解線性規(guī)劃問題步驟8：檢視結果，如圖 3.12 所示。計算結果 X1 = 72，X2 = 24，最大利潤為 1248 萬元。此結果與圖解法、單形法之解相同。圖3.12線性規(guī)劃之計算結果3.5Excel求解線性規(guī)劃問題步驟8：檢視結果，如圖 33.6線性規(guī)劃的特殊解一、無限解若我們將產(chǎn)品組合問題中的限制式不等式修改為。以圖解法說明此問題最佳解的特殊性。首先，繪製每一個限制條件所有可行區(qū)。由於代表目標函數(shù)的直線愈往右上方，目標值越高，而整個斜線區(qū)域均為可行區(qū)。此時，線性規(guī)劃便發(fā)生無限解的情況。請參考下頁圖 3.13。3.6線性規(guī)劃的特殊解一、無限解3.6線性規(guī)劃的特殊解3

17、.6線性規(guī)劃的特殊解3.6線性規(guī)劃的特殊解二、退化解 Max Z = 12X1 + 16X2 S.T. 3X1 + 8X2 240 6X1 + 2X2 480 X1, X2 03X1 + 8X2 240 的可行區(qū)：以 3X1 + 8X2 = 240 直線方程式左方的區(qū)域表示。同理，6X1 + 2X2 480 可行區(qū)為 6X1 + 2X2 = 480 直線方程式左方的區(qū)域表示。 X1, X2 0 為座標軸右上方的區(qū)域。此時，可行區(qū)的交集區(qū)域，如圖 3.14 斜線面積所示。3.6線性規(guī)劃的特殊解二、退化解3.6線性規(guī)劃的特殊解3.6線性規(guī)劃的特殊解3.6線性規(guī)劃的特殊解三、多重解Max Z = 12X1 + 16X2S.T. 3X1 + 4X2 3306X1 + 2X2 480X1, X2 03X1 + 4X2 330 的可行區(qū)：以 3X1 + 4X2 = 330 直線方程式左方的區(qū)域表示。同理，6X1 + 2X2 480 可行區(qū)為 6X1 + 2X2 = 480 直線方程式左方的區(qū)域表示。X1, X2 0 為座標軸