Operations Research  Linear Programming
Economics Application  Profit Maximization
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
firm's production decision  sensitivity analysis  dual simplex method  dual simplex tableaux profit maximizing solution  postoptimality analysis  dual solution interpretation  references
The Firm's Production Decision.
A firm can produce a product using three production processes. Let the variables x_{1}, x_{2}, and x_{3} stand for the product and the quantities of the product produced by activities 1, 2, and 3, respectively. Each process uses labour (L), capital (K), and materials and supplies (M) to produce the product. The variable capital stands for various types of machinery and equipment. Assume that the use of labour and capital is measured in hours, and that M is an index number for the quantities of materials and supplies used. The availability of inputs of labour, capital, and materials and supplies, and the amounts of each input used to produce one unit of product by each production activity, are categorized by the coefficients of the following table:
L:  25  * x_{1} +  32  * x_{2} +  43  * x_{3}  <=  850 
K:  35  * x_{1} +  25  * x_{2} +  20  * x_{3}  <=  800 
M:  30  * x_{1} +  36  * x_{2} +  40  * x_{3}  <=  980 
The first column of the table means that 25 hours of labour (L), 35 hours of capital (K), and 30 units of materials and supplies (M) are used by process 1 to produce one unit of x_{1}. The first row of the table means that 25, 32, and 43 units of labour are used to produce one unit of x_{1}, x_{2}, and x_{3}, respectively. Furthermore, the total hours of labour used can not exceed 850 hours. The other columns and rows read similarly.
The unit costs of L, K, and M are:
w_{L} = 14, w_{K} = 34, and w_{M} = 12,
and the costs to produce one unit of x_{1}, x_{2}, and x_{3} are:
cost_{1} = 1900 = 14 * 25 + 34 * 35 + 12 * 30,
cost_{2} = 1730 = 14 * 32+ 34 * 25 + 12 * 36,
cost_{3} = 1762 = 14 * 43+ 34 * 20 + 12 * 40.
While the items produced by each process are similar, they are of differing quality. Consumers will pay a premium for higher quality items. I assumed that each item's quality depends on the "amount of capital equipment" used in its production. You can change this assumption by changing the prices in the userfriendly form below, i.e. perhaps it is the labour intensive item that commands a price premium for the product of interest. The new web page will recompute the relevant variables.
Consumers' tastes are reflected in the prices of one unit of x_{1}, x_{2}, and x_{3}:
price_{1} = 2610, price_{2} = 2400, and price_{3} = 2250
The profits to the firm of producing one unit of x_{1}, x_{2}, and x_{3} given by:
profit = price  cost:
are:
profit_{1} = 710, profit_{2} = 670, and profit_{3} = 488
The primal objective of the firm is to maximize profits, by producing appropriate amounts of products x_{1}, x_{2}, and x_{3}. The firm's primal production decision is captured in the firm's Primal Linear Programming Problem.

Primal Linear Program
Maximize the Objective Function (P)

P =  710  * x_{1} +  670  * x_{2} +  488  * x_{3} 
subject to:

L:  25  * x_{1} +  32  * x_{2} +  43  * x_{3}  <=  850 
K:  35  * x_{1} +  25  * x_{2} +  20  * x_{3}  <=  800 
M:  30  * x_{1} +  36  * x_{2} +  40  * x_{3}  <=  980 

x_{1} >= 0; x_{2} >= 0; x_{3} >= 0


Using matrix notation this is: 
Primal Linear Program
Maximize the Objective Function (P)
P = c^{T} x subject to
A x <= b, x >= 0

Solution Sensitivity Analysis.
The form below permits you to change the data that specify the firm's production decision. You can perform a sensitivity analysis of the firm's linear programming problem by changing the data, and clicking "Submit L.P.". A new web page will display with all the firm's data updated with your new data, and the firm's new optimal production program. Compare the new results with the results of the current web page.
After you fill in your data and click "Submit L.P.", the program will automatically calculate a sequence of tableaux that solves the primal and dual l.p. problems. Examine the tableaux that follow to see how the dual simplex method proceeds to find the solution.
Dual Simplex Method.
The standard form for the initial dual simplex tableau is:
Initial Tableau 
b  A  I_{3} 
0  c^{T}  O_{3}^{T} 
In the dual simplex algorithm, a sequence of tableaux are calculated. A given Tableau^{k} has the form:
Tableau^{k} 
ß  U  B 
µ  t^{T}  y^{T} 

= 

after consolidating the center 2 by 2 block of matrices.
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 dual program;
Phase II  generate tableaux that decrease the value of µ turning ß >= 0, without dropping back into Phase 0 or I, i.e. find a feasible basic dual program that minimizes the objective function D.

The Tableaux of the Dual Simplex Method.
Phase I: Goal: get Ø >= 0.
Tableau^{0} 

b^{0} 
x^{0}_{1} 
x^{0}_{2} 
x^{0}_{3} 
s^{0}_{1} 
s^{0}_{2} 
s^{0}_{3} 
row sum 
L^{0}  850  25  32  43  1  0  0  951 
K^{0}  800  35  25  20  0  1  0  881 
M^{0}  980  30  36  40  0  0  1  1087 
P^{0}  0  710  670  488  0  0  0  1868 
P^{0} / K^{0}  0  20.286  26.8  24.4  0  0  0  0 
Basis for Tableau^{0}: [s_{1}, s_{2}, s_{3}, ]. Value of Objective Function = 0.
Proceed to the next tableau as follows:
Phase 0: Complete.
Phase I: Goal: get Ø >= 0.
A. In Tableau^{0}:
1. Select a target column, tcol, with Ø_{tcol} < 0: Ø^{0}_{1} = 710, tcol = 1.
2. Select any row, r, with a positive entry in tcol = 1 as the pivot row: row = 2 associated with x_{2,1} = 35 and constraint K.
3. Compute the ratios Ø / K as per the last row. Discard ratios which are not positive and ratios associated with artificial variables.
Select the column with the least positive ratio as the pivot column: col = 1 associated with 20.286. Thus x_{2,1} = 35 is the pivot; variable s_{2} will leave the basis; variable x_{1} will enter the basis.
B. To create Tableau^{1}:
4. Compute row K^{1} = K^{0} / (35).
5. Subtract multiples of row K^{1} from all other rows of Tableau^{0} so that column x_{1} = e_{2} 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} 
row sum 
L^{1} = L^{0}  (25) * K^{1}  278.571  0  14.143  28.714  1  0.714  0  321.714 
K^{1} = K^{0} / (35)  22.857  1  0.714  0.571  0  0.029  0  25.171 
M^{1} = M^{0}  (30) * K^{1}  294.286  0  14.571  22.857  0  0.857  1  331.857 
P^{1} = P^{0}  (710) * K^{1}  16228.571  0  162.857  82.286  0  20.286  0  16003.714 
P^{1} / M^{1}  0  0  11.176  3.6  0  23.667  0  0 
Basis for Tableau^{1}: [s_{1}, x_{1}, s_{3}, ]. Value of Objective Function = 16228.57.
Proceed to the next tableau as follows:
Phase 0: Complete.
Phase I: Goal: get Ø >= 0.
A. In Tableau^{1}:
1. Select a target column, tcol, with Ø_{tcol} < 0: Ø^{1}_{2} = 162.857, tcol = 2.
2. Select any row, r, with a positive entry in tcol = 2 as the pivot row: row = 3 associated with x_{3,2} = 14.571 and constraint M.
3. Compute the ratios Ø / M as per the last row. Discard ratios which are not positive and ratios associated with artificial variables.
Select the column with the least positive ratio as the pivot column: col = 3 associated with 3.6. Thus x_{3,3} = 22.857 is the pivot; variable s_{3} will leave the basis; variable x_{3} will enter the basis.
B. To create Tableau^{2}:
4. Compute row M^{2} = M^{1} / (22.857).
5. Subtract multiples of row M^{2} from all other rows of Tableau^{1} so that column x_{3} = e_{3} 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} 
row sum 
L^{2} = L^{1}  (28.714) * M^{2}  91.125  0  4.163  0  1  0.363  1.256  95.181 
K^{2} = K^{1}  (0.571) * M^{2}  15.5  1  0.35  0  0  0.05  0.025  16.875 
M^{2} = M^{1} / (22.857)  12.875  0  0.638  1  0  0.038  0.044  14.519 
P^{2} = P^{1}  (82.29) * M^{2}  17288  0  110.4  0  0  17.2  3.6  17198.4 
P^{2} / M^{2}  0  0  173.176  0  0  458.667  0  0 
Basis for Tableau^{2}: [s_{1}, x_{1}, x_{3}, ]. Value of Objective Function = 17288.
Proceed to the next tableau as follows:
Phase 0: Complete.
Phase I: Goal: get Ø >= 0.
A. In Tableau^{2}:
1. Select a target column, tcol, with Ø_{tcol} < 0: Ø^{2}_{2} = 110.4, tcol = 2.
2. Select any row, r, with a positive entry in tcol = 2 as the pivot row: row = 3 associated with x_{3,2} = 0.638 and constraint M.
3. Compute the ratios Ø / M as per the last row. Discard ratios which are not positive and ratios associated with artificial variables.
Select the column with the least positive ratio as the pivot column: col = 2 associated with 173.176. Thus x_{3,2} = 0.638 is the pivot; variable x_{3} will leave the basis; variable x_{2} will enter the basis.
B. To create Tableau^{3}:
4. Compute row M^{3} = M^{2} / (0.638).
5. Subtract multiples of row M^{3} from all other rows of Tableau^{2} so that column x_{2} = e_{3} in Tableau^{3}.
Phase II: Goal: get ß >= 0.
Tableau^{3} 

b^{3} 
x^{3}_{1} 
x^{3}_{2} 
x^{3}_{3} 
s^{3}_{1} 
s^{3}_{2} 
s^{3}_{3} 
row sum 
L^{3} = L^{2}  (4.163) * M^{3}  7.059  0  0  6.529  1  0.118  0.971  0.382 
K^{3} = K^{2}  (0.35) * M^{3}  8.431  1  0  0.549  0  0.071  0.049  8.904 
M^{3} = M^{2} / (0.638)  20.196  0  1  1.569  0  0.059  0.069  22.775 
P^{3} = P^{2}  (110.4) * M^{3}  19517.647  0  0  173.176  0  10.706  11.176  19712.706 
P^{3} / L^{3}  0  0  0  0  0  0  11.515  0 
Basis for Tableau^{3}: [s_{1}, x_{1}, x_{2}, ]. Value of Objective Function = 19517.65.
Proceed to the next tableau as follows:
Phase 0: Complete.
Phase I: Complete.
Phase II: Goal: get ß >= 0.
A. In Tableau^{3}:
1. Select a pivot row, row, with b^{3}_{row} < 0: row = 1 associated with b^{3}_{1} = 7.059.
2. Compute the ratios Ø / L as per the last row. Discard ratios which are not positive and ratios associated with artificial variables.
Select the column with the least positive ratio as the pivot column: col = 6 associated with 11.515. Thus x_{1,6} = 0.971 is the pivot; variable s_{1} will leave the basis; variable s_{3} will enter the basis.
B. To create Tableau^{4}:
3. Compute row L^{4} = L^{3} / (0.971).
3. Subtract multiples of row L^{4} from all other rows of Tableau^{3} so that column s_{3} = e_{1} in Tableau^{4}.
Tableau^{4} 

b^{4} 
x^{4}_{1} 
x^{4}_{2} 
x^{4}_{3} 
s^{4}_{1} 
s^{4}_{2} 
s^{4}_{3} 
row sum 
L^{4} = L^{3} / (0.971)  7.273  0  0  6.727  1.03  0.121  1  0.394 
K^{4} = K^{3}  (0.049) * L^{4}  8.788  1  0  0.879  0.051  0.065  0  8.923 
M^{4} = M^{3}  (0.069) * L^{4}  19.697  0  1  2.03  0.071  0.051  0  22.747 
P^{4} = P^{3}  (11.18) * L^{4}  19436.364  0  0  248.364  11.515  12.061  0  19708.303 
P^{4} / ^{4}  0  0  0  0  0  0  0  0 
Basis for Tableau^{4}: [s_{3}, x_{1}, x_{2}]. Value of Objective Function = 19436.36.
Phase 0: Complete.
Phase I: Complete.
Phase II: Complete.
Primal Solution: [s_{3}, x_{1}, x_{2}] = [7.273, 8.788, 19.697]; P = 19436.364.
(Primal x variables not in the basis have a value of 0). Dual Solution: [y_{L}, y_{K}, y_{M}] = [11.515, 12.061, 0]; D = 19436.364.
Firm's Profit Maximizing Solution.
Quantities of the product produced by each production process, and the accompanying revenues, costs, and profits.
 Production Process  
 x_{1}  x_{2}  x_{3}  Totals 
price  2610  2400  2250  
output  8.788  19.697  0  
revenue  22936.36  47272.73  0  70209.09 
L  219.7  630.3  0  850 
K  307.58  492.42  0  800 
M  263.64  709.09  0  972.73 
cost  16696.97  34075.76  0  50772.73 
profit  6239.39  13196.97  0  19436.36 
unit profit  710  670  488  
Post Optimality Analysis.
Over what ranges of the values of the coefficients of the model, such as profits (c_{1}, c_{2}, c_{3}), or the availability of inputs (b_{L}, b_{K}, b_{M}), will the above basic feasible solution remain optimal? By the phrase "remain optimal," I mean that the variables in the basis of the current optimal basic solution remain in the basis of the new optimal basic solution, after the values of the coefficients are altered. As long as the list of variables in each basis is the same, even though the values of the variables may change with the changes in the coefficients of the model, the current basic solution is said to remain optimal.
The primal variables, x_{1}, x_{2}, and x_{3}, take on the values 8.79, 19.7, and 0 with per unit profits of 710, 670, and 488 at per unit prices of 2610, 2400, and 2250. The basis variables associated with rows (
1, 2, 3) of Tableau^{4} are the variables (
s_{3}, x_{1}, x_{2}
) whose associated objective function coefficients are (
0, 710, 670).
Objective Function Coefficients  NonBasic Variables
By how much can one increase the price of
x_{3} before this variable will enter the basis of a new basic optimal solution. To determine the entry price for x_{3}, one computes the opportunity cost of producing one unit of x_{3} = the profits given up to produce one unit of x_{3} = z_{3}, using standard L.P. notation. The value of z_{3} is calculated by weighting each entry of the column associated with x_{3} in Tableau^{4} by the objective function coefficient associated with the row of that entry:
z_{3} = 0 * 6.73 + 710 * 0.88
+ 670 * 2.03 = 736.36.
Per unit profits for x_{3} can increase from 488 to 736.36, and the price per unit of x_{3} can increase from 2250 to 2498.36 before x_{3} will enter the basis in the new optimal primal solution.
Objective Function Coefficients  Basic Variables
By how much can one decrease the price of variable x_{1} before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.
To determine the basis upset price for x_{1}, one needs to know the decrease in profits that result from increasing the value of each nonbasic variable by one unit, i.e. the opportunity cost, z_{j} of producing one unit of each nonbasic variable variable, x_{j}.
One also needs to know by how much the value of each nonbasis variable will increase from a one unit decrease in the basic variable x_{1}, i.e. the tradeoff rate x_{2, j}, from row 2 of Tableau^{4} associated with basis variable x_{1}, between the variable x_{1} and each nonbasis variable, x_{j}.
Call zc_{j} the difference between z_{j} and the objective function coefficient c_{j} for variable x_{j}, divided by x_{2, j} from Tableau^{4}. (For slack variables, the objective function coefficient is 0.) If zc_{j} > 0, then the nonbasic variable x_{j} is a candidate to replace x_{1}, when the price of x_{1} (or equivalently, the objective function coefficient, c_{1}) is reduced by zc_{j}. Taking the least positive zc_{j} over all candidate nonbasic variables yields the possible decrease in the price of x_{1} before this variable leaves the basis of the existing optimal solution, i.e. a different primal or slack variable will be associated with row 2.
For the basic variable x_{1} associated with row 2 of Tableau^{4}, the candidate nonbasic variables — primal variables x_{j}, or slack variables s_{j} — and their zc_{j} values are given by:
x_{j}: zc_{j} = (z_{j}  c_{j}) / x_{2, j}, or
s_{j}: zc_{j} = (z_{j}  0) / x_{2, j}.
The zc_{j} values for x_{1} associated with row 2 of Tablueau^{4} are:
s_{2}: zc_{5} = (12.06  0) /
0.06 = 186.56
The least positive zc_{j} is zc_{5} = 186.56. Consequently, profits per unit for x_{1} can decrease from 710 to
523.44, and the price per unit of x_{1} can decrease from 2610 to 2423.44 before the existing basis is upset. (x_{1} might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).
Similarily, by how much can one decrease the price of variable x_{2} before a new optimal basic solution is obtained, i.e. the current list of basis variables is replaced by a different list.
The zc_{j} values for x_{2} associated with row 3 of Tablueau^{4} are:
x_{3}: zc_{3} = (736.36  488) /
2.03 = 122.33
s_{1}: zc_{4} = (11.52  0) /
0.07 = 162.86
The least positive zc_{j} is zc_{3} = 122.33. Consequently, profits per unit for x_{2} can decrease from 670 to
547.67, and the price per unit of x_{2} can decrease from 2400 to 2277.67 before the existing basis is upset. (x_{2} might possibly be in the basis (possibly as a degenerate variable) of the new optimal primal basic solution).
Postoptimality Analysis.
RHS Coefficients  bvector Constraints
Over what ranges of values for the availability of labour (L), capital (K), and materials and supplies (M), will the existing set of basic variables remain in the basis of the optimal solution, after these variables values are adjusted?
In the postoptimality analysis for the objective function coefficients, I used the the columns in Tableau^{4}associated with each nonbasis variable x_{j} or s_{j}, or / and the row of Tableau^{4} associated with the basis variable.
The postoptimaility analysis for the resource constraints associated with the L, K, and M values, I use the matrix formed from the columns of with the slack variables in Tableau^{4}.
On the simplex algorithm page, I showed how this matrix, called B, is the inverse of the matrix A_{B} from Tableau^{0} associated with the basis variables in the optimal primal solution. Moreover, the ß column of the final tableau, Tableau^{4}, is equal to the product of the B matrix and the original vector of resource constraints, b, i.e. ß = B * b, which also yields the values of the basis variables, x_{basis} in the optimal primal solution.
The range of values of the coefficients of the bvector that will maintain the current basis depends on the following observation. If I change the ith coefficient b_{i} to b_{i}, then the new vector, b, must obey:
x_{basis} = ß = B * b >= 0
since the values of the new optimal x_{basis} coefficients must be nonnegative for the exisiting basis to continue as the basis in the the new optimal basic primal solution.
The B matrix for the current optimal basic solution is:
B  = 
1.03  0.121  1  0.051  0.065  0  0.071  0.051  0 

With b = (850, 800, 980), the perturbed RHS coefficients must obey:
1.03 * L + 0.121 * 800 + 1 * 980 >= 0  0.051 * L + 0.065 * 800 + 0 * 980 >= 0  0.071 * L + 0.051 * 800 + 0 * 980 >= 0 
1.03 * 850 + 0.121 * K + 1 * 980 >= 0  0.051 * 850 + 0.065 * K + 0 * 980 >= 0  0.071 * 850 + 0.051 * K + 0 * 980 >= 0 
1.03 * 850 + 0.121 * 800 + 1 * M >= 0  0.051 * 850 + 0.065 * 800 + 0 * M >= 0  0.071 * 850 + 0.051 * 800 + 0 * M >= 0 
Since these inequalities must be satisfied simultaneously for each b_{i} considered separately, the upper and lower bounds are:
 L  K  M 
RHS bvector 
850  800  980 
Lower limit 
571.43  664.06  972.73 
Upper limit 
857.06  860  inf 
If you change the data on the form in the sensitivity analysis section above and click "Submit L.P.", this web page will display the tableaux for the new optimal solution. Continue this process until you convince yourself of the validity of the postoptimality analysis.
Economic Interpretation of the Dual Solution.
The firm's dual problem is to determine the values y_{L}, y_{K}, and y_{M} per unit of input L, K and M that will minimize the total value of resources used, yet maintain each product's level of profit. The firm's dual production decision is captured in the firm's Dual Linear Programming Problem.

Dual Linear Program
Minimize the Objective Function (D)

D =  850  * y_{L} +  800  * y_{K} +  980  * y_{M} 
subject to:

x_{1}:  25  * y_{L} +  35  * y_{K} +  30  * y_{M}  >=  710 
x_{2}:  32  * y_{L} +  25  * y_{K} +  36  * y_{M}  >=  670 
x_{3}:  43  * y_{L} +  20  * y_{K} +  40  * y_{M}  >=  488 

y_{L} >= 0; y_{K} >= 0; y_{M} >= 0


Using matrix notation this is: 
Dual Linear Program
Minimize the Objective Function (D)
D = b^{T} y subject to
y^{T} A >= c^{T}, y >= 0

The solution to this minimization problem is:
Dual Solution: [y_{L}, y_{K}, y_{M}] = [11.515, 12.061, 0]; D = 19436.364.
The variables, y_{L}, y_{K}, and y_{M}, measure the increase in profits, P in the primal program, from a one unit increase in the availability of labour (L), capital (K), and materials and supplies (M), respectively. (See what happens to profits when you increase the resource constraint of an input by one unit on the form in the sensitivity analysis section above and click "Submit L.P.".)
A value of zero for a variable y_{i}, associated with a positive value for slack variable s_{i} in the optimal solution of the primal program, means that excess amounts of that input are available.
The variables, y_{L}, y_{K}, and y_{M}, are referred to as opportunity prices, or shadow prices for the inputs L, K, and M.
End of the Linear Programming Dual Simplex Method
Linear Programming References.

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

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.
 Wu, Nesa, and Richard Coppins. Linear Programming and Extensions. New York: McGrawHill, 1981.
