Linear Programming - Sensitivity Analysis.

We revisit the problem that plans production in relation to the four variants of
same product that we formulated before as a P.L. problem. To remember it,
the problem and its formulation will be repeated below.

Production Planning Problem:

A company manufactures four variants of the same product and at the final part of the process
In the industrial sector, there are assembly, polishing, and packaging operations. For each variant, the
Time required for these operations is shown below (in minutes) as gain for
unit sold.

Assembly Polishing Packaging Profit ($)

Variant 1 2 3 2 1.50
2 4 2 3 2.50
3 3 3 2 3.00
4 7 4 5 4.50

• Given the current state of the workforce, the company estimates that each year they
they have 100,000 minutes of assembly time available, 50,000 minutes of time
of polishing and 60000 minutes of packaging time. How many of each variant should
Make the company by year and what is the associated profit?
• Now suppose that the company is free to decide how much time should be given to each
one of the three operations (assembly, polishing, and packaging) within the time
acceptable total of 210000 (= 100000 + 50000 + 60000) minutes. How many of each
What variant should the company make per year and what is the associated profit?

Production Planning Solution

Variables

Yes:

xiit is the number of units of variant i (i = 1,2,3,4) made per year

TassIt is the number of minutes used in assembly per year.

Tpolit is the number of minutes used in polishing per year
TpacIt is the number of minutes spent on packaging per year

where: xi>= 0 i=1,2,3,4 and Tass, Tpol, Tpacgreater than or equal to 0

Restrictions

a) definition of operation time

Tass= 2x1+ 4x2+ 3x3+ 7x4assembly

Tpol= 3x1+ 2x2+ 3x3+ 4x4polishing
Tpac= 2x1+ 3x2+ 2x3+ 5x4(packaging)
(b) operation time limits

The operational time limits depend on the situation being considered. In

the first situation, where the maximum time that can be taken in each operation is
specified, we simply have:

Tass<= 100000 (assembly)

Tpol<= 50000 (polishing)
Tpac<= 60000 (packaging)

In the second situation, where the only limitation is the total time spent on all the
operations, we simply have:

Tass+ Tpol+ Tpack<= 210000 (total time)

Objective

Presumably, the goal will be to maximize Profit – we will then have:

maximize 1.5x1+ 2.5x2+ 3.0x3+ 4.5x4

giving us the complete formulation of the problem.

Un resumen de las entradas en elpaquete computacional(WinQSB) para la primera situación

considered in the problem (maximum time that can be taken in each operation is
specified) is shown below:

The solution to this problem is also shown below:

We can observe that the optimal solution of the LP problem has the values Profit =
58000 ($) for Tass82000, Tpol=50000, Tpack=60000, X1=0, X2=16000, X3=6000 and X4=0.

This is then the solution of LP - but it turns out that the simplex algorithm gives us a bit
more useful information. This information relates to:

• change the coefficient of the objective function for a given variable

• force a variable that is currently zero to be non-zero
• change the right side of a constraint.

We will address each of these in due time, and note here that the analysis presented
below ONLY applies for a single change, if two or more things change then that
we need to solve the PL problem effectively:

• Suppose we vary the coefficient of X2in the objective function. How will it change the
optimal solution of the LP?

Currently X1=0, X2=16000, X36000 y X4=0. The columns Allowable Min/Max c(i)
(Max/Min of c(i) Acceptable) in the previous table tells us that, as long as the coefficient of
X2in the objective function varies between 2.3571 and 4.50, the values of the variables in the solution
the optimal PL will remain unchanged. Note, however, that the value of the optimal solution
real will change.

In terms of the original problem we are effectively saying that the decision to produce
16000 of variant 2 and 6000 of variant 3 remain optimal even when the profit for
the unit in variant 2 is really not 2.5 (but varies in the range 2.3571 to 4.50).

Similar conclusions can be drawn for X.1, X3y X4.

In terms of the Simplex algorithm, this is understood because in the current simplex the
basic solution (vertex of the feasible region) remains optimal as long as the coefficient of
X2the objective function varies between 2.3571 and 4.50.

• for the variables, the column Reduced Cost gives us, for each variable
what is currently zero (X1y X4), an estimate of how much the objective function
it will change if we make them non-zero.

So we have the table

Variable X1 X4
Opportunity Cost 1.5 0.2
New value (= or >=) X1= A X4=B
ó X1>=A X4>=B
Estimated change objective function 1.5A 0.2B

The objective function will always worsen (decrease if we have a maximization problem).
or it will increase if we have a minimization problem) at least in this estimation. For
A or B very large are more inaccurate; this estimate is the exact change that would occur if
we were going to solve the LP with the corresponding constraint for the new value of X1or X4
added.

If exactly 100 of variant 1 were to be produced, what would your estimate be of

new value of the objective function?

Note aquí que el valor en la columnaReduced Cost(Costo Reducido) para una variable a
it is called 'opportunity cost' (costo de oportunidad) for the variable.

Note here that an alternative (and equally valid) interpretation of the reduced cost is
the amount by which the objective function coefficient for a variable needs to
change before that variable becomes non-zero.

So for the variable X1the objective function needs to change by 1.5 (increases while
that we are maximizing) before that variable becomes non-zero. In
other words, referring to our original situation, the profit per unit in variant 1
I would need to increase by 1.5 before it was feasible to produce any of the variant.
Similarly, the profit per unit in variant 4 would need to increase by 0.2 beforehand.
It would be beneficial to produce any of variant 4.

• For each constraint, the column headed by Shadow Price tells us

It tells exactly how much the objective function will change if we change the side.
right of the corresponding restriction within the limits given in the columns
Allowable Min/Max RHS (Minimum/Maximum Acceptable of the Right Side).

So we can form the table:

Restriction Assembly Polishing Packaging

Opportunity Cost (ignore sign) 0 0.80 0.30
Change on the right side a b c
Change in Objective Function 0 0.80b 0.30c
Lower limit of the right side 82000 40000 33333.34
Current value on the right side 100000 50000 60000
Upper Right Side Limit - 90000 75000

For example, regarding the polishing restriction, as long as its right side is
remain between 40000 and 90000, the change in the objective function will be exactly 0.80
[change on the right side of 50000].

The direction of change in the objective function (up or down) depends on the direction of the
change on the right side of the constraint and the nature of the objective (maximize or
minimize).

To decide whether the objective function will rise or fall in usage:

• the most (least) restrictive constraint after the change on the right side implies that
the objective function worsens (improves)
• if the goal is to maximize (minimize) then to worsen means to decrease (increase),
to improve means to rise (to fall)

So:

• If
you had 100 extra hours, what operation would you assign them to?
• If
you had to take 50 hours between polishing or packing, which would you choose?
Would you choose?
• What value will the new objective function have in these two cases?
•

The value in the column Shadow Price for the constraint is often called
marginal value or dual value.

Note that, as it would seem logical, if the constraint disappears, the shadow price is zero (that is,
if the restriction disappeared, a small change on the right side cannot alter the
optimal solution).

Comentarios:

• The different PL programs have different formats for inputs/outputs.

but the same information is obtained as discussed earlier.
• You may have found everything above very confusing. Essentially the
Interpreting the results of the PL is something that comes with practice.
• Much of the information obtained (as discussed earlier) derived from the
solution to the LP problem, can be useful for the analysis by estimating the effect of the
changes (e.g., changes in costs, production capacities, etc.)
controversies/expenses when resolving the PL.
• This sensitivity information gives us a measure of how robust the solution is.
to say how sensitive it is to changes in the input data.

Note here that, as stated earlier, the analysis related to:

 • changes in the coefficient of the objective function for a variable; and
• force a variable that is currently zero to be non-zero; and
• changes on the right side of a constraint,

it is only valid for a single change. If two (or more) changes are made, the situation is more
complex and is advisable to solve the PL problem.

Example of Sensitivity in Linear Programming.

Consider the linear problem:

Maximize
3x1+ 7x2+ 4x3+ 9x4
subject to:
x1+ 4x2+ 5x3+ 8x4<= 9 (1)
x1+ 2x2+ 6x3+ 4x4<= 7 (2)
xi>= 0 i=1,2,3,4

Solve this linear problem using the WinQSB program.

• What will be the values of the variables in the optimal solution?

• What is the optimal value of the Objective Function?
• What restrictions will be firm?
• How would you estimate that the objective function would change if:
owe changed the right side of the constraint (1) to 10
owe changed the right side of restriction (2) to 6.5
owe add the restriction x to the problem30.7

Solving the problem the solution is:

One interpretation of the previous results will be:

• the values of the variables are X1=5, X2=1, X3=0, X4=0,

• The optimal value of the objective function is 22.0
 • both restrictions are firm (there are no deficiencies or surpluses). Note here that the
(implicit) constraints that ensure the variables are non-negative (xi>=0
i=1,2,3,4) are (by agreement) not considered in deciding which restrictions are firm.

• a change in the objective function = (10-9) x 0.5 = 0.5. As long as the constraint is
less restrictive the objective function will improve. So when we have a
The maximization problem will increase. Referring to the Allowable column.
RHS (Minimum/Maximum Acceptable on the Right Side) we see that the new value (10) on the side
the right of the restriction (1) is within the limits specified there so that the
the new value of the objective function is exactly 22.0 + 0.5 = 22.5
• a change in the objective function = (7-6.5) x 2.5 = 1.25. If we make the constraint more...
restrictive the objective function will worsen. So if we have a problem of
maximization will decrease. Regarding the previous constraint (1) the new value of
the right side of restriction (2) is within the limits in the Allowable column
RHS (Minimum/Maximum Acceptable on the Right Side) we see that the new value of the function
the objective will be exactly 22.0 - 1.25 = 20.75
• A change in the objective function = 0.7 x 13.5 = 9.45. The objective function will worsen.
(it will decrease) if any variable that is always zero in the optimal of the LP is changed
to a non-zero value. It is estimated that it will decrease to 22.0 - 9.45 = 12.55. Note that the value
calculated here is just an estimate of the change in the value of the objective function. The
real change may be different from the estimated one (but it will always be greater than or equal to
he is estimated.

Note that we can, if we wish, explicitly enter the four constraints x.i>= 0;
i=1,2,3,4. Although this is unnecessary (since the program automatically assumes that each
variable is >= 0) is not incorrect. However, it may alter some of the figures of the
solution - in particular, the figures of the Reduced Cost can be different. This illustrates that
such figures are not necessarily defined solely in the optimal solution of
linear programming.