Management Science

Solutions with LINDO

Sensitivity Analysis

1
LP Solution
• Once an LP problem is solved, there a re 4 possible
solution alternatives
1. The LP has one optimum solution.
2. The LP has multiple (alternative) optimum solutions.
More than one optimum solution are found.
3. LP is infeasible. Feasible region does not exist. It has
no feasible solutions (The feasible region contains no
points).
4. The LP is unbounded. In the feasible region there are
points with arbitrarily large (in a max problem)
objective function values. 2
• A constraint is binding (active, tight) if the left-hand and right-
hand side of the constraint are equal when the optimal values
of the decision variables are substituted into the constraint.
• A constraint is nonbinding (inactive) if the left-hand side and
the right-hand side of the constraint are unequal when the
optimal values of the decision variables are substituted into
the constraint.

3
Dakota Example
• The Dakota Furniture Company manufactures desks, tables,
and chairs. The manufacture of each type of furniture requires
lumber and two types of skilled labor: finishing and carpentry.
• Currently, 48 board feet of lumber, 20 finishing hours, and 8
carpentry hours are available. A desk sells for $60, a table for
$30, and a chair for $20. At most five tables can be sold.
Resource Desk Table Chair Limit
Lumber 8 6 1 48
Finishing 4 2 1,5 20
Carpentry 2 1,5 0,5 8
Demand (max) - 5 - 4
Price ($) 60 30 20
Dakota Example – LP Model
max z = 60x1+30x2+20x3
s.t 8x1 + 6x2+ x3 ≤ 48
4x1 + 2x2+1,5x3 ≤ 20
2x1 + 1,5x2+ 0,5x3 ≤ 8
x2 ≤ 5
x1,x2,x3 ≥ 0

max 60x1+30x2+20x3
Subject to
8x1 + 6x2+ x3 <= 48
4x1 + 2x2+1.5x3 <= 20
2x1 + 1.5x2+ 0.5x3 <= 8 5
x2 <= 5
Alternative Solutions
• If Row 0 coefficient of a nonbasic variable is 0, then there are
alternative solutions involving that unbasic variable.

• Revised Dakota Example:

• Let’s change the Dakota example for $35/table.
• New z = 60 x1 + 35 x2 + 20 x3

6
Unbounded LP

• Breadco Example
• Breadco Bakeries bakes two kinds of bread: French and
sourdough. Each loaf of French bread can be sold for 36¢, and
each loaf of sourdough bread for 30¢. A loaf of French bread
requires 1 yeast packet and 6 oz of flour; sourdough requires 1
yeast packet and 5 oz of flour. At present, Breadco has 5 yeast
packets and 10 oz of flour. Additional yeast packets can be
purchased at 3¢ each, and additional flour at 4¢/oz. Formulate
and solve an LP that can be used to maximize Breadco’s profits
( revenues - costs).
7
• Max Z = 36x1 + 30x2 -3x3 - 4x4
• Subject to;
• x1 +x2  5+ x3
• 6x1 +5x2  10+ x4
• x1, x2  0

8
• Giapetto Example
• max z = 3x1 + 2x2
• Subject to
• 2x1 + x2 ≤ 100 (Assembly constraint)
• x1 + x2 ≤ 80 (Carpentry constraint)
• x1 ≤ 40 (Demand Constraint)

• x1, x2 ≥ 0 (Sign constraints)

9
Modified Giapetto (1)
• Giepetto Example
• max z = 3x1 + 2x2
• Subject to
• 2x1 + x2 ≤ 100
• x1 + x2 ≤ 80
• x1 ≤ 40
• x2 ≥ 90

• x1, x2 ≥ 0

• No feasible region!
10
Modified Giapetto (2)
• Giepetto Example
• maks z = 3x1 + 2x2
• S.T.
• x1 ≤ 40
• x2 ≥ 90

• x1, x2 ≥ 0

• Unbounded LP

11
What is sensitivity analysis?
• Sensitivity Analysis:
• To find out how changes in the parameters of the LP
affects the solution

• Reduced Cost: Belongs to a non-basic variable

• The amount of increase/decrease for the coefficient of a non-
basic variable to become a basic variable
• For any nonbasic variable, the reduced cost for the variable is
the amount by which the nonbasic variable's objective
function coefficient must be improved before that variable will
become a basic variable in some optimal solution to the LP.
12
• Reduced cost of a basic variable is zero (see definition)!
Sensitivity Analysis
• Shadow price:
• Belongs to a constraint
• What happens to the value of the objective function value if the
righthand side is increased by 1. (how much it increases in
maximization problems, how much it decreases in minimization
problems)

• This is only valid, if the solution stays optimal.

• A  constraint always has a nonpositive shadow price

• A  constraint always has a nonnegative shadow price
13
• Conceptualization
• max z = 6 x1 + x2 + 10x3
• x1 + x3 ≤ 100
• x2 ≤ 1
• All variables ≥ 0
• This is a very easy LP model and can be solved manually without
utilizing Simplex.
• x2 = 1 (This variable does not exist in the first constraint. In this case,
as the problem is a maximization problem, the optimum value of
the variable equals the RHS value of the second constraint).
• x1 = 0, x3 = 100 (These two variables do exist only in the first
constraint and as the objective function coefficient of x3 is greater
than that of x1, the optimum value of x3 equals the RHS value of the
first constraint).
• If we improve the objective function coefficient of x1 more
than its reduced cost, there would be a unique optimal
solution: [100, 1, 0].
• Shadow Price
• If the RHS of the first constraint is increased by 1, new optimal
solution of x3 would be 101 instead of 100. In this case, new z
value would be 1011.
• If we use the definition: 1011 - 1001 = 10 is the shadow price
of the first constraint.
• Similarly the shadow price of the second constraint can be
calculated as 1 (please find it).
Utilizing Lindo Output for Sensitivity
• Lindo output reveals the reduced costs of x1, x2, and x3 as 4, 0,
and 0 respectively.
• In the maximization problems, the reduced cost of a non-basic
variable can also be read from the allowable increase value of
that variable at obj. coefficient ranges. Here, the corresponding
value of x1 is 4.
• In the minimization problems, the reduced cost of a non-basic
variable can also be read from the allowable decrease value of
that variable at obj. coefficient ranges.
• The same Lindo output reveals the shadow prices of the
constraints in the "dual price" section:
• Here, the shadow price of the first constraint (Row 2) equals 10.
• The shadow price of the second constraint (Row 3) equals 1.
Some important equations
• If the change in the RHS of the constraint leaves the current basis
optimal (within the allowable RHS range), the following equations can
be used to calculate new objective function value:
• for maximization problems
• • new obj. fn. value = old obj. fn. value + (new RHS – old RHS) × shadow
price

• for minimization problems

• • new obj. fn. value = old obj. fn. value – (new RHS – old RHS) × shadow
price

• For Lindo example, as the allowable increases in RHS ranges are infinity
for each constraint, we can increase RHS of them as much as we want.
But according to allowable decreases, RHS of the first constraint can be
decreased by 100 and that of second constraint by 1.
• Lets assume that new RHS of the first constraint is 60.
• As the change is within allowable range, we can use the first
equation (max. problem):
• znew = 1001 + ( 60 - 100 ) 10 = 601.
• If the change in the objective function coefficient leaves the
current basis optimal (within the allowable range), the
following equations can be used to calculate new objective
function value:
• for maximization problems
• • new obj. fn. value = old obj. fn. value + (new coefficient – old
coefficient) × decision variable’s value

• for minimization problems

• • new obj. fn. value = old obj. fn. value - (new coefficient – old
coefficient) × decision variable’s value
• Lets assume that new obj func coefficient of the first decision
var is 9.
• As the change is within allowable range, we can use the first
equation (max. problem):
• znew = 1001 + ( 9 - 6 ) 0 = 1001.
• Lets assume that new obj func coefficient of the third decision
var is 20.
• As the change is within allowable range, we can use the first
equation (max. problem):
• znew = 1001 + ( 20 - 10 ) 100 = 2001.
Next week Lindo & Sensitivity
!Dakota Carpentry
!x1, x2, x3 the number of desks, tables and
chairs to be produced Weekly profit: z
 
Max 60x1+ 30x2 + 20x3
st
WOOD) 8x1 + 6x2 + x3 <= 48
FINISHING) 4x1 + 2x2 + 1.5x3 <= 20
CARPENTRY) 2x1 + 1.5x2 + 0.5x3 <= 8
DEMAND) x2 <= 5
END
24
OBJECTIVE FUNCTION VALUE
1) 280.0000
VARIABLE VALUE REDUCED COST
X1 2.000000 0.000000
X2 0.000000 5.000000
X3 8.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

TAHTA) 24.000000 0.000000
MONTAJ) 0.000000 10.000000
MARANGOZ) 0.000000 10.000000
TALEP) 5.000000 0.000000

NO. ITERATIONS= 2

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 60.000000 20.000000 4.000000
X2 30.000000 5.000000 INFINITY
X3 20.000000 2.500000 5.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
25
TAHTA 48.000000 INFINITY 24.000000
MONTAJ 20.000000 4.000000 4.000000
MARANGOZ 8.000000 2.000000 1.333333
TALEP 5.000000 INFINITY 5.000000
Examples
• What happens to the objective function value, if the profit for a desk
(objective function coefficient for x1) is 70?

• What happens to the objective function value, if the profit for a table
(objective function coefficient for x2) is 25?

• What happens to the objective function value, if the profit for a chair
(objective function coefficient for x3) is 10?

• What happens to the objective function value, if we have 30 boards of wood?

• What happens to the objective function value, if we have 22 hours of

finishing?

26
• What happens to the objective function value, if we have 6 hours for
carpentry?
Next week 100% Rule
• What if values of more than one parameter changes!

• In the objective function for non-basic variables

• Are all values in the allowable range?

• At least one basic variable.

• 100% Rule is applied.

27
100% Rule - DietExample
Chocolat
Price Calorie e Sugar Fat(oun
(TL) s (ounce) (ounce) ce)
Cake (1 slice) 5 400 3 2 2
Chocolate icecream (1
spoonful) 2 200 2 2 4
Coke (1 Bottle) 3 150 0 4 1
Pineapple pie (1 Slice) 8 500 0 4 5
Minimum amounts 500 6 10 10

• MIN 5 KEK + 2 CD + 3 KL+ 8 AP

• SUBJECT TO
• KALORI) 400 KEK + 200 CD + 150 KL + 500 AP >= 500
• CIKOLATA) 3 KEK + 2 CD >= 6
• SEKER) 2 KEK + 2 CD + 4 KL + 4 AP >= 10 28
• YAG) 2 KEK + 4 CD + KL + 5 AP >= 8
• END
• OBJECTIVE FUNCTION VALUE
• 1) 9.000000
• VARIABLE VALUE REDUCED COST
• KEK 0.000000 2.750000
• CD 3.000000 0.000000
• KL 1.000000 0.000000
• AP 0.000000 5.000000

• ROW SLACK OR SURPLUS DUAL PRICES

• KALORI) 250.000000 0.000000
• CIKOLATA) 0.000000 -0.250000
• SEKER) 0.000000 -0.750000
• YAG) 5.000000 0.000000

• RANGES IN WHICH THE BASIS IS UNCHANGED:

• OBJ COEFFICIENT RANGES
• VARIABLE CURRENT ALLOWABLE ALLOWABLE
• COEF INCREASE DECREASE
• KEK 5.000000 INFINITY 2.750000
• CD 2.000000 1.833333 0.500000
• KL 3.000000 1.000000 3.000000
• AP 8.000000 INFINITY 5.000000
• RIGHTHAND SIDE RANGES
• ROW CURRENT ALLOWABLE ALLOWABLE
• RHS INCREASE DECREASE
• KALORI 500.000000 250.000000 INFINITY 29
• CIKOLATA 6.000000 4.000000 2.857143
• SEKER 10.000000 INFINITY 4.000000
• YAG 8.000000 5.000000 INFINITY
• If the price of cd is 3 TL’s, what happens to the objective
function value? (3-2)=1*3=3 9+3=12
• If RHS of cikolata is 7? 9-(7-6)*(-0.25)=9.25

30
Examples
• If the price of cake is 3 TL’s and of the pineapple pie is 5 TL’s, does the solution change?
What happens to the objective function value?
• Non basic var. They are in the allow range. BFS remain optimal. Obj func value does not
change.

• If the price of cake is 4 TL’s and of the coke is 3.5 TL’s, does the solution change? What
happens to the objective function value?
• =(1/2.75 )+(0.5/1)=0.36+0.5=0.86 100% rule
• cake is still non basic. For coke the change in z is: (new coef-old
coef)*1=9+(0.5*1)=9+0.5=9.5
• If the price of pineapple pie is 6 TL’s and of the chocolate icecream is 3 TL’s, does the
solution change? What happens to the objective function value?
• =2/5+1/1.83=0.4+0.55 less than 1 100%rule
• Pineapple pie is still non basic. For chocolate icecream the change in z is: (new coef-old
coef)*1=0+(1*3)=9+3=12
• If all prices are 3 TL’s, does the solution change? What happens to the objective function
value? 31
• 2/2.75+1/1.83+5/5 greater than 1 we have to solve again
100% Rule
• For constraints

• Non Binding constraints: Watch out for the allowable range!

• At least one binding constraint: 100% Rule

32
Examples
• What happens if the calorie constraint is changed to 700, and the fat
constraint is changed to 12? Both of them nonbinding constraint. In the
allow range. BFS stays optimal. Obj func value does not change
• What happens if the calorie constraint is changed to 600, and the
chocolate constraint is changed to 8?
• =calorie const is non-binding, chocolate binding.
• =100/250+2/4=0.9 less than 1. bfs stays optimal.
• New z= old z-(2*(*-0.25)=9+0.5=9.5
• What happens if the sugar constraint is changed to 15, and the fat
constraint is changed to 11?sugar binding, fat non-binding.
• 5/infinity+3/5=0.6 bfs stays optimal
• Newz=old z-(5*-0.75)-(3*0)=9+3.75=12.75
• What happens if the sugar constraint is changed to 8, and the chocolate
constraint is changed to 4?sugar binding, chocolate binding 33
• 2/4+2/2.86=1.2 greater than 1. bfs changes, solve again