第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted.

Presentation on theme: "第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted."— Presentation transcript:

1 第2章 線性規劃概要 © 2016 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

2 第2章 線性規劃概要 2.1 簡單的極大化問題 2.2 圖解法 2.3 極點與最佳解 2.4 Par公司問題的電腦解
2.5 簡單的極小化問題 2.6 特殊案例 2.7 一般線性規劃的符號 第2章 線性規劃概要 第29頁

3 前言 線性規劃的典型應用實例： 1. 製造商想建立其生產排程與存貨政策，以滿足未來某段期間的銷售需求。理想的生產排程與存貨政策將能同時滿足客戶的需求，並使生產與存貨的成本極小化。 2. 財務分析師必須由眾多股票及債券商品中，擇定一投資組合，希望此投資組合能使投資報酬極大化。 第2章 線性規劃概要 第30頁

4 前言 線性規劃的典型應用實例： 3. 行銷經理想要由眾多的廣告媒體諸如廣播、電視、報紙、雜誌等，決定其廣告預算的最佳配置，以使得廣告的效用極大化。 4. 某公司在全美各地擁有若干座倉庫。針對若干客戶的需要，公司想要決定各個倉庫對每個客戶的送貨量，以使運輸成本極小化。 第2章 線性規劃概要 第30頁

5 前言 對所有的線性規劃問題而言，目標是使某個數量極大化或是極小化。
限制條件(constraints)使得目標的滿足只能到達某個程度，限制條件是每個線性規劃問題的共同特徵。 第2章 線性規劃概要 第31頁

6 2.1 簡單的極大化問題 為Par公司的問題建立數學模式，分別決定標準型及豪華型球袋的生產量，使得總利潤最大。
第2章 線性規劃概要 第32頁

7 問題的模式化 問題的模式化(problem formulation / modeling)是將問題由文字描述轉成數學描述的過程。
問題模式化的步驟 徹底瞭解問題 描述目標 描述每個限制條件 限制條件1　切割及染色所使用的工時必須小於或等於可用的切割及染色工時。 限制條件2　縫製所使用的工時必須小於或等於可用的縫製工時。 第2章 線性規劃概要 第32-33頁

8 問題的模式化 限制條件3 細部製作所使用的工時必須小於或等於可用的細部製作工時。
限制條件3　細部製作所使用的工時必須小於或等於可用的細部製作工時。 限制條件4　檢驗及包裝所使用的工時必須小於或等於可用的檢驗及包裝工時。 定義決策變數 S = 標準型球袋的數量 D = 豪華型球袋的數量 　　 S及D就是決策變數(decision variables)　 第2章 線性規劃概要 第34-35頁

9 問題的模式化 以決策變數來表示目標 10S + 9D 稱為目標函數 Max 10S + 9D 以決策變數表示限制條件 限制條件1：
(2.1) 限制條件2： (2.2) 第2章 線性規劃概要 第2章 線性規劃概要 第33-34頁

10 問題的模式化 限制條件3： (2.3) 限制條件4： (2.4) 非負限制式(nonnegativity constraints)
第2章 線性規劃概要 第34頁

11 Par公司問題的數學敘述 (2.6) Par公司問題的數學模式是一種線性規劃模式(linear programming model or linear program)。 所有變數都是獨立項（沒有相乘項），且都是一次方的函數稱為線性函數(linear functions)。 第2章 線性規劃概要 第35頁

12 2.2 圖解法 只包含兩個決策變數的線性規劃問題可以用圖解法求解。 第2章 線性規劃概要 第35-36頁

13 2.2 圖解法 第2章 線性規劃概要 第37頁

14 2.2 圖解法 第2章 線性規劃概要 第38頁

15 2.2 圖解法 第2章 線性規劃概要 第39頁

16 2.2 圖解法 第2章 線性規劃概要 第40頁

17 2.2 圖解法 圖2.3 與圖2.4 的四張圖經過重疊之後，可以得到一張同時有四個限制式的圖，結果如圖2.5 所示。圖2.5 的陰影區域包含能同時滿足四個限制條件的所有解。因為能夠滿足所有限制式的解稱為可行解(feasible solutions)，此陰影區域稱為可行解區域，或簡稱可行區域(feasible region)。任何位於可行區域之內或邊界上的點都稱為可行解點(feasible solution point)。 第2章 線性規劃概要 第38頁

18 2.2 圖解法 第2章 線性規劃概要 第40頁

19 2.2 圖解法 第2章 線性規劃概要 第41頁

20 2.2 圖解法 第2章 線性規劃概要 第42頁

21 2.2 圖解法 第2章 線性規劃概要 第43頁

22 2.2 圖解法 第2章 線性規劃概要 第45頁

23 2.2 圖解法 第2章 線性規劃概要 第46頁

24 極大化問題圖解法摘要 圖解法解極大化問題的步驟可以摘要如下： 畫出每個限制式的可行解的圖形。 找出同時滿足所有限制式的可行區域。
畫出某個目標值的目標函數線。 將目標函數線往目標值大的方向平移，一直到可行區域的邊緣為止。 目標函數線上具有最大目標值的可行解就是最佳解。 第2章 線性規劃概要 第46-47頁

25 寬鬆變數 將最佳解的值(S=540, D=252)代入每個限制式，得到以下的資訊。
在線性規劃中，任何一個限制式未用完的量都稱為此限制式的寬裕值。 寬裕值 第2章 線性規劃概要 第47頁

26 寬鬆變數 線性規劃問題的式子中加入寬鬆變數(slack variables)以代表寬裕值或未閒置產量。
加入S1、S2 、S3及S4四個寬鬆變數之後 第2章 線性規劃概要 第47頁

27 寬鬆變數 當線性規劃問題的限制式寫成等式的形式，稱為標準型(standard form)。
Par公司問題的標準型，最佳解(S=540, D=252)的寬鬆變數值為： 不影響可行區域及最佳解，此限制式稱為冗餘限制式(redundant constraint)。 第2章 線性規劃概要 第47-48頁

28 2.3 極點與最佳解 Par公司的標準型高爾夫球袋的單位利潤由10美元減為5美元，而豪華型球袋的單位利潤與其他限制條件則不變。修正過的目標函數： Max 5S + 9D 第2章 線性規劃概要 第48頁

29 2.3 極點與最佳解 限制式沒有改變，所以可行區域沒變。 利潤線已經換成新的目標函數。
以線性規劃的術語，稱這些頂點為可行區的極點(extreme points)。 可以在可行區域的極點，找到線性規劃問題的最佳解。 第2章 線性規劃概要 第48-49頁

30 2.3 極點與最佳解 第2章 線性規劃概要 第49頁

31 2.4 Par公司問題的電腦解 最佳解 寬裕值 第2章 線性規劃概要 第51頁

32 2.5 一個簡單的極小化問題─M&D化學 A=產品A的加侖數 B=產品B的加侖數
Min　2A+3B A的產量至少必須為125加侖 1A 125 A與B的總產量必須至少350加侖 1A+1B  325 可用工時的上限為600小時 2A+1B  600 第2章 線性規劃概要 第52頁

33 2.5 一個簡單的極小化問題─M&D化學 非負限制式(A, B  0) M&D化學問題的線性規劃模式 第2章 線性規劃概要 第52頁

34 2.5 一個簡單的極小化問題─M&D化學 將目標函數線向左下 方移動，直到可行區 域的邊緣。 第2章 線性規劃概要 第53頁

35 2.5 一個簡單的極小化問題─M&D化學 第2章 線性規劃概要 第53頁

36 極小化問題圖解法摘要 最小化的圖解法求解步驟摘要如下： 畫出每個限制式的可行解的圖形。 找出同時滿足所有限制式的可行區域。
畫出某個目標值的目標函數線。 將目標函數線往目標值小的方向平移，一直到可行區域的邊緣為止。 目標函數線上具有最小目標值的可行解就是最佳解。 第2章 線性規劃概要 第54頁

37 剩餘變數 在線性規劃的術語中，超過限制式右側值的量稱為剩餘值。
A產品的產量超過最低要求250－125＝125加侖，此超過的產量稱為剩餘值(surplus)。 在的限制式中，在不等式的左手邊減去一個剩餘變數(surplus variable)可以將限制式轉成等式的形式。 第2章 線性規劃概要 第54頁

38 剩餘變數 在加入兩個剩餘變數S1、S2於的限制式，以及一個寬鬆變數S3於的限制式之後，M&D化學的線性規劃模式變成：
第2章 線性規劃概要 第54頁

39 M&D化學問題的電腦解 第2章 線性規劃概要 第56頁

40 多重最佳解 由圖解法可知，在可行區域的極點可找到最佳解。現在讓我們看一個特例：最佳解的目標函數線與某個關鍵限制式在可行區域的邊緣發生重疊。此種現象將導致所謂的多重最佳解(alternative optimal solutions)；也就是同時存在許多組解可以提供最佳目標函數值。 第2章 線性規劃概要 第57頁

41 多重最佳解 在此線段上皆為最佳解 第2章 線性規劃概要 第57頁

42 無可行解 無可行解(infeasibility)：沒有一個解可以同時滿足所有的限制式，包括非負限制式。 第2章 線性規劃概要 第58頁

43 無可行解 第2章 線性規劃概要 第59頁

44 無限解 如果一個極大化問題的解可以無限大，或者一個極小化問題的解可以無限小，而不會違反任何的限制條件，此問題具有無限解(unbounded)。 第2章 線性規劃概要 第59、61頁

45 2.7 一般線性規劃的符號 經常使用於線性規劃，更具普遍性的符號表示法， 是將 x 加上下標的數字表示決策變數。例如， Par公司的問題，我們可以將決策變數定義成： x1 = 標準型球袋的數量 x2 = 標準型球袋的數量 使用一般符號的缺點是：不再能輕易地得知決策 變數所代表的意義。 優點是描述一個具有很多決策變數的問題時會變得比較容易。 第2章 線性規劃概要 第60-61頁

46 2.7 一般線性規劃的符號 第2章 線性規劃概要 第62頁