Chapter 2 線性規劃.

Presentation on theme: "Chapter 2 線性規劃."— Presentation transcript:

1 Chapter 2 線性規劃

2 LP的一般模式如下: 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

3 管理科學中文版「一般線性規劃模式」如下:
管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

4 LP的標準型式：(第3章)1/2 以矩陣表示 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

5 LP的標準型式：(第3章)2/2 以表格表示 x A b c d 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

6 LP模式的假設條件 成正比假設(Proportionality Assumption)
變數關係是直線關係 可加性假設(Additivity Assumption) Z(X) = Z1(x1)+Z2(x2)+…+Zn(xn) 可分性假設(Divisibility Assumption) xi 可以是分數或小數 確定性假設(Deterministic Assumption, Certainty Assumption) c, A, b 是確定參數，沒有機率變數 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

7 線性規劃成正比假設 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

8 例題1 一家公司生產兩種肥料，高磷與低磷。有三種原料來製造這兩種肥料，以甲、乙、丙代表。
生產1包高磷肥料，需要甲原料2公斤、乙原料1公斤、丙原料1公斤。 生產1包低磷肥料，需要甲原料1公斤、乙原料1公斤，不需要丙原料。 該公司每天有1500公斤甲原料，1200公斤乙原料，500公斤丙原料；每包高磷肥料利潤15元，每包低磷肥料利潤10元。問該公司每天該如何生產，使總利潤最大？ 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

9 解答1 x1 = 高磷肥料的生產量(包/天) x2 = 低磷肥料的生產量(包/天) 肥料生產問題的目標函數和限制條件如下：
管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

10 線性規劃模式的投入 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

11 線性規劃模式的產出 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

12 線性規劃模式的投入與產出 以 LP 的表格型式 表示： 活動為行 (Column) 投入產出的項目為列 (Row)
管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

13 LP模式的投入與產出—例題 1 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

14 例題1 根據投入與產出法的 LP模式 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

15 多週期生產計畫 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

16 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

17 多週期生產問題的LP模式 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

18 製紙公司生產問題1/4 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

19 製紙公司生產問題2/4 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

20 製紙公司生產問題3/4 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

21 製紙公司生產問題4/4 數學式如下 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

22 2.3線性規劃模式解答的特性 一個LP問題，一定有下列四種結果之一：
可行解區是空集合，即沒有可行解(infeasible, no feasible solution) 無界的(unbounded) 有唯一的最佳解(unique optimal solution) 有多重最佳解(multiple optimal solution) 或無限多最佳解(infinity optimal solution) 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

23 線性規劃模式解答的特性 LP模式在幾何上，有兩個重要觀念： 可行解區如果不是空集合，則是多面體的凸集合。
若有最佳解，則一定有一個最佳解在可行解區的端點上。 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

24 檢查是否凸集合？如果是，端點為何？ 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

25 2.4 線性規劃模式圖解法 圖解法的步驟如下： 取兩個決策變數當作縱橫兩個座標軸。 將限制式劃在座標圖上，其交集為可行解區。
劃出目標函數線。目標函數線平行移動。 如果LP問題是求極大，則目標函數線往增加方向平行移動到最後接觸可行解區，該最後接解點為最佳解。如果LP問題是求極小，則目標函數線往減小方向平行移動。 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

26 例題4： 利用圖解法求肥料生產問題的解答。 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

27 有最佳解的LP模式 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

28 有多重最佳解的LP模式 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

29 無界的LP模式 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

30 無解的LP模式 2 4 x1 x2 6 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

31 電腦應用範例 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

32 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

33 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

34 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

35 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

36 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

37 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

38 LP無解的結果 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】

39 LP無界的結果 管理科學：作業研究與電腦應用 【Ch.2 線性規劃】