線性規劃 Linear Programming

Presentation on theme: "線性規劃 Linear Programming"— Presentation transcript:

1 線性規劃 Linear Programming

2 第四章 線性規劃 第一節 線性規劃的意義和模式 第二節 線性規劃問題的範例和解法 第三節 線性規劃問題的特殊解 第四節 對偶問題
第一節 線性規劃的意義和模式 第二節 線性規劃問題的範例和解法 第三節 線性規劃問題的特殊解 第四節 對偶問題 第五節 敏感性分析 第六節 線性規劃實例

3 第一節 線性規劃的意義和模式(1/6) 一、線性規劃的意義
第一節 線性規劃的意義和模式(1/6) 一、線性規劃的意義 線性規劃（ Linear Programming ）為計量管理學的重要方法之一，目的在解決如何分配有限的經濟資源，以發揮其最高效用。

4 第一節 線性規劃的意義和模式(2/6) 二、線性規劃的模式
第一節 線性規劃的意義和模式(2/6) 二、線性規劃的模式 線性規劃理論乃是一種數學工具，在各種有限資源的限制條件 ( Constraints ）下，將有關問題及數據資料以數學模式（ Mathematical Model ) 方式列出，對問題之分析與瞭解頗有助益。然後，採用計量分析（ Quantitative Analysis ）的技巧，求取最適方案（ Optimum Solution ) ，提供決策管理階層，作為決策的依據。

5 第一節 線性規劃的意義和模式(3/6) 線性規劃理論所能解決的管理問題，其中有關的未知數，應變數（ Dependent Variable ）與自變數（ Independent variables ）之間，係呈線性（ Linear ) 關係。問題中的應變數，通常表示求取某項經濟上的目標（ Objectives ) ，例如利潤（ Profits ）、成本（ Costs ）、產量（ Products ）、容量（ Capacity ）的極大值( Maximum ）或極小值（ Minimum ）。問題中的自變數乃是各種可運用經濟資源的數量，自變數又受到這些有限經濟資源的限制。

6 第一節 線性規劃的意義和模式(4/6) 根據上述特性，可以寫出線性規劃的一般“數學模式”如下：

7 第一節 線性規劃的意義和模式(5/6) 以上線性規劃的數學模式中， f (x)為應變數，而x1,x2,….xn則表示影響f(x)的自變數。所以第一式我們稱之為線性規劃的目標函數（ Objective Function ) ，此目標函數必須不違反各種資源限制因素所形成的線性聯立方程組（ System of Equations ）。各限制式之常數項bi左邊之符號也可能為＝或≧的形式。

8 第一節 線性規劃的意義和模式(6/6) 求解線性規劃問題的方法有兩種，圖解法（ Graph Method ）及單形法 ( Simplex Method ）。圖解法對於只含兩個變數的問題，可以很容易地求出問題的答案。但如果問題中所含之變數增多時，圖解法所繪的立體空間，便不太容易顯示出問題的答案，則必須採用“單形法”求解。

9 第二節 線性規劃問題的範例和解法(1/58) 一、圖解法 (一)最大利潤問題
第二節 線性規劃問題的範例和解法(1/58) 一、圖解法 (一)最大利潤問題 假定某工廠製造x1及x2兩種產品，每種產品在製造過程中，都必須經過兩部不同的機器 M1及 M2 分別處理。每一單位的x1需要機器 Ml 處理 2 小時及機器 M2 處理 3 小時。每一單位的x2需要機器 M1 處理 4 小時及機器 M2 處理 2 小時。每一單位物的利潤為 60 元，每單位物的利潤為 50 元。機器 M1 的有效時間為 80 小時，機器 M2 的有效時問為 60 小時。則此工廠為求得最大利潤，應生產多少單位之x1及x2，且能符合機器有效時間的限制。

10 第二節 線性規劃問題的範例和解法(2/58) 因此，若以 P 代表工廠的利潤，分別由產品x1及產品x2得來，則目標函數為：
第二節 線性規劃問題的範例和解法(2/58) 因此，若以 P 代表工廠的利潤，分別由產品x1及產品x2得來，則目標函數為： 製造產品x1及x2所需時間的總和，不得超過兩部機器的有效時間。故機器 M1 有效時間的限制式可以寫成下式：

11 第二節 線性規劃問題的範例和解法(3/58) 同理，機器 M2 有效時間的限制式為：
第二節 線性規劃問題的範例和解法(3/58) 同理，機器 M2 有效時間的限制式為： 此外， x1及x2必須不得為負數，因為x1及x2分別為產品之產量，必須等於或大於零，即x1≧0， x2 ≧0，亦即答案是在平面圖形中的第一象限 ( First Quadrant ）

12 第二節 線性規劃問題的範例和解法(4/58) 因此，整個線性規劃問題可以寫成數學方程式：

13 第二節 線性規劃問題的範例和解法(5/58)

14 第二節 線性規劃問題的範例和解法(6/58) 所處理的均為線性方程式，可行解（ Feasible Solutions ）構成之可行區域（ Feasible Region ）所形成之多邊形必常為凸多邊形（ Convex Region ）。 尋找線性規劃問題解答，只要求端點上的產量組合，便可找出產生最大利潤的最適當解。

15 第二節 線性規劃問題的範例和解法(7/58) 端點 B 之座標，可以應用解聯立方程式的方法，求下列聯立方程式：

16 第二節 線性規劃問題的範例和解法(8/58)

17 第二節 線性規劃問題的範例和解法(9/58) 另外，在原點上x1及x2都是零，利潤為零，故此端點可以不必考慮。因此將 A 點， B 點及 C 點的座標代入目標函數式：

18 第二節 線性規劃問題的範例和解法(10/58) 二、最小成本問題
第二節 線性規劃問題的範例和解法(10/58) 二、最小成本問題 某飼料公司生產含有x1及x2兩種原料的混合飼料 200 磅，織成本每磅 $ 3 ，壯成本每磅＄ 8 ，為了保證該飼料最基本的營養價值，成份中x1不得多於 80 磅， x2不得少於 60 磅。則此公司欲求成本為最小， x1及x2應如何混合調製，以符合各項條件。

19 第二節 線性規劃問題的範例和解法(11/58) 則目標函數為： 此混合飼料之總重為 200 磅，故重量之限制式為：
第二節 線性規劃問題的範例和解法(11/58) 則目標函數為： 此混合飼料之總重為 200 磅，故重量之限制式為： 兩種原料x1及x2之限制條件則為以下兩個限制式：

20 第二節 線性規劃問題的範例和解法(12/58) 此外， x1及x2必須不得為負數，因為x1及x2分別為兩種原料的重量，必須等於或大於零，即x1≧0， x2 ≧0， ；亦即答案是在平面圖形中的第一象限。因此，綜合以上各式，得以下線性規劃問題：

21 第二節 線性規劃問題的範例和解法(13/58)

22 第二節 線性規劃問題的範例和解法(14/58) 由以上的結果可以看出，端點 B ( 80 , 120 ）的成本為最低，故最低成本 C＝＄ 1200 ， x1 ＝ 80 磅， x2 = 120 磅混合調製。

23 第二節 線性規劃問題的範例和解法(15/58) 二、單形法
第二節 線性規劃問題的範例和解法(15/58) 二、單形法 單形法（ Simplex Method ）乃係採取一種系統化的方法來求解線性規劃問題。因為，由圖解法已得知，線性規劃的最佳解都出現在端點上，單形法利用系統化的方法來檢試各個的端點。其特點是每次所選擇的某一個端點所得的目標函數值必定比前一次所選擇的端點為佳，而不必檢試所有的端點，便可求得目標函數最適值的端點。

24 第二節 線性規劃問題的範例和解法(16/58) 單形法的第一個步驟，是把問題中的不等式化為等式，可利用鬆弛變數 ( Slack Variables ）達到這項步驟。並且這些新的鬆弛變數也可列入目標函數中，其利潤係數在目標函數中均為零，故不影響目標函數之原意。

25 第二節 線性規劃問題的範例和解法(17/58) 原線性規劃問題加入鬆弛變數後，可得：

26 第二節 線性規劃問題的範例和解法(18/58) 現在問題的兩個方程式具有四個未知數，因此我們無法求得唯一解，因為在代數聯立方程式有唯一解的條件，乃未知數的數目必須和方程式一樣多。然而，我們設法先把四個未知數之中的兩個，令其為零，以求解另外兩個，由此可以得到六組答案，其結果如下表：

27 第二節 線性規劃問題的範例和解法(19/58)

28 第二節 線性規劃問題的範例和解法(20/58) 在上述六組解中，恰與圖解法所得之六個端點相同，此六個端點稱之為基礎解（ Basic Solutions ）。其中有兩組出現負值，稱之為基礎非可行解（ Basic Infeasible Solutions ) ，而其餘四組稱之為基礎可行解（ Basic Feasible Solutions ) ，基礎可行解每組中非零之變數稱之為基礎變數（ Basic Variables ）。

29 第二節 線性規劃問題的範例和解法(21/58) 單形法乃將每個端點所對應的目標函數值一個個地算出來，但由一個初解基礎變數（ Initial Basic Variables ）開始，求出目標函數值。然後，再選擇一個新的端點，此新端點之選擇則需用數學技巧，使所得之目標函數值較前為優。原線性規劃問題加進鬆弛變數之後為：

30 第二節 線性規劃問題的範例和解法(22/58) 首先應用高斯消去法（ Gaussian Elimination ）一步一步求解，先以鬆弛變數做為初解：

31 第二節 線性規劃問題的範例和解法(23/58) 代入目標函數：
第二節 線性規劃問題的範例和解法(23/58) 代入目標函數： 因此，如x1或x2由 0 增加，均可使 P 值由 0 增加，而x1之係數大於必x2 之係數，故x1可使 P 值增加的速度較快，故選擇x1為新的基礎變數之一，此新的基礎變數稱之為代入變數（ Entering Variable ）。又由限制式 知，當x1由 0 增至 20 時，先使x4為 0 ，故此因代入變數進入基礎解中而離開基礎變數者稱之代出變數（ Leaving variable ）。新的一組基礎燮數則為 x1及x3 。

32 第二節 線性規劃問題的範例和解法(24/58)

33 第二節 線性規劃問題的範例和解法(25/58) 故新的一組基礎變數則為x1或x2 。

34 第二節 線性規劃問題的範例和解法(26/58) 此時， x3及x4前之係數均為負值，故x3及x4如由 0 增加，必使 P 值減少。此時解為最適解。即：

35 第二節 線性規劃問題的範例和解法(27/58) 經過上述的數學運算技巧，巧妙選擇了代入變數及代出變數的方式，衹要檢試三個端點便可求最佳解，而原問題共有六個端點，亦簡化了我們求解的過程。以上的運算過程，可以由表格的方式簡化之，稱之為單形法表（ Simplex Tabulation ）。此例的單形法表如次頁所示。

36 第二節 線性規劃問題的範例和解法(28/58)

37 第二節 線性規劃問題的範例和解法(29/58)

38 第二節 線性規劃問題的範例和解法(30/58) 假如線性規劃問題中有 n 個限制式，基礎變數的數目要等於限制條件數，在單形法表運算過程中應該同於下表的形式：

39 第二節 線性規劃問題的範例和解法(31/58) Cj ：單形法表中勺之右方將目標函數各變數之單位利潤分別列在各變數之上方。 cj之下方則將基礎變數之單位利潤列入。 Zj：單形法表中方列之各項值，代表某一代入變數進入基礎變數，目標函數受原先各基礎變數減少而降低值之總和。我們可以從原來限制方程式中看出：

40 第二節 線性規劃問題的範例和解法(32/58) 故zj列中各項值的求法，是將各變數下各行的係數分別乘以勺行中相對的單位利潤，而計其總和：

41 第二節 線性規劃問題的範例和解法(33/58) Cj－Zj：
第二節 線性規劃問題的範例和解法(33/58) Cj－Zj： 將表中最上列的cj值減去右，即得cj－zj列之各項值，代表該代入變數進入基礎變數，目標函數之淨增值。當cj－zj為正時，表示一單位之代入變數，使目標函數所獲的淨利。而cj－zj為負時，則表示一單位之代入變數，使目標函數所造成的損失。 cj－zj又稱為單形值（ Simplex Value ）或單形法則（ Simplex Criterion ）。

42 第二節 線性規劃問題的範例和解法(34/58) 代入變表的選擇
第二節 線性規劃問題的範例和解法(34/58) 代入變表的選擇 由於cj－zj代表一單位之代入變數，使目標函數所獲的淨增量，故選擇cj－zj列中之最大正值所對之變數x1為代入變數，因其使目標函數增加速度最快，使其存在下一組基礎變數之中，此最大正值之 cj－zj所對之行稱之為樞軸行（ Pivot Column ) ，表示以該行之變數來取代一部分的基礎變數，樞軸行中的係數，分別表示增加一個代入變數所必須減少原基礎變數的數量。

43 第二節 線性規劃問題的範例和解法(35/58) 代出變數的選擇
第二節 線性規劃問題的範例和解法(35/58) 代出變數的選擇 選出cj－zj列中之最大正值所對之變數為代入變數之後，下一個步驟為決定在現有基礎變數中何者為代出變數，使其與代入變數交換。其方法是將原基礎變數之解值除以代出變數這一行的係數：

44 第二節 線性規劃問題的範例和解法(36/58) 選擇二式中最小者，表示代入變數x1由零所能增加的最大極限，因為由原來的限制方程式：
第二節 線性規劃問題的範例和解法(36/58) 選擇二式中最小者，表示代入變數x1由零所能增加的最大極限，因為由原來的限制方程式： 可以看出，當x1由零增加的數量超過 20 ， x4成為負值，違反限制式。因此，以上所計算的最小值，即決定了何者為代出變數的那一列，稱之為樞軸列（ Pivot Row ) ，同時決定了x4為代出變數。樞軸行及樞軸列所交之點稱之為樞軸元素（ Pivot Element ）。用圓圈標示出來。

45 第二節 線性規劃問題的範例和解法(37/58) 新基礎變數的決定
第二節 線性規劃問題的範例和解法(37/58) 新基礎變數的決定 樞軸元素決定後，為了使新基礎變數中包括代入變數物，樞軸元素必須轉換為 l ，用樞軸元素的數值來除該列， x1就導入了新的基礎變數之中，此基礎變數之解值也同時顯示出來，因為每列實際上是代表一個限制方程式，方程式的所有係數除以一個常數將無影響。樞軸元素化為 1 之後，再將此樞軸元素所對之行中的其他係數，運用行列式列運算（ Row operation ）方法，將其化為零，便可得到其他基礎變數的解值，呈現在 index 格子內。

46 第二節 線性規劃問題的範例和解法(38/58) 最後，基礎變數之解值x1 ＝ 20 ， x3＝ 40 分別乘以其單位利潤，計其總和，寫在 index 之下方．則為目標函數夕新解值，顯然比第一組基礎變釋的解好多了。同時，繼續將此第二組基礎變數之cj－zj列求出，以決定是否可以進一步改進。同理，可以看出，如將不存在基礎變數中之x2當作新的代入變數，每代進一個x2可使目標函數增加 10 個單位，

47 第二節 線性規劃問題的範例和解法(39/58) 故cj－zj列中尚有正值時，目標函數之現解值尚非最適解，可以繼續探討第三個端點，以求解另一組新的基礎變數，其求解過程與以上過程完全相同，直到cj－zj列中全為零或負值，最適解便求得，因為任何新的取代現象，都無法增加目標函數之值。

48 第二節 線性規劃問題的範例和解法(40/58) (二)最小成本問題－大 M 法
第二節 線性規劃問題的範例和解法(40/58) (二)最小成本問題－大 M 法 單形法求解最小成本問題的過程，與求解最大利潤的方法略有不同，因為最小成本問題的限制式中常有左邊大於右邊的不等式，以及左邊等於右邊的限制式，茲以前述最小成本問題為例：

49 第二節 線性規劃問題的範例和解法(41/58) 如果依照最大利潤問題的方法，僅加鬆弛變數於不等式中，則無法得到第一組基礎變數，而且限制式中的變數有出現負值的現象：

50 第二節 線性規劃問題的範例和解法(42/58) 因此，為了解決以上困擾，除了加鬆弛變數外，我們引入另一種新的變數於等式及大於之限制式中，此種新的變數，稱之為人造變數（ Artificial Variables ）。

51 第二節 線性規劃問題的範例和解法(43/58) 原線性規劃問題，加鬆弛變數及人造變數之後，得以下數學式：

52 第二節 線性規劃問題的範例和解法(44/58) 其中x4及x5為鬆弛變數，x3及x6為則為人造變數，原數學式經引入兩種變數之後，便很容易地獲得第一組基礎變數做為初解： 但第一組基礎變數，其中x3＝ 200 使x1＋x2 ＝ 0 ， x6＝ 60 使x2＝ 0 , 均不符合原限制式x1＋x2 ＝ 200 及x2≧60。

53 第二節 線性規劃問題的範例和解法(45/58) 如要符合各限制式，必須設法使人造變數 x3及x6人造變數為不存在基礎變數的最適解之中，故在目標函數中人造變數前加一個極大的成本係數，以 M 代表此極大的成本係數，稱之為大 M 法（ Big M Method ）。人造變數前加一個大 M 之後，根據單形法的運算過程中，在cj－zj列中必為極大正值，故永久不能被選為代入變數，無法存在最適解的基礎變數中。

54 第二節 線性規劃問題的範例和解法(46/58) 由於cj－zj代表一單位的代入變數，使目標函數所獲之淨值增量，故最大利潤問題選擇cj－zj列中之最大正值所對之變數為代入變數。而最小成本問題則選擇cj－zj列中之最小負值所對之變數為代入變數，可使目標函數之成本減少，直至 cj－zj列全部為零或正值時，最低成本之最適解便得到。

55 第二節 線性規劃問題的範例和解法(47/58)

56 第二節 線性規劃問題的範例和解法(48/58)

57 第二節 線性規劃問題的範例和解法(49/58)

58 第二節 線性規劃問題的範例和解法(50/58) (三)最大利潤問題一大 M 法
第二節 線性規劃問題的範例和解法(50/58) (三)最大利潤問題一大 M 法 最大利潤問題如有大於或等於的限制條件，其目標函數中的人造變數前則加一個極大利潤係數的負值（－M ）。茲以下述最大利潤問題為例：

59 第二節 線性規劃問題的範例和解法(51/58)

60 第二節 線性規劃問題的範例和解法(52/58)

61 第二節 線性規劃問題的範例和解法(53/58)

62 第二節 線性規劃問題的範例和解法(54/58)

63 第二節 線性規劃問題的範例和解法(55/58) (四)右邊比值出現負值時，代出變數的選擇 假設線性規劃的限制條件為： 則單形法表右邊比值為：

64 第二節 線性規劃問題的範例和解法(56/58) 可知x1可增加至無限大， x3均不為負值；但x1增至 20 時， x4為零，故必選x4為代出變數。故比值為負值者不選。

65 第二節 線性規劃問題的範例和解法(57/58) (五)右邊比值出現零時，代出變數的選擇 右邊比值出現零的情況有兩種：

66 第二節 線性規劃問題的範例和解法(58/58) 可知必選x3為代出變數， x1與x3交換，端點變更，但目標值不變。

67 第三節 線性規劃問題的特殊解(1/16) 當線性規劃問題有多餘的限制條件，其解就會有退化的現象。例如兩個限制條件x1 ≧16 及x1 ≧30 ，前者就為不必要的限制條件；因為x1 ≧30就一定可說x1 ≧16 。但大多數限制條件之形式比較複雜，多餘的限制條件並不易辨別出來。線性規劃若有退化情形發生，則在單形法求解過程中，表格右邊的比值會出現相等。茲以下列說明：

68 第三節 線性規劃問題的特殊解(2/16)

69 第三節 線性規劃問題的特殊解(3/16)

70 第三節 線性規劃問題的特殊解(4/16)

71 第三節 線性規劃問題的特殊解(5/16)

72 第三節 線性規劃問題的特殊解(6/16)

73 第三節 線性規劃問題的特殊解(7/16) 二、無限解問題（ Unbounded solution )
第三節 線性規劃問題的特殊解(7/16) 二、無限解問題（ Unbounded solution ) 當線性規劃問題的單形法求解過程中，邊比值全部為負值(包括 )時，則為無限制解。例如當限制條件為： 如以x1為代入變數，則右邊比值均為負值，移項後如下：

74 第三節 線性規劃問題的特殊解(8/16) 三、多組解問題（ Multiple Solution)
第三節 線性規劃問題的特殊解(8/16) 三、多組解問題（ Multiple Solution) 線性規劃問題也會出現多組最適解的情形，此時在圖形上則有兩個端點有相同的最大利潤或最小成本。茲以下例來判斷多組解的情形：

75 第三節 線性規劃問題的特殊解(9/16)

76 第三節 線性規劃問題的特殊解(10/16) 如以單形法來判斷多組解亦可，本例加入鬆弛變數：

77 第三節 線性規劃問題的特殊解(11/16)

78 第三節 線性規劃問題的特殊解(12/16)

79 第三節 線性規劃問題的特殊解(13/16) 故其解為： 以及此兩端點間之所有點均為最適解。

80 第三節 線性規劃問題的特殊解(14/16) 四、無解問題（ No solution )
第三節 線性規劃問題的特殊解(14/16) 四、無解問題（ No solution ) 線性規劃問題如其限制式在圖形上並無可行區域，則為無解的情形。茲以下例來判斷無解的情形：

81 第三節 線性規劃問題的特殊解(15/16) 其限制式在圖形上無共同區域，亦無端點可得，故無解。可以單形法來判斷無解的情形，本例加入鬆弛變數及人造變數：

82 第三節 線性規劃問題的特殊解(16/16)

83 第四節 對偶問題(1/22) 線性規劃數學式如將目標函數中各變數之係數予以轉換，並將限制式中各變數之係數列成轉置矩陣；則可得原函數（ Primal Function ）之對偶函數 ( Dual Function ) ，如以單形法求解原函數，其對偶函數之解值亦可直接由原函數之單形法表格中讀出；茲以下例說明之：

84 第四節 對偶問題(2/22)

85 第四節 對偶問題(3/22) 以單形法分別求解以上原函數及對偶函數：

86 第四節 對偶問題(4/22)

87 第四節 對偶問題(5/22)

88 第四節 對偶問題(6/22)

89 第四節 對偶問題(7/22)

90 第四節 對偶問題(8/22) 原函數之最適解變數為： 其值可由對偶函數之單形法表最後cj－zj列對應鬆弛變數y3及y5處求得。
第四節 對偶問題(8/22) 原函數之最適解變數為： 其值可由對偶函數之單形法表最後cj－zj列對應鬆弛變數y3及y5處求得。 對偶函數之最適解燮數為：

91 第四節 對偶問題(9/22) 其值可由原函數之單形法表最後cj－zj列對應鬆弛變數x3及x4處求得。對偶變數乃代表原函數在最適解適用範圍內，有限資源之邊際價值 ( Marginal Value ) ，即當原函數在最適解實施時，有限資源每增加一單位，目標函數能增加的利潤。故對偶變數的最適值代表生產者已按最適產量生產，如欲更進一步提高利潤，增添每單位資源供應量所願支付的最高價格，故又稱為資源的影價格（ Shadow Prices ）。

92 第四節 對偶問題(10/22) 一、對偶限制條件（ Dual constraints ）之意義
第四節 對偶問題(10/22) 一、對偶限制條件（ Dual constraints ）之意義 設線性規劃原函數為兩部機器 M1 及 M2 用來生產兩種產品x1及x2 ，產品x1之單位利潤為 12 元，產品x2之單位利潤為 4 元。其耗用時間及有限時數如下表：

93 第四節 對偶問題(11/22) 原函數則可寫成下式： 可求得其最適解產量組合為x1 =2 ， x2= 0 ，目標函數最大利潤為 24 元。

94 第四節 對偶問題(12/22) 對偶函數則設 y1為使用機器 M1每小時之邊際價值， y2 為使用機器 M2 每小時之邊際價值。故兩部機器 M1 及 M2 生產每單位產品物或物所耗用的時數資源對各產品利潤之貢獻至少應等於其單位利潤，此乃最有利使用資源之條件，形成對偶函數之限制條件：

95 第四節 對偶問題(13/22) 可由原函數及對偶函數最適解答案看出，原函數最適解為x1 = 2 ， x2 = 0；對偶函數最適解為 y1 = 4 , y2 = 2 。產品x1 ＝ 2 （存在基礎變數中），其耗用資源之邊際價值則為 0 : 恰等於產品x1之單位利潤 12 元。產品x1 ＝ 0 （不存在基礎變數中），如增加其產量每單位所耗用資源之邊際價值則為： 大於產品x2之單位利潤 4 元，故以不增加其產量較有利，而將資源用於生產兩個單位之產品x1為最適解。

96 第四節 對偶問題(14/22) 二、對偶目標函數之意義
第四節 對偶問題(14/22) 二、對偶目標函數之意義 對偶目標函數指出兩部機器 M1 及 M2 生產產品x1及x2 ，在最適解產量組合下，所耗用資源（時數）之總邊際價值為： 對偶目標函數最適值必等於原函數目標函數最適值，稱之為“對偶定理” ( Dual Theorem ）。

97 第四節 對偶問題(15/22) 對偶定理指出對偶目標函數最適值必等於原函數目標函數最適值，而對偶燮數值必在對偶限制條件所圍之可行區域內，此區域係由原函數各產品所耗用資源的邊際價值大於或等於其單位利潤所形成之發散區域（ Divergent Area )，對偶目標函數最適值因等於原函數各產品之總利潤，故其值為此可行區域內之最小者。

98 第四節 對偶問題(16/22) 故對偶目標函數乃使諸產品所耗用資源之總邊際價值為最小。茲以座標圖進一步證實之：

99 第四節 對偶問題(17/22)

100 第四節 對偶問題(18/22) 吾人尚可進一步證明原函數目標函數值與對偶函數目標函數值之問有限制作用。設x1， x2為一組符合原函數限制式的變數， y1， y2 為一組符合對偶函數限制式的變數；將y1， y2分別乘原函數限制式，同樣地將x1， x2分別乘對偶函數限制式：

101 第四節 對偶問題(19/22) 把以上原函數及對偶函數乘出來的限制式左式及右式分別各自加在一起，二者左式之和恰相等，因此：
第四節 對偶問題(19/22) 把以上原函數及對偶函數乘出來的限制式左式及右式分別各自加在一起，二者左式之和恰相等，因此： 可知如對偶問題有可行解，則原函數就有一個可行解；如原函數目標值為無限大，則對偶函數無解。

102 第四節 對偶問題20/22 三、原函數與對偶函數的關係
第四節 對偶問題20/22 三、原函數與對偶函數的關係 以上分析可知，原函數鬆弛變數有正值時，相關對偶函數變數值為零；原函數鬆弛變數值為零時，相關對偶函數變數值為正值，以上關係稱之為補餘定理（ Theorem of Complementary Slackness ）。

103 第四節 對偶問題(21/22) 原函數與對偶函數的關係除了對偶函數最適解可以直接由原函數最適解單形法表中找出外，兩者最適解之問尚有下述的關係。 試將對偶函數最適解 y1 = 4 ， y2 = 0 代入對偶函數限制條件，以觀察是否符合：

104 第四節 對偶問題(22/22) 對偶函數最適值代入限制條件後，可知均符合；而左式與右式的差值是：

105 第五節 敏感性分析(1/14) 線性規劃問題在獲得最適解後，即可據以制定其生產方式，取得最適之生產目標；然而身為管理決策分析人員並不因而滿足，必須更進一步去了解問題中各有關變數數值發生變動時，可能造成的影響。例如產品價格、資源供應量、或欲生產新產品所發生的影響，對決策管理有其重大的意義。敏感性分析則能協助吾人預先獲知所需數據，期能未雨綢繆，掌握全盤。

106 第五節 敏感性分析(2/14) 一、產品價格變化時
第五節 敏感性分析(2/14) 一、產品價格變化時 分析線性規劃目標函數中諸產品之係數（單位利潤或成本）變更時有何影響，則視該產品變數是否存在原問題最適解基礎變數中而定，茲分別討論。前例中，如產品x2 之利潤係數自 4 變為（ 4 ＋ △ ）， △ 為增量（ Delta ) ，因x2為原問題最適解之非基礎變數，故在單形法運算過程中，最適解勺一有列中，只有對應物之係數會增加一個 △ 的正值，其餘變數的係數則不變。

107 第五節 敏感性分析(3/14) 因此可以看出，當（- 4 ＋ △ ） > 0 時， x2則可作為代入變數進入基礎變數中，使原來最適解改變。亦即 △ ＞ 4 時，原來最適解已非最適解。故維持原有最適解不變， x2之單位利潤可增加之範圍為：

108 第五節 敏感性分析(4/14)

109 第五節 敏感性分析(5/14)

110 第五節 敏感性分析(6/14) 當最適解cj－zj列對應x2及x3之係數大於零而為正值時，則可作為代入變數進入基礎變數中，使原有基礎變數改變。故維持原有最適解不變， x1的單位利潤增量之允許範圍為： 亦即只要x1的單位利潤增量合於下式，則現有基礎變數最適值不會變動（目標函數增加 2 △ ） :

111 第五節 敏感性分析(7/14) 二、資源供應量（右手限制常數）變化時
第五節 敏感性分析(7/14) 二、資源供應量（右手限制常數）變化時 線性規劃限制條件的右手限制常數數值變動時，由於在單形法運算過程，最適解cj－zj列各項數值均不受影響而保持不變，故最適解原基礎變數仍為基礎變數。基礎變數之數值及目標函數值則可能變動。

112 第五節 敏感性分析(8/14)

113 第五節 敏感性分析(9/14)

114 第五節 敏感性分析(10/14) 同時亦可分析，維持原有最適解基礎變數型態（數值有增減）， △ 值允許範圍為：
第五節 敏感性分析(10/14) 同時亦可分析，維持原有最適解基礎變數型態（數值有增減）， △ 值允許範圍為： 亦即只要機器 M1 有限時數的增量合於下式的範圍，則可用單形法結果直接判斷，x1之產量為（2 ＋ △ 3 ) ，不生產x2，而 △ 值每增加一單位，目標函數值增加 4 △ 。在此範圍以外，應以單形法重新求解。

115 第五節 敏感性分析(11/14) 三、新產品的增加 分析線性規劃問題增加一項新產品是否可使原來目標函數最適解增加，可由原函數最適解單形法表
第五節 敏感性分析(11/14) 三、新產品的增加 分析線性規劃問題增加一項新產品是否可使原來目標函數最適解增加，可由原函數最適解單形法表 cj－zj列中找出對偶變數值與新產品的資源耗用量及單位利潤，予以比較便可得知。 原例中，設若某項新產品x3所耗用機器 M1 及 M2 的時數分別為 小時及 小時，其單位利潤為6元。

116 第五節 敏感性分析(12/14) 由於對偶變數代表原函數在最適解情況下，資源每增加一單位，目標函數能增加的利潤，亦即增加每單位資源所願支付的最高價格（影價格）。故此項新產品每單位所耗用資源的價值為： 由於此項新產品的單位利潤為 6 元，大於耗用資源的價值，故值得將其加入生產活動，運用單形法重新求取最適解如下，得其最適產量組合為x1＝ 1 , x2＝ 4 ，目標函數值增至 36 元。

117 第五節 敏感性分析(13/14)

118 第五節 敏感性分析(14/14)

119 第六節 線性規劃實例(1/37) 例題 4-1 產品x1及x2均需經 M1 及 M2 兩部機器分別處理，售出後所得利潤x1為每件 60 元， x2為每件 50 元，今知 M1 及 M2每日生產 x1及x2之最大能量如下表： 列出線性規劃數學式，並求最大利潤的每日生產方法。

120 第六節 線性規劃實例(2/37)

121 第六節 線性規劃實例(3/37)

122 第六節 線性規劃實例(4/37)

123 第六節 線性規劃實例(5/37)

124 第六節 線性規劃實例(6/37) (二)以單形法求解，其單形法表如下：

125 第六節 線性規劃實例(7/37)

126 第六節 線性規劃實例(8/37) 例題 4-2 某工廠生產x1， x2，x3三種產品，每種產品都需經過鑄造、焊接及磨光三種過程，各需工時如下： 各工作部門可用時數為：鑄造 120 小時，焊接 150 小時，磨光 200 小時。各項產品之單位利潤： x1為 5 元， x2為 8 元， x3為 4 元。試決定各產品之產量，使利潤為最大。

127 第六節 線性規劃實例(9/37)

128 第六節 線性規劃實例(10/37)

129 第六節 線性規劃實例(11/37)

130 第六節 線性規劃實例(12/37)

131 第六節 線性規劃實例(13/37) ∴Max . P = 210 ， x1= 10 ， x2 = 20 最大利潤為 210 元， x1的產量為 10 ， x2的產量為 20 ， x3的產量為 0 。

132 第六節 線性規劃實例(14/37) 例題 4-3 某工廠生產甲、乙兩種袋裝產品，各產品每袋所需 A , B , C 三種原料的的份量及各原料的現有庫存量如下表。甲產品每袋的利潤為 20 元，乙產品每袋的利潤為 35 元。試求在最大利潤目標下的產品組合。

133 第六節 線性規劃實例(15/37)

134 第六節 線性規劃實例(16/37)

135 第六節 線性規劃實例(17/37) ∴Max . P = 1,050 ， x1= 15 ， x2= 20 最大利潤為 1,050 元，生產甲產品 15 袋，乙產品 20 袋。

136 第六節 線性規劃實例(18/37) 例題 4-4 聯合汽車零件公司，生產甲、乙、丙三種零件，其單位利潤分別為 20 元， 30 元， 10 元。三種零件所需及可用工時、原料如下表所示。試求其最大利潤的產量組合。

137 第六節 線性規劃實例(19/37)

138 第六節 線性規劃實例(20/37)

139 第六節 線性規劃實例(21/37)

140 第六節 線性規劃實例(22/37) ∴Max . P = 800 ， x1= 10 ， x2= 20 ， x3= 0 最大利潤為 800 元，生產甲產品 10 單位，乙產品 20 單位，不生產丙產品。

141 第六節 線性規劃實例(23/37) 例題 4-5 求解以下線性規劃問題：

142 第六節 線性規劃實例(24/37)

143 第六節 線性規劃實例(25/37) 最佳解的可行區域無限制，故為無限解。 P 值可得至無限大。

144 第六節 線性規劃實例(26/37)

145 第六節 線性規劃實例(27/37) 例題 4-6 求解以下線性規劃問題：

146 第六節 線性規劃實例(28/37)

147 第六節 線性規劃實例(29/37) 目標函數 C ＝4x1+6x2與限制式 2x1－x2＝2，故最小C值在( 0 , 2 )，( 1.5, 1 ）以及連接此兩點之直線上之一切點，均為其解。

148 第六節 線性規劃實例(30/37)

149 第六節 線性規劃實例(31/37)

150 第六節 線性規劃實例(32/37) cj－zj列均為正值，故最適解已得： Min . x1= 12 ， x2= 0 。但cj－zj 列對應x1之值為 0 ，為多組解。

151 第六節 線性規劃實例(33/37) 例題 4-7 求解以下線性規劃問題：

152 第六節 線性規劃實例(34/37)

153 第六節 線性規劃實例(35/37)

154 第六節 線性規劃實例(36/37)

155 第六節 線性規劃實例(37/37)