Simplex algorithm: Framework a sequence of What's a tableau? (simplex) tableaus 1. Pick an initial tableau 1. How? pdate the tableau 2. What's the rule? 3. Terminate 3. When to terminate? Why optimal? Complexity?
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 X,+x 2 follows. (A tableau. st.-x1+x2+x3=1 =1+x1-x x1+x4=3 x 4 3-x1 x+x= 2 xe=2-x 2 x1,…x5≥0 Z=X1+x 2 The equalities are Ax =b 11100 A=10010,b=3 0100 et z=obj=x+x 2
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 follows A=10010,b=3 01001 1+x1-x Let z=obj=X1+x2 x 4 3-x1 B=3, 4, 5 is a basis x5=2-x2 Z=X1+x AB= I3 is non-singular 2 口Ag: columns:j∈B}ofA Set x1=x2=0, and get 1,xa=3,x=2 The basis is feasible Andz=0 ap b X n n2 Xn B 132 ≥0 1 2 3 4 0 001320
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=0b=x1+x2 follows clearly one needs to x3=1+x1-x2 Increase x1? x 4 3-x1 Lets say x x5=2-x2 Z=X1+x o we keep x=0 2 Set x1=x2=0, and get How much can we 1,xa=3,x=2 increase x,? Andz=0 a We need to maintain the first three equalities X n n2 Xn 1 2 3 4 001320
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 x2=1-x 1+x1-x x 3-x1 xe=2-x 2 xe=2-x 2 To maintain訕lx;≥0,We z=X1+x2 need x2≤1andx2≤2.■Setx1=0,x2=1,and o obtained from the first and update other variables third equalities above x3=0,x4=3,x5=1 So x can increase to and z =1 ■Andx2 becomes0 x1 x2 x3 x4 x5 01031
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