線性規劃
作業研究(Operations Research, OR)主要是探討在進行組織運作時所產生的作業問題。運用科學的方法,即以數學模式或計量方法,提供管理者作出決策,可適用於不同的產業領域,包含有限資源的分配及各項活動的安排等,目的是使整體效益達到最佳化,亦可稱為管理科學(Management Science)、決策科學 (Decision Science)。
運用作業研究解決問題之程序如下:
一. 定義問題
二. 資料收集
三. 建立數學模式
四. 求解模式
五. 模式驗證
六. 建立控管程序
建立線性規劃模式
求解
所謂線性規劃(Lincar Programming, LP)為研究資源如何以最佳方式分配的問題。在所使用的數學函數中(包含目標函數、功能限制式),均需滿足線性(linearity)條件。
4個基本假設
(1)確定性
(2)比例性
(3)可加性
(4)可分性
如何建模
- 設立決策變數
(單指標或雙指標) - 建立目標函數
- 建立限制式
- 決定決策變數之範圍
機艙問題
切水管問題
投資規劃問題
人員排班問題
線性規劃轉換標準模式
(為了求解)
標準模式
(擴充形式augmented form)
1.限制式為等號(=)
2.決策變數非負(≥0)
3.RHS值為非負(≥0)
≤限制式 加上slack variable
≥限制式 減掉surplus variable
RHS值為負 整列乘負號
決策變數為負 變數變換
決策變數無限制(實數) 變數變換
決策變數是範圍 視為2個功能限制式
目標函數小中取大問題 變數變換
目標函數絕對值問題 變數變換
(題庫2-1)
圖解法(Graphical Method)
1.繪製限制式、可行解區域
2.目標式斜率平移
3.帶入結果角解,即最佳
任何線性規劃問題必為凸集合
基解解釋
求解情況之判斷
1.唯一最佳解
2.多重最佳解
(直線參數式)
3.無可行解
4.無限值解
5.退化解
單體法(Simplex Method)
單體法一律從原點出發且沿著邊界走,進行尋優,這麼做是因為此方法最有效率(等利潤性質)。
1.轉標準模式,繪製單體表格
2.決定進入
3.決定退出
4.高斯消去
5.判斷最佳解
6.結束或回到步驟2
因為單體法都是從原點出發,所以一開始slack變數必是BV,其他變數則是NBV=0
單體法特殊情況
1.多重最佳解
2.無限值解
3.退化解
4.無可行解
大M法(Big M method)
單體法必從原點開始,當今天限制式為"≧"或"=",會導致原點是不可行解,單體法也無法使用。
加上人工變數,使原點滿足可行解,最後必須確保人工變數退出基底,所以會在目標式給予懲罰值大M。
唯一只有“=”必須加人工變數,“≥”用dual simplex較容易。
大M法的步驟只有第一步要先還原回proper form,其餘與一般單體法相同,AV均退出達最佳。
計算量很大
兩階段法(Two-Phase Method)
其目的與大 M 法相同,但採用計算程序不同。
Max,Min問題都一樣的做法
1.僅處理人工變數使人工變數退出基底變數,求得可行解,作法為極小化人工變數。
2.代入原目標函數求出最佳解
單體法矩陣形式或修正單體法(Revised Simplex Method)
其優點可以提高計算效率(對電腦而言)以及方便進行敏感度分析。
要把表格位置記熟即可
若考試遇到,則採用此種方式,在題目卷上把左邊單體法表格做完,然後再到答案卷上,把右邊一個一個步驟寫上去。
這樣比較快
注意!!如果有特殊情況遇到人工變數(≧,=),那人工變數就會在閒置變數那一欄,正常做即可
範例1.19
常考的觀念題