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
An introductory example ■Now we want to improve Rewrite equalities as z=obj=x1+x2. follows. Clearly one needs to X3=1+x1-X2 increase x1 or x2. x4=3-X1 Let's say x2. X5=2 -X2 Z=X1+x2 ▣we keep x1=0. Set x1=x2=0,and get How much can we x3=1,x4=3,x5=2. increase x2? We need to maintain the And =0. first three equalities. (X1 X2 X3 X4 X5 0 0132 19
An introductory example ◼ Now we want to improve 𝑧 = 𝑜𝑏𝑗 = 𝑥1 + 𝑥2 . ◼ Clearly one needs to increase 𝑥1 or 𝑥2 . ◼ Let’s say 𝑥2 . ❑ we keep 𝑥1 = 0. ◼ How much can we increase 𝑥2? ❑ We need to maintain the first three equalities. ◼ 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 19
An introductory example Setting x1=0,the first Rewrite equalities as three equalities become follows. x3=1-x2 x3=1+x1-x2 x4=3 x4=3-X1 x5=2-x2 X5=2-X2 ■To maintain all x;≥O,we Z=x1+x2 need x2≤1andx2≤2. ■ Set x1 =0,x2 =1,and obtained from the first and update other variables third equalities above. x3=0,x4=3,x5=1. So x2 can increase to 1. ■Andz=1. And x3 becomes 0. X2 X3 X4 X5 103 1 1) 20
An introductory example ◼ Setting 𝑥1 = 0, the first three equalities become 𝑥3 = 1 − 𝑥2 𝑥4 = 3 𝑥5 = 2 − 𝑥2 ◼ To maintain all 𝑥𝑖 ≥ 0, we need 𝑥2 ≤ 1 and 𝑥2 ≤ 2. ❑ obtained from the first and third equalities above. ◼ So 𝑥2 can increase to 1. ◼ And 𝑥3 becomes 0. ◼ Rewrite equalities as follows. 𝑥3 = 1 + 𝑥1 − 𝑥2 𝑥4 = 3 − 𝑥1 𝑥5 = 2 − 𝑥2 𝑧 = 𝑥1 + 𝑥2 ◼ Set 𝑥1 = 0, 𝑥2 = 1, and update other variables 𝑥3 = 0, 𝑥4 = 3, 𝑥5 = 1. ◼ And 𝑧 = 1. ◼ 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑧 0 1 0 3 1 1 20