University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

176

Pages:

5
Author:

nuevatagangahw

Optimization Methods Duality Theory II c c a1 a3 A a5 c a2 a4 a1 B c a3 a4 a2 a1 c C a1 a5 a1 D 1 Outline Slide 1 Geometry of duality The dual simplex algorithm Farkas lemma Duality as a proof technique 2 The Geometry of Duality cx aix bi i = 1 : : : m max p b m s:t: pi ai = c i�1 p0 min s:t: 0 Slide 2 0 X 0 3 Dual Simplex Algorithm 3.1 Motivation Slide 3 In simplex method B 1 b 0 ; Primal optimality condition c ; cB B 1 A 0 0 0 same as dual feasibility 1 ; 0 a2 c a1 a3 a3 a2 x* a1 Simplex is a primal algorithm: maintains primal feasibility and works towards dual feasibility Dual algorithm: maintains dual feasibility and works towards primal feasibility Slide 4 c x ; 0B B xB(1) .. . xB(m) B c1 ... 1 A1 ... B j ; j cn j 1An ; j Do not require B 1 b 0 Require c � 0 (dual feasibility) Dual cost is p b = cB B 1b = cB xB If B 1b 0 then both dual feasibility and primal feasibility, and also same cost ) optimality Otherwise, change basis ; 0 ; 0 0 ; 3.2 An iteration 1. Start with basis matrix B and all reduced costs 0. 2. If B 1b 0 optimal solution found else, choose l s.t. xB(l) < 0. ; 2 Slide 5 p2 x2 1 . D c 1 . . . . . B b C C A . . A E D 1 2 x1 . . E B 1/2 1 p1 ( b) (a ) 3. Consider the lth row (pivot row) xB(l) v1 : : : vn. If 8i vi 0 then dual optimal cost = +1 and algorithm terminates. Slide 6 4. Else, let j s.t. cj = min ci jvj j i v <0 jvi j 5. Pivot element vj : Aj enters the basis and AB(l) exits. f j i g 3.3 An example min x1 + x2 s:t: x1 + 2x2 2 x1 1 x1 x2 0 min x1 + x2 max s.t. x1 + 2x2 ; x3 = 2 s.t. x1 ; x4 = 1 x1 x2 x3 x4 0 Slide 7 2p1 + p2 p1 + p2 1 2p1 1 p1 p2 0 x1 x2 x3 x4 0 1 1 0 0 x3 = ;2 ;1 ;2* 1 0 0 1 x4 = ;1 ;1 0 x1 x2 ;1 1/2 0 x2 = 1 1=2 1 x4 = ;1 ;1* 0 3 x3 x4 1/2 0 ;1=2 0 0 1 Slide 8 Slide 9 A1 A3 A2 p b . x1 x2 ;3=2 0 0 x2 = 1/2 0 1 x1 = 1 1 0 x3 x4 1/2 1/2 ;1=2 1=2 0 ;1 4 Duality as a proof method 4.1 Farkas lemma Slide 10 Theorem: Exactly one of the following two alternatives hold: 1. 9x � 0 s.t. Ax = b. 2. 9p s.t. p A � 0 and p b < 0. 0 0 0 4.1.1 Proof \ ) If 9x � 0 s.t. Ax = b, and if p A � 0 , then p b = p Ax 0 \ ( Assume there is no x � 0 s.t. Ax = b (P ) max 0 x (D) min p b s:t: p A 0 s:t: Ax = b 00 0 0 0 0 00 0 0 0 x0 (P) infeasible ) (D) either unbounded or infeasible Since p = 0 is feasible ) (D) unbounded ) 9p : p A 0 and p b < 0 0 0 0 4 0 Slide 11