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)

沒有留言:

張貼留言