6/14/2011

使用混合整數規劃治療攝護腺癌

文章 E.K. Lee and M. Zaider, Operations research advances cancer therapeutics, Interfaces, 2007 Franz Edelman Award Issue, 38(1):5-25, 2008. (摘要可以在網路上找到全文) 

攝護腺癌之近接治療 (Brachytherapy):『將放射性射源置放在靠近 (攝護腺) 腫瘤附近、或直接置放於腫瘤中,藉由其蛻變所產生的能量射束來治療腫瘤的技術』。可以參見 wiki 的示意圖。


此論文是利用混合整數規劃 (mixed integer programming) 決定多個放射性物質放置的位置。決定要不要在某個位置放置放射性射源是 0 或 1,形成決策變數 (decision variables);某一點的腫瘤會從多個射源得到放射性物質,其可以接受的劑量有上下範圍,所以形成限制式 (constraints)。因為問題的複雜度 (基本上是 dense MIP),作者在一系列的論文中,發展出新的方法,在數秒中,得到的次佳解在最佳解的 95% 以內,所以適合外科手術進行中 (intraoperative) 及時使用。

根據作者的估計,經由降低射源的數目和加快手術的時間,每個人可以省下 5 千美元的手術成本,而且病人手術後的品質 (副作用、恢復等等) 較好 (無價)。

6/13/2011

使用二次規劃決定河川的放水方式

兼顧紐約市用水、環境維護、和缺水的可能。使用的模型是二次規劃 (quadratic programming)。

文章 Peter Kolesar and James Serio, Breaking the Deadlock: Improving Water-Release Policies on the Delaware River Through Operations Research, Interfaces, 2011, v. 41, pages 18-34. 摘要


6/07/2011

誰養魚?


這是作業研究課程新增的作業。

網路上資料說明此題源自 1981 年柏林的德國邏輯思考學院,98% 的測驗者無法於半小時內解題;學會整數規劃後,讓您成為 2% 的人。

房子棑列方式如上圖。使用 1 到 5 代表不同的東西,例如下面集合中 N1 代表英國人,S5 代表香煙品牌 Prince。如果最終答案是 N1 = 2,代表英國人住在第 2 間房子。

N(ationality) = {英國人,瑞典人,丹麥人,挪威人,德國人}
D(rink) = {茶,咖啡,牛奶,啤酒,水}
C(olor) = {紅,綠,白,黃,藍}
P(et) = {狗,鳥,貓,馬,魚}
S(moke) = {Pall Mall, Dunhill, Blend, Blue Master, Prince}

圖檔中第一個要求是『英國人 (N1) 住在紅色房屋 (C1) 裏』,其限制式是 N1 = C1,因為我們還不知道英國人住在那一間,所以沒有指定其數字。

要求同學按照提示的號碼,寫下其整數規劃的限制式。

同學的反應還不錯,所以打算明年再增加此類的問題。

6/06/2011

人腦思考的局限 (為什麼要使用作業研究?)

3 乘 3 幻方 


放入 1 到 9 (和是 45),任何方向的和都是一樣 (45 / 3 = 15)。x1 到 x9 稱為決策變數 (decision variables)。

可以使用推理得知中間是 5,和其答案 (底部);或者金庸小說《射鵰英雄傳》中瑛姑百思才得其解,黃蓉卻編得出順口的口訣 (公式解)。可參見 E. W. Weisstein, "Magic Square." From MathWorld--A Wolfram Web Resource.  

使用整數規劃 
(目標) Min x1 (固定最小值在左上角) 
(限制式) 
x1 + x5 + x9 = 15 (共有 2 個對角方程式)
x1 + x2 + x3 = 15 (共有 3 個橫的方程式)
x1 + x4 + x7 = 15 (共有 3 個直的方程式)
xi 是 {1, 2, 3, …, 9} 且不同

7 乘 7 的幻方,您可以嘗試使用推理 ... (人腦思考的局限)




但是,同樣類似的方程式可以得到其整數規劃 (integer programming) 的數學模型,然後使用現有的軟體求解 (例如 cplex)

(目標) Min x1 (固定最小值在左上角) 
(限制式) 
x1 + x9 + ... + x49 = 175 (共有 2 個對角方程式)
x1 + x2 + ... + x7 = 175 (共有 7 個橫的方程式)
x1 + x8 + ... + x43 = 175 (共有 7 個直的方程式)
xi 是 {1, 2, 3, …, 49} 且不同

當然,這個整數規劃的求解又是另外一個問題,牽涉到組合爆炸 (Combinatorial explosion)