The basic algorithm for solving a standard minimization problem is covered in Section 4.3. This process, called the Simplex Method, uses matrices and row operations to gauge whether an objective function is maximized at corner points.
In the example below, I write out a standard maximization problem from an application and then solve it with the Simplex Method.
How will changes in the objective function’s coefficients change the optimal solution?
In the previous question, we examined how changing the constants in the constraints changed the optimal solution to a standard maximization problem. Such modification led to a different feasible region and changes to the optimal solution.
In this question, we examine how changes in the coefficients of the objective function change the optimal solution. If one of the coefficients of the objective function increases or decreases, the feasible region remains the same. Since the feasible region is defined by the constraints and not the objective function, there are no changes to the corner points. A change in one of the coefficients changes the slope of the isoline, the line that corresponds to setting the objective function equal to a constant.
Let’s recall the problem we have been analyzing:
Figure 10 – A standard maximization problem and its corresponding feasible region.
The objective function takes on the optimal value P = 3450 at the corner point (15, 20). The isoprofit line 70x + 120y = 3450 just touches the feasible region at that point verifying this assertion.
Now let’s try increasing and decreasing the coefficient on x in the objective function.
Figure 11 – This graph shows the feasible region with the isoprofit line at the optimal solution (gray dashed line) and the isoprofit line for the optimal solution in the modified problem (purple dashed line). The coefficient on x has decreased from 70 to 40.
As the coefficient on x is decreased, the isoprofit line for the optimal solution gets less steep. At a value of 40, the isoprofit line passes through (0, 25) and (15, 20). At this point, the isoprofit line forms the border of the feasible region there so all points on the line between (0, 25) and (15, 20) yield the same maximum profit. If the coefficient is decreased to a value less than 40, (15, 20) is no longer part of the optimal solution.
Figure 12 -This graph shows the feasible region with the isoprofit line at the optimal solution (gray dashed line) and the isoprofit line for the optimal solution in the modified problem (purple dashed line). The coefficient on x has increased from 70 to 120.
As the coefficient on x is increased, the isoprofit line for the optimal solution gets steeper. At a value of 120, the isoprofit line passes through (0, 25) and (25, 10). The isoprofit line forms the border of the feasible region there, so all points on the line between (0, 25) and (25, 10) yield the same maximum profit. If the coefficient is increased to a value greater than 120, (15, 20) is no longer part of the optimal solution.
As long as the coefficient on x in the objective function falls between 40 to 120, the optimal solution includes (x, y) = (15, 20). If the coefficient is equal to 40 or 120, any ordered pair on a line connecting (15, 20) to one of the adjacent corner points is optimal. However, if the coefficient on x falls outside of 40 to 120 the optimal solution moves to a new corner point.
Recall that the coefficient on x in the objective function is the profit for each frame bag. If the profit per frame bag were to increase by up to $50 (to $120) or decrease by up to $30 (to $40), the optimal solution would not change. This solution, 15 frame bags and 20 panniers, is fairly insensitive to changes in the coefficient on x. Even though the location of the optimal solution does not change over this range, the profit does not change. Notice that we are only varying one coefficient at a time. Varying both coefficients simultaneously is beyond the scope of this presentation.
Example 3 Find the Range of Values For Which a Corner Point Remains Optimal
The coefficient on y in the objective function for the linear programming problem
can be varied to find a range of values over which (15, 20) is the optimal solution. Over what range of coefficient values will (15, 20) remain optimal?
Solution Let’s examine the graphical solution for this linear programming problem.
From the earlier discussion on varying the coefficient on x, we observed that changing the coefficient causes the slope of the isoprofit to change. If the slope of the isoprofit line increases so that it coincides with the constraint x + y ≤ 35, the optimal solution is all points on the line connecting (15, 20) and (25, 10). If the slope of the isoprofit line decreases so that it coincides with the constraint x + 3y ≤ 75, the optimal solution is all point on the line connecting (15, 20) and (0, 25).
Figure 13 – In a, the coefficient on y in the objective function has been increased from 120 to 210. In b, the coefficient on y has been decreased from 120 to 70.
As long as the coefficient on y falls in the range 70 to 210, the solution (15, 20) is optimal. Outside of this range, (15, 20) is no longer optimal. If we can determine the coefficient values that cause the isoprofit line to fall on the binding constraint borders, we know the range of values over which the solution remains optimal.
In Figure 13a, the constraint border x + 3y = 35 and isoprofit line 70x + 210y = 5250 coincide. Notice that on each line, the coefficient on y is three times as large as the coefficient on x. Because of this, both lines have the same slope. We can always use this information to find the values of any missing constraints.
For instance, to find the coefficient on y in the objective function that makes its slope the same as the slope on x + y = 35, we can observe that the coefficients must be the same. Therefore, the coefficients in the objective function must be the same. Since we have fixed the coefficient on x and are only varying the coefficient on y, we conclude that isoprofit lines for P = 70x + 70y are parallel to the constraint border x + y = 35. In particular, the isoprofit line 70x +70y = 2450 is exactly the same line.
Putting this together, we observe that the coefficient on y can range from 70 to 210 and the corner point at (15, 20) is optimal.
How will changes in a constraint’s constant change the optimal solution?
To help us answer this question, let’s develop a new application. Unlike earlier applications of the Simplex Method, this application will be an oversimplified example to make the sensitivity analysis easier to understand. Once we have developed and solved this application, we’ll examine how the optimal solution changes when we change the constants on the right hand side of the constraints.
Example 1 Solve the Standard Maximization Problem
A custom manufacturer of bicycle accessories produces two types of bags which can be mounted on a bicycle. Frame bags are mounted in the interior frame of a bicycle, and panniers are mounted on a rack over the rear wheel of a bicycle. Each of these products is built to the measurements of the customer’s bicycle and involves a large outlay of employee labor.
The manufacturer has enough materials on hand to produce a total of 35 frame bags and panniers each week. Several employees produce these products. Two employees are able to dedicate 75 hours each week to cut the fabric for these products, and two other employees are able to dedicate 60 hours each week to assembling and packing the products.
Each frame bag takes employees one hour to cut the fabric and two hours to assemble and package. Each pannier takes employees three hours to cut the fabric and one hour to assemble and package. If the profit from each frame bag is $70 and the profit from each pannier is $120, how many units of each product should the manufacturer accept to insure that profit is maximized?
Solution Assume this manufacturer can pick and choose which orders to accept so that it is able to maximize profit by allocating its resources most efficiently. The basic question we must answer is how many frame bags and how many panniers will be produced so that the profit is as large as possible? This indicates the variables should be defined as
x: the number of frame bags produced each week
y: the number of panniers produced each week
Each frame bag generates $70 of profit, and each pannier generates $120 of profit. We can use this information to write the total profit P as
P = 70x + 120y
If the amount of materials and labor is unlimited, the manufacturer can produce an unlimited number of frame bags and panniers for an unlimited amount of profit.
However, this manufacturer has a limited amount of materials and labor available. The total number of frame bags and panniers that can be produced in a week is 35. Since the variables describe the individual numbers of each product, we know that
x + y ≤ 35
The total number of labor hours available for cutting fabric is 75 hours. This total relates to the individual amounts of time required to cut frame bags (1 hour per frame bag) and panniers (3 hours per pannier). By multiplying the amounts per product by the variables, we get the amount of cutting time for x frame bags, 1x, and the amount of cutting time for y panniers, 3y. The constraint
x + 3y ≤ 75
indicates that the total amount time required to cut the material must be less than or equal to 75 hours.
The same type of reasoning for assembly and packaging yields the constraint
2x + y ≤ 60
Putting the constraints and objective function together with non-negativity constraints yields the standard maximization problem,
The initial simplex tableau for this linear programming problem is
The pivot for this matrix is the 3 in the second row and second column. To change this entry to a 1, multiply the second row by 1/3:
To complete the first iteration of the Simplex Method, we need to use row operations to fill the rest of the second column with zeros.
Since the indicator row contains a negative entry in the first column, we need to choose a new pivot.
The first column is the pivot column. Let’s examine the quotients to determine the pivot row:
The lowest quotient, 15, is formed from the last column and the pivot column occurs in the first row so we’ll pick the pivot to be the 2/3 . Multiply the pivot row by 3/2 to create a 1 in the first row, first column:
Next, use row operations to create zeros below the pivot.
Since the indicator row contains no negative numbers, we can use this tableau to read the optimal solution.
If we cover the nonbasic variables,
we see that the optimal solution is x = 15, y = 20. This means the largest profit, $3450, occurs when 15 frame bags and 20 panniers are produced each week.
Since this problem contains two decision variables xand y, we can also solve this problem graphically.
Figure 1 – The feasible region for Example 1.
Figure 1 shows the feasible region corresponding to the constraints for the linear programming problem. The dashed line corresponds to the isoprofit at P = 3450. Any profit higher than $3450 pushes the isoprofit outside of the feasible region, and any lower pushes it inside the feasible region. The solution pictured here, (15, 20), is the greatest profit in the feasible region.
In Example 1, the Simplex Method and the graphical method for solving the linear programming problem both indicate that 15 frame bags and 20 panniers should be produced to achieve a maximum profit of $3450. The question we want to examine now is what would happen if the linear programming problem were changed slightly. For instance, what would happen if the constants in any of the constraints were to change?
Questions such as this one often arise in business applications since the values in the linear programming problem are estimates. Estimates are subject to error or changing values if operating conditions change for the business. An example would be if another person was utilized to help produce frame bags and panniers. This would clearly impact the number of hours that would be available for cutting, assembly and packaging. Will this change the optimal solution? Will it increase or decrease the profit?
To answer these questions, let’s change the constant in the second constraint. Suppose the number of hours available for cutting increases from 75 to 87. This changes the second constraint in the linear programming problem from x + 3y ≤ 75 to x + 3y ≤ 87. This change does not affect the slope of the line, but it does shift the line up vertically.
Figure 2 – Increasing the number of hours available for cutting shifts the border of the cutting constraint up.
This change moves the corner point at (15, 20) to (9, 26). The corner point matching the optimal solution has moved.
We would expect the optimal solution to change also.
Figure 3 – The solution to the linear programming problem with 87 hours available to cutting.
The corner point matching the optimal solution moves from (15, 20) to (9, 26) when the number of hours for cutting increases by 12 hours. The increased availability of labor increases the profit from $3450 to $3750. The extra 12 hours of labor increases the profit by $300.
We can also see how the profit changes if the number of hours for cutting decreases by 12 hours. In this case, the constraint x + 3y ≤ 75 becomes x + 3y ≤ 63. In this case, the border of the feasible region shifts down.
Figure 4 – Decreasing the number of hours available for cutting shifts the border of the cutting constraint down.
This change shifts the corner point from (15, 20) to (21, 14). This ordered pair yields the maximum profit of
P = 70 (21) + 120 (14) = 3150
Figure 5 – The solution to the linear programming problem with 63 hours available to cutting.
Decreasing the available cutting time from 75 hours to 63 hours reduces the maximum profit from $3450 to $3150. This tells us that each hour the cutting time is reduced, drops the profit by $25.
Whether the cutting time is increased or decreased by 12 hours, the change in profit is $300. Another way to say this is that a change of one hour of cutting time changes profit by $25 since
This value is called the shadow price of the constraint.
The shadow price of a constraint is the amount the objective function changes at the optimal solution when the constant in the constraint is increased by one unit.
For a standard maximization problem, the shadow price of a constraint appears in the final simplex tableau. Recall the final simplex tableau for this linear programming problem,
The shadow price for the second constraint is located in the fourth column of the indicator row.
Each constraint in the standard maximization problem has a shadow price associated with it. The shadow prices are located in the indicator row of the final simplex tableau beneath the slack variables.
Example 2 Find and Interpret the Shadow Price
The standard linear programming problem from Example 1,
has a final simplex tableau
Suppose amount of material available increased so that an additional 5 frame bags or panniers could be made each week. This will change the first constraint from from x + y ≤ 35 to x + y ≤ 40.
a. Find the shadow price for this constraint.
Solution Increasing the amount of available material for a total of 5 more frame bags and panniers changes the first constraint from x + y ≤ 35 to x + y ≤ 40. The shadow price for this constraint is located in the indicator row under the slack variable corresponding to the constraint, s1. In this case, the shadow price is 45.
b. How will profit change when the total capacity to produce frame bags and panniers is increased from 35 to 40?
Solution The shadow price of 45 relates an increase in the constant in the first constraint to an increase in the objective function. This means increasing the capacity to produce frame bags and panniers by 1 unit increases the profit by $45. A five unit increase would increase the profit by five times as much, 5 ($45) = $225.
Shadow prices help us to make informed decisions about changing the resources (the constants in the constraints) for a problem. Knowing the benefits of changing the constant in one of the constraints allow us to decide whether the costs of making this change is reasonable. For instance, if increasing capacity by five units increases profit by $225, but costs $250 to make that change, then the change is not warranted.
In Example 2, we changed the constant in one of the constraints whose border passed through the optimal solution. Now let’s examine how changing the constant in a constraint whose border does not pass through the optimal solution affects the solution to the linear programming problem. Let’s look the first two constraints at the optimal solution (15, 20):
If the optimal solution is substituted into the left hand side of the first two constraints, the left hand side is equal to the right hand side. This means that at the optimal solution, the entire capacity is being utilized and all of the cutting time is being utilized to produce 15 frame bags and 20 panniers.
This type of behavior defines a binding constraint. At binding constraints, the resources modeled by the constraint are fully utilized.
The same cannot be said of nonbinding constraints. Let’s look at the third constraint at the optimal solution (15, 20):
In this constraint, substituting the optimal solution in the left hand side yields a value of 50. This means that only 50 hours of assembly and finishing time is utilized to produce 15 frame bags and 20 panniers. Ten hours of the available 60 hours for assembly and finishing is not utilized. In the language of linear programming, we say there is 10 hours of slack in this constraint.
If the hours for assembly and finishing are underutilized, adding more time for assembly and finishing will not change the optimal solution.
When the amount of time is for assembly and finishing is decreased by 5 hours, the shape of the feasible region changes. The corner point at (25, 10) moves to (20, 15). At this point, there is still 5 hours of slack, so 5 hours of assembly and finishing time is not being utilized. This has no effect on the optimal solution.
Figure 6 – If the amount of time available for assembly and finishing is reduced by 5 hours to 55 hours, the assembly and finishing constraint shifts down. This moves the corner point at (25,10) to (20, 15).
Once the amount of time is reduced by an amount that eliminates the slack, the constraint on assembly and finishing affects the solution. If the amount of time for assembly and finishing is dropped to 50 hours, all three constraints intersect at the same point, and all three constraints are binding. In this case, the capacity, cutting time and assembly and finishing time are fully utilized.
Figure 7 – If the amount of time available for assembly and finishing is reduced by 10 hours to 50 hours, the assembly and finishing constraint shifts down. This moves the corner point at (25,10) to (15, 20).
If the amount of time for assembly and finishing is reduced below 50 hours, the assembly and finishing constraint becomes binding, and the capacity constraint becomes nonbinding. Any changes in the assembly and finishing constraint now move the optimal corner point to a new position.
Figure 8 – If the amount of time available for assembly and finishing is reduced by 15 hours to 45 hours, the assembly and finishing constraint shifts down. This reduction causes the optimal solution to change to (12, 20).
For instance, if only 45 hours are available for assembly and finishing, the optimal solution is to produce 12 frame bags and 21 panniers. All of the cutting time and assembly and finishing time is fully utilized, but the capacity is underutilized since only 33 products are being produced.
These changes can be summarized by saying that the total amount of time for assembly and finishing time can be increased above 60 hours an unlimited amount without affecting the optimal solution. But if the total amount of time for assembly and finishing is reduced by more than 10 hours below 50 hours, the optimal solution will move to a new position.
Precautions must be taken when interpreting shadow prices. Shadow prices are valid for the optimal corner point over a range of changes to the constant in a constraint. In the standard maximization problem we have been examining, we can increase the amount of time allotted for cutting by 30 or decrease the amount of time allotted for cutting by 20 and still change the profit 45 for each 1 hour change in cutting time.
Figure 9 – In graph a, the constant in the second constraint has been decreased from 75 to 55 and the optimal corner point is relocated from (15, 20) to (25, 10). In graph b, the constant in the second constraint has been increased from 75 to 105 and the optimal corner point is relocated from (15, 20) to (0, 35).
As long as the constant on the right hand side of the second constraint varies from 55 to 105, the same two constraints are binding. Any values outside of this range changes which constraints are binding. This occurs because the optimal corner point no longer falls on the border of the cutting constraint and the capacity constraint.
Recall the linear programming problem for the contract breweries from sections 4.2 and 4.4:
In this problem, we wish to minimize the cost C of producing barrels Q1 of American ale from brewery 1 and Q2 barrels of American ale from brewery 2. The final simplex tableau for this problem is
Shadow prices for standard minimization problems are found in a different location of the final simplex tableau. The solution to this problem, (Q1, Q2) = (8000, 2000), is found beneath the slack variables in the indicator row. The shadow prices are located in the first two rows of the last column.
The shadow price for the production requirement is 105. If the production requirement of producing at least 10,000 barrels is increased by 1 unit to 10,001 barrels, the total cost will increase by $105. The shadow price for the constraint -0.25Q1 + Q2 ≥ 0 is 20. If the right hand side were to increase by one unit from 0 to 1, the total cost would increase by $20. Changing the right hand side of Q1 – Q2 ≥ 0 by 1 unit does not change the total cost.
How do you apply the Simplex Method to a minimization application?
The dual problem strategy works for standard minimization problems involving more variables or more constraints. Example 4 has two decision variables, but three constraints. This changes the sizes of the matrices involved, but not the process of applying the Simplex Method to the dual standard maximization problem.
Example 4 Find the Minimum Cost
In Section 4.2, we found the cost C of contracting barrels of American ale from contract brewery 1 and barrels of America ale from contract brewery 2. The linear programming problem for this application is
Follow the parts a through c to solve this linear programming problem.
a. Rewrite this problem so that it is a standard minimization problem.
Solution The objective function must have the form w = d1y1 + d2y2 + … + dn yn where y1, y2, … , yn are the decision variables, and d1, d2, … , dn are constants. In this case the decision variables are Q1 and Q2, and C is used instead of w. A different name for the variable is acceptable as long as the terms on the right side each contain a constant times a variable.
The constraints must have the form e1y1 + e2y2 + … + en yn ≥ f, where e1, e2, … , enand f are constants. The first constraint, Q1 + Q2 ≥ 100, has the proper format, but with the decision variables Q1 and Q2 instead of y1 and y2.
The second and third constraints must be modified to match the form e1y1 + e2y2 + … + en yn ≥ f. Subtract 0.25Q1 from both sides of the constraint Q2 ≥ 0.25Q1 to yield
-0.25Q1 + Q2 ≥ 0
The third constraint is converted to the proper form by rearranging the inequality Q1 ≥ Q2. Subtract Q2 from both sides to yield
Q1 – Q2 ≥ 0
These changes lead to a standard minimization problem,
b. Find the dual problem for the standard minimization problem.
Solution The dual maximization problem is found by forming a matrix from the constraints and objective function. The coefficients and constants in the constraints compose the first three rows. The coefficients from the objective function are placed the fourth row of the matrix.
The dual maximization problem’s coefficients and constant are found by switching the rows and columns of the matrix
We’ll use the decision variables x1, x2, and x3 and write the corresponding dual maximization problem,
c. Apply the Simplex Method to the dual problem to find the solution to the standard minimization problem.
Solution The standard minimization problem is solved by applying the Simplex Method to the dual maximization problem. The first step is to write out the system of equations we’ll work with including the slack variables:
This system of equations corresponds to the initial simplex tableau
The only negative number in the indicator row is -10,000, so the pivot column is the first column. We choose the pivot row by forming quotients from the last column and the pivot column:
The smallest quotient is 100 so the first row is the pivot row.
Conveniently, the pivot is already a 1 and we can use row operations to change the rest of the column to zeros.
The new matrix still has a negative number in the indicator row, so we must choose a new pivot. The second column is the pivot column. The second row is the pivot row since it contains the only admissible quotient, 25/1.25.
The pivot, 1.25, is changed to a 1 by multiplying the second row by 1/1.25:
With a 1 in the pivot, we can use row operations to put zeros in the rest of the pivot column. Multiply the pivot row by 0.25 and add it to the first row to put a zero at the top of the pivot column. Multiply the pivot row by 2500 and add it to the third row to put a zero at the bottom of the pivot row:
No entry in the indicator row is negative, so we know that this tableau corresponds to the solution. The solution to the minimization problem lies in the indicator row in the columns corresponding to the slack variables,
The lowest cost is $1,050,000 and occurs when (Q1, Q2) = (8000, 2000). This means the lowest cost occurs when 8000 barrels are contracted from brewery 1 and 2000 barrels are contracted from brewery 2.