線性規劃

作業研究(Operations Research, OR)主要是探討在進行組織運作時所產生的作業問題。運用科學的方法,即以數學模式或計量方法,提供管理者作出決策,可適用於不同的產業領域,包含有限資源的分配及各項活動的安排等,目的是使整體效益達到最佳化,亦可稱為管理科學(Management Science)、決策科學 (Decision Science)。

運用作業研究解決問題之程序如下:
一. 定義問題
二. 資料收集
三. 建立數學模式
四. 求解模式
五. 模式驗證
六. 建立控管程序

建立線性規劃模式

求解

所謂線性規劃(Lincar Programming, LP)為研究資源如何以最佳方式分配的問題。在所使用的數學函數中(包含目標函數、功能限制式),均需滿足線性(linearity)條件。

4個基本假設
(1)確定性
(2)比例性
(3)可加性
(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
常考的觀念題