Chapter 9
LINEAR PROGRAMMING
          
One of the best known mathematical programming models is the linear programming model, where all the functions in the model are linear in all variables.  Linear programming models are used for optimum allocation of fixed inputs among competing needs. Linear programming has been successfully used in solving many business and economic problems.  The model may be written as:
      
Optimize:   Z = (Subscript[c, 1])(Subscript[x, 1]) + . . . .  + (Subscript[c, n])(Subscript[x, n])                
Subject to:       (Subscript[a, 11])(Subscript[x, 1]) +  . . . . + (Subscript[a, 1  n])(Subscript[x, n]) {< = >} (Subscript[b, 1])        
                                   . . . . . . . .
                                   . . . . . . . .
                        (Subscript[a, m1])(Subscript[x, 1]) + . . . . + (Subscript[a, mn])(Subscript[x, n]) {< = > } (Subscript[b, m])
                               (Subscript[x, 1]), . . . ., (Subscript[x, n]) > 0

Where, (Subscript[x, 1]), ....., (Subscript[x, n]) are the decision variables and a's, b's, and c's are the known constants.  The objective is to optimize (maximize or minimize) the objective function Z subject to m + n constraints (m constraints and n non-negativity restrictions on decision variables).  

In matrix form the model may be written as:

Optimize:  Z = c'x
Subject to:  A.x {<=>} b
                       x ≥ 0
Where c is a n.1 vector of constant coefficients of objective function, A is a m.n matrix of constant coefficients of constraint equations, b is a n.1 vector of constraints and Z is the objective variable.
 
There are different ways of solving a linear programming model. The best known, however, is the Simplex method, developed  by George  B. Dantzig during the World War II.

In the next section, the graphic solution of the linear programming problems is presented.   The following sections present the Simplex solution of the linear programming models, the solution to minimizing problems, and the duality.

TOOL BOX
Mathematica Commands			Function

Polygon[{{2,0}, {2,2}, {2,4}, {0,2}}]		Draws a polygon with vertices at (2,0), (4,2), (2,4), and (0, 2). 

Table[Plot[2x+i], {x, 0, 3}], {i, 0, 5}]		Plots 2x+i for i =0 to 5.  Double click on the graph to see its 
						movements.

ConstrainedMax[2x1+3x2,			Solves the linear programming problem Max: Z =2x1+3x2,
{x1+2x2 <= 7,3x1+x2 <= 6},{x1,x2}]		Subject To:  x1+ 2x2 < 7 and  3x1 + x2 <  6.            

ConstrainedMin[2x1+ 3x2,			Solves the linear programming problem Max: Z = 2x1+3x2, 
{x1+2x2 >= 7,3x1+x2 >= 6},{x1,x2}]		Subject To:  x1+ 2x2 > 7 and 3x1 + x2 >  6.       


I.  Graphic Solution of the Linear Programming Models: The ConstrainedMax Command

If the linear programming problem involves only two variables, the simplest way to solve the problem is using graphs of the functions. The graphic solution is illustrated by the following examples.  

Example:
A firm produces two goods, x1 and x2, which it sells at prices $2 and $3 each, respectively.  The firm employs two fixed inputs labor and capital, available to the firm at fixed quantities of 7 and 8 units respectively.  Each x1 requires one unit of labor and three units of capital. Each x2 requires two units of labor and one unit of capital. Set up a linear programming problem of maximizing total revenue subject to the constraints and find the optimum solution. 

Solution:  Set up the objective function and the constraints based on the given information
Maximize:  Z = 1.5x1 + x2           
Subject to:   x1 + 2x2 < 7               
                    3x1 +  x2 < 6             
                          x1, x2 > 0                   

the first step in solving the problem is to find the constraint region. The constraint region is the set of points that simultaneously satisfies the constraints.  To find the constraint region, graph both constraints 



and find the region that satisfies both constraints.  In a maximizing problem, this generally results in a polygon with the vertices at the intersections of the constraints, the constraints and the axes, and the origin.  Here, the two constraints meet each other at (1, 3) and the constraining region is a polygon with the vertices at (0, 0), (0, 3.5), (2, 0), and (1, 3).


The Simplex method provides us with a prove that the optimum solution of the linear programming problems always lies on one of the corner points of the polygon or on one of the sides of the polygon, if there are multiple solutions.  The optimum solution, however, depends on the slope of the objective function and the point at which the objective function is tangent to the constraint region. The constraint region and a group of objective lines are graphed below 


as the objective line is moved from the north east corner of the quadrant toward the constraint region, the first point where the objective line touches the constraint region (the point of tangency) provides us with the optimum solution to the problem.  In this case, the solution is (1, 3), which is the intersection of the two constraints, and the maximum value of Z is Z = 11.

The optimum solution can be tested for using  the Mathematica command ConstrainedMax as follows,
Clear[x1,  x2]
ConstrainedMax[
          2  x1 +  3  x2, {x1  +  2  x2  <=  7, 
            3  x1  +  x2  <=  6}, {x1, x2}]
{11, {x1 -> 1, x2 -> 3}}

It may happen that the slope of the objective function is the same as the slope of one of the constraints.  In  that case, the linear programming problem will have multiple solutions.  Any point on the constraint function which also lies on the constraint region will be a solution to the problem.  For example, if the objective function of the preceding example were Z = (Subscript[x, 1]) + 2(Subscript[x, 2]), which has the same slope as the first constraint, the point (0, 3.5), or (1,3), or any point on the line joining these two points is a solution to the problem. All of these points will maximize Z with a value of Z = 7.  The following figure shows the case of multiple solutions.



If the objective line intersects the constraint region in one of the vertices lying on the axes (point (2, 0) or (0, 3.5)), the firm will produce positive amounts of one good and none of the other. Such a solution is called a degenerate solution.  For example, if the objective function was  Z = 4x1 + x2, the solution would be x1 = 2 and x2 = 0. If the objective function was Z = x1 + 3x2, the solution would be x1 = 0 and x2 = 3.5.  The following figure shows the degenerate solution (2, 0).



Graphic Solution of the Example Using Mathematica:  To solve the problem using Mathematica, graph the constraints and the objective function to find the optimum point.  To graph the constraints, first write (Subscript[x, 2]) of each equation in terms of (Subscript[x, 1])and graph them.  For the first constraint, this is 
Clear[x1, x2,  equ1,  cons1]
equ1 = Solve[x1 + 2  x2 == 7,  x2]
eq1[x1_] := x2 /. equ1[[1]]
cons1=Plot[eq1[x1], {x1,  0,  7},PlotStyle -> {AbsoluteThickness[2]}, AxesLabel -> {"X1",  "X2"} ]

{{x2 -> ((7 - x1)/2)}}

⁃  Graphics  ⁃
for the second constraint this is
Clear[x1,  x2,  equ2,  cons2]
equ2 = Solve[3  x1 + x2 == 6,  x2]
eq2[x1_] := x2 /. equ2[[1]]
cons2=Plot[eq2[x1], {x1,  0,  2},PlotStyle -> {AbsoluteThickness[2]}, AxesLabel -> {"X1",  "X2"}]
{{x2 -> -3 (-2 + x1)}}

⁃  Graphics  ⁃

To graph the two constraints together, use the show command as below,
cons = Show[cons1,  cons2]

⁃  Graphics  ⁃
The constraint region is the shaded area shown below, with the vertices (0, 0), (0, 3.5), (1, 3), and (2, 0)
consregion =  
          Show[Graphics[ {Hue[ .7],  
                Polygon[{{0,  0},  {0,  3.5},  {1, 3},  {2, 0}}]}]]

⁃  Graphics  ⁃
To show the constraints and the constraint region together, use the show command
Show[cons ,  consregion]

⁃  Graphics  ⁃

To graph the constraints and the objective together use the show command, listing all three equations.  However, listing the objective as a "Table" with an index "i" allows for graphing several parallel lines of objective and for movement of them to visually pinpoint the optimum solution.  
Show[Plot[{eq1[x1],  eq2[x1]}, {x1,  0,  2}, PlotStyle -> {AbsoluteThickness[2]},AxesLabel -> {"X1", "x2"}], Table[
              Plot[-1.5 x1 + i,  {x1,  0,  2},  
                DisplayFunction -> Identity],   {i,  3,  6 }] ,Graphics[{Hue[ .7],  
                Polygon[{{0,  0},  {0,  3.5},  {1, 3},  {2, 0}}]}]]


⁃  Graphics  ⁃


When the objective line is moved from the north east portion of the first quadrant toward the constraint region, the first point where the objective line touches the constraint region will be the optimizing point.  In this case, the solution is (1, 3), which is the intersection of the two constraints.  The solution can be tested for using  the Mathematica command "ConstrainedMax" as below,
ConstrainedMax[
          2  x1 +  3  x2, {x1  +  2  x2  <=  7, 
            3  x1  +  x2  <=  6}, {x1, x2}]
{11, {x1 -> 1, x2 -> 3}}

For the multiple solutions the objective function is changed to It may happen that the slope of the objective function is the Z = x1 + 2x2, which has the same slope as the first constraint, the point (0, 3.5), or (1,3), or any point on the line joining these two points is a solution to the problem. All of these points will maximize Z with a value of Z = 7.  The following figure shows the multiple solution.
Show[Plot[{eq1[x1],  eq2[x1]}, {x1,  0,  2},  PlotStyle -> {AbsoluteThickness[2]},   AxesLabel -> {"X1", "x2"}], Table[
              Plot[- .5 x1 + i,  {x1,  0,  2},  
                DisplayFunction -> Identity],   {i,  3,  5 }],Graphics[{Hue[ .7],  
                Polygon[{{0,  0},  {0,  3.5},  {1, 3},  {2, 0}}]}]]


⁃  Graphics  ⁃

If the objective function intersects the constraint region in the corner points (2, 0) or (0, 3.5), the solution is called degenerate solution.  The following graph shows degenerate solution with an objective function of Z = 4x1 + x2, the solution is x1 = 2 and x2 = 0. If the objective function is Z = x1 + 3x2, the solution is x1 = 0 and x2 = 3.5.  The following figure shows the degenerate solution (2, 0).
Show[Plot[{eq1[x1],  eq2[x1]}, {x1,  0,  2},  PlotStyle -> {AbsoluteThickness[2]},AxesLabel -> {"X1", "x2"}], Table[
              Plot[-4 x1 + i,  {x1,  0,  2},  
                DisplayFunction -> Identity],   {i,  6,  9 }],Graphics[{Hue[ .7],  
                Polygon[{{0,  0},  {0,  3.5},  {1, 3},  {2, 0}}]}]]


⁃  Graphics  ⁃

Do More Practice:
1- Double the labor and capital inputs to 14 and 12, respectively.  Redo the problem and compare the solution to the one in the text.
2- Double the objective function coefficients to 3 and 2, respectively.  Keep other parameters the same as in the text.  Redo the problem and compare the solution to the one in the text.
3- Let the objective be Z = .5x1 + x2.  Keep other parameters the same as in the text.  Redo the problem and compare the solution to the one in the text.
4- Let the objective be Z =  x2.  Keep other parameters the same as in the text.  Redo the problem and compare the solution to the one in the text.

Example: Minimizing Problem 
Suppose that the objective of a firm is to minimize cost subject to the constraints given as follows:
Minimize:  C = 7x1 + 6x2 
Subject to:         x1 + 3x2 > 2
                         2x1 +  x2 > 3
                             x1, x2  > 0 
where, x1 and x2 are the prices of two inputs, labor and capital, and C is the cost.  Find the optimum solution to the problem.
Solution:  The first step is to find the constraint region.  Graph the constraints and find the region that satisfies both constraints (the blue region in the graph below).  



Since the objective is to minimize C, the optimum solution will be the point where the objective line touches (is tangent to) the lowest point of the constraint region.  The optimum solution, however, depends on the slope of the objective function, as shown in the following graph.


The two constraints intersect at the point ((7/5), (1/5)) and the graph above shows that the objective line is tangent to the constraint region at this point.  Hence, the optimum solution is the intersection of the two constraints at ((7/5), (1/5)), with a minimum cost of C = 11.  

If the slope of the objective function is the same as the slope of one of the constraints, then the problem will have a multiple solutions and any point on that constraint that also satisfies the constraint region will be a solution.  If the slope of the objective function is such that it is tangent to the constraint region on one of the corner points on the x-axis, then the problem will have a degenerate solution (see, the Do More Practice at the end of this section). 

To check the solution using the Mathematica, use the command ConstrainedMin as follows   
Clear[x1,  x2]
ConstrainedMin[
          7  x1  +  6  x2, {x1  +  3  x2 >=  2,  
            2  x1  +  x2  >=  3},  {x1,  x2}]
{11, {x1 -> (7/5), x2 -> (1/5)}}

Graphic Solution of the Example Using Mathematica: To generate the lines and solve the problem using Mathematica, first write each equation in terms of one variable, say (Subscript[x, 1]) and plot them.  For the first constraint, this is done as
Clear[x1,  x2,  equ1,  equ2]
equ1 = Solve[x1  +  3  x2 == 2,  x2]
eq1[x1_] = x2 /. equ1[[1]];
Plot[eq1[x1], {x1,  0,  2},PlotStyle -> {AbsoluteThickness[2]}, AxesLabel -> {"X1", "X2"} ]

{{x2 -> ((2 - x1)/3)}}

⁃  Graphics  ⁃
for the second constraint, this is done as 
Clear[x1,  x2]
equ2 = Solve[2  x1 +  x2 == 3,  x2]
eq2[x1_] = x2 /. equ2[[1]];
Plot[eq2[x1], {x1,  0,  2},PlotStyle -> {AbsoluteThickness[2]},   AxesLabel -> {"X1", "x2"}]
{{x2 -> 3 - 2 x1}}

⁃  Graphics  ⁃
The two constraints intersect at the solution of the following two equations,
Solve[{x1 + 3  x2 == 2,  2  x1 + x2 == 3},  {x1,  x2}]
{{x1 -> (7/5), x2 -> (1/5)}}
The constraint region is the polygon with the vertices at (0, 3), (2, 0), and ((7/5), (1/5)).  The polygon is shown below together with the constraint lines.
Show[Plot[{eq1[x1],  eq2[x1]}, {x1,  0,  2} , PlotStyle -> {AbsoluteThickness[2]},AxesLabel -> {"X1", "X2"}],  Graphics[{Hue[ .7],  
                    Polygon[{ {0,  3},  {2, 0},  {7/5, 1/5}}]}]]     


⁃  Graphics  ⁃

The optimum solution, however, depends on the slope of the objective function, as shown in the following graph.  The following commands plot the constraint region and a group of objective lines.

Show[Plot[{eq1[x1],  eq2[x1]}, {x1,  0,  2}, PlotStyle -> {AbsoluteThickness[2]}, AxesLabel -> {"X1", "X2"}],  Table[
                Plot[(-7/6) x1 + i,  {x1,  0,  2},  
                  DisplayFunction -> Identity],   {i,  1,  3 }], Graphics[{Hue[ .7],  
                  Polygon[{ {0,  3},  {2, 0},  {7/5, 1/5}}]}]]     


⁃  Graphics  ⁃

Hence, the optimum solution is the intersection of the two constraints at ((7/5), (1/5)), with a minimum cost of C = 11.  The optimum solution can also be derived using Mathematica command ConstrainedMin as follows,

ConstrainedMin[
          7  x1  +  6  x2, {x1  +  3  x2 >=  2,  
            2  x1  +  x2  >=  3},  {x1,  x2}]
{11, {x1 -> (7/5), x2 -> (1/5)}}

The graphic solution is limited to the cases where there are no more than two decision variables.  However, graphic solutions illustrate two important features of linear programming problems.  First, the solution will occur at a corner point of the constraint region (or along the constraint line, if the solution is not unique);  Second, the constraint region forms a convex set. (for definition of the convex sets see appendix at the end of Chapter 8.)

Do More Practice:
1- Double the constraining values to 4 and 6, respectively.  Redo the problem and compare the solution to the one in the text.
2- Double the objective function coefficients to 14 and 12, respectively.  Keep other parameters the same as in the text.  Redo the problem and compare the solution to the one in the text.
3- Let the objective be C = 2x1 + 6x2.  Keep other parameters the same as in the text.  Redo the problem and compare the solution to the one in the text.
4- Let the objective be Z =  4x1 + 2x2.  Keep other parameters the same as in the text.  Redo the problem and compare the solution to the one in the text.


Problems:
Using the graphic solution, find the optimum values of decision variables and objective variables of the following problems.
1.         Maximize:  z =  x1 + 2x2
            Subject to:       x1 + 4x2 < 12
                                  3x1 + 2x2 < 18
                                         x1, x2  > 0
2.    Solve problem 1 when the objective function is  z = 10x1 + 3x2 
3.     Solve problem 1 when the objective is z = 6x1 + 4x2.
4.         Maximize:  z = 2x1 + 3x2
            Subject to:     x1 + 3x2 < 10
                                4x1 +   x2 < 12
                                  x1 +   x2 <  6 
                                     x1,  x2   >  0
5.   Solve  problem 4 when  the  objective  function  is z = 3x1 + 2x2.
6.          Maximize: z = x1 + 2x2
            Subject to:  x1 +  x2 < 10
                             2x1 + 3x2 < 20
                                  x1, x2   > 0
7.   Solve problem.6, when the objective function is z = x1.
8.          Minimize:  C = 13y1 + 18y2
            Subject to:      y1 +  3y2 > 3
                                 4y1 +  2y2 > 2
                                      y1, y2    > 0
9.         Minimize:  C = y1 + 5y2
            Subject to:  4y1 +   y2  > 6
                                 y1 + 2y2  > 5
                                 y1 +10y2  > 13
                                     y1, y2   > 0
10.  Solve problem 9,  when the objective function is C = 6y1 + y2.   

II. Simplex Solution of the Linear Programming Models
The Simplex algorithm is an efficient procedure to find the optimum solution of linear programming problems. The preceding section showed that the solution of a linear programming problem occurs at a corner point of the constraint region, which is the intersection or the solution set of a system of equations.  However, there is more to finding a solution to a linear programming problem than finding a solution to a system of equations.  For a student of economics, Simplex method is a step by step practice in economics of resource allocation.  The solution starts from the corner point origin, which could be the worst or one of the non-optimal solutions, and proceeds to the optimum solution.  In each step, the question is what to produce next and how much to produce, given the constraints on available resources.  These questions are all economic questions that, in the Simplex method, are answered through the marginal cost marginal benefit analysis and other economic criterion.  The procedure sorts out from the totality of solutions to the system of linear equations a specific solution that is optimal.     

A standard linear programming model is a linear programming model in which the objective function is maximized subject to the constraints of  the " < " form. That is,

Maximize:     Z = c1x1 +.......... + cnxn
Subject to:          a11x1 +.......... + an1xn < b1
                                ..................
                                ..................
                       am1x1 +.......... + amnxn < bm
                               x1, ........, xn > 0

The Simplex method starts with a solution which is feasible, but not optimum. It then continues with iterations in such a way that each new solution is at least as good as the previous one.  

A Feasible Solution:  To a linear programming problem is a set of (Subscript[x, s]) that satisfy the constraints and the non-negativity restrictions.  An Optimal Solution is a feasible solution that optimizes the objective function.

To use the Simplex method, the first step is to set the inequality constraint to equality by adding slack variables.  A slack variable is a positive variable to be added to the inequality constraints of the "<" form to set them to equality. 

The following example illustrates the application of Simplex algorithm. 

Example:  Solve the following linear programming problem, using the Simplex algorithm. 
  Maximize:  Z = 2x1 + 3x2
   Subject to:      x1 + 2x2 < 7
                          3x1 +  x2 < 6
                             x1, x2 > 0
 Solution:  The first step is to add slack variables to the inequality constraints to set them to equalities.  
  Maximize: Z = 2x1 + 3x2
   Subject to:      x1 + 2x2 + s1 = 7
 	            3x1 +  x2 + s2 = 6
                          x1, x2, s1, s2   > 0
Here, s1 and s2 are the slack variables.  For the clarity of exposition, the coefficients are written in the table of coefficients. Then the elimination procedure is used to set the matrix of coefficients into reduced form.
	Table 1.  Table of coefficients
________________________________
Variable:   x1     x2     s1    s2   Constant
_________________________________
                   1      2      1      0         7
                   3      1      0      1         6
__________________________________
Objective    2      3      0      0         Z

The initial basic feasible solution to the problem is s1= 7 and s2 = 6. The basic feasible solution is determined by the standard basis (unit matrix of the constraint column in table of coefficients, highlighted yellow). This solution implies that both inputs go to slack (they are idle or are not used), with no production taking place.  Hence, s1 = 7, s2 = 6, x1 = x2 = 0, and Z = 0.

Certainly, this solution is not a proper solution and the value of Z can be improved by entering one of the decision variables into the basic solution. The Simplex criteria for selecting such a variable is to choose the variable which gives the largest per unit increase to the objective function( highest marginal revenue).  Here, that variable is x2, with a coefficient of 3 in the objective row. The column presenting x2 (the new entry to the basic solution) in the table of coefficients is called the pivot column.

Since the inputs set a restriction on the values of the decision variables, the next step is to determine which constraint is more restrictive.  This is decided by dividing available inputs, (7 units of labor and 6 units of capital), by the corresponding input requirements for x2, (2 units of labor and 1 unit of capital).  The ratios for labor and capital are (7/2)and (6/1), respectively.  Hence, the more restrictive constraint is labor.  The row representing the more restrictive constraint is called the pivot row.  Here, the pivot row is the first row (labor).
The intersection of the pivot column and the pivot row represents the pivot element. Here, the pivot element is 2.

Once the pivot element is decided, the elimination technique can be applied to bring x2 into the basic solution by transforming the pivot element to one, and all the other  entries in the pivot column to zero. 
	Table 2. Table of coefficients
________________________________________
Variable:       x1      x2      s1      s2       Constant
________________________________________
                    .5       1       .5      0           3.5
                  2.5       0      -.5      1           2.5
________________________________________
Objective     .5       0     -1.5      0        Z - 10.5
The basic variables, decided by the unit matrix in the constraint rows (highlighted by yellow), in table 2 are x2 = 3.5 and  s2 = 2.5, which results in a solution, x1 = 0, x2 = 3.5, s1 = 0, s2 = 2.5, and an objective value of Z = 10.5.  Note that, non-basic variables (here, x1 and s1) have a value of zero.

The elimination technique to get from table 1 to table 2 is as follows,

1- Divide all the elements of pivot row by pivot element, (2).
2- Multiply the first row by -1 and add it to the second row.
3- Multiply the first row by -3 and add it to the third row.

As long as there is a positive value in the objective row, there is a chance to increase the objective variable by changing the basic variables. Here, the variable that can increase the objective is x1, with a positive coefficient of .5 in the objective row. Hence, x1 will represent the pivot column.

The pivot row is selected by finding the more restrictive constraint. Divide elements of the constant column in table 2 by the corresponding input coefficients in the pivot column (x1 column), ((3.5/5) = 7, (2.5/2.5) = 1). The more restrictive constraint is capital. The pivot element is 2.5, in the intersection of the first column and the second row.

Therefore, x1 enters the basic solution. Table 3 represents the new basic feasible solution.
	 Table 3. Table of coefficients
______________________________________
Variable:       x1     x2     s1       s2      Constant
_____________________________________
                      0       1      .6      -.2            3
                      1       0     -.2       .4            1
______________________________________
Objective       0       0    -1.4     -.2      Z - 11


The basic feasible solution is x1 = 1, x2 = 3, which corresponds to the unit matrix (highlighted yellow) with an objective value of Z = 11.  This solution is also the optimum solution because there is no positive entry in the objective row.  Therefore, the optimum solution is x1 = 1, x2 = 3, s1 = s2 = 0 and Z = 11.  Z can be calculated either by using the objective function and substituting for decision variables, or by setting the last entry in the  objective row equal to zero, (Z - 11 = 0).

To solve the problem using Mathematica, use the command "ConstrainedMax". 
Clear[x1,  x2]
ConstrainedMax[
          2  x1  +  3  x2,  {x1  +  2  x2  <= 7,  
            3  x1  +  x2  <=  6},  {x1,  x2}]
{11, {x1 -> 1, x2 -> 3}}

Example:  Solve the following linear programming problem, using the Simplex algorithm. 
  Maximize:  Z = 4x1 +  x2
   Subject to:          x1 + 2x2 < 7
                            3x1 +  x2 < 6
                              x1, x2 > 0 
Solution:  Set the inequality constraint to equality by adding the slack variables (s1, s2).
  Maximize: Z = 4x1 +  x2
   Subject to:         x1 + 2x2 + s1 = 7
                          3x1 +  x2 + s2 = 6
                            x1, x2, s1, s2 > 0
The table of coefficients is
	Table 1. Table of coefficients
____________________________________
Variable:     x1    x2      s1     s2   Constant
___________________________________
                    1      2       1      0           7
                    3      1       0      1           6
_________________________________
Objective     4      1     	 0      0          Z

The initial solution is x1 = x2 = 0, s1 = 7, s2 = 6, and Z = 0.  Both inputs are going  slack (s1 and s2 are in the basic solution) and no production is taking place.  The pivot column is column x1with the largest revenue margin of 4.  The pivot row is selected by dividing elements of the constant column (constraints on inputs) to the corresponding elements of the pivot column ((7/1), (6/3)).  Since the second constraint row is setting the constraining limit, it is selected as the pivot row.  The intersection of the pivot column and the pivot row decides the pivot element, which is "3" in the x1 column.  Therefore x1 enters the basic solution.
	Table 2.  Table of coefficients
____________________________________
Variable:     x1    x2      s1     s2   Constant
_____________________________________
                    0     (5/3)      1      -(1/3)      5
                    1     (1/3)      0       (1/3)      2
____________________________________
Objective    0    -(1/3)      0      -(4/3)     Z - 8

Since all the entries in the objective row are negative, there is no way to increase the objective variable with further iteration. Therefore, the optimum solution  x1 = 2, x2 = 0, s1 = 5, s2 = 0 and Z = 8. With x2 = 0, the solution is also a degenerate solution.  
It is also clear from table 2 that s1 is in the basic solution,  with a value of s1 = 5.  This implies that from the total 7 units of labor available for the firm, only 2 units are used and 5 units go slack.
To solve the problem using Mathematica,
Clear[x1,  x2]
ConstrainedMax[
          4  x1  +  x2,  {x1  +  2  x2  <= 7,  
            3  x1  +  x2  <=  6},  {x1,  x2}]
{8, {x1 -> 2, x2 -> 0}}

Problems:        
 Solve the following problems through the Simplex method:
1,.        Maximize:  z =  x1 + 2x2
            Subject to:       x1 + 4x2 < 12
                                   3x1 + 2x2 < 18
                                         x1, x2  > 0 
 2.          Maximize  z = 10x1 + 3x2
             Subject to:       x1 + 4x2 < 12
                                   3x1 + 2x2 < 18
                                         x1, x2  > 0 
 3.         Maximize:  z = 2x1 + 3x2
              Subject to:     x1 + 3x2 < 10
                                   4x1 +  x2 < 12
                                     x1 +  x2 <  6 
                                      x1, x2   >  0
4.         Maximize:  Z = 3x1 + 5x2
             Subject to:       x1 + 2x2 < 8
                                    3x1 +  x2 <  9
       .                                 x1, x2 > 0   
 5.         Maximize:  Z = 10x1 + 5x2 + 6x3
              Subject to:       3x1 +  x2 + 3x3 < 60
                                       2x1 + 2x2 +  x3 < 50
                                          x1, x2, x3 > 0
6.  A firm manufactures three products,  x1,  x2, and x3, which are sold at market prices of $3, $5,and $4,respectively. The firm has limitations on its machine time and available labor. Total machine time available is 180 hours, and total labor available is 40 man-hours.  Each unit of product x1 requires 2 hours of machine time and one man-hour. Each unit of product x2 requires 3 machine hours and .5 man-hour.   Each unit of product x3 requires 1.5 hours of machine time and 3 man-hours. Set up the linear programming problem of maximizing total revenue subject to the constraints.


III. The Minimizing Problem: The ConstrainedMin Command 
The Simplex algorithm is devised for standard linear programming problems, where the objective function is to be maximized subject to inequalities of the " <" form.  When the problem is a minimizing one with the inequalities of the ">" form, there is no initial standard basis or basic feasible solution and the Simplex algorithm cannot get started.  To solve this problem, a method has been devised which is called Phase I of the Simplex method. The procedure is illustrated in the following example.

Example:  Solve the following linear programming problem, using the Simplex algorithm.
  Minimize:  C = 7y1 + 6y2                 
   Subject to:          y1 + 3y2 > 2                  
                            2y1 +  y2 > 3   
                              y1,  y2  > 0
The first step is to set the inequality constraints to equality by adding surplus variables. A surplus variable (su) is a positive variable that is subtracted from the inequality constraints of the ">" form to set them to equality.
  Minimize:  C = 7y1 + 6y2                 
  Subject to:          y1 + 3y2 - su1 = 2 
                           2y1 +  y2 - su2 = 3 
                             y1,  y2 > 0
Where, su1 and su2 are surplus variables. The Simplex process, however, cannot get started, because there is no standard basis or basic feasible solution. To get the process started, an initial basic feasible solution is created  by adding artificial variables to the constraints.  

Unlike the slack and surplus variables, artificial variables do not have any meaning.  Once artificial variables are added, the Simplex method will have an initial basic feasible solution and can get started.  However, so long as any artificial variable remains at the positive level, we do not have a set of admissible variables that forms a basic feasible solution.

The objective, thus, is to minimize the value of the artificial variables, and if possible, reduce their values to zero.  Therefore, the Phase I problem can be written as
  Minimize:    W = A1 + A2
  Subject to:     y1 + 3y2 - su1 + A1 = 2 
                       2y1 +  y2 - su2 + A2 = 3 
                         y1, y2, su1, su2 >0 
Where,  A1  and  A2  are  artificial  variables. Table.1, below,  represents the table of coefficients. 
Table 1  The Minimizing Problem
_______________________________________________
Variable:    y1     y2     su1     su2     A1     A2     Constant
_______________________________________________                                          
                   1       3      -1        0          1       0           2
                   2       1       0       -1          0       1           3
_______________________________________________
Objective    7       6       0       0          1       1           W

The objective in Phase I is to force W to zero.   If the original problem has a basic feasible solution, Phase I will terminate with W = 0.

The criteria for choosing the pivot column is the same as in maximizing problems.  After all, any minimizing problem can be transformed to a maximizing problem by multiplying it by (-1).  Therefore, in a minimizing problem the negative coefficient of the largest numerical value determines the entering variable.  Hence, the pivot column is the column corresponding to y1, with an objective coefficient of 7. The pivot row is the second constraint.
Table 1 of Phase I
___________________________________________________
Variable:   y1      y2     su1     su2      A1      A2       Constant  
___________________________________________________
                 0       (5/2)       -1       (1/2)        1       -(1/2)         (1/2)            
                 1       (1/2)        0      -(1/2)        0        (1/2)         (3/2)     
__________________________________________________
Objective   0      (5/2)        0       (7/2)        1       -(5/2)      W - (21/2)

The next variable to enter the basic solution is su2, which has the largest coefficient in the objective, ((7/2)).   The pivot row is the first constraint row.
Table 2 of Phase I
______________________________________________
Variable:  y1     y2    su1    su2      A1    A2    Constant
_______________________________________________
                0        5      -2       1         2      -1        1             
                1        3      -1       0         1       0        2            
_____________________________________________
Objective  0    -15      7        0       -6       1     W - 14           

Since A1 and A2 are not in the basic feasible solution, the Phase I terminates here, with A1 = A2 = 0.  As well, W = A1 + A2 = 0. 

If Phase I ends up with a W > 0, it implies that either the system of equations in the constraints are inconsistent and have no solution, or the equations have a solution with at least one of the decision variables being negative.  

 When Phase I terminates in a basis containing only decision and surplus variables, the artificial variables can be dropped from the true objective, and Phase II starts.
Table 1 of Phase II
________________________________________
Variable:    y1     y2    su1   su2    Constant
________________________________________
                  0       5       -2      1        1                  
                  1       3       -1      0        2                  
_______________________________________
Objective    0    -15       7     0       C - 14                 

Based on the Simplex criteria, the variable that contributes to minimizing cost (C) is y2 with a negative marginal contribution of (-15).  Therefore, y2 will enter the basic solution. The pivot row is the row corresponding to the first constraint. 
Table 2 of Phase II
__________________________________________
Variable:    y1     y2    su1   su2     Constant
__________________________________________
                   0      1      -.4      .2          .2               
                   1      0       .2     -.6          1.4             
_________________________________________
Objective    0      0        1      3        C - 11     

The basic feasible solution is y1 = 1.4 and y2 = .2, with the value of C = 11. Since all the coefficients in the objective row are positive or zero, any further iteration will either increase C or will have no effect on C.  Therefore, the above solution is a basic feasible optimal solution.  It is also clear from the solution that the value of the surplus variables su1 = su2 = 0.

To solve the same problem using Mathematica, use the command ConstrainedMin as follows:
Clear[y1,  y2]
ConstrainedMin[
          7  y1  +  6  y2,  {y1  +  3  y2  >=  2,  
            2  y1  +  y2  >=  3},  {y1,  y2}]
{11, {y1 -> (7/5), y2 -> (1/5)}}

Problems:
Solve the following problems through the Simplex method.
1.          Minimize:  C = 13y1 + 18y2
            Subject to:     y1 +  3y2 > 3
                                 4y1 +  2y2 > 2
                                      y1, y2    > 0
2.         Minimize:  C = y1 + 5y2
            Subject to:  4y1 +  y2  > 6
                                 y1 + 2y2  > 5
                                 y1 +10y2  > 13
                                     y1, y2   > 0
3.  Solve problem 1,  when the objective function is C = 6y1 + y2.   
4.         Minimize:  C = y1 + y2     
             Subject to:     3y1 + y2 > 9                
                                    y1 +2y2 > 8
                                    y1, y2 > 0                                   
5.       Minimize:  C = 2y1 + 3y2
            Subject to:      3y1 +  y2 > 12
                                     y1 +  y2 > 7
                                    y1 + 3y2 > 9
                                    y1, y2  > 0
6.  Solve problem 5   for the case where the objective function is  C = 3y1 + 2y2.
7.     Minimize: C = 18y1 + 15y2 +  4y3
            Subject to:      4y1 +  3y2 +1.5y3 > 6
                                 12y1 +  4y2 +   y3 > 10   
                                 12y1 + 10y2 +   y3 > 9
                                     y1, y2, y3  > 0   

IV. Duality
The general form of the linear programming problem in matrix form can be written as:

  Optimize:  z = c'.x
Subject to:  A.x {< = >} b 
                          x > 0
 
Where, c is a nx1 vector of objective coefficients, c' is c transposed, x is a nx1 vector of decision variables, A is a mxn matrix of  constraint coefficients, and b is a mx1 vector of constraints.  The standard form of the linear programming problem is:

  Maximize:  Z = c'.x
   Subject to:  A.x < b
                       x > 0
   
For every linear programming problem there is a corresponding problem, which is called the dual, the solution of which is closely related to the original problem.  The original problem is called primal.  To construct the dual from a primal, take the following steps:

1- Write the primal in standard linear programming form.
2- Change the decision variables x to new variables, say y.  The new variables y are the dual variables or the implicit price of the constraints (b). Therefore, the number of y variables will be as many as the number of the constraints; i.e., y is a mx1 vector.
3- Change the objective from a maximizing problem to a minimizing problem.
4- Change the constraint functions to A'.y, where A' is A transposed.
5- Change the inequalities from "<" to ">" form.
6- Change the place of  b with c.

Hence, the dual can be written as:

Minimize:  C = b'.y
Subject to:  A'.y > c
               y > 0

The following examples demonstrate the procedure.

Example:  Construct the dual problem of the following primal.
  Maximize:  Z = x1 + 3x2
   Subject to:     6x1 + 2x2 < 15
                         3x1 + 5x2 < 40
                         2x1 + 3x2 < 24
                               x1, x2 > 0
The coefficients in matrix form are:  c' = (({{1, 3}})),  x = (({{x1}, {x2}})),  A = (({{6, 2}, {3, 5}, {2, 3}})), and  b = (({{15}, {40}, {24}})).
Since the problem is in standard linear programming form, no change in the sign of the constraints is required.   The dual is: 
Minimize:  C = b'.y = 15y1 + 40y2 + 24y3
Subject to:  A'.y  = (({{6, 3, 2}, {2, 5, 3}})) (({{y1}, {y2}, {y3}})) > (({{1}, {3}}))
                   y > 0
Or:
  Minimize:  C = 15y1 + 40y2 + 24y3
  Subject to:        6y1 +  3y2 +  2y3 > 1
                           2y1 +  5y2 +  3y3 > 3
                            y1, y2, y3  > 0


Example:  Write the dual of the following primal:
  Minimize:  C = 3x1 + 2x2  
  Subject to:         3x1 + 4x2 < 30
                            2x1 +  x2 > 10
                            2x1 + 3x2 > 15  
                                x1, x2 > 0
Since the primal is not in standard form, the first step is to standardize the primal.
  Maximize:   -Z = -3x1 - 2x2
   Subject to:            3x1 + 4x2 <  30
                              -2x1 -  x2   < -10
                              -2x1 - 3x2  < -15
                                  x1, x2  > 0
The dual problem corresponding to this standard form is
  Minimize:  C = 30y1 - 10y2 - 15y3 
  Subject to:           3y1 -  2y2 -  2y3 > -3
                              4y1 -   y2 -  3y3 > -2
                                y1,  y2,  y3 > 0
Dual problems and their solution are of great importance in linear programming models.  In a revenue-maximizing problem, the dual variables represent the implicit prices or the shadow prices of the fixed inputs (b).  Contrary to variable inputs which are bought by the firms at the market prices, there is no market price for fixed inputs.  Dual variables are interpreted as the prices at which the management leases the services of fixed inputs to production managers.  Mathematically, dual variables are the Lagrangian multipliers of the constraints in the Lagrangian function of a linear programming problem.  Therefore, they represent the rate of change of the objective variable with respect to the corresponding constraints.  That is, in a linear programming problem of maximizing revenue with respect to the given input constraints, the dual variable yi = (dZ/dbi).  This implies that yi is the marginal revenue product of input bi.  According to the condition IV of the Kuhn-Tucker condition in Chapter 8, if bi is fully utilized (the constraint is binding), its marginal revenue product or its implicit price will be positive, yi > 0.  On the other hand, if  bi is not fully utilized (the constraint is non-binding), its marginal revenue product will be zero, yi = 0. 

One excellent feature of the Simplex method is that the optimal solution of the primal provides information about the values of the dual variables. The positive values of the entries for the slack variables in the objective row of the final table, or the basic feasible optimal solution, represents the implicit price of corresponding inputs (constraints).  For example, in the final table (Table 3) of the first example of section II, The Simplex Solution of the Linear Programming Models, which is reproduced below,
	 Table 3.  Table of coefficients
______________________________________
Variable:       x1     x2     s1       s2      Constant
_____________________________________
                      0       1      .6      -.2            3
                      1       0     -.2       .4            1
______________________________________
Objective       0       0    -1.4     -.2      Z - 11
the absolute values under the slack variables s1 and s2  in the objective row are 1.4 and .2, respectively.  These coefficients represent the implicit prices of labor (7 units) and capital (6 units), respectively.  The total cost of producing x1 and x2, then is C = 1.4(7) + .2(6) = 11, which is the same as the optimum value of Z. 

Furthermore, the optimal solution of the primal is related to optimal solution of the dual in such a way that if  both the primal and the dual problems have feasible solutions, both have optimal solutions, and the optimal value of the two objective variables will be equal.  In any linear programming problem, (Subscript[x, s]) are the dual variables for the dual problem, and (Subscript[y, s]) are the dual  variables for the primal problem.  Based on the Kuhn-Tucker conditions, if an input, say bi, goes to slack (si > 0), its implicit price or Lagrange multiplier must be zero (yi = 0);  and if an input is fully utilized (si = 0), then its implicit price is positive (yi > 0).  Also, if a surplus variable is positive ((Subscript[su, i]) > 0), the corresponding product incurs a loss or needs a price subsidy and should not be produced (xi = 0); and if a product does not need a surplus or price subsidy ((Subscript[su, i]) = 0),  it should  be produced (xi > 0).   In a linear programming problem, this guarantees that in the optimal solution C = Z.

The following example is designed to show how the solution sets of a primal and a dual in a linear programming are related and how by solving one the solution of the other can be derived.

Example:  Revenue-Maximizing Problem
Suppose the following problem represents a revenue-maximizing problem of a firm that hires the services of three fixed inputs labor, land, and capital at 15, 40, and 24 units each, respectively.  The firm produces two goods, x1 and x2, which are sold at market prices of $1 and $3 each, respectively.  With the given input requirements, the revenue maximizing problem of the firm is modeled as: 
Primal: 	  Maximize:  Z = x1 + 3x2
   Subject to:     6x1 + 2x2 < 15
                         3x1 + 5x2 < 40
                         2x1 + 3x2 < 24
                               x1, x2 > 0                              
The optimal solution of this problem yields the following table:
Optimal Solution Table of Primal
____________________________________________
Variable:       x1     x2     s1       s2       s3	Constant
____________________________________________
                      3       1      .5        0        0	    (15/2)	
                    -12      0     -2.5     1        0               (5/2)
                     -7       0     -1.5     0        1               (3/2)
____________________________________________
Objective      -9       0     -(3/2)     0        0            Z - (45/2)
The primal has a degenerate solution with x1 = 0, x2 = (15/2), and Z = (45/2).  Since s2 and s3 are also in the basic solution of the final table (unit matrix highlighted yellow), s2 = (5/2) and s3 = (3/2).  That is, (5/2) units of the second input and (3/2)units of the third input are idle (go to slack). The positive values of the slack variables in the objective row of the final table are y1 = (3/2), y2 = 0, and y3 =0 ((Subscript[y, s]) are denoting the internal prices of the inputs).  This implies that, the first constraint (labor) is binding and all of the labor input is used in the production process.  Therefore, labor has a positive internal price or shadow price of  y1 =(3/2) .  However, the second and third constraint are non-binding and not all of the land and capital inputs are used in the production.   Therefore, their internal price or shadow prices are zero, y2 = y3 = 0.  Also, the total cost of production is C = ((3/2)) 15 + (0) 40 + (0) 24 = (45/2), which equals to Z. 

The dual problem to this primal changes the problem to a cost-minimizing problem, where the objective is to minimize the cost of inputs given the constraints on the market prices of x1 and x2 which are $1 and $3, respectively.  That is,  
Dual:  	 Minimize:  C = 15y1 + 40y2 + 24y3
  Subject to:        6y1 +  3y2 +  2y3 > 1
                           2y1 +  5y2 +  3y3 > 3
                            y1, y2, y3  > 0
The constraints of the dual problem compare marginal costs and marginal revenues of the products.  The left side of each constraint represents the marginal cost of one product and the right side represents the corresponding marginal revenue or the market price.  If the marginal cost of (Subscript[x, i]) is greater than its marginal revenue, (Subscript[x, i ])'s production requires a subsidy and a profit-maximizing or cost-minimizing firm will produce zero amounts of (Subscript[x, i]).   The optimal solution of this problem is presented in the following table (for the complete solution of the dual, see the Appendix at the end of the chapter).
Final Table of the Optimum Solution to Dual
_______________________________________________
Variable:       y1       y2     y3       su1      su2      Constant
_______________________________________________
                      1       (5/12)     1.5        0         -.5            (3/2)
                      0       12        7          1          -3             8
_______________________________________________
Objective       0       (5/2)       (3/2)        0         (15/2)        C - (45/2)

The feasible optimal solution to the dual is, y1 = (3/2), y2 = y3 = 0, and C = (45/2).  That is, to minimize cost, 15 units of labor input will be used in the production at internal price of y1 = (3/2).  Of course, land and capital are also used in production of x1 and x2.  But, since these inputs are available at excessive amounts, their internal prices are zero, y2 = y3 = 0.  Also, since su1 is in the basic solution (the unit matrix, highlighted yellow), its value is su1 = 8.  That is, the marginal cost of producing the second output (x2) is greater than its marginal revenue by 8 points, or its production requires subsidy.  Therefore, the second product will be produced at zero quantity.  The positive values under the surplus variables (su1 and su2) in the objective row of the final table show the quantities of x1 and x2, respectively.  That is, x1 = 0 and x2 = (15/2).   

The fact that the solution of a primal provides all the information on the solution to its dual or vise versa, can help in solving some dual or primal in an easier way by transforming a primal to dual or a dual to primal, as the case may require.  For example, the dual of the previous example with two constraints and three variables can't be solved using graphic method.  However, by transforming it to its primal (three constraint and two variable) the problem can easily be solved through the graphic method.
The solutions to the previous example can be checked using Mathematica as follows,
Clear[x1,  x2]
ConstrainedMax[
          x1  +  3  x2,  {6  x1  +  2  x2  <=  15,  
            3  x1  +  5  x2  <=  40,  
            2  x1  +  3  x2  <=  24},  {x1,  x2}]
{(45/2), {x1 -> 0, x2 -> (15/2)}}
The solution to dual is,
Clear[y1,  y2,  y3]
ConstrainedMin[
          15  y1  +  40  y2  +  
            24  y3,  {6  y1  +  3  y2  +  2  y3  >=  1,  
            2  y1  +  5  y2  +  3  y3  >=  3},  {y1,  y2,  y3}]
{(45/2), {y1 -> (3/2), y2 -> 0, y3 -> 0}}

Problems:
1.    The following table summarizes the technological relationships between fixed inputs and outputs of a firm.                                 
                                                                                                           
                       x1         x2         x3            x4          Fixed Inputs
         _________________________________________________
         One        5          1            3             1                         90
         Two        2          6            2            4                        120
         __________________________________________________
The products are sold at market prices of p1 = 10, p2 = 6, p3 = 8, and p4 = 3.  Set up linear programming problem and find the optimal solution.
2.    Construct the dual of the problem 1. 
3.    Solve the primal and the dual in problems 1 an 2 and check for the  correspondence of the solution between the dual and primal.
4.   The optimal  feasible solution to a linear programming problem of a firm with three outputs x1, x2, x3, and two fixed inputs labor (L = 45 units) and capital (K = 50 units) is given as follows: (s1 and s2 are slack variables for labor and capital respectively).
         ______________________________________________
                         x1       x2       x3       s1       s2      constant
         ______________________________________________
                       -(1/4)       0         1       (3/4)       2         150
                          1        1        0      -(5/2)      (1/4)       100
         _____________________________________________
         objective  -2      0          0     -8     -11.8     Z - 950                      
         The market prices of the three products are 3, 2, and 5 respectively.
         a) How many units of x1, x2, and x3 will be produced?
         b) What is the total revenue of the firm at the optimal solution?
         c) What are the internal prices of labor and capital?
         d) What is the total cost?
5.    The optimal feasible solution to a linear programming problem of a firm with three outputs x1, x2, x3, and three fixed inputs, labor ( L = 30 units), capital (K = 45 units), and raw material (M = 80) is given as follows: (S1, S2, and S3 are slack variables for labor, capital, and raw material respectively).   
         _______________________________________________________
         Variable:     x1      x2      x3      s1      s2      s3      Constant
         ________________________________________________________
                             0        3       1       (3/4)      0       (5/8)         20
                             0        5       0      -(1/2)      1        3          30
                             1       (1/6)      0        2       0      -(1/4)        25
         ________________________________________________________
         Objective    0      -(1/2)      0    -2(1/3)      0     -.5     Z - 110
         the market prices of the three products are 2, 1, and 3 respectively.
         a) How many units of x1, x2, and x3 will be produced?
         b) What is the total revenue of the firm?
         c) What are the internal prices of labor, capital, and raw material?
         d) What is the total cost?                       


V. Sensitivity Analysis 
Linear programming deals with constrained optimization.  That is, at least in the short-run, the constraints are fixed and they can't be exchanged in the market.  For example, in the revenue-maximizing problem of the section I,

Maximize:  Z = 1.5x1 + x2           
Subject to:   x1 + 2x2 < 7               
                    3x1 +  x2 < 6             
                          x1, x2 > 0                   

we are assuming that labor and capital inputs are fixed at quantities of 7 and 6 units, respectively and the firm can't add to inputs or dispose of inputs.  Input sensitivity analysis deals with relaxing the assumption of fixed constraints and analyzes the effect of a change in one constraint on the optimal solution of the problem.  Let's, for example, relax the assumption of fixed capital input and assume that capital input can be increased.  Given that the first input (labor) is fixed, the question is what will be the effect of increase in capital on total revenue, on outputs (X1 & X2), and what is the limit of the increase in capital.  Formulating the increments in capital to the optimizing problem gives,

Clear[z, u,  x1,  x2]
fu = 
            Table[ConstrainedMax[ 
                2  x1 + 3  x2, {x1  +  2  x2  <=  7, 
                  3  x1  +  x2  <=  6 + i},  {x1,  x2}],  {i,  
                20}];
u = N[Table[List[i,  fu[[i,  1]]],  {i,  20}]];
ListPlot[u,    PlotStyle -> {RGBColor[1, 0, 0],  
                    PointSize[ .03]}, AxesLabel -> {"Capital",  "Revenue"}]


⁃  Graphics  ⁃

the solution and the graph above show that as capital input increases total revenue will increase. With labor input fixed, maximum total revenue is achieved when capital input is 22 units, where X1=7, X2 = 0, and the total revenue is $14.

Now let the first input (labor) be variable and assume that the second input (capital) is fixed.  Formulating the problem into the constrained optimizing problem gives,

Clear[z, u,  x1,  x2]
fu = 
            Table[ConstrainedMax[ 
                2  x1 + 3  x2, {x1  +  2  x2  <=  7 + i, 
                  3  x1  +  x2  <=  6},  {x1,  x2}],  {i,  10}];
u = N[Table[List[i,  fu[[i,  1]]],  {i,  10}]];
ListPlot[u,    PlotStyle -> {RGBColor[1, 0, 0],  PointSize[ .03]}, AxesLabel -> {"Labor",  "Revenue"}]


⁃  Graphics  ⁃

the solution and the graph above show that as labor input increases total revenue will increase. With capital input fixed, maximum total revenue is achieved when labor input is 12 units, where X1= 0, X2 = 6, and the total revenue is $18.

Appendix:  Solution Tables of the Dual Problem

Minimize:   C = 15y1 + 40y2 + 24y3
Subject to:	     6y1 +  3y2  +  2y3 ≥ 1
	                 2y1 +  5y2  +  3y3 ≥ 3
		       y1, y2, y3 ≥ 0

Note:  Pivot columns are highlighted yellow, pivot rows are highlight green.   	       
	Su1 and su2 are surplus variables, A1 and A2 are artificial variables.
	
Table 1.  The Minimizing Problem
________________________________________________________
Variable:    y1      y2      y3       su1      su2      A1     A2     Constant
________________________________________________________                                          
                   6         3       2         -1         0          1         0           36
                   2         5       3          0         -1         0         1           20
________________________________________________________
Objective   15      40     24          0          0          1         1           W


Table 1 of Phase I
________________________________________________________
Variable:    y1      y2      y3         su1       su2        A1     A2     Constant
________________________________________________________                                          
                   2         1       (2/3)         -(1/3)          0         (1/3)         0           (1/3)
                  -8        0      ((-1)/3)          (5/3)         -1        ((-5)/3)        1           (4/3)
________________________________________________________
Objective   -65      0      ((-8)/3)        (40/3)          0        ((-40)/3)       0        W-

Table 2 of Phase I
________________________________________________________
Variable:    y1      y2      y3         su1       su2        A1     A2     Constant
________________________________________________________                                          
                   (2/5)       1       (3/5)         0          -(1/5)          0         (1/5)           (3/5)
                 -(24/5)      0     ((-1)/5)         1          -(3/5)         -1        (3/5)            (4/5)
________________________________________________________
Objective   -1        0       0           0            8           0        -8        W - 24

The Phase one terminates here with A1 = A2 = W = 0


 Table 1 of Phase II
_________________________________________________
Variable:    y1      y2      y3         su1       su2           Constant
_________________________________________________                                          
                   (2/5)       1       (3/5)         0          -(1/5)                   (3/5)
                 -(24/5)      0     ((-1)/5)         1          -(3/5)                   (4/5)
_________________________________________________
Objective   -1        0        0          0            8               C - 24


Table 2 of Phase II, The Final Table
_______________________________________________
Variable:      y1       y2       y3       su1        su2      Constant
_______________________________________________
                     1        (5/2)       (3/2)          0         -(1/2)             (3/2)                 
                     0       12         7           1          -3               8      
_______________________________________________
Objective      0       (5/2)        (3/2)          0         (15/2)         C - (45/2)                 

The optimum solution is y1 = (3/2), y2 = y3 = 0, and C = (45/2).  The solution to the dual problem reveals the solution of the primal also.  The values under su1 and su2 in the objective row are the values of x1 and x2, respectively.  That is, x1 = 0 and x2 = (15/2).  Since x1and x2 are valued at $1 and $3 respectively, Z = (0) 1 + ((15/2)) 3 = (45/2).  That is, in the final solution C = Z = (45/2).