如何使用整數線性規劃去解決「麥記格到最抵」問題

, , at April 22nd, 2009 by 小影

話說在電鋸裡看到「無聊問題」，除了寫程式去解決這問題，我們還可以把它當成一個 限制滿足問題 (Constraint Satisfaction Problem)，用整數線性規劃 ( Integer Linear Programming) 去解決。在此請讓我大膽試用學了兩個小時的 ILP 來解這問題吧！(因為是初學者，如果有錯還請指正，謝謝！)

* * *

首先我們假設只有以下六種貨品：

  • i1 雙層芝士孖堡
  • i2 至尊漢堡
  • i3 中薯條
  • i4 中可樂
  • i5 雙層芝士孖堡套餐
  • i6 至尊漢堡套餐

設每種貨品的價格為 p1, p2, …, p6。
設每種食品的目標數量為 w1, w2…, w6。
設每種貨品的落單量為 x1, x2 …, x6。( <– 這是我們想要的答案 )

1. 設我們想要 1 個芝士孖堡 (w1 = 1)，那我們可得以下方程：

x1 + x5 >= w1 = 1

2. 同樣我們想要 1 個至尊漢堡 (w2 = 1)：

x2 + x6 >= w2 = 1

3. 想要1個中薯條和1個中可樂 (w3 = 1, w4 = 1)：

x3 + x5 + x6 >= w3 = 1
x4 + x5 + x6 >= w4 = 1

4. 落單的總價錢等於每樣貨品的落單量乘價錢：

total price  2009-04-22_0158

5. 以上方程式的解，就是能付合我們其望的落單指示。其中能最小化 total price P 的解就是「格到最抵」的答案了！(我還沒有示範怎樣解以上方程？唏這樣簡單的算術就別要我做啦 … 好了我是懶得計數…)

把以上方法通用化，就可以解決任何組合的食品和套餐的問題。我會試試使用 Java 的 CSP Solver 把這個 Model 實作試試這種另類的解法。

好了，為甚麼要使用 Integer Programming 去解而不用 programming 去解決問題呢？因為使用了它就不用寫程式了！只要定義 Integer Programming 的 Model 和使用通用的 IP Solver 就可以解決任何問題啦，想想都覺得爽呀！

* * *

問：電腦可以很簡單地解決 Integer Programming 問題嗎？

答：呃… 那是 NP-Hard 的問題，即是非常困難！一般來說很慢，除非有人為那問題設計出特定的算法…

問：那為何不直接設算法解決上面那個問題好了？

答：呃… 這純綷顯示我們懂得這個方法 (假)。有些複雜的資源分配問題是難以用普通算法去解決的，使用 ILP 我們不需要有複雜的算法也可能得出正確的解。

* * *

歡迎為此問題提供更無聊的解法 =)

延申閱讀

Random Posts

  1. 2 Responses to “如何使用整數線性規劃去解決「麥記格到最抵」問題”

  2. By Justin Yip on Apr 22, 2009 | Reply

    純粹好奇，
    點解你會聽過Constraint Satisfaction Problem既？？？

  3. By 小影 on Apr 22, 2009 | Reply

    因為我是讀 Computer Science 的人嘛！ (其實我也只是在讀 CS Master Degree 時有一科說過這題目一堂啦)

Post a Comment