Problem: max z = 2 x1 - x2 + 3 x3 + x4 - x1 -2x2 + x3 + 2x4 <= 6 x1 - x3 + 2x4 >= 2 2 x1 + x2 - x3 - x4 <= 8 0 <= xj <=5 j=1,...,5 Initial Phase 1 Problem: max -w = -x0 ---------------------------------------------- -x1 - 2 x2 + x3 + 2 x4 + x5 = 6 x1 - x3 + 2 x4 - x6 + x0 = 2 2 x1 + x2 - x3 - x4 + x7 = 8 ---------------------------------------------- 2 x1 - x2 + 3 x3 + x4 = z ---------------------------------------------- 0 <= x_i i=0,1,...,7 x_i <= 5 i=1,...,4 Initial dictionary (Phase 1): z = 2 x1 - x2 + 3 x3 + x4 ---------------------------------- x0 = 2 - x1 + x3 - 2 x4 + x6 x5 = 6 + x1 + 2 x2 - x3 - 2 x4 x1=x2=x3=x4=0 x7 = 8 -2 x1 - x2 + x3 + x4 ---------------------------------- -w = -2 +x1 - x3 + 2 x4 - x6 ---------------------------------- Second dictionary (Phase 1): z = 4 + 5 x3 - 3 x4 + 2 x6 - 2 x0 - x2 ------------------------------------ x1 = 2 + x3 - 2 x4 + x6 - x0 x1=2, x2=x3=x4=0 x5 = 8 - 4 x4 + x6 - x0 + 2 x2 x7 = 4 - x3 + 5 x4 - 2 x6 + 2 x0 - x2 -------------------------------------- -w = -x0 Feasible! End of phase 1. Drop x0 and w x1 = 2 + x3 - 2 x4 + x6 x1=2, x2=x3=x4=0 x5 = 8 - 4 x4 + x6 + 2 x2 x7 = 4 - x3 + 5 x4 - 2 x6 - x2 -------------------------------------- z = 4+ 5 x3 - 3 x4 + 2 x6 - 2 x0 - x2 ------------------------------------------------------------------- First Phase 2 pivot: x3 = -2 + x1 + 2 x4 - x6 x5 = 8 +2 x2 - 4 x4 + x6 x1=5,x2=0,x3=3,x4=0 x7 = 6 - x1 - x2 + 3 x4 - x6 z=19 --------------------------------- z = -6 + 5 x1 - x2 + 7 x4 - 3 x6 Second Phase 2 pivot: x4 = 1 - 1/2 x1 + 1/2 x3 + 1/2 x6 x5 = 4 + 2 x1 + 2 x2 - 2 x3 - x6 x1=5,x2=0,x3=5,x4=1 x7 = 9 - 5/2 x1 - x2 + 3/2 x3 + 1/2 x6 z=26 ----------------------------------- z = 1 + 3/2 x1 - x2 + 7/2 x3 + 1/2 x6 ----------------------------------- Third Phase 2 pivot: x4 = 3 + 1/2 x1 + x2 - 1/2 x3 - 1/2 x5 x6 = 4 + 2 x1 + 2 x2 - 2 x3 - x5 x1=5,x2=0,x3=5,x4=3 x7 = 11 - 3/2 x1 + 1/2 x3 - 1/2 x5 z=28 ------------------------------------- z = 3 + 5/2 x1 + 5/2 x3 - 1/2 x5