1、線性規劃線性規劃（linear programming，LP）是是協助企業決策者將有限的資源做最有效協助企業決策者將有限的資源做最有效率使用，率使用，以達到利潤極大化利潤極大化或成本極小成本極小化化目標的重要數學工具。3.1線性規劃的意義與假設一、意義一、意義線性規劃線性規劃（linear programming，LP）為一種數學工具，當企業決策者面臨有限面臨有限資源的配置問題資源的配置問題時，以線性數學模式加以描述，並尋求最佳的解決方案尋求最佳的解決方案，以達成利潤極大化利潤極大化或成本極小化成本極小化的企業目標。3.1線性規劃的意義與假設有關線性規劃的解有幾個重要名詞，說明如下：(1)可行
2、解（可行解（feasible solution）：指可以滿足所有限制式的解。(2)可行區域（可行區域（feasible region）：指所有可行解所形成的集合。(3)最佳解（最佳解（optimal solution）：指在可行區內，能使目標函數達到極大化或最小化的解。3.1線性規劃的意義與假設二、線性規劃的假設二、線性規劃的假設企業決策者在運用線性規劃時，必須注意數學模式背後所隱含的假設，分述如下：1.線性線性2.可加性可加性3.比例性比例性4.可分割性可分割性5.確定性確定性6.非負性非負性3.1線性規劃的意義與假設三、典型的線性規劃三、典型的線性規劃依據目標函數的不同，典型的線性規劃分為
3、兩大類：1.極大化問題極大化問題2.極小化問題極小化問題兩者的最重要的差異為：前者目標式為極大值目標式為極大值，限制式的不不等式方向等式方向為；後者目標式為極小後者目標式為極小值值，限制式的不等式方向不等式方向為。相同點的決策變數均需滿足均含非負限制式。3.1線性規劃的意義與假設四、求解的方法四、求解的方法線性規劃可透過圖解法圖解法、單形法單形法與電腦軟體電腦軟體三種方法求解。1.圖解法圖解法：只能適用於兩個決策變數適用於兩個決策變數的情境，此方法的優點是有助於對於線性規劃相關經濟意義的解釋。2.單形法單形法：是透過表格計算方式求解透過表格計算方式求解，可用於 3 個以上決策變數的情境，但是當
4、變數太多時，則計算較為繁複。3.電腦軟體電腦軟體：是最便利的方法最便利的方法，一旦模式的重要參數設定妥當，即可快速計算之答案。3.2圖解法 圖解法最重要的關鍵原理在於：最佳解最佳解必定出現於可行區的邊角必定出現於可行區的邊角，稱為邊角解邊角解（coner solution）。利用此性質，決策分析者只要藉由比較所有邊角解的目標值大小，即可找出目標函數的最佳解。3.2圖解法 圖解法的步驟：步驟 1：在座標平面繪製每一個限制條件的可行區。步驟 2：求解所有可行區邊界直線相交點的座標，此即所謂的邊角解。步驟 3：將各個邊角解代入目標函數，比較目標值的大小。步驟 4：若目標為求極大值時，以目標值最大的邊
5、角解為最佳解；若目標為求極小值時，以目標值最小的邊角解為最佳解。3.3單形法（一）：極大值 單形法單形法（Simplex method）是由 G.B.Dantzig 於1947 為解決線性規劃問題所發展出來的方法。單形法求解極大值之的步驟：步驟 1：先將原模式轉化為標準式。先將原模式轉化為標準式。將目標函數轉化為：Z 12X1 16X2=0 將限制式轉換為標準等式，規則如下：小於或等於（）限制式：將不等式加入差額變數（slack variable）。等式限制條件為：在等式限制式中加入人工變數（artifi cal variable）。大於或等於（）限制式：將不等式減去差額變數並加上人工變數。3
6、.3單形法（一）：極大值 步驟 2：依據目標函數與限制式標準化後，依據相關係數與常數，建立單形法的起始表起始表（注意：係數應對齊），如表3.1所示。其中表頭（其中表頭（Z、X1、X2、S1、S2）為相關）為相關變數，變數，RHS（Right-hand Side）為目標式）為目標式與限制式等號右邊常數項，中間部分為限與限制式等號右邊常數項，中間部分為限制條件中相關係數。此時表格左方的制條件中相關係數。此時表格左方的 S1 與與S2 稱為基本變數（稱為基本變數（bacic variable,BV）。）。3.3單形法（一）：極大值 步驟 3：選擇進入變數（enter variable）：選擇對利潤目
7、標貢獻最多的非基本變數利潤目標貢獻最多的非基本變數，作為進入變數以取代基本變數。進入變數所在的行進入變數所在的行稱為基準行（稱為基準行（pilot column）。）。3.3單形法（一）：極大值 步驟 4：選擇離去變數離去變數（leaving variable）。找出在基準行中係數為正值的 aij 並計算 ri 值，。比較每個 ri，並以最小的 ri 所在的列數作為基準列（基準列（pilot row）。以基）。以基準列對應的變數作為離去變數準列對應的變數作為離去變數。iiijbra3.3單形法（一）：極大值 步驟 5：決定基準元素基準元素。利用基準列與基準行的交集元素，作為基準元素。步驟 6：
8、修正單形表：將基準行化為單位向量。3.3單形法（一）：極大值 步驟 7：檢查最佳解條件檢查最佳解條件。若目標列係數均為正值或零（即不存在負的係數），表示現有的解為最佳解並計算目標值。若目標列係數仍存在負的係數，則重回步驟 37，直到上一條件成立為止。由於修正後，表3.4目標列中 X1 的係數值為 4，小於 0。所以，重回37的步驟找出基準行與基準列與基準元數，結果如下表：3.3單形法（一）：極大值 由上表可知，此時新的進入變數為 X1，離去變數為 S2。由於基準元素為 5，故：(1)將限制式第 2 列所有係數除以（5），使基準元 數化為 1。(2)將新限制式第 2 列所有係數乘上（1/2）加到
9、第 1 列係數。3.3單形法（一）：極大值(3)將新限制式的第 1 列所有係數乘上（4）加到目 標列。(4)基本變數中以 X1 取代 S2，修正後的單形表如表 3.6：3.3單形法（一）：極大值將上述過程彙整後，如表3.7：3.4單形法（二）：極小值 線性規劃求解極小值之單形法，一般又稱為大大M法法。例題：廠商追求成本極小化的要素組合問題為例。Min C=240Y1+480Y2S.T.2Y1+6Y2 124Y1+2Y2 16Y1,Y2 0(1)先將原模式目標函數乘上（1）轉化為極大值Z=C=240Y1 480Y2 移項後成為：Z+240Y 1+480Y2=03.4單形法（二）：極小值(2)由於
10、兩個限制式均含，因此，兩個限制式均同時減去差額變數同時減去差額變數，並加上人工變數加上人工變數。修正如下：2Y1+6Y2 S1+A1=124Y1+2Y2 S2+A2=16(3)由於存在人工變數，將新的目標函數將新的目標函數中人工變數的係數設定為（中人工變數的係數設定為（M），其），其中中M為無窮大的正數。為無窮大的正數。本例的目標函數再修正為：Z=240Y1 480Y2 M*A1 M*A2 移項後成為：Z+240Y1+480Y2+M*A1+M*A2=03.4單形法（二）：極小值(4)依據目標函數與限制式的係數，建立單形法起始表，如表3.8所示：3.4單形法（二）：極小值(5)將人工變數所在的行
11、向量化為單位將人工變數所在的行向量化為單位向量，亦即將目標列中的人工變數向量，亦即將目標列中的人工變數係數係數 M 化為化為 0。本例中將第1 列限制式所有係數乘上（M）加到目標列；接著，將第 2 列限制式所有係數乘上（M）加到目標列。修正完成後，如表 3.9 所示：3.4單形法（二）：極小值 本例的單形法計算表格，如表3.10所示：3.5Excel求解線性規劃問題一、啟動線性規劃功能一、啟動線性規劃功能Excel 為一般常用的商用計算軟體，它也提供了求解線性規劃的工具。當線性規劃模型包含了 3 個以上的決策變數時，圖解法便不適用，即使採用單形法求解，過程亦相當繁複。此時，可利用 Excel
12、軟體所提供的求解工具。3.5Excel求解線性規劃問題在使用 Excel 2003 求解之前，需先需先喚醒喚醒 Excel 內線性規劃的計算功能內線性規劃的計算功能。步驟如圖 3.4及圖 3.5。圖3.4Excel求解的準備動作圖3.5啟動規劃求解功能3.5Excel求解線性規劃問題二、二、Excel的求解步驟的求解步驟：開啟Excel，依據線性規劃模型中的目標函數與每個限制式的相關係數、變數以及資源限制式計算公式輸入到 Excel。：點選工具規劃求解（V）。（在Excel 2007 中可點選資料、分析、規劃求解開始參數對話。）3.5Excel求解線性規劃問題：進入參數對話方塊參數對話方塊。(
13、1)設定目標儲存格設定目標儲存格選項：設定儲存儲存目標函數的座標位置。(2)等於等於選項；點選極大值。(3)推測推測選項：取一個目標函數的初始值，如 0。(4)變數儲存格變數儲存格選項：設定決策變數儲存格的座標位置。圖3.6參數設定的對話方塊3.5Excel求解線性規劃問題：限制式限制式選項：點選新增到新增限制式 的對話：(1)儲存格參照位址儲存格參照位址：設定勞動與資本需求量加總公式的位置（一次可同時設定兩條方程式）。(2)選擇限制式的類型：選選=（可視問題 或 或選擇）。(3)限制值限制值：設定勞動與資本供給量數值的座標位址。完成後如圖 3.7 所示。(4)按確定即完成限制式設定。圖3.7
14、限制條件的對話方塊（一）3.5Excel求解線性規劃問題：設定選項。(1)完成參數設定後的對話畫面，如圖3.8所示。圖3.8限制條件的對話方塊（二）3.5Excel求解線性規劃問題(2)點選選項。(3)勾選採用線性模式採用線性模式與採用非負採用非負值值，按確定。圖3.9設定選項的對話方塊3.5Excel求解線性規劃問題：點選求解求解。圖3.10對話方塊3.5Excel求解線性規劃問題：點選保存運算結果保存運算結果 按確定。圖3.11求解結果的設定3.5Excel求解線性規劃問題步驟8：檢視結果，如圖 3.12 所示。計算結果 X1=72，X2=24，最大利潤為 1248 萬元。此結果與圖解法、
15、單形法之解相同。圖3.12線性規劃之計算結果3.6線性規劃的特殊解一、無限解一、無限解若我們將產品組合問題中的限制式不等式修改為。以圖解法說明此問題最佳解的特殊性最佳解的特殊性。首先，繪製每一個限制條件所有可行區繪製每一個限制條件所有可行區。由於代表目標函數的直線愈往右上方，目標函數的直線愈往右上方，目標值越高，而整個斜線區域均為可行目標值越高，而整個斜線區域均為可行區。區。此時，線性規劃便發生無限解的情線性規劃便發生無限解的情況。況。請參考下頁圖 3.13。3.6線性規劃的特殊解3.6線性規劃的特殊解二、退化解二、退化解 Max Z=12X1+16X2 S.T.3X1+8X2 240 6X1
16、+2X2 480 X1,X2 03X1+8X2 240 的可行區：以 3X1+8X2=240 直線方程式左方的區域表示。同理，6X1+2X2 480 可行區為 6X1+2X2=480 直線方程式左方的區域表示。X1,X2 0 為座標軸右上方的區域。此時，可行區的交集區域，如圖 3.14 斜線面積所示。3.6線性規劃的特殊解3.6線性規劃的特殊解三、多重解三、多重解Max Z=12X1+16X2S.T.3X1+4X2 3306X1+2X2 480X1,X2 03X1+4X2 330 的可行區：以 3X1+4X2=330 直線方程式左方的區域表示。同理，6X1+2X2 480 可行區為 6X1+2X2=480 直線方程式左方的區域表示。X1,X2 0 為座標軸右上方的區域。所以，解的可行區，如圖 3.15 所示。3.6線性規劃的特殊解3.6線性規劃的特殊解此時，目標函數的最佳解，除了 X1=70,X2=30 為最佳解（Z值=1320）外，位於可行區內 3X1+4X2=330線上的產量組合，如 X1=30,X2=60 亦為最佳解（Z值=1320）。因此，當目標函數與某限制條當目標函數與某限制條件斜率相等時，便會出現此種多重解件斜率相等時，便會出現此種多重解的狀況的狀況。此時，可行區邊界與目標函可行區邊界與目標函數重合線段數重合線段 上的解均為最佳解上的解均為最佳解。AB
