➣ Reading Time: 4 minutes

IP Problems

1.knapsack problem/背包問題

  • 特色:基礎題,選擇要不要把東西放進背包(只有0or1可選)

2.knapsack problem/背包問題-續

  • 特色:簡易條件式,可透過些微判斷得到條件式

3.fixed-charge problem/存在才需支付問題

  • 特色:如何讓你的存在影響到我會存在

ex:要做某商品才需要付機器租用費,反之則不租則不用付

4.set-covering problem/覆蓋範圍問題

  • 特色:依照距離,能在時限內的只需要有1即可達成條件

條件式 IP problems

1.either-or problem

★小提示:

難理解的話可以先思考這題,
想讀書或睡覺
★可能之一: 讀書 + “不睡”
★可能之二: 睡覺 + “不讀”

★特別注意:

either-or 並不是 or問題,一方成立另一方不可以成立

基本條件式:

f<=0 or g<=0 (這邊其實這樣表示不是很好,應該只有一個能成立)

轉換成

f <= My
g <= M(1-y)

其中:

M為極大數
y等於0或1

y等於0時:

f<=0 f<=0的條件"單獨"發生 
g<=M M極大 此式恆成立 (不重要的式子)

y等於1時:

f<=M M極大 此式恆成立 (不重要的式子)
g<=0 g<=0的條件"單獨"發生

2.if-then problem

基本條件式:

if f>0 then g>=0 

轉換得

-g <= My
f <= M(1-y)
M為極大數
y等於0或1

等於0時:

-g<=0 -g<=0(等價於g>=0)的條件"單獨"發生 而前式f>0(自動成立)
f<=M M極大 此式恆成立 (不重要的式子)

等於1時:

-g<=M M極大 此式恆成立 (不重要的式子)
f<=0 f<=0的條件"單獨"發生 g因此不受限
 ⭐管理科學/作業研究 MS/OR – 相關文章連結整理⭐:
1.【管理科學】 LP 問題, LP problem, LP solution procedure 第一次期中考筆記
2.【管理科學】 IP problem, 條件式 IP problems (either-or, if-then problem) 第一次期中考筆記
3.【管理科學】 solve LP problems, simplex method 詳細步驟與觀念 圖文說明講解 第二次期中考筆記
4.【管理科學】 simplex method 變形, two-phase method 二階解(另解) 第二次期中考筆記
5.【管理科學】 Duality & Postoptimality Analysis (敏感度分析) 期末考筆記
6.【管理科學】 運輸問題 (Transportation problem) 期末考筆記