線性規劃
作業研究(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
常考的觀念題