
Operations Research  Linear Programming  Simplex Algorithm
by
Elmer G. Wiens
Egwald's popular web pages are provided without cost to users. Please show your support by joining Egwald Web Services as a Facebook Fan:
Follow Elmer Wiens on Twitter:
Graphical Solution 
Simplex Algorithm 
Primal Simplex Tableaux Generator 
Dual Simplex Algorithm 
Dual Simplex Tableaux Generator
Economics Application  Profit Maximization 
Economics Application  Least Cost Formula
example problem  l.p. standard form  basic simplex algorithm  algorithm validity primal simplex algorithm  unbounded & unfeasible problems  degeneracy  references
Solve an example problem.
Consider the following linear programming problem:
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} subject to
L1: 0.25 x_{1} + 1.0 x_{2} <= 65
L2: 1.25 x_{1} + 0.5 x_{2} <= 90
L3: 1.0 x_{1} + 1.0 x_{2} <= 85
x_{1} >= 0; x_{2} >= 0

Dual Linear Program
Minimize the Objective Function (D)
D = 65 y_{1} + 90 y_{2} + 85 y_{3} subject to
G1: 0.25 y_{1} + 1.25 y_{2} + 1.0 y_{3} >= 15
G2: 1.0 y_{1} + 0.5 y_{2} + 1.0 y_{3} >= 10
y_{1} >= 0; y_{2} >= 0; y_{3}= 0

This problem is solved on the graphical solution web page. The primal optimal program is x = (x_{1}, x_{2}) = (63.333, 21.667) yielding a value for the objective function P = 1166.67. The dual optimal program is y = (y_{1}, y_{2}, y_{3}) = (0, 6.67, 6.67), with an optimal value for the objective function D = 1166.67.
The Simplex L.P. Standard Form.
The above example can be stated as a particular set of data of the general canonical form.
A =

 a_{11} a_{12} 
 a_{21} a_{22} 
 a_{31} a_{32} 

=

 0.25 1.00 
 1.25 0.50 
 1.00 1.00 

I_{3} 
=

 1.00 0.00 0.00 
 0.00 1.00 0.00 
 0.00 0.00 1.00 

O_{3}  =   0   0   0  
b =   b_{1}   b_{2}   b_{3}  
=   65   90   85  
c =   c_{1}   c_{2}  
=   15   10  
x =   x_{1}   x_{2}  
s =   s_{1}   s_{2}   s_{3}  
y =   y_{1}   y_{2}   y_{3}  
t =   t_{1}   t_{2}  
The standard forms for the primal and dual problems can be stated with the slack variables s and t:
Primal Linear Program
Maximize the Objective Function (P)
P = c^{T} x subject to



Dual Linear Program
Minimize the Objective Function (D)
D = y^{T} b subject to


A x + s = b, x >= 0, s >= 0

y^{T} A  t^{T} = c^{T}, y >= 0, t >= 0

This example l.p. problem has the nice feature that all constraints are <= constraints, and the vector of RHS coefficients b >= 0.
The Basic Simplex Algorithm.
The algorithms used on this web page are based on the lecture notes of Rodrigo A. Restrepo.
The first version of the simplex algorithm exploits the special structure of the example l.p. problem. The standard form (augemented form of the simplex algorithm for the initial simplex tableau in the basic simplex algorithm is:
Initial Tableau 
b  A  I_{3}  O_{3} 
0  c^{T}  O_{3}^{T}  1 
Label rows & columns. Use the data from the example to fill in the initial tableau. Add two new columns: the column of row sums used to check arithmetic, and the column labelled b^{0} / x^{0}_{1} whose values are determined in step A. 2. below. (If you perform the simplex row operations on the column of row sums, and then check that each entry equals the sum of that row, you have a check on your arithmetic as you proceed with hand calculations.)
Simplex Tableau^{0} 

b^{0}  x^{0}_{1} 
x^{0}_{2}  s^{0}_{1} 
s^{0}_{2}  s^{0}_{3} 
e_{4}  row sum 
b^{0} / x^{0}_{1} 
L^{0}_{1} 
65  0.25 
1.00  1.00 
0.00  0.00 
0.00  67.25 
65 / .25 = 260.00 
L^{0}_{2} 
90  1.25 
0.50  0.00 
1.00  0.00 
0.00  92.75 
90 / 1.25 = 72.00 
L^{0}_{3} 
85  1.00 
1.00  0.00 
0.00  1.00 
0.00  88.00 
85 / 1.00 = 85.00 
P^{0} 
0.00  15 
10  0.00 
0.00  0.00 
1.00  24 

Tableau^{0} solution:
Variables s_{1}, s_{2}, s_{3} are the basic variables, since their columns are e_{1}^{T} = (1, 0, 0, 0), e_{2}^{T} = (0, 1, 0, 0), and e_{3}^{T} = (0, 0, 1, 0). The primal program is s^{T} = (65, 90, 85), with x^{T} = (0.00, 0.00). The primal objective function has the value P = c^{T}x = c_{1}x_{1} + c_{2}x_{2} = 0.00. The infeasible dual program (found in the bottom row) is t^{T} = (15, 10), and y^{T} = (0.00, 0.00, 0.00).
Proceed to the next tableau as follows:
A. In Tableau^{0}:
1. Since the coefficient of x_{1} in the last row, 15, is the most negative, x_{1} will enter the basis.
2. Compute the ratios b_{i} / x_{i,1} as per the last column: select the row with the smallest positive ratio, L_{2} = 72. Thus x_{2,1} = 1.25 is the pivot , and slack variable s_{2} will leave the basis.
B. To create Tableau^{1}:
3. Compute row L^{1}_{2} by dividing row L^{0}_{2} by the pivot = 1.25.
4. Subtract multiples of row L^{1}_{2} from all other rows of Tableau^{0} so that x^{1}_{1} = e_{2} in Tableau^{1}.
Notes:
1. Step A.2 ensures that b^{1} >= 0 after step B.4.
2. Step A.1 ensures that step B.4 adds a positive number to P^{0}: 1080 = 15*72 = 15 * (90 / 1.25) = c_{1} * b^{0}_{2} / x^{0}_{2,1}
3. The vector x^{0}_{1} = .25 s^{0}_{1} + 1.25 s^{0}_{2} + 1.0 s^{0}_{3}  15 e_{4}. Since the coefficient of s^{0}_{2}, 1.25, is not zero, x^{0}_{1} can replace s^{0}_{2} in the basis. Furthermore, the row operations of Step 3. and 4. do not change the status of vectors x^{0}_{1}, s^{0}_{1},s^{0}_{3}, and e_{4} as a basis of the Euclidean space E^{4}.
Simplex Tableau^{1} 

b^{1}  x^{1}_{1} 
x^{1}_{2}  s^{1}_{1} 
s^{1}_{2}  s^{1}_{3} 
e_{4}  row sum 
b^{1} / x^{1}_{2} 
L^{1}_{1} = L^{0}_{1}  .25 L^{1}_{2} 
47  0.00 
0.90  1.00 
0.20  0.00 
0.00  48.7 
47 / 0.9 = 52.222 
L^{1}_{2} = L^{0}_{2} / 1.25 
72  1.00 
0.40  0.00 
0.80  0.00 
0.00  74.2 
72 / 0.4 = 180.00 
L^{1}_{3} = L^{0}_{3}  1.0 L^{1}_{2} 
13  0.00 
0.60  0.00 
0.80  1.00 
0.00  13.80 
13 / 0.6 = 21.667 
P^{1} = P^{0}  (15.0) L^{1}_{2} 
1080.00  0.00 
4  0.00 
12  0.00 
1.00  1089 

Tableau^{1} solution:
Variables x_{1}, s_{1}, s_{3} are basic variables. The primal program is s^{T} = (47, 0, 13), with x^{T} = (72., 0.00). The primal objective function has the value P = c^{T}x = c_{1}x_{1} + c_{2}x_{2} = 15*72 + 4*0 = 1080.00. The infeasible dual program (found in the bottom row) is t^{T} = (0, 4), and y^{T} = (0.00, 12.00, 0.00).
Proceed to the next tableau as follows:
A. In Tableau^{1}:
1. Since the coefficient of x_{2} in the last row, 4, is the most negative, x_{2} will enter the basis.
2. Compute the ratios b_{i} / x_{i,2} as per the last column: select the row with the smallest positive ratio, L_{3} = 21.667. Thus x_{3,2} = 0.60 is the pivot , and slack variable s_{3} will leave the basis.
B. To create Tableau^{2}:
3. Compute row L^{2}_{3} by dividing row L^{1}_{3} by the pivot = 0.60.
4. Subtract multiples of row L^{2}_{3} from all other rows of Tableau^{1} so that x^{2}_{2} = e_{3} in Tableau^{2}.
Simplex Tableau^{2} 

b^{2}  x^{2}_{1} 
x^{2}_{2}  s^{2}_{1} 
s^{2}_{2}  s^{2}_{3} 
e_{4}  row sum 

L^{2}_{1} = L^{1}_{1}  0.90 L^{2}_{3} 
27.5  0.00 
0.00  1.00 
1.00  1.50 
0.00  28.0 

L^{2}_{2} = L^{1}_{2}  0.40 L^{2}_{3} 
63.333  1.00 
0.00  0.00 
1.333  0.667 
0.00  65.0 

L^{2}_{3} = L^{1}_{3} / 0.60 
21.667  0.00 
1.00  0.00 
1.333  1.667 
0.00  23.0 

P^{2} = P^{1}  (4.0) L^{2}_{3} 
1166.67  0.00 
0.00  0.00 
6.667  6.667 
1.00  1181 

Tableau^{2} solution:
Variables x_{1}, x_{2}, s_{1} are basic variables. The feasible primal program is s^{T} = (27.5, 0, 0), with x^{T} = (63.333, 21.667). The primal objective function has the value P = c^{T}x = c_{1}x_{1} + c_{2}x_{2} = 15*63.333 + 4*21.667 = 1111.67. The feasible dual program (found in the bottom row) is t^{T} = (0, 0), and y^{T} = (0.00, 6.667, 6.667).
Since these feasible programs satisfy the complementary slackness conditions:
t^{T}x = t_{1}x_{1} + t_{2}x_{2}= 0
y^{T}s = y_{1}s_{1} + y_{2}s_{2} + y_{3}s_{3} = 0,
they are optimal programs.
Notes:
1.0 In the Final Tableau, all the coefficients in the last row corresponding to the primal variables, x_{1} and x_{2}, and the slack variables are nonnegative. Therefore, the simplex algorithm terminates displaying the optimal primal and dual programs along with the optimal value of the objective function.
2.0 Each Tableau contains the unit vectors e_{1}, e_{2}, e_{3}, and e_{4} among its columns.
3.0 A given Tableau^{k} has the form:
Tableau^{k} 
ß  U  B  O_{3} 
µ  t^{T}  y^{T}  1 
4.0 The row operations performed on the matrix of each tableau are equivalent to premultiplying the tableau's matrix by some nonsingular matrix. Therefore, a nonsingular matrix B exists such that:
Tableau^{2} = B Tableau^{0}
Validity of the Simplex Algorithm.
In block matrix form, the last equation is:
Tableau^{2} 
ß  U  B  O_{3} 
µ  t^{T}  y^{T}  1 

= 
B 
Tableau^{0} 
b  A  I_{3}  O_{3} 
0  c^{T}  O_{3}^{T}  1 

where B is a 4 by 4 (in the example above) nonsingular matrix, i.e. B has an inverse. The last 2 by 2 block of matrices in this equation implies:
Substituting for B in the first matrix equation, the first 2 by 2 block of matrices implies that:

= 


= 
Bb  BA 
y^{T}b  y^{T}A  c^{T} 

Equating matrices yields:
1. ß = Bb, 2. U = BA, 3. µ = y^{T}b, 4. t^{T} = y^{T}A  c^{T} >= 0

Furthermore, since Tableau^{2} is the final tableau, y >= 0, so (y, t) is a feasible program for the dual problem.
By construction of Tableau^{0}, and since row operations preserve equations in subsequent tableaus:
Ux + Bs = ß > BAx + Bs = Bb
using 1. and 2. above. But B nonsingular implies the matrix B is nonsingular. Premultiplying by B's inverse yields:
Ax + s = b
Therefore, (x, s) is a feasible program for the primal problem.
Finally, the steps of the simplex algorithm rule that when a slack variable, s_{k}, is in the basis, the corresponding dual variable y_{k} = 0. If s_{k} is not in the basis, then s_{k} = 0. Therefore, complementary slackness obtains:
y^{T}s = 0.
Similarly, if a primal variable, x_{k} enters the basis (is not 0), then t_{k} = 0. Therefore, complementary slackness obtains:
t^{T}x = 0.
The pairs (x, s) and (y, t) are feasible and obey complementary slackness. Consequently, (x, s) is an optimal program for the primal problem, and (y, s) is an optimal program for the dual problem.
Example Block Matrices.
Look at Tableau^{2}, and note that the basic variables, s_{1}, x_{1}, x_{2}, plus the last column are the unit vectors e_{1}, e_{2}, e_{3}, e_{4}. Listing the columns corresponding to these variables in Tableau^{0} yields a matrix, call it A_{B}:
A_{B}  = 
s^{0}_{1} 
x^{0}_{1} 
x^{0}_{2} 
e_{4} 
1.00 
0.25 
1.00 
0.00 
0.00 
1.25 
0.50 
0.00 
0.00 
1.00 
1.00 
0.00 
0.00 
15 
10 
1.00 

Computing the inverse of A_{B} yields a matrix found in Tableau^{2}, namely B:
A_{B}^{1}  = 
s^{2}_{1} 
s^{2}_{2} 
s^{2}_{3} 
e_{4} 
1.00 
1.0 
1.50 
0.00 
0.00 
1.333 
0.6667 
0.00 
0.00 
1.333 
1.6667 
0.00 
0.00 
6.667 
6.667 
1.00 

=
 B 
Premultiplying Tableau^{0} by B yields Tableau^{2}.
The Primal Simplex Algorithm.
The basic simplex algorithm described above can be extended to handle a variety of complications, including = constraints with artificial variables, (Hadley, 108148). However, an algorithm developed by Dantzig et al. for implementation on computers handles these complications in a straightforward manner that is amenable to hand calculation. The standard form for the primal simplex method assumes all constraints are <=, or = constraints, but places no restrictions on the signs of the RHS b_{i} variables.
In the primal simplex algorithm, a sequence of tableaux are calculated. A given Tableau^{k} has the form:
Tableau^{k} 
ß  U  B  O_{3} 
µ  t^{T}  y^{T}  1 

= 

after consolidating the center 2 by 2 block of matrices.
This primal simplex algorithm uses a "threephase method":
Phase 0  drive all artificial variables (associated with = constraints) to zero, i.e. eliminate them from the basis;
Phase I  find a tableau with ß >= 0, i.e. a feasible primal program;
Phase II  generate tableaux that increase the value of µ, without dropping back into Phase 0 or I, until Ø >= 0 for all sign restricted variables, i.e. find a feasible primal program that maximizes the objective function.

The following example will be solved using the primal simplex algorithm (Restrepo, Linear Programming, 5866), to illustrate this technique.
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} + 15 x_{3} subject to
L1: 1.0 x_{1} + 1.0 x_{2} + 1.0 x_{3} <= 85
L2: 1.25 x_{1} + 0.5 x_{2} + 1.0 x_{3} <= 90
L3: 0.6 x_{1} + 1.0 x_{2} + 0.5 x_{3} = 51.5
x_{1} >= 0; x_{2} >= 0; x_{3} >= 0

Click to pop a new window with the primal and dual
l.p. problem displayed with the = constraint replaced with <= and >= constraints, and the solution obtained with the online l.p. solver.
The following diagram illustrates the constraints and the objective function at its maximum value.
PPlane passing through (81.667, 0, 0), (0, 122.5, 0), and (40, 10, 35) when P = 1225
L1plane passing through (63.33, 21.67, 0), (0, 85, 0), (0, 0, 85), and (20, 0, 65)
L2plane passing through (72, 0, 0), (63.33, 21.67, 0), and (20, 0, 65)
L3plane passing through (67.63, 10.92, 0), (0, 51.5, 0), and (40, 10, 35)
L1plane & L2plane intersect along the line passing through (63.33, 21.67, 0) and (20, 0, 65)
With P = 1225, the Pplane intersects the primal feasible set only at the point (40, 10, 35).

If necessary, multiply any = constraints by 1 to get the RHS negative, and introduce the slack variables into the statement of the problem. The variable s_{3} is an artificial variable, since the third constraint is an equation.
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} + 15 x_{3} subject to
L1: 1.0 x_{1} + 1.0 x_{2} + 1.0 x_{3} + s_{1} = 85
L2: 1.25 x_{1} + 0.5 x_{2} + 1.0 x_{3} + s_{2} = 90
L3: 0.6 x_{1}  1.0 x_{2}  0.5 x_{3} + s_{3} = 51.5
x_{1} >= 0; x_{2} >= 0; x_{3} >= 0
s_{1} >= 0; s_{2} >= 0; s_{3} >= 0

Dual Linear Program
Minimize the Objective Function (D)
D = 85 y_{1} + 90 y_{2}  51.5 y_{3} subject to
G1: 1.0 y_{1} + 1.25 y_{2}  0.6 y_{3}  t_{1} = 15
G2: 1.0 y_{1} + 0.5 y_{2}  1.0 y_{3}  t_{2} = 10
G3: 1.0 y_{1} + 1.0 y_{2}  0.5 y_{3}  t_{3} = 15
y_{1} >= 0; y_{2} >= 0; y_{3} sign unrestriced
t_{1} >= 0; t_{2} >= 0; t_{3} >= 0

The standard form for the initial primal simplex tableau is:
Initial Tableau 
b  A  I_{3}  O_{3} 
0  c^{T}  O_{3}^{T}  1 
Label rows & columns. Use the data from the example to fill in the initial tableau. Label column s_{3} with a * to indicate that it is an artificial variable. Add two new columns: the column of row sums used to check arithmetic, and the column labelled b / x_{k}, that will be used in Phases I and II.
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
x^{0}_{3} 
s^{0}_{1} 
s^{0}_{2} 
s^{0}_{3}* 
e_{4} 
row sum 
b / x_{k} 
L^{0}_{1} 
85  1.00 
1.00  1.00 
1.00  0.00 
0.00  0.00 
89  
L^{0}_{2} 
90  1.25 
0.50  1.00 
0.00  1.00 
0.00  0.00 
93.75  
L^{0}_{3} 
51.5  0.60 
1.00  0.50 
0.00  0.00 
1.00  0.00 
52.6  
P^{0} 
0.00  15 
10  15 
0.00  0.00 
0.00  1.00 
39  
Tableau^{0} solution:
Variables s_{1}, s_{2}, s_{3} are the basic variables, since their columns are e_{1}^{T} = (1, 0, 0, 0), e_{2}^{T} = (0, 1, 0, 0), and e_{3}^{T} = (0, 0, 1, 0). The primal program is s^{T} = (85, 90, 51.5), with x^{T} = (0.00, 0.00, 0.00). The primal objective function has the value P = c^{T}x = c_{1}x_{1} + c_{2}x_{2} + c_{3}x_{3} = 0.00.
Proceed to the next tableau as follows:
Phase 0. Drive the artificial variables from the basis.
A. In Tableau^{0}:
1. Select an artificial variable in the basis: s^{*}_{3} = e_{3}.
2. Select a nonzero element in row L3 as pivot: x_{3,1} = .6. (I repeat the simplex algorithm with x_{3,2} = 1 as the pivot below.)
B. To Create Tableau^{1}:
3. Compute row L^{1}_{3} = L^{0}_{3} / (0.6).
4. Subtract multiples of row L^{1}_{3} from all other rows of Tableau^{0} so that x^{1}_{1} = e_{3} in Tableau^{1}.
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
x^{1}_{3} 
s^{1}_{1} 
s^{1}_{2} 
s^{1}_{3}* 
e_{4} 
row sum 
b^{1} / x^{1}_{2} 
L^{1}_{1} = L^{0}_{1}  1.0 L^{1}_{3} 
0.8333  0.00 
0.6667  0.1667 
1.00  0.00 
1.667  0.00 
1.3334  1.25 
L^{1}_{2} = L^{0}_{2}  1.25 L^{1}_{3} 
17.292  0.00 
1.5834  0.0416 
0.00  1.00 
2.0834  0.00 
15.8333  10.9 
L^{1}_{3} = L^{0}_{3} / (0.6) 
85.8333  1.00 
1.6667  0.8333 
0.00  0.00 
1.6667  0.00 
87.6667  51.49 
P^{1} = P^{0}  (15) L^{1}_{3} 
1287.5  0.00 
15  2.5 
0.00  0.00 
25  1.00 
1276  
Tableau^{1} solution:
Basis: x_{1}, s_{1}, s_{2}.
The primal unfeasible program: x^{T} = (85.8333, 0.00, 0.00); s^{T} = (0.8333, 17.292, 0).
The primal objective function has the value P = 1287.5.
Proceed to the next tableau as follows: Since the artificial variable s^{*}_{3} associated with the = constraint is not in the basis, Phase 0 is complete.
Phase I. Since b^{1}_{1} and b^{1}_{2} are negative, the algorithm is in Phase I.
Goal: Generate a feasible program so that b >= 0.
A. In Tableau^{1}:
1. Select a target row, r, with b_{r} < 0: b^{1}_{2} = 17.292, r = 2.
2. Select any column, col, with a negative entry in row 2 as the pivot column: col = 2 associated with variable x_{2}, x_{2,2} = 1.5834.
3. Compute the ratios b_{i} / x_{i,2} as per the last column.
Select the row with the smallest positive ratio: L_{1} = 1.25. Thus x_{1,2} = 0.6667 is the pivot; slack variable s_{1} will leave the basis; x_{2} will enter the basis.
To Create Tableau^{2}:
4. Compute row L^{2}_{1} = L^{1}_{1} / (0.6667).
5. Subtract multiples of row L^{2}_{1} from all other rows of Tableau^{1} so that x^{2}_{2} = e_{1} in Tableau^{2}.
Tableau^{2} 

b^{2} 
x^{2}_{1} 
x^{2}_{2} 
x^{2}_{3} 
s^{2}_{1} 
s^{2}_{2} 
s^{2}_{3}* 
e_{4} 
row sum 
b^{2} / x^{2}_{3} 
L^{2}_{1} = L^{1}_{1} / ( 0.6667) 
1.25  0.00 
1.00  .25 
1.5  0.00 
2.5  0.00 
2  5 
L^{2}_{2} = L^{1}_{2}  (0.15834) L^{2}_{1} 
15.313  0.00 
0.00  0.4375 
2.375  1.00 
1.875  0.00 
19  35 
L^{2}_{3} = L^{1}_{3}  1.6667 L^{2}_{1} 
83.75  1.00 
0.00  1.25 
2.5  0.00 
2.5  0.00 
91  67 
P^{2} = P^{1}  15 L^{2}_{1} 
1268.75  0.00 
0.00  1.25 
22.5  0.00 
12.5  1.00 
1306  
Tableau^{2} solution:
Basis: x_{1}, x_{2}, s_{2}.
The primal unfeasible program: x^{T} = (83.75, 1.25, 0.00); s^{T} = (0, 15.313, 0).
The primal objective function has the value P = 1268.75.
Proceed to the next tableau as follows:
Phase I. Since b^{2}_{2} is negative, the algorithm is in Phase I.
Goal: Generate a feasible program so that b >= 0.
A. In Tableau^{2}:
1. Select a target row, r, with b_{r} < 0: b^{2}_{2} = 15.313, r = 2.
2. Select any column, col, with a negative entry in row 2 as the pivot column: col = 3 associated with variable x_{3}, x_{2,3} = 0.4375.
3. Compute the ratios b_{i} / x_{i,3} as per the last column.
Select the row with the smallest positive ratio: L_{2} = 35. Thus x_{2,3} = 0.4375 is the pivot; slack variable s_{2} will leave the basis; x_{3} will enter the basis.
To Create Tableau^{3}:
4. Compute row L^{3}_{2} = L^{2}_{2} / (0.4375).
5. Subtract multiples of row L^{3}_{2} from all other rows of Tableau^{2} so that x^{3}_{3} = e_{2} in Tableau^{3}.
Tableau^{3} 

b^{3} 
x^{3}_{1} 
x^{3}_{2} 
x^{3}_{3} 
s^{3}_{1} 
s^{3}_{2} 
s^{3}_{3}* 
e_{4} 
row sum 

L^{3}_{1} = L^{2}_{1}  0.25 L^{3}_{2} 
10  0.00 
1.00  0.00 
0.1429  0.5714 
1.4286  0.00 
8.857  
L^{3}_{2} = L^{2}_{2} / (0.4375) 
35  0.00 
0.00  1.00 
5.4286  2.2857 
4.2857  0.00 
43.43  
L^{3}_{3} = L^{2}_{3}  1.25 L^{3}_{2} 
40  1.00 
0.00  0.00 
4.2857  2.8571 
2.8571  0.00 
36.71  
P^{3} = P^{2}  1.25 L^{3}_{2} 
1225  0.00 
0.00  0.00 
15.7143  2.8571 
7.1429  1.00 
1251.71  
Tableau^{3} solution:
Basis: x_{1}, x_{2}, x_{3}.
The primal feasible program: x^{T} = (40, 10, 35); s^{T} = (0, 0, 0).
The primal objective function has the value P = 1225.
For this tableau, b >= 0, the artificial variable, s^{*}_{3}, is not in the basis, and all entries in the last row corresponding to the variables x_{1}, x_{2}, x_{3}, s_{1}, and s_{2} are nonnegative.
The primal simplex algorithm terminates without proceeding to Phase II, since all conditions of Phase I and II are satisfied.
The optimal programs are:
x = (40, 10, 35), s = (0, 0, 0); y = (15.71, 2.86, 7.14), t = (0, 0, 0); P = 1225.
To demonstrate Phase II of the primal simplex algorithm, begin with Tableau^{0} above, but use x_{3,2} = 1 as the pivot.
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
x^{0}_{3} 
s^{0}_{1} 
s^{0}_{2} 
s^{0}_{3}* 
e_{4} 
row sum 
b / x_{k} 
L^{0}_{1} 
85  1.00 
1.00  1.00 
1.00  0.00 
0.00  0.00 
89  
L^{0}_{2} 
90  1.25 
0.50  1.00 
0.00  1.00 
0.00  0.00 
93.75  
L^{0}_{3} 
51.5  0.60 
1.00  0.50 
0.00  0.00 
1.00  0.00 
52.6  
P^{0} 
0.00  15 
10  15 
0.00  0.00 
0.00  1.00 
39  
Proceed to the next tableau as follows:
Phase 0. Drive the artificial variables from the basis.
A. In Tableau^{0}:
1. Select an artificial variable in the basis: s^{*}_{3} = e_{3}.
2. Select a nonzero element in row L3 as pivot: x_{3,2} = 1
B. To Create Tableau^{1}:
3. Compute row L^{1}_{3} = L^{0}_{3} / (1.0).
4. Subtract multiples of row L^{1}_{3} from all other rows of Tableau^{0} so that x^{1}_{2} = e_{3} in Tableau^{1}.
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
x^{1}_{3} 
s^{1}_{1} 
s^{1}_{2} 
s^{1}_{3}* 
e_{4} 
row sum 
b^{1} / x^{1}_{3} 
L^{1}_{1} = L^{0}_{1}  1.0 L^{1}_{3} 
33.5  0.40 
0.00  0.5 
1.00  0.00 
1.00  0.00 
36.4  67 
L^{1}_{2} = L^{0}_{2}  0.5 L^{1}_{3} 
64.25  0.95 
0.00  0.75 
0.00  1.00 
0.50  0.00 
67.45  85.7 
L^{1}_{3} = L^{0}_{3} / (1.0) 
51.5  0.6 
1.0  0.5 
0.00  0.00 
1.0  0.00 
52.6  103 
P^{1} = P^{0}  (10) L^{1}_{3} 
515  9.0 
0  10 
0.00  0.00 
10  1.00 
487  
Tableau^{1} solution:
Basis: x_{2}, s_{1}, s_{2}.
The primal feasible program: x^{T} = (0.00, 51.5, 0.00); s^{T} = (33.5, 64.25, 0).
The primal objective function has the value P = 515.
Proceed to the next tableau as follows:
Phase 0 is complete: The artificial variable s^{*}_{3} = 0.
Phase I is complete: b = ß >= 0.
Phase II. Similar to the Basic Simplex Algorithm: try to increase the value of P = µ by obtaining nonnegative entries in Ø (the last row) for the signrestricted primal and slack variables.
A. In Tableau^{1}:
1. Since the coefficient of x_{3} in the last row, 10, is the most negative, x_{3} will enter the basis.
2. Compute the ratios b_{i} / x_{i,3} as per the last column: select the row with the smallest positive ratio, L_{1} = 67. Thus x_{1,3} = 0.5 is the pivot , and slack variable s_{1} will leave the basis.
B. To create Tableau^{2}:
3. Compute row L^{2}_{1} by dividing row L^{1}_{1} by the pivot = 0.5.
4. Subtract multiples of row L^{2}_{1} from all other rows of Tableau^{1} so that x^{2}_{3} = e_{1} in Tableau^{2}.
Tableau^{2} 

b^{2} 
x^{2}_{1} 
x^{2}_{2} 
x^{2}_{3} 
s^{2}_{1} 
s^{2}_{2} 
s^{2}_{3}* 
e_{4} 
row sum 
b^{2} / x^{2}_{1} 
L^{2}_{1} = L^{1}_{1} / (0.5) 
67  0.8 
0.00  1.00 
2.0  0.00 
2.0  0.00 
72.8  83.75 
L^{2}_{2} = L^{1}_{2}  0.75 L^{2}_{1} 
14  0.35 
0.00  0.00 
1.50  1.00 
1.00  0.00 
12.85  40 
L^{2}_{3} = L^{1}_{3}  0.5 L^{2}_{1} 
18  0.20 
1.00  0.00 
1.00  0.00 
2.00  0.00 
16.2  90 
P^{2} = P^{1}  (10) L^{2}_{1} 
1185  1.00 
0.00  0.00 
20.0  0.00 
10.0  1.00 
1215  
Tableau^{2} solution:
Basis: x_{2}, x_{3}, s_{2}.
The primal program: x^{T} = (0.00, 18, 67); s^{T} = (0, 14.0, 0).
The primal objective function has the value P = 1185.
Proceed to the next tableau as follows:
Phase II. The last row, Ø, still has a negative entry.
A. In Tableau^{2}:
1. Since the coefficient of x_{1} in the last row, 1, is negative, x_{1} will enter the basis.
2. Compute the ratios b_{i} / x_{i,1} as per the last column: select the row with the smallest positive ratio, L_{2} = 40. Thus x_{2,1} = 0.35 is the pivot , and slack variable s_{2} will leave the basis.
B. To create Tableau^{3}:
3. Compute row L^{3}_{2} by dividing row L^{2}_{2} by the pivot = 0.35.
4. Subtract multiples of row L^{3}_{2} from all other rows of Tableau^{2} so that x^{3}_{2} = e_{2} in Tableau^{3}.
Tableau^{3} 

b^{3} 
x^{3}_{1} 
x^{3}_{2} 
x^{3}_{3} 
s^{3}_{1} 
s^{3}_{2} 
s^{3}_{3}* 
e_{4} 
row sum 

L^{3}_{1} = L^{2}_{1}  0.8 L^{3}_{2} 
35  0.00 
0.00  1.00 
5.4286  2.2857 
4.2857  0.00 
43.43  
L^{3}_{2} = L^{2}_{2} / (0.35) 
40  1.00 
0.00  0.00 
4.2856  2.857 
2.857  0.00 
36.71  
L^{3}_{3} = L^{2}_{3}  0.2 L^{3}_{2} 
10  0.00 
1.00  0.00 
0.1429  0.5714 
1.4286  0.00 
8.857  
P^{3} = P^{2}  (1) L^{3}_{2} 
1225  0.00 
0.00  0.00 
15.7143  2.8571 
7.1429  1.00 
1251.71  
Tableau^{3} solution:
For this tableau, b >= 0, the artificial variable, s^{*}_{3}, is not in the basis, and all entries in the last row corresponding to the variables x_{1}, x_{2}, x_{3}, s_{1}, and s_{2} are nonnegative. The primal simplex algorithm terminates.
Basis: x_{1}, x_{2}, x_{3}.
The primal feasible program: x^{T} = (40, 10, 35); s^{T} = (0, 0, 0).
The primal objective function has the value P = 1225.
The optimal programs are:
x = (40, 10, 35), s = (0, 0, 0); y = (15.71, 2.86, 7.14), t = (0, 0, 0); P = 1225.
Unbounded and Unfeasible Problems.
As shown on the graphical web page,
the next example has an unbounded primal solution, with an unfeasible dual problem.
Primal Linear Program
Maximize the Objective Function (P)
P = 15 x_{1} + 10 x_{2} subject to
L1: 0 x_{1} + 1.0 x_{2} <= 50
L2: 1.5 x_{1} + 1.0 x_{2} <= 20
x_{1} >= 0; x_{2} >= 0

Dual Linear Program
Minimize the Objective Function (D)
D = 50 y_{1}  20 y_{2} subject to
G1: 0 y_{1}  1.5 y_{2} >= 15
G2: 1.0 y_{1} + 1.0 y_{2} >= 10
y_{1} >= 0; y_{2} >= 0

To solve this problem using the primal simplex algorithm, set up the initial tableau as usual:
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
s^{0}_{1} 
s^{0}_{2} 
e_{3} 
row sum 
b / x_{1} 
L^{0}_{1} 
50  0.00 
1.00  1.00 
0.00  0.00 
52  infinity 
L^{0}_{2} 
20  1.5 
1.00  0.00 
1.00  0.00 
19.5  13.3 
P^{0} 
0.00  15 
10  0.00 
0.00  1.00 
24  
Phase 0: Complete since there are no artificial variables.
Phase I: Since b^{0}_{2} = 20 <= 0, the algorithm is in Phase I.
Goal: Generate a feasible program so that b >= 0.
A. In Tableau^{0}:
1. Select a target row, r, with b_{r} < 0: b^{0}_{2} = 20, r = 2.
2. Select any column, col, with a negative entry in row 2 as the pivot column: col = 1 associated with variable x_{1}, x_{2,1} = 1.5.
3. Compute the ratios b_{i} / x_{i,3} as per the last column.
Select the row with the smallest positive ratio: L_{2} = 13.3. Thus x_{2,1} = 1.5 is the pivot; slack variable s_{2} will leave the basis; x_{2} will enter the basis.
To Create Tableau^{1}:
4. Compute row L^{1}_{2} = L^{0}_{2} / (1.5).
5. Subtract multiples of row L^{1}_{2} from all other rows of Tableau^{0} so that x^{1}_{2} = e_{2} in Tableau^{1}.
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
s^{1}_{1} 
s^{1}_{2} 
e_{3} 
row sum 
b / x_{2} 
L^{1}_{1} = L^{0}_{1}  0 L^{1}_{2} 
50  0.00 
1.00  1.00 
0.00  0.00 
52  50 
L^{1}_{2} = L^{0}_{2} / (1.5) 
13.333  1.00 
0.667  0.00 
0.667  0.00 
13  20 
P^{1} = P^{0}  (15) L^{1}_{2} 
200  0.00 
20.005  0.00 
10.005  1.00 
171  
Phase I is complete: b = ß >= 0.
Phase II. Try to increase the value of P = µ = 200 by eliminating negative entries from the last row.
A. In Tableau^{1}:
1. Since the coefficient of x_{2} in the last row, 20.005, is the most negative, x_{2} will enter the basis.
2. Compute the ratios b_{i} / x_{i,2} as per the last column: select the row with the smallest positive ratio, L_{1} = 50. Thus x_{1,2} = 1.0 is the pivot , and slack variable s_{1} will leave the basis.
B. To create Tableau^{2}:
3. Compute row L^{2}_{1} by dividing row L^{1}_{1} by the pivot = 1.0.
4. Subtract multiples of row L^{2}_{1} from all other rows of Tableau^{1} so that x^{2}_{2} = e_{1} in Tableau^{2}.
Tableau^{2} 

b^{2} 
x^{2}_{1} 
x^{2}_{2} 
s^{2}_{1} 
s^{2}_{2} 
e_{3} 
row sum 
b / s_{2} 
L^{2}_{1} = L^{1}_{1} / 1 
50  0.00 
1.00  1.00 
0.00  0.00 
52  infinity 
L^{2}_{2} = L^{1}_{2}  (0.667) L^{2}_{1} 
46.667  1.00 
0.00  0.667 
0.667  0.00 
47.67  71.46 
P^{2} = P^{1}  (20.005) L^{2}_{1} 
1200.25  0.00 
0.00  20.005 
10.005  1.00 
1211.25  
Phase I is complete: b = ß >= 0.
Phase II. The coefficient of s_{2} = 10.005 in the last row.
A. In Tableau^{2}:
1. Since the coefficient of s_{2} in the last row is 10.005, s_{2} will enter the basis.
2. Compute the ratios b_{i} / s_{i,2} as per the last column. The smallest positive ratio, L_{1} = infinity. No suitable ratio exists. ==>> P is unbounded.
As the following diagram shows, the objective function P is unbounded since it intersects the feasible set for any large positive number = P.
Degeneracy and Cycling.
The primal simplex algorithm calculates a sequence of tableaus. The algorithm breaks down when in a given Tableau^{k}:
Tableau^{k} 
ß  U  B  O_{3} 
µ  t^{T}  y^{T}  1 

= 

a zero entry appears in the ß column and/or in the Ø row for a variable that is not one of the standard basis variables.
The example from N. Paul Loomba (152) illustrates the degeneracy problem.
Primal Linear Program
Maximize the Objective Function (P)
P = 22 x_{1} + 30 x_{2} + 25 x_{3} subject to
L1: 2 x_{1} + 2 x_{2} + 0 x_{3} <= 100
L2: 2 x_{1} + 1 x_{2} + 1 x_{3} <= 100
L3: 1 x_{1} + 2 x_{2} + 2 x_{3} <= 100
x_{1} >= 0; x_{2} >= 0; x_{3} >= 0

The three dimensional diagram shows how the three restraining planes intersect at the point (33.33, 16.67, 16.67).
PPlane passing through (75, 0, 0), (0, 55, 0), (0, 0, 66), and (33.33, 16.67, 16.67) when P = 1650
L1plane passing through (50, 0, 0), (0, 50, 0) perpendicular to the X1X2 plane
L2plane passing through (50, 0, 0), (0, 100, 0), and (0, 0, 100)
L3plane passing through (100, 0, 0), (0, 50, 0), and (0, 0, 50)
L1 & L2 planes intersect along the line through (50, 0, 0), (33.33, 16.67, 16.67), and (0, 50, 50)
L1 & L3 planes intersect along the line through (50, 0, 25), (33.33, 16.67, 16.67), and (0, 50, 0)
L2 & L3 planes intersect along the line through (33.33, 33.33, 0), (33.33, 16.67, 16.67), and (33.33, 0, 33.33)
With P = 1650, the Pplane intersects the primal feasible set only at the point (33.33, 16.67, 16.67).

This problem's initial tableau is:
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
x^{0}_{3} 
s^{0}_{1} 
s^{0}_{2} 
s^{0}_{3} 
e_{4} 
row sum 
b / x_{2} 
L^{0}_{1} 
100  2.0 
2.0  0.0 
1.00  0.00 
0.00  0.00 
105.0  50.0 
L^{0}_{2} 
100  2.0 
1.0  1.0 
0.00  1.00 
0.00  0.00 
105.0  100.0 
L^{0}_{3} 
100  1.0 
2.0  2.0 
0.00  0.00 
1.00  0.00 
106.0  50.0 
P^{0} 
0.00  22 
30  25 
0.00  0.00 
0.00  1.00 
76.00  
The pivot column is 2, since 30 is the most negative Ø entry; the pivot row is 1, since 50.0 is the smallest b / x_{2} ratio; and the pivot = 2. However, row L^{0}_{3} also has a 50.0 = b / x_{2} ratio. Applying the primal simplex algorithm yields the next tableau:
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
x^{1}_{3} 
s^{1}_{1} 
s^{1}_{2} 
s^{1}_{3} 
e_{4} 
row sum 
b / x_{3} 
L^{1}_{1} = L^{0}_{1} / 2 
50.00  1.00 
1.00  0.00 
0.50  0.00 
0.00  0.00 
52.50  infinity 
L^{1}_{2} = L^{0}_{2}  1 L^{1}_{1} 
50.00  1.00 
0.00  1.00 
0.50  1.00 
0.00  0.00 
52.50  50.0 
L^{1}_{3} = L^{0}_{3}  2 L^{1}_{1} 
0.00  1.00 
0.00  2.00 
1.00  0.00 
1.00  0.00 
1.00  0.00 
P^{1} = P^{0}  (30) L^{1}_{1} 
1500.00  8.00 
0.00  25.00 
15.00  0.00 
0.00  1.00 
1499.00  
The variable x_{2} has replaced s_{1} in the basis. But ß_{3} = b^{1}_{3} = 0.0  the tableau is degenerate.
Charnes perturbation procedure resolves the degeneracy problem by adding small constants to the RHS of the constraints. Letting € = .1, the RHS vector b becomes:
b_{p} = (b_{1}+€, b_{2}+€^{2}, b_{3}+€^{3})'
The perturbed problem's initial tableau is:
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
x^{0}_{3} 
s^{0}_{1} 
s^{0}_{2} 
s^{0}_{3} 
e_{4} 
row sum 
b / x_{2} 
L^{0}_{1} 
100.1  2.0 
2.0  0.0 
1.00  0.00 
0.00  0.00 
105.1  50.05 
L^{0}_{2} 
100.01  2.0 
1.0  1.0 
0.00  1.00 
0.00  0.00 
105.01  100.01 
L^{0}_{3} 
100.001  1.0 
2.0  2.0 
0.00  0.00 
1.00  0.00 
106.001  50.0005 
P^{0} 
0.00  22 
30  25 
0.00  0.00 
0.00  1.00 
76.00  
The pivot column is 2, since 30 is the most negative Ø entry; the pivot row is 3, since 50.005 is the smallest b / x_{2} ratio; and the pivot = 2. Applying the primal simplex algorithm yields the next tableau:
Tableau^{1} 

b^{1} 
x^{1}_{1} 
x^{1}_{2} 
x^{1}_{3} 
s^{1}_{1} 
s^{1}_{2} 
s^{1}_{3} 
e_{4} 
row sum 
b / x_{1} 
L^{1}_{1} = L^{0}_{1}  2 L^{1}_{3} 
0.099  1.00 
0.00  2.00 
1.00  0.00 
1.00  0.00 
0.901  0.099 
L^{1}_{2} = L^{0}_{2}  2 L^{1}_{3} 
50.0095  1.50 
0.00  0.00 
0.00  1.00 
0.50  0.00 
52.0095  33.3397 
L^{1}_{3} = L^{0}_{3} / 2 L^{1}_{1} 
50.0005  0.50 
1.00  1.00 
0.00  0.00 
0.50  0.00 
53.0005  100.001 
P^{1} = P^{0}  (30) L^{1}_{1} 
1500.015  7.00 
0.00  5.00 
0.00  0.00 
15.00  1.00 
1514.015  
Because of the b^{0} vector was perturbed, no zero appears in the b^{1} vector.
The variable x_{2} has replaced the slack variable s_{3} in the basis.
The pivot column is 1, since 7 is the most negative Ø entry; the pivot row is 1, since 0.0990 is the least positive b / x_{1} ratio; and the pivot = 1. Applying the primal simplex algorithm yields:
Tableau^{2} 

b^{2} 
x^{2}_{1} 
x^{2}_{2} 
x^{2}_{3} 
s^{2}_{1} 
s^{2}_{2} 
s^{2}_{3} 
e_{4} 
row sum 
b / x_{3} 
L^{2}_{1} = L^{1}_{1} / 1 
0.099  1.00 
0.00  2.00 
1.00  0.00 
1.00  0.00 
0.901  0.0495 
L^{2}_{2} = L^{1}_{2}  1.5 L^{2}_{1} 
49.861  0.00 
0.00  3.00 
1.50  1.00 
1.00  0.00 
53.361  16.6203 
L^{2}_{3} = L^{1}_{3}  0.5 L^{2}_{1} 
49.951  0.00 
1.00  2.00 
0.50  0.00 
1.00  0.00 
53.451  24.9755 
P^{1} = P^{0}  (7) L^{2}_{1}> 
1500.708  0.00 
0.00  9.00 
7.00  0.00 
8.00  1.00 
1507.080  
The variable x_{1} has replaced the slack variable s_{1} in the basis.
The pivot column is 3, since 9 is the most negative Ø entry; the pivot row is 2, since 16.6201 is the least positive b / x_{3} ratio; and the pivot = 3. Applying the primal simplex algorithm yields:
Tableau^{3} 

b^{3} 
x^{3}_{1} 
x^{3}_{2} 
x^{3}_{3} 
s^{3}_{1} 
s^{3}_{2} 
s^{3}_{3} 
e_{4} 
row sum 

L^{3}_{1} = L^{2}_{1}  (2) L^{3}_{2} 
33.3397  1.00 
0.00  0.00 
0.00  0.6667 
0.3333  0.00 
34.673  
L^{3}_{2} = L^{2}_{2} / 2 
16.6203  0.00 
0.00  1.00 
0.50  0.3333 
0.3333  0.00 
17.787  
L^{3}_{3} = L^{2}_{3}  2 L^{3}_{2} 
16.7103  0.00 
1.00  0.00 
0.50  0.6667 
0.3333  0.00 
17.877  
P^{1} = P^{0}  (9) L^{3}_{2}> 
1650.291  0.00 
0.00  0.00 
2.50  3.00 
11.00  1.00 
1667.791  
The variable x_{3} replaces the slack variable s_{3} in the basis. The basis consists of all three primal variables, x_{1}, x_{2}, and x_{3}.
The last tableau contains the solutions to the primal and dual perturbed problems. Letting:
B  = 
s^{3}_{1} 
s^{3}_{1} 
s^{3}_{3} 
e_{4} 
0.00 
0.6667 
0.3333 
0.00 
0.50 
0.3333 
0.3333 
0.00 
0.50 
0.6667 
0.3333 
0.00 
2.50 
3.00 
11.00 
1.00 

The solution to the original primal problem is:
(x_{1}, x_{2}, x_{3}, P)' = B * (b_{1}, b_{2}, b_{3}, 0)' = B *(100, 100, 100, 0) = (33.33, 16.67, 16.67, 1650.0)'.
The solution to the dual problem is:
(y_{1}, y_{2}, y_{3}, D)' = (2.5, 3.00, 11.0, 1650.0)'.
Linear Programming References.
 Budnick, Frank S., Richard Mojena, and Thomas E. Vollmann. Principles of Operations Research for Management. Homewood: Irwin, 1977.
 Dantzig, G., A. Orden, and P. Wolfe. "The Generalized Simplex Method for Minimizing a Linear Form under Inequality Restraints." Pacific Journal of Mathematics. 8, (1955): 183195.

Dantzig, George B. Linear Programming and Extensions. Princeton: Princeton U P, 1963.

Dorfman, R., P. Samuelson, and R. Solow. Linear Programming and Economics Analysis. New York: McGrawHill, 1958.

Hadley, G. Linear Algebra. Reading, Mass.: AddisonWesley, 1961.

Hadley, G. Linear Programming. Reading, Mass.: AddisonWesley, 1962.
 Hillier, Frederick S. and Gerald J. Lieberman. Operations Research.. 2nd ed. San Francisco: HoldenDay, 1974.

Karlin, S. Mathematical Methods in the Theory of Games and Programming. Vols. I & II. Reading, Mass.: AddisonWesley, 1959.
 Loomba, N. Paul. Linear Programming: An Introductory Analysis. New York: McGrawHill, 1964.
 Press, William H., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes: The Art of Scientific Computing. Cambridge: Cambridge UP, 1989.

Saaty, Thomas L. Mathematical Methods of Operations Research. New York: McGrawHill, 1959.
 Sierksma, Gerard. Linear and Integer Programming: Theory and Practice. 2nd ed. New York: Marcel Dekker, 2002.

Sposito, Vincent. Linear and Nonlinear Programming. Ames, Iowa: Iowa UP, 1975.

Sposito, Vincent. Linear Programming with Statistical Applications. Ames, Iowa: Iowa UP, 1989.

Strang, Gilbert. Linear Algebra and Its Applications.3rd ed. San Diego: Harcourt, 1988.

Restrepo, Rodrigo A. Theory of Games and Programming: Mathematics Lecture Notes. Vancouver: University of B.C., 1967.

Restrepo, Rodrigo A. Linear Programming and Complementarity. Vancouver: University of B.C., 1994.

Taha, Hamdy A. Operations Research: An Introduction. 2nd ed. New York: MacMillan, 1976.
 Wagner, Harvey M. Principles of Management Science: With Applications to Executive Decisions. 2nd ed. Englewood Cliffs: PrenticeHall, 1975.
 Wagner, Harvey M. Principles of Operations Research: With Applications to Managerial Decisions. 2nd ed. Englewood Cliffs: PrenticeHall, 1975.
 Wu, Nesa, and Richard Coppins. Linear Programming and Extensions. New York: McGrawHill, 1981.

