對偶

簡單範例

每個線性規畫問題, 都有一個相對應的問題 (想像照鏡子), 稱為它的對偶 dual; 相對地, 原來那個問題稱為 primal。 例如 farmer.lp 的 dual 是 farmer-dual.lp。

一般式:

Maximize Z = cT x 互為 Minimize W = yT b
s.t. A x <= b <====> s.t. AT y >= c
and x >= 0 對偶 and y >= 0

左右兩側這兩類題目恰好屬於 「資源有限, 求最高利潤」 及 「指定產量, 求最低成本」 兩類最常見的線性規劃題型。

對偶的意義與性質

詳見: Robert Vanderbei: 要不要把店賣掉? weak duality theory 與 strong duality theory

  1. min <==> max; "<=" <==> ">="; variable <==> constraint
  2. weak duality property: primal problem 的任何一個 feasible solution x 及 dual problem 的任何一個 feasible solution y 都必然滿足 cT x <= bT y
  3. strong duality property: primal problem 的 optimal solution x 及 dual problem 的 optimal solution y 滿足 cT x = bT y

請注意 lp_solve farmer.lp 與 lp_solve farmer-dual.lp 的輸出: 兩者的 objective value 相等。

非標準型如何求對偶?

詳見 Bruce A. McCarl: 變換規則 (第四章倒數第二頁)

  1. 不等號方向與標準型 _一致_ 的限制條件 <==> 大於等於零的變數
  2. 不等號方向與標準型 _相反_ 的限制條件 <==> 小於等於零的變數
  3. "等號" 的限制條件 <==> 不限正負的變數

例: tucker.lp 的對偶是 tucker-dual.lp。 我寫了一個小程式 dual.txt 可以幫您驗證您所列出的對偶是否正確。 下載後請將之更名為 dual.pl, 並且這樣執行: lp_solve -S5 tucker.lp | perl dual.pl 自己做範例時, 請注意 lp_solve 語法當中關於負的變數如何標示。 練習題: ex1.lp, ex2.lp。