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