LP: Iso-Profit Line Method — Corner-Point Method — Sensitivity Analysis
FORMULATING LINEAR PROGRAMMING PROBLEMS
One of the most common linear programming applications is the product-mix problem. Two or more products are usually produced using limited resources. The company would like to determine how many units of each product it should produce to maximize overall profit given its limited resources.
Let’s look at an example.
Shader Electronics Example
The Shader Electronics Company produces two products: (1) the Shader Walkman, a portable CD/DVD player, and (2) the Shader Watch-TV, a wristwatch-size internet-connected color television. The production process for each product is similar in that both require a certain number of hours of electronic work and a certain number of labor-hours in the assembly department. Each Walkman takes 4 hours of electronic work and 2 hours in the assembly shop. Each Watch-TV requires 3 hours in electronics and 1 hour in assembly. During the current production period, 240 hours of electronic time are available, and 100 hours of assembly department time are available. Each Walkman sold yields a profit of $7; each Watch-TV produced may be sold for a $5 profit.
Shader’s problem is to determine the best possible combination of Walkmans and Watch-TVs to manufacture to reach the maximum profit. This product-mix situation can be formulated as a linear programming problem.
Table B.1
Shader Electronics Company Problem Data
We begin by summarizing the information needed to formulate and solve this problem (see Table B.1). Further, let’s introduce some simple notation for use in the objective function and constraints. Let
X1= number of Walkmans to be produced X2= number of Watch-TVs to be produced
Now we can create the LP objective function in terms of X1 and X2:
Maximize profit=$7X1+$5X2
We name the decision variables X1 and X2 here but point out that any notation (such as WM and WT) would be fine as well.
Our next step is to develop mathematical relationships to describe the two constraints in this problem. One general relationship is that the amount of a resource used is to be less than or equal to (≤) the amount of resource available.
First constraint: Electronic time used is ≤ Electronic time available.
4X1+3X2≤240 (hours of electronic time)
Second constraint: Assembly time used is ≤ Assembly time available.
2X1+1X2≤100 (hours of assembly time)
Both these constraints represent production capacity restrictions and, of course, affect the total profit. For example, Shader Electronics cannot produce 70 Walkmans during the production period because if X1=70, both constraints will be violated. It also cannot make X1=50 Walkmans and X2=10 Watch-TVs. This constraint brings out another important aspect of linear programming; that is, certain interactions will exist between variables. The more units of one product that a firm produces, the fewer it can make of other products.
GRAPHICAL SOLUTION TO A LINEAR PROGRAMMING PROBLEM
The easiest way to solve a small LP problem such as that of the Shader Electronics Company is the graphical solution approach. The graphical procedure can be used only when there are two decision variables (such as number of Walkmans to produce, X1, and number of Watch-TVs to produce, X2). When there are more than two variables, it is not possible to plot the solution on a twodimensional graph; we then must turn to more complex approaches described later in this module.
Graphical solution approach
A means of plotting a solution to a two-variable problem on a graph.
Decision variables
Choices available to a decision maker.
Graphical Representation of Constraints
To find the optimal solution to a linear programming problem, we must first identify a set, or region, of feasible solutions. The first step in doing so is to plot the problem’s constraints on a graph.
The variable X1 (Walkmans, in our example) is usually plotted as the horizontal axis of the graph, and the variable X2 (Watch-TVs) is plotted as the vertical axis. The complete problem may be restated as:
Maximize profit =$7X1+$5X2
Subject to the constraints
4X1+3X2≤240 (electronics constraint)
2X1+1X2≤100 (assembly constraint) X1≥0 (number of Walkmans produced is greater than or equal to 0) X2≥0 (number of Watch TVs produced is greater than or equal to 0)
These two constraints are also called the nonnegativity constraints.
The first step in graphing the constraints of the problem is to convert the constraint inequalities into equalities (or equations).
The equation for constraint A is plotted in Figure B.1 and for constraint B in Figure B.2.
To plot the line in Figure B.1, all we need to do is to find the points at which the line 4X1+3X2=240 intersects the X1 and X2 axes. When X1=0 (the location where the line touches the X2 axis), it implies that 3X2=240 and that X2=80. Likewise, when X2=0, we see that 4X1=240 and that X1=60. Thus, constraint A is bounded by the line running from (X1=0, X2=80) to (X1=60, X2=0). The shaded area represents all points that satisfy the original inequality.
Constraint B is illustrated similarly in Figure B.2. When X1=0, then X2=100; and when X2=0, then X1=50. Constraint B, then, is bounded by the line between (X1=0, X2=100) and (X1=50, X2=0). The shaded area represents the original inequality.
Figure B.3 shows both constraints together. The shaded region is the part that satisfies both restrictions. The shaded region in Figure B.3 is called the area of feasible solutions, or simply the feasible region.
Feasible region
The set of all feasible combinations of decision variables.
This region must satisfy all conditions specified by the program’s constraints and is thus the region where all constraints overlap. Any point in the region would be a feasible solution to the Shader Electronics Company problem. Any point outside the shaded area
would represent an infeasible solution. Hence, it would be feasible to manufacture 30 Walkmans
FIGURE B.1 ■ Constraint A
FIGURE B.2 ■ Constraint B
FIGURE B.3 ■ Feasible Solution Region for the Shader Electronics Company Problem
and 20 Watch-TVs (X1=30, X2=20), but it would violate the constraints to produce 70 Walkmans and 40 Watch-TVs. This can be seen by plotting these points on the graph of Figure B.3.
Iso-Profit Line Solution Method
Now that the feasible region has been graphed, we can proceed to find the optimal solution to the problem. The optimal solution is the point lying in the feasible region that produces the highest profit.
Once the feasible region has been established, several approaches can be taken in solving for the optimal solution. The speediest one to apply is called the iso-profit line method.
Iso-profit line method
An approach to solving a linear programming maximization problem graphically.
We start by letting profits equal some arbitrary but small dollar amount. For the Shader Electronics problem, we may choose a profit of $210. This is a profit level that can easily be obtained without violating either of the two constraints. The objective function can be written as $210=7X1+5X2.
This expression is just the equation of a line; we call it an iso-profit line. It represents all combinations (of X1, X2) that will yield a total profit of $210. To plot the profit line, we proceed exactly as we did to plot a constraint line. First, let X1=0 and solve for the point at which the line crosses the X2 axis:
$210=$7(0)+$5X2 X2=42 Watch-TVs
Then let X2=0 and solve for X1:
$210=$7X1+$5(0) X1=30 Walkmans
We can now connect these two points with a straight line. This profit line is illustrated in Figure B.4. All points on the line represent feasible solutions that produce a profit of $210.
We see, however, that the iso-profit line for $210 does not produce the highest possible profit to the firm. In Figure B.5, we try graphing two more lines, each yielding a higher profit. The middle equation, $280=$7X1+$5X2, was plotted in the same fashion as the lower line. When X1=0,
$280=$7(0)+$5X2 X2=56 Watch-TVs
Iso means “equal” or “similar.” Thus, an iso-profit line represents a line with all profits the same, in this case $210.
FIGURE B.4 ■ A Profit Line of $210 Plotted for the Shader Electronics Company
FIGURE B.5 ■ Four Iso-Profit Lines Plotted for the Shader Electronics Company
When X2=0,
$280=$7X1+$5(0) X1=40 Walkmans
Again, any combination of Walkmans (X1) and Watch-TVs (X2) on this iso-profit line will produce a total profit of $280.
Note that the third line generates a profit of $350, even more of an improvement. The farther we move from the 0 origin, the higher our profit will be. Another important point to note is that these iso-profit lines are parallel. We now have two clues as to how to find the optimal solution to the original problem. We can draw a series of parallel profit lines (by carefully moving our ruler in a plane parallel to the first profit line). The highest profit line that still touches some point of the feasible region will pinpoint the optimal solution. Notice that the fourth line ($420) is too high to count because it does not touch the feasible region.
The highest possible iso-profit line is illustrated in Figure B.6. It touches the tip of the feasible region at the corner point (X1=30, X2=40) and yields a profit of $410.
FIGURE B.6 ■ Optimal Solution for the Shader Electronics Problem
Corner-Point Solution Method
A second approach to solving linear programming problems employs the corner-point method. This technique is simpler in concept than the iso-profit line approach, but it involves looking at the profit at every corner point of the feasible region.
Corner-point method
A method for solving graphical linear programming problems.
The mathematical theory behind linear programming states that an optimal solution to any problem (that is, the values of X1, X2 that yield the maximum profit) will lie at a corner point, or extreme point, of the feasible region. Hence, it is necessary to find only the values of the variables at each corner; the maximum profit or optimal solution will lie at one (or more) of them.
Once again we can see (in Figure B.7) that the feasible region for the Shader Electronics Company problem is a four-sided polygon with four corner, or extreme, points. These points are labeled ①, ②, ③ and ④ on the graph. To find the (X1, X2) values producing the maximum profit, we find out what the coordinates of each corner point are, then determine and compare their profit levels.
Point ①: (X1=0, X2=0) Profit $7(0)+$5(0)=$0
Point ②: (X1=0, X2=80) Profit $7(0)+$5(80)=$400
Point ④: (X1=50, X2=0) Profit $7(50)+$5(0)=$350
We skipped corner point ③ momentarily because to find its coordinates accurately, we will have to solve for the intersection of the two constraint lines. As you may recall from algebra, we can apply the method of simultaneous equations to the two constraint equations:
To solve these equations simultaneously, we multiply the second equation by -2:
-2(2X1+1X2=100)=-4X1-2X2=-200
and then add it to the first equation:
4X1+3X2=240 -4X1-2X2=-200+
+1X2=40
or X2=40.
FIGURE B.7 ■
The Four Corner Points of the Feasible Region
Doing this has enabled us to eliminate one variable, X1, and to solve for X2. We can now substitute 40 for X2 in either of the original equations and solve for X1. Let us use the first equation. When X2=40, then
4X1+3(40)=240
4X1+120=240
or
4X1=120 X1=30
Although the values for X1 and X2 are integers for Shader Electronics, this will not always be the case.
Thus, point ③ has the coordinates (X1=30, X2=40). We can compute its profit level to complete the analysis:
Point: (X1=30, X2=40) Profit=$7(30)+$5(40)=$410
Because point ③ produces the highest profit of any corner point, the product mix of X1=30 Walkmans and X2=40 Watch-TVs is the optimal solution to the Shader Electronics problem. This solution will yield a profit of $410 per production period; it is the same solution we obtained using the iso-profit line method.
SENSITIVITY ANALYSIS
Operations managers are usually interested in more than the optimal solution to an LP problem. In addition to knowing the value of each decision variable (the X_is) and the value of the objective function, they want to know how sensitive these answers are to input parameter changes. For example, what happens if the coefficients of the objective function are not exact, or if they change by 10% or 15%? What happens if right-hand-side values of the constraints change? Because solutions are based on the assumption that input parameters are constant, the subject of sensitivity analysis comes into play. Sensitivity analysis, or postoptimality analysis, is the study of how sensitive solutions are to parameter changes.
Parameter
Numerical value that is given in a model. Sensitivity analysis
An analysis that projects how much a solution may change if there are changes in the variables or input data.
There are two approaches to determining just how sensitive an optimal solution is to changes. The first is simply a trial-and-error approach. This approach usually involves resolving the entire problem, preferably by computer, each time one input data item or parameter is changed. It can take a long time to test a series of possible changes in this way.
The approach we prefer is the analytic postoptimality method. After an LP problem has been solved, we determine a range of changes in problem parameters that will not affect the optimal solution or change the variables in the solution. This is done without resolving the whole problem. LP software, such as Excel’s Solver or POM for Windows, has this capability. Let us examine several scenarios relating to the Shader Electronics example.
Program B.1 is part of the Excel Solver computer-generated output available to help a decision maker know whether a solution is relatively insensitive to reasonable changes in one or more of the parameters of the problem. (The complete computer run for these data, including input and full output, is illustrated in Programs B.2 and B.3 later in this module.)
Sensitivity Report
The Excel Sensitivity Report for the Shader Electronics example in Program B.1 has two distinct components: (1) a table titled Adjustable Cells and (2) a table titled Constraints. These tables permit us to answer several what-if questions regarding the problem solution.
The Sensitivity Report has two parts: Adjustable Cells and Constraints.
We are analyzing only one change at a time.
It is important to note that while using the information in the sensitivity report to answer what-if questions, we assume that we are considering a change to only a single input data value. That is, the sensitivity information does not always apply to simultaneous changes in several input data values.
The Adjustable Cells table presents information regarding the impact of changes to the objective function coefficients (i.e., the unit profits of $7 and $5) on the optimal solution. The Constraints table presents information related to the impact of changes in constraint right-hand-side (RHS) values (i.e., the 240 hours and 100 hours) on the optimal solution. Although different LP software packages may format and present these tables differently, the programs all provide essentially the same information.
PROGRAM B.1 ■
Sensitivity Analysis for Shader Electronics Using Excel’s Solver
Changes in the Resources or Right-Hand-Side Values
The right-hand-side values of the constraints often represent resources available to the firm. The resources could be labor-hours or machine time or perhaps money or production materials available. In the Shader Electronics example, the two resources are hours available of electronics time and hours of assembly time. If additional hours were available, a higher total profit could be realized. How much should the company be willing to pay for additional hours? Is it profitable to have some additional electronics hours? Should we be willing to pay for more assembly time? Sensitivity analysis about these resources will help us answer these questions.
If the size of the feasible region increases, the optimal objective function
value could improve. .
If the right-hand side of a constraint is changed, the feasible region will change (unless the constraint is redundant), and often the optimal solution will change. In the Shader example, there were 100 hours of assembly time available each week and the maximum possible profit was $410. If the available assembly hours are increased to 110 hours, the new optimal solution seen in Figure B.8(a) is (45, 20) and the profit is $415. Thus, the extra 10 hours of time resulted in an increase in profit of $5 or $0.50 per hour. If the hours are decreased to 90 hours as shown in Figure B.8(b), the new optimal solution is (15, 60) and the profit is $405. Thus, reducing the hours by 10 results in a decrease in profit of $5 or $0.50 per hour. This $0.50 per hour change in profit that resulted from a change in the hours available is called the shadow price, or dual value. The shadow price for a constraint is the improvement in the objective function value that results from a one-unit increase in the right-hand side of the constraint.
Shadow price (or dual)
The value of one additional unit of a scarce resource in LP.
Validity Range for the Shadow Price
Given that Shader Electronics’ profit increases by $0.50 for each additional hour of assembly time, does it mean that Shader can do this indefinitely, essentially earning infinite profit? Clearly, this is illogical. How far can Shader increase its assembly time availability and still earn an extra $0.50 profit per hour? That is, for what level of increase in the RHS value of the assembly time constraint is the shadow price of $0.50 valid?
The shadow price is valid only as long as the change in the RHS is within the Allowable Increase and Allowable Decrease values.
The shadow price of $0.50 is valid as long as the available assembly time stays in a range within which all current corner points continue to exist. The information to compute the upper and lower limits of this range is given by the entries labeled Allowable Increase and Allowable Decrease in the Sensitivity Report in Program B.1. In Shader’s case, these values show that the shadow price of $0.50 for assembly time availability is valid for an increase of up to 20 hours from the current value and a decrease of up to 20 hours. That is, the available assembly time can range from a low of 80 (= 100 20) to a high of 120 (= 100 +20) for the shadow price of $0.50 to be valid. Note that the allowable decrease implies that for each hour of assembly time that Shader loses (up to 20 hours), its profit decreases by $0.50.
Changes in the Objective Function Coefficient
Let us now focus on the information provided in Program B.1 titled Adjustable Cells. Each row in the Adjustable Cells table contains information regarding a decision variable (i.e., Walkmans or Watch-TVs) in the LP model.
Allowable Ranges for Objective Function Coefficients
As the unit profit contribution of either product changes, the slope of the iso-profit lines we saw earlier in Figure B.5 changes. The size of the feasible region, however, remains the same. That is, the locations of the corner points do not change.
There is an allowable decrease and an allowable increase for each objective function coefficient over which the current optimal solution remains optimal.
The limits to which the profit coefficient of Walkmans or Watch-TVs can be changed without affecting the optimality of the current solution is revealed by the values in the Allowable Increase and Allowable Decrease columns of the Sensitivity Report in Program B.1. The allowable increase in the objective function coefficient for Watch-TVs is only $0.25. In contrast, the allowable decrease is $1.50. Hence, if the unit profit of Watch-TVs drops to $4 (i.e., a decrease of $1 from the current value of $5), it is still optimal to produce 30 Walkmans and 40 Watch-TVs. The total profit will drop to $370 (from $410) because each Watch-TV now yields less profit (of $1 per unit). However, if the unit profit drops below $3.50 per Watch-TV (i.e., a decrease of more than $1.50 from the current $5 profit), the current solution is no longer optimal. The LP problem will then have to be resolved using Solver, or other software, to find the new optimal corner point.
A new corner point becomes optimal if an objective function coefficient is decreased or increased too much.
USING SOFTWARE TO SOLVE LP PROBLEMS
All LP problems can also be solved with the simplex method, using software such as POM for Windows or Excel. This approach produces valuable economic information such as the shadow price, or dual, and provides complete sensitivity analysis on other inputs to the problems. Excel uses Solver, which requires that you enter your own constraints. Excel OM does not have an LP module. POM for Windows requires only that demand data, supply data, and shipping costs be entered. In the following section we illustrate how to create an Excel spreadsheet for LP problems.
Using Excel Spreadsheets
Excel offers the ability to analyze linear programming problems using built-in problem-solving tools. Excel’s tool is named Solver. Solver is limited to 200 changing cells (variables), each with 2 boundary constraints and up to 100 additional constraints. These capabilities make Solver suitable for the solution of complex, realworld problems.
We use Excel to set up the Shader Electronics problem in Program B.2. The objective and constraints are repeated here:
Objective function: Maximize profit =
$7(No. of Walkmans) + $5(No. of Watch-TVs)
Subject to: 4(Walkmans) + 3(Watch-TVs)≤240
2(Walkmans) + 1(Watch-TV)≤100
PROGRAM B.2 ■ Using Excel to Formulate the Shader Electronics Problem
The Excel screen in Program B.3 shows Solver’s solution to the Shader Electronics Company problem. Note that the optimal solution is now shown in the changing cells (cells B8 and C8, which served as the variables). The Reports selection performs more extensive analysis of the solution and its environment. Excel’s sensitivity analysis capability was illustrated earlier in Program B.1.
PROGRAM B.3 ■ Excel Solution to Shader Electronics LP Problem
Using POM for Windows
POM for Windows can handle LP problems with up to 22 constraints and 99 variables. As output, the software provides optimal values for the variables, optimal profit or cost, and sensitivity analysis. In addition, POM for Windows provides graphical output for problems with only two variables.
