Examples of the Basic Simplex Method

The Basic Simplex Method has the following restrictions:
  1. All variables have non-negative values
  2. All Inequzlities, expressed in standard linear form, have the variable terms on the left side of the inequality
  3. The inequality is a "less than or equal to" ≤
  4. The constant on the right of the inequality is positive
  5. The task is to "maximize" an objective linear function of the given varaibles.
This page provides links to three sets of problems where each version of each problem is worked out, using the basic simplex method, in a step by step method. Follow the links for the different problems.
Problem 1: the inequalities for this are given as
1 x1 + 3 x2 ≤ 30
2 x1 + 3 x2 ≤ 33
1 x1 + 1 x2 ≤ 13
2 x1 + 1 x2 ≤ 21
3 x1 + 1 x2 ≤ 30
It would be possible and even reasonable to graph these inequalities and to find the corner points of the critical region. Using those corner points we could then evaluate the objective functions given below to find the coordinates of the point giving the largest objective value. However, the pages below demonstrate solving these situations using the basic simplex method.
  Solve to maximize 1 x1 + 2 x2 Solution at (3,9) max=21
  Solve to maximize 4 x1 + 5 x2 Solution at (6,7) max=59
  Solve to maximize 2 x1 + 1 x2 Solution at (9,3) max=21
  Solve to maximize 7 x1 + 2 x2 Solution at (10,0) max=70, note that the process does not give the value of x2 and we just take it as 0.
  Solve to maximize 5 x1 + 4 x2 Solution at (8,5) max=60
  Solve to maximize 1 x1 + 4 x2 Solution at (0,10) max=21, note that the process does not give the value of x1 and we just take it as 0.
Problem 2: the inequalities for this are given as
–3 x1 + 1 x2 ≤ 4
–1 x1 + 1 x2 ≤ 6
–1 x1 + 3 x2 ≤ 24
2 x1 + 3 x2 ≤ 42
3 x1 + 2 x2 ≤ 43
5 x1 + 2 x2 ≤ 65
It would be possible and even reasonable to graph these inequalities and to find the corner points of the critical region. Using those corner points we could then evaluate the objective functions given below to find the coordinates of the point giving the largest objective value. However, the pages below demonstrate solving these situations using the basic simplex method.
  Solve to maximize –4 x1 + 1 x2 Solution at (0,4) max=4, note that the process does not give the value of x1 and we just take it as 0.
  Solve to maximize –2 x1 + 1 x2 Solution at (1,7) max=5
  Solve to maximize –1 x1 + 2 x2 Solution at (3,9) max=21
  Solve to maximize –1 x1 + 4 x2 Solution at (6,10) max=34
  Solve to maximize 1 x1 + 4 x2 Solution at (6,10) max=46
  Solve to maximize 1 x1 + 1 x2 Solution at (9,8) max=17
  Solve to maximize 2 x1 + 1 x2 Solution at (11,5) max=27
  Solve to maximize 3 x1 + 1 x2 Solution at (13,0) max=39, note that the process does not give the value of x2 and we just take it as 0.
Problem 33: the inequalities for this are given as
–8 x1 + 3 x2 ≤ 12
–2 x1 + 9 x2 ≤ 99
–3 x1 + 7 x2 ≤ 56
4 x1 + 3 x2 ≤ 117
7 x1 + 4 x2 ≤ 191
Note that these inequalities cover more of the first quadrant, they have less "nice" boundary slopes than we have experienced, and their intersection does not necessarily have corner points at integer values. Therefore, althoughit would be possible to graph these inequalities and to find the corner points of the critical region, doing so will involve numerous fractional values. On the other hand, the pages below demonstrate solving these situations using the basic simplex method, which also will involve fractions, but we can deal with them via simple elementary row operations.
  Solve to maximize 11 x1 + 7 x2 Solution at (21,11) max=308
  Solve to maximize 1 x1 + 2 x2 Solution at (18,15) max=48
  Solve to maximize –5 x1 + 16 x2 Solution at (189/13,185/13) max=155

©Roger M. Palay
Saline, MI 48176
February, 2014