Simplex algorithm:Framework A sequence of -What's a tableau? (simplex)tableaus 1.Pick an initial tableau 1.How? 2.Update the tableau 2.What's the rule? 3.Terminate 3.When to terminate? Why optimal? Complexity? 16
Simplex algorithm: Framework ◼ A sequence of (simplex) tableaus 1. Pick an initial tableau 2. Update the tableau 3. Terminate ◼ What’s a tableau? 1. How? 2. What’s the rule? 3. When to terminate? Why optimal? Complexity? 16
An introductory example Consider the following LP Rewrite equalities as max X1+X2 follows.(A tableau.) S.t.-x1+x2+x3=1 x3=1+x1-X2 X1+X4=3 X4=3-X1 x2+x5=2 X5=2-x2 X1,X5≥0 Z=x1+X2 The equalities are Ax =b, -1110( Let z=obj=x1+x2. 17
An introductory example ◼ Consider the following LP max 𝑥1 + 𝑥2 𝑠.𝑡. −𝑥1 + 𝑥2 + 𝑥3 = 1 𝑥1 + 𝑥4 = 3 𝑥2 + 𝑥5 = 2 𝑥1 ,… , 𝑥5 ≥ 0 ◼ The equalities are 𝐴𝑥 = 𝑏 , 𝐴 = −1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 , 𝑏 = 1 3 2 ◼ Let 𝑧 = 𝑜𝑏𝑗 = 𝑥1 + 𝑥2 . ◼ Rewrite equalities as follows. (A tableau.) 𝑥3 = 1 + 𝑥1 − 𝑥2 𝑥4 = 3 − 𝑥1 𝑥5 = 2 − 𝑥2 𝑧 = 𝑥1 + 𝑥2 17
An introductory example The equalities are Ax =b,Rewrite equalities as /-11100八N follows. x3=1+x1-x2 Let z=obj=x1+x2. X4=3-X1 ■B={3,4,5}is a basis: X5=2 -X2 AB I3 is non-singular. Z=x1+X2 AB:columns jE B}of A. ■ Set x1=x2 =0,and get The basis is feasible: X3=1,x4=3,x5=2. And=0. (X1 X2 X3 X4 X5 0 013 2 ) 18
An introductory example ◼ The equalities are 𝐴𝑥 = 𝑏 , 𝐴 = −1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 , 𝑏 = 1 3 2 ◼ Let 𝑧 = 𝑜𝑏𝑗 = 𝑥1 + 𝑥2 . ◼ 𝐵 = 3,4,5 is a basis: 𝐴𝐵 = 𝐼3 is non-singular. ❑ 𝐴𝐵: columns 𝑗:𝑗 ∈ 𝐵 of 𝐴. ◼ The basis is feasible: 𝐴𝐵 −1𝑏 = 1 3 2 ≥ 0 0 0 . ◼ Rewrite equalities as follows. 𝑥3 = 1 + 𝑥1 − 𝑥2 𝑥4 = 3 − 𝑥1 𝑥5 = 2 − 𝑥2 𝑧 = 𝑥1 + 𝑥2 ◼ Set 𝑥1 = 𝑥2 = 0, and get 𝑥3 = 1, 𝑥4 = 3, 𝑥5 = 2. ◼ And 𝑧 = 0. ◼ 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑧 0 0 1 3 2 0 18