Please enable JavaScript.
Coggle requires JavaScript to display documents.
對偶問題 - Coggle Diagram
對偶問題
對偶性質
complementary slackness property
互補差額性質 ：若[X;Xs]與[Y;Ys]是互補基解(必是一組可行，另一組不可行)，則(X,Ys)(Xs,Y)對應之中，必然是基變數對應非基變數。因此，對應的變數相乘等於0。
若 (x,s)、(y,u)為一組可行互補基解，則(x,s)、(y,u)均為最佳解，若且唯若xu=0 且 ys=0 。
weak duality property
弱對偶性質(若x是maximize問題的可行解，且y是minimize問題的可行解，則此兩點的目標函數值必然cx≤yb，即Z值≤W值。)（等號成立在最佳解）
strong duality property
強對偶性質(若 x*是maximize問題的最佳解，且 y* 是minimize問題的最佳解，則此兩點的目標函數值必然cx*=y*b，即Z值=W值。)
complementary solutions property
互補解性質(在單形法每一回合找到可行解x時，同時也找到x的互補解y，也就是當時的Z列之slack variable之係數。互補解的特性是值相等，也就是同一回合的cx=yb；然而當x不是最佳解時，它的互補解y不是可行解。)
complementary optimal solutions property
互補最佳解性質 (在單形法求出最佳解x*時，它的互補解就是對偶問題的最佳解y*，由強對偶性質得知Z=W，且y*就是主問題各限制式的陰影價格。)
complementary basic solution property
互補基解性質 (（P）的每個基解，在（D）之中都有一個相對應的基解，稱為互補基解。（一個可行的基解對應一個不可行的互補基解，最佳解發生在兩互補基解均為可行解時）若[X;Xs]與[Y;Ys]是互補基解，則cx=by。)
原題與偶題之最終解對應關係表
原-->偶
無限值解-->無可行解
無可行解-->無限值解/無可行解
多重解-->退化解
退化解-->多重解
原題轉成偶題：
口訣：大轉小，先同在異。
小轉大，先異在同。（大同）
對偶單體法(dual simplex method)
為求解線性規劃問題的另一種作法，而單體法與對偶單體法的最大差別為對偶單體法允許 RHS 值為負數
遇到≥限制式，用對偶單體法會比big M / two-phase 還容易。
如果限制式其中一條有等號，就不能使用它且只能使用人工變數。
作法：
(1)限制式轉成≤
(2)加入slack variable
(3)RSH中，負最大的退出
(4)只考慮基準列中的負係數，絕對值比值最小的進入
(5)所有RHS值均為正數，即得可行解(多數為最佳)，沒有達到，就繼續迴圈
只考慮基準列中「負」的係數，因為要透過對偶單體法，把原本因為RHS為負的不可行解區域，拉回到可以解區域
原題是Max或Min問題都可以，對偶單體法只是為了退到可行解區域，看是否為最佳解而已，跟Max/Min無關。
求對偶問題時，其中一個目的為當主要問題不容易求解時，可以轉成偶題以提升求解效率。
第一種解釋方法，較難懂。
經濟意義：
(1)yi：是單位資源i，對利潤的貢獻(shadow price)
(2)yi ≥ 0：貢獻必須非負，最少是0
(3)∑aijyi ≥ Cj：表示此資源組合對目標函數的貢獻，必須至少大於或等於1單位活動j對利潤的貢獻(CjXj)
(4) Min W=∑biyi：為目標函數，可以視為最小化活動消耗的資源的總隱含價值(可想成成本)
（成本與貢獻，一體兩面。限制式要想成貢獻，目標式要想成成本。）
所以，對偶問題的最小化目標可以理解為在滿足貢獻約束的情況下，使得資源的總成本最小。
第二種：交大教授的估計最大值法
第三種：最常被講的方式
販賣資源問題，有人想買資源
最小化成本
影子價格(shadow price)
影子價格（每增加1單位資源，對目標函數產生增量）= 偶題最佳解 = slack variable之係數
假設資源需要外購，則shadow prices在經濟意義上可視為，購買資源所願意支付的最高成本
影子價格的意義可以再強對偶中看出來，當今天達最佳，Z=W，可以看到b1每增加一單位，W就會增加y1，對應過去的Z也會增加y1，這就是資源量每增加一單位，對目標函數值的影響。