Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Dual Interpretations and Duality Applications Yinyu Ye Department of Management Science and Engineering Stanford University Stanford CA 94305 U S A http www stanford edu yyye LY Chapters 4 1 4 2 6 8 1 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Production Problem I max pT x s t Ax r x 0 where p profit margin vector A resources consumption rate matrix r available resource vector x production level decision vector 2 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Production Problem II Liquidation Pricing y the fair price vector AT y p competitiveness y 0 positivity min rT y minimize the total liquidation cost 3 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 maximize x1 subject to x1 Primal 1 x2 x1 x1 Dual 2x2 minimize y1 subject to y1 y1 y2 x2 x2 1 1 5 0 1 5y3 y3 1 y2 y3 2 y2 y3 0 4 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Optimal Value Function For fixed matrix A and objective coefficient vector c the optimal value is a function of right hand side vector b z b minimize subject to cT x Ax b x 0 Theorem z b is a convex function in b that is for any 0 1 z b1 1 b2 z b1 1 z b2 5 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Shadow Prices of the Optimal Value Suppose a new right hand vector b such that b b and b k i bi i k k Then the optimal dual solution y has a property yk z b z b as long as y remains the dual optimal solution for b since z b b T y z b yk Thus the optimal dual solution is the shadow price vector of the right hand vector vector or the rate of the net change of the optimal objective value over the net change of an entry of the right hand vector vector 6 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Transportation Problem min s t m n i 1 n j 1 cij xij j 1 xij m i 1 xij xij si i 1 m dj j 1 n 0 i j 7 Yinyu Ye MS E Stanford d1 d2 d3 1 8 C11 x11 1 s1 2 s2 2 3 dn MS E310 Lecture Note 04 m n Demand Supply sm Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Transportation Dual max m i 1 si ui s t ui supply site unit price vi demand site unit price ui vj cij competitiveness n ui vj j 1 dj vj cij i j 9 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Max Flow and Min Cut Given a directed graph with nodes 1 m and edges A where node 1 is called source and node m is called the sink and each edge i j has a flow rate capacity kij The Max Flow problem is to find the largest possible flow rate from source to sink Let xij be the flow rate from node i to node j Then the problem can be formulated as maximize subject to xm1 j 1 j A x1j xm1 0 j j i A xji j i j A xij 0 i 2 m 1 j j m A xjm j m j A xmj xm1 0 j j 1 A xj1 0 xij kij i j A 10 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 6 2 2 3 3 4 1 3 3 4 7 Sink Source 5 11 3 4 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 The dual of the Max Flow problem minimize subject to i j A kij zij yi yj zij 0 i j A y1 ym 1 zij 0 i j A yi node potential value At an optimal solution has property y 1 1 ym 0 and for all other i 1 if i S yi 0 if i S This problem is called the Min Cut problem 12 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 2 2 3 1 3 13 4 Sink Source 3 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Application Combinatorial Auction Pricing I Given the m different states that are mutually exclusive and exactly one of them will be true at the maturity A contract on a state is a paper agreement so that on maturity it is worth a notional 1 if it is on the winning state and worth 0 if is not on the winning state There are n orders betting on one or a combination of states with a price limit and a quantity limit 14 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Combinatorial Auction Pricing II an order m R j R qj R aj is the combination betting vector where each component is either 1 or 0 a1j a 2j aj amj The j th order is given as a j where 1 is winning and 0 is non winning j is the price limit for one such a contract and qj is the maximum number of contracts the better like to buy 15 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 16 World Cup Information Market Order 1 2 3 4 5 Argentina 1 0 1 1 0 Brazil 1 0 0 1 1 Italy 1 0 1 1 0 Germany 0 1 0 1 1 France 0 0 1 0 0 Bidding Prize 0 75 0 35 0 4 Quantity limit q 10 5 10 10 5 Order fill x x1 x2 x3 x4 x5 0 95 0 75 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Combinatorial Auction Pricing III Pricing each state Let xj be the number of contracts awarded to the j th order Then the j th better will pay the amount j xj and the total collected amount is n j xj T x j 1 If the ith state is the winning state then the auction organizer need to pay back n aij xj j 1 The question is how to decide x Rn 17 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Combinatorial Auction Pricing IV LP model max T x z s t Ax e z 0 x q x 0 T x the optimistic amount can be collected z the worst case amount need to pay back 18 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Combinatorial Auction V The dual min qT y s t AT p y eT p 1 p y 0 p represents the state price and What is y 19 Yinyu Ye MS E Stanford MS E310 Lecture Note 04 Combinatorial Auction V Strict Complementarity xj 0 aTj p yj j and yj 0 so that aTj p j 0 xj qj yj 0 so that aTj p j xj qj yj 0 so that aTj p …