Download presentation
Presentation is loading. Please wait.
1
Chapter 3 線性規劃單形法
2
“眾裡尋他千百度， 驀然回首， 那人卻在燈火闌珊處。” —辛棄疾《青玉案‧元夕》 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
3
and that has made all the difference.”
“森林內的兩條分叉路， 我選擇了人跡罕至的一條， 從此一切變得不一樣。” —佛羅斯特 “Two roads diverged in a wood, and I took the one less traveled by, and that has made all the difference.” —Robert Frost(1874 – 1963) “The Road Not Taken” 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
4
為什麼引用這兩首詩？ 辛棄疾的詩是尋找「那人」，Frost的詩是選擇「人跡」的路徑。 單形法是尋找「數量」的解答，是選擇「數學」的路徑。
管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
5
「數學」和「人」有什麼不同？ 「數學」沒有「驀然」、沒有「燈火闌珊」、沒有「罕至」、沒有「一切變得不一樣」。
「數量」是有些「畫意」，但是缺乏「詩情」。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
6
LP的一般模式如下: 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
7
標準型式(Standard form)： 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
8
LP的標準型式：第3章 以矩陣表示 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
9
LP的標準型式：第3章 X A b c d 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
10
LP的正規型式：第3章 以矩陣表示 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
11
正規型式(canonical form)：
管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
12
LP標準型式 LP正規型式 LP的正規型式： Max/Min xN xB I Z 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
13
求極小(Min)的LP問題如下： 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
14
肥料生產問題圖形1/2 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
15
肥料生產問題圖形2/2 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
16
基解 Basic Solution * x1 4 A F (0,6) (4,6) 2x2 12 D (4,3) B (0,0) C
(2,6) E A (0,6) F (4,6) 2x2 12 D (4,3) 基解 B (0,0) C (4,0) 3x1 + 2x2 18 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
17
基可行解 Basic Feasible Solution
x1 4 (2,6) E A (0,6) F (4,6) * 2x2 12 D (4,3) 基可行解 B (0,0) C (4,0) 3x1 + 2x2 18 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
18
3.3 單形演算法 首先是求極小LP 問題 Min cTx 的單形演算法： 找到一個基可行解(正規型式且 ≧0)。
找到一個基可行解(正規型式且 ≧0)。 檢查是否最佳解：若 ≧0，則最佳解為xB = ，xN = 0，為最佳目標函數值，結束。 從非基變數 xN 當中選擇一個進入變數 如果 xt 行的係數 均為零或負數，則本題是無界的，結束。否則，從基變數xB中選擇一個退出變數，利用比值檢定找 將xt行的係數 中正數除右手常數 ，取其比值最小的，其對應的基變數xk即為退出變數。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
19
軸運算(pivot)：以為軸元素，利用基本列運算： 新基變數xB，及新的 xN、 。回到第2步。
管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
20
例題1 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
21
解答1/3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
22
解答2/3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
23
解答3/3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
24
圖3.2 求極大LP問題單形法 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
25
例題2 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
26
解答1/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
27
解答2/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
28
解答3/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
29
解答4/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
30
解答5/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
31
解答6/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
32
例題3 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
33
解答1/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
34
解答2/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
35
解答3/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
36
解答4/6 (階段1) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
37
解答5/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
38
解答6/6 (階段2) 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
39
修正單形演算法(矩陣運算) x A b c d 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
40
例題4 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
41
解答1/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
42
解答2/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
43
解答3/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
44
解答4/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
45
解答5/5 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
46
求極大的LP問題的的修正單形演算法步驟：
決定基變數 xB，並檢查 是否大於等於0。 計算 ，若 ，則為最佳解，停止。 找 中最大者，令為進入變數 xt。 計算 。若 ，則問題無界，停止。 計算 ，利用比值檢定找退出變數 xr。 令xB=xB-{xr}+{xt}，到第1步。 管理科學：作業研究與電腦應用 【Ch.3 線性規劃單形法】
Similar presentations
