Example #1.) Initial Dictionary: z = 0.00 - 1.00 x1 + 1.00 x2 + 3.00 x3 ----------------------------------------------------------- x4 = 10.00 - 1.00 x1 x5 = 5.00 - 1.00 x2 x6 = 2.00 - 1.00 x3 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x4 basic): No upper bound row 2 (x5 basic): Upper bound = 5.0000 row 3 (x6 basic): No upper bound LEAVING VARIABLE: x5 NEW DICTIONARY: z = 5.00 - 1.00 x1 + 3.00 x3 - 1.00 x5 ----------------------------------------------------------- x4 = 10.00 - 1.00 x1 x2 = 5.00 - 1.00 x5 x6 = 2.00 - 1.00 x3 ENTERING VARIABLE: x3 RATIOS (for each constraint): row 1 (x4 basic): No upper bound row 2 (x2 basic): No upper bound row 3 (x6 basic): Upper bound = 2.0000 LEAVING VARIABLE: x6 NEW DICTIONARY: z = 11.00 - 1.00 x1 - 1.00 x5 - 3.00 x6 ----------------------------------------------------------- x4 = 10.00 - 1.00 x1 x2 = 5.00 - 1.00 x5 x3 = 2.00 - 1.00 x6 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 4,2,3 } Optimal Solution: x = ( 0 , 5 , 2, 10, 0, 0 ) Optimal Objective Value: z = 11 Example #2.) Flip the third constraint to get initial dictionary z = 0.00 + 3.00 x1 - 1.00 x2 --------------------------------------------- x3 = 8.00 - 1.00 x1 x4 = 10.00 - 1.00 x1 - 1.00 x2 x5 = 8.00 - 2.00 x1 + 1.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 8.0000 row 2 (x4 basic): Upper bound = 10.0000 row 3 (x5 basic): Upper bound = 4.0000 LEAVING VARIABLE: x5 NEW DICTIONARY: z = 12.00 + 0.50 x2 - 1.50 x5 --------------------------------------------- x3 = 4.00 - 0.50 x2 + 0.50 x5 x4 = 6.00 - 1.50 x2 + 0.50 x5 x1 = 4.00 + 0.50 x2 - 0.50 x5 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 8.0000 row 2 (x4 basic): Upper bound = 4.0000 row 3 (x1 basic): No upper bound LEAVING VARIABLE: x4 NEW DICTIONARY: z = 14.00 - 0.33 x4 - 1.33 x5 --------------------------------------------- x3 = 2.00 + 0.33 x4 + 0.33 x5 x2 = 4.00 - 0.67 x4 + 0.33 x5 x1 = 6.00 - 0.33 x4 - 0.33 x5 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 3,2,1 } Optimal Solution: x = ( 6, 4, 2, 0, 0 ) Optimal Objective Value: z = 14 Example #3.) Luckily, though we have an equality constraint, we have an isolated variable, x2. So divide that equation on both sides by 2 and use x2 and slack variable x4 in initial basis. Initial Dictionary: z = 0.00 + 2.00 x1 - 1.00 x3 --------------------------------------------- x2 = 10.00 - 2.00 x1 + 1.00 x3 x4 = 10.00 - 1.00 x1 - 1.00 x3 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x2 basic): Upper bound = 5.0000 row 2 (x4 basic): Upper bound = 10.0000 LEAVING VARIABLE: x2 NEW DICTIONARY: z = 10.00 - 1.00 x2 --------------------------------------------- x1 = 5.00 - 0.50 x2 + 0.50 x3 x4 = 5.00 + 0.50 x2 - 1.50 x3 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 1,4 } Optimal Solution: x = ( 5, 0, 0, 5 ) Optimal Objective Value: z = 10 Example #4.) Toss in three slack variables to get initial dictionary z = 0.00 + 1.00 x1 + 2.00 x2 --------------------------------------------- x3 = 40.00 - 4.00 x1 - 1.00 x2 x4 = 20.00 - 2.00 x1 - 1.00 x2 x5 = 10.00 - 1.00 x1 - 1.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 10.0000 row 2 (x4 basic): Upper bound = 10.0000 row 3 (x5 basic): Upper bound = 10.0000 LEAVING VARIABLE: x3 NEW DICTIONARY: z = 10.00 + 1.75 x2 - 0.25 x3 --------------------------------------------- x1 = 10.00 - 0.25 x2 - 0.25 x3 x4 = 0.00 - 0.50 x2 + 0.50 x3 x5 = 0.00 - 0.75 x2 + 0.25 x3 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x1 basic): Upper bound = 40.0000 row 2 (x4 basic): Upper bound = 0.0000 row 3 (x5 basic): Upper bound = 0.0000 LEAVING VARIABLE: x4 NEW DICTIONARY: (degenerate pivot) z = 10.00 + 1.50 x3 - 3.50 x4 --------------------------------------------- x1 = 10.00 - 0.50 x3 + 0.50 x4 x2 = 0.00 + 1.00 x3 - 2.00 x4 x5 = 0.00 - 0.50 x3 + 1.50 x4 ENTERING VARIABLE: x3 RATIOS (for each constraint): row 1 (x1 basic): Upper bound = 20.0000 row 2 (x2 basic): No upper bound row 3 (x5 basic): Upper bound = 0.0000 LEAVING VARIABLE: x5 NEW DICTIONARY: (degenerate pivot) z = 10.00 + 1.00 x4 - 3.00 x5 --------------------------------------------- x1 = 10.00 - 1.00 x4 + 1.00 x5 x2 = 0.00 + 1.00 x4 - 2.00 x5 x3 = 0.00 + 3.00 x4 - 2.00 x5 ENTERING VARIABLE: x4 RATIOS (for each constraint): row 1 (x1 basic): Upper bound = 10.0000 row 2 (x2 basic): No upper bound row 3 (x3 basic): No upper bound LEAVING VARIABLE: x1 NEW DICTIONARY: z = 20.00 - 1.00 x1 - 2.00 x5 --------------------------------------------- x4 = 10.00 - 1.00 x1 + 1.00 x5 x2 = 10.00 - 1.00 x1 - 1.00 x5 x3 = 30.00 - 3.00 x1 + 1.00 x5 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 4,2,3 } Optimal Solution: x = ( 0, 10, 30, 10, 0 ) Optimal Objective Value: z = 20 Example #5.) Toss in three slack variables to get Initial Dictionary: z = 0.00 - 2.00 x1 + 5.00 x2 + 1.00 x3 ----------------------------------------------------------- x4 = 6.00 - 1.00 x1 x5 = 6.00 - 2.00 x2 x6 = 12.00 - 3.00 x3 ENTERING VARIABLE: x2 (first j with positive cj-bar) RATIOS (for each constraint): row 1 (x4 basic): No upper bound row 2 (x5 basic): Upper bound = 3.0000 row 3 (x6 basic): No upper bound LEAVING VARIABLE: x5 NEW DICTIONARY: z = 15.00 - 2.00 x1 + 1.00 x3 - 2.50 x5 ----------------------------------------------------------- x4 = 6.00 - 1.00 x1 x2 = 3.00 - 0.50 x5 x6 = 12.00 - 3.00 x3 ENTERING VARIABLE: x3 RATIOS (for each constraint): row 1 (x4 basic): No upper bound row 2 (x2 basic): No upper bound row 3 (x6 basic): Upper bound = 4.0000 LEAVING VARIABLE: x6 NEW DICTIONARY: z = 19.00 - 2.00 x1 - 2.50 x5 - 0.33 x6 ----------------------------------------------------------- x4 = 6.00 - 1.00 x1 x2 = 3.00 - 0.50 x5 x3 = 4.00 - 0.33 x6 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 2,3,4 } Optimal Solution: x = ( 0, 3, 4, 6, 0, 0 ) Optimal Objective Value: z = 19 Example #6.) Flip the second constraint and introduce three slack variables to start with: z = 0.00 - 2.00 x1 + 1.00 x2 + 2.00 x3 ----------------------------------------------------------- x4 = 10.00 - 1.00 x1 - 1.00 x2 - 1.00 x3 x5 = 12.00 - 2.00 x1 - 1.00 x2 x6 = 15.00 - 1.00 x2 - 2.00 x3 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x4 basic): Upper bound = 10.0000 row 2 (x5 basic): Upper bound = 12.0000 row 3 (x6 basic): Upper bound = 15.0000 LEAVING VARIABLE: x4 NEW DICTIONARY: z = 10.00 - 3.00 x1 + 1.00 x3 - 1.00 x4 ----------------------------------------------------------- x2 = 10.00 - 1.00 x1 - 1.00 x3 - 1.00 x4 x5 = 2.00 - 1.00 x1 + 1.00 x3 + 1.00 x4 x6 = 5.00 + 1.00 x1 - 1.00 x3 + 1.00 x4 ENTERING VARIABLE: x3 RATIOS (for each constraint): row 1 (x2 basic): Upper bound = 10.0000 row 2 (x5 basic): No upper bound row 3 (x6 basic): Upper bound = 5.0000 LEAVING VARIABLE: x6 NEW DICTIONARY: z = 15.00 - 2.00 x1 - 1.00 x6 ----------------------------------------------------------- x2 = 5.00 - 2.00 x1 - 2.00 x4 + 1.00 x6 x5 = 7.00 + 2.00 x4 - 1.00 x6 x3 = 5.00 + 1.00 x1 + 1.00 x4 - 1.00 x6 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 2,5,3 } Optimal Solution: x = ( 0, 5, 5, 0, 7, 0 ) Optimal Objective Value: z = 15 Example #7.) Initial dictionary: z = 0.00 + 1.00 x1 + 1.00 x2 --------------------------------------------- x3 = 24.00 - 1.00 x1 - 3.00 x2 x4 = 16.00 - 1.00 x1 - 1.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 24.0000 row 2 (x4 basic): Upper bound = 16.0000 LEAVING VARIABLE: x4 NEW DICTIONARY: z = 16.00 - 1.00 x4 --------------------------------------------- x3 = 8.00 - 2.00 x2 + 1.00 x4 x1 = 16.00 - 1.00 x2 - 1.00 x4 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 3,1 } Optimal Solution: x = ( 16, 0, 8, 0) Optimal Objective Value: z = 16 Example #8.) Initial dictionary: z = 0.00 + 1.00 x1 + 3.00 x2 --------------------------------------------- x3 = 12.00 - 2.00 x1 - 1.00 x2 x4 = 8.00 - 1.00 x1 - 1.00 x2 x5 = 12.00 - 1.00 x1 - 2.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 6.0000 row 2 (x4 basic): Upper bound = 8.0000 row 3 (x5 basic): Upper bound = 12.0000 LEAVING VARIABLE: x3 NEW DICTIONARY: z = 6.00 + 2.50 x2 - 0.50 x3 --------------------------------------------- x1 = 6.00 - 0.50 x2 - 0.50 x3 x4 = 2.00 - 0.50 x2 + 0.50 x3 x5 = 6.00 - 1.50 x2 + 0.50 x3 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x1 basic): Upper bound = 12.0000 row 2 (x4 basic): Upper bound = 4.0000 row 3 (x5 basic): Upper bound = 4.0000 LEAVING VARIABLE: x4 (Bland's Rule: choose smaller subscript) NEW DICTIONARY: z = 16.00 + 2.00 x3 - 5.00 x4 --------------------------------------------- x1 = 4.00 - 1.00 x3 + 1.00 x4 x2 = 4.00 + 1.00 x3 - 2.00 x4 x5 = 0.00 - 1.00 x3 + 3.00 x4 ENTERING VARIABLE: x3 RATIOS (for each constraint): row 1 (x1 basic): Upper bound = 4.0000 row 2 (x2 basic): No upper bound row 3 (x5 basic): Upper bound = 0.0000 LEAVING VARIABLE: x5 NEW DICTIONARY: z = 16.00 + 1.00 x4 - 2.00 x5 --------------------------------------------- x1 = 4.00 - 2.00 x4 + 1.00 x5 x2 = 4.00 + 1.00 x4 - 1.00 x5 x3 = 0.00 + 3.00 x4 - 1.00 x5 ENTERING VARIABLE: x4 RATIOS (for each constraint): row 1 (x1 basic): Upper bound = 2.0000 row 2 (x2 basic): No upper bound row 3 (x3 basic): No upper bound LEAVING VARIABLE: x1 NEW DICTIONARY: z = 18.00 - 0.50 x1 - 1.50 x5 --------------------------------------------- x4 = 2.00 - 0.50 x1 + 0.50 x5 x2 = 6.00 - 0.50 x1 - 0.50 x5 x3 = 6.00 - 1.50 x1 + 0.50 x5 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 4,2,3 } Optimal Solution: x = ( 0, 6, 6, 2, 0 ) Optimal Objective Value: z = 18 Example #9.) Initial dictionary: z = 0.00 + 2.00 x1 - 1.00 x2 --------------------------------------------- x3 = 10.00 - 1.00 x1 + 2.00 x2 x4 = 14.00 - 1.00 x1 + 1.00 x2 x5 = 6.00 + 1.00 x1 - 1.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 10.0000 row 2 (x4 basic): Upper bound = 14.0000 row 3 (x5 basic): No upper bound LEAVING VARIABLE: x3 NEW DICTIONARY: z = 20.00 + 3.00 x2 - 2.00 x3 --------------------------------------------- x1 = 10.00 + 2.00 x2 - 1.00 x3 x4 = 4.00 - 1.00 x2 + 1.00 x3 x5 = 16.00 + 1.00 x2 - 1.00 x3 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x1 basic): No upper bound row 2 (x4 basic): Upper bound = 4.0000 row 3 (x5 basic): No upper bound LEAVING VARIABLE: x4 NEW DICTIONARY: z = 32.00 + 1.00 x3 - 3.00 x4 --------------------------------------------- x1 = 18.00 + 1.00 x3 - 2.00 x4 x2 = 4.00 + 1.00 x3 - 1.00 x4 x5 = 20.00 - 1.00 x4 ENTERING VARIABLE: x3 RATIOS: None. STOP: Problem is UNBOUNDED. Example #10.) Initial dictionary: z = 0.00 + 2.00 x1 + 3.00 x2 --------------------------------------------- x3 = 9.00 - 1.00 x1 + 2.00 x2 x4 = 15.00 - 4.00 x1 - 3.00 x2 x5 = 15.00 + 1.00 x1 - 2.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 9.0000 row 2 (x4 basic): Upper bound = 3.7500 row 3 (x5 basic): No upper bound LEAVING VARIABLE: x4 NEW DICTIONARY: z = 7.50 + 1.50 x2 - 0.50 x4 --------------------------------------------- x3 = 5.25 + 2.75 x2 + 0.25 x4 x1 = 3.75 - 0.75 x2 - 0.25 x4 x5 = 18.75 - 2.75 x2 - 0.25 x4 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x3 basic): No upper bound row 2 (x1 basic): Upper bound = 5.0000 row 3 (x5 basic): Upper bound = 6.8182 LEAVING VARIABLE: x1 NEW DICTIONARY: z = 15.00 - 2.00 x1 - 1.00 x4 --------------------------------------------- x3 = 19.00 - 3.67 x1 - 0.67 x4 x2 = 5.00 - 1.33 x1 - 0.33 x4 x5 = 5.00 + 3.67 x1 + 0.67 x4 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 3,2,5 } Optimal Solution: x = ( 0, 5, 19, 0, 5 ) Optimal Objective Value: z = 15 Example #11.) Initial dictionary: z = 0.00 + 3.00 x1 - 1.00 x2 --------------------------------------------- x3 = 10.00 - 1.00 x1 + 1.00 x2 x4 = 8.00 - 1.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 10.0000 row 2 (x4 basic): No upper bound LEAVING VARIABLE: x3 NEW DICTIONARY: z = 30.00 + 2.00 x2 - 3.00 x3 --------------------------------------------- x1 = 10.00 + 1.00 x2 - 1.00 x3 x4 = 8.00 - 1.00 x2 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x1 basic): No upper bound row 2 (x4 basic): Upper bound = 8.0000 LEAVING VARIABLE: x4 NEW DICTIONARY: z = 46.00 - 3.00 x3 - 2.00 x4 --------------------------------------------- x1 = 18.00 - 1.00 x3 - 1.00 x4 x2 = 8.00 - 1.00 x4 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 1,2 } Optimal Solution: x = ( 18, 8, 0, 0 ) Optimal Objective Value: z = 46 Example #12.) Initial dictionary: z = 0.00 + 3.00 x1 + 2.00 x2 --------------------------------------------- x3 = 30.00 + 1.00 x1 - 3.00 x2 x4 = 100.00 - 4.00 x1 + 1.00 x2 ENTERING VARIABLE: x1 RATIOS (for each constraint): row 1 (x3 basic): No upper bound row 2 (x4 basic): Upper bound = 25.0000 LEAVING VARIABLE: x4 NEW DICTIONARY: z = 75.00 + 2.75 x2 - 0.75 x4 --------------------------------------------- x3 = 55.00 - 2.75 x2 - 0.25 x4 x1 = 25.00 + 0.25 x2 - 0.25 x4 ENTERING VARIABLE: x2 RATIOS (for each constraint): row 1 (x3 basic): Upper bound = 20.0000 row 2 (x1 basic): No upper bound LEAVING VARIABLE: x3 NEW DICTIONARY: z = 130.00 - 1.00 x3 - 1.00 x4 --------------------------------------------- x2 = 20.00 - 0.36 x3 - 0.09 x4 x1 = 30.00 - 0.09 x3 - 0.27 x4 STOP: All cj-bar <= 0 so we have reached optimality. Optimal Basis: { 2,1 } Optimal Solution: x = ( 20, 30, 0, 0 ) Optimal Objective Value: z = 130