IE312
Practice Problems from Chapter 5
13 of 13
IE 312 Optimization
Fall 2006
Practice Problems for Midterm II
These problems are from the review section of Chapter 5, specifically problems 4,5,7,13, and 15
Solutions
1. Problem 4
a) Ruby cost change from $100 to $190
Obj coef. ranges for R:
Current coef. = -100 Allowable increase = 100 Allowable decrease = 100
This means as long as the cost of extra ruby is between $0 and $200 the current basis still optimal. Therefore Zales will still produce the same amount of type 1 and type 2 rings, and buy the same amount of extra rubies.
Zales still purchase rubies and have the same optimal solution.
However the objective value (profit) will change to 19000+15(100-190) = $17650.
b) Now X2>=23
RHS for X2
Current RHS = 25 Allowalble increase =0 Allowable decrease = 2.5
Db = -2 à the current basis remains optimal.
Dual price row 6 is -200
For Max problem: new opt z-value = old opt z-value + (constraint shadow price) Db
New profit = 19000+(-200*-2) = $19400
c) To keep the same profit
Pay for extra labor hour = extra money made from extra labor = Dual price row 4 = $200
So Zales would be willing to pay for another hour is $200 at most.
d) Pay for another sapphire
Pay for extra sapphire = extra money made from extra sapphire = Dual price row 3 = $0
So Zales would not pay any money for another sapphire. Actually Zales has 10 units surplus amount of sapphire (slack row 3 = 10).
2. Problem 5
a), b)
Slope of C1 = -2
Slope of C2 = -1
Slope of C3 = -1/2
A typical isoprofit when price of ALE = PA and price of BEER = PB is
PA*ALE+ PB*BEER = Z
Slope of isoprofit = - PA/ PB
If the slope of isoprofit is between -2 and -1/2, the current basis remain optimal (i.e., the optimal solution still at (13.33, 13.33)).
To find range of PA, we assume other parameters are fixed. -2≤- PA/ 50 ≤-1/2à 25≤ PA ≤100.
To find range of PB, we assume other parameters are fixed. -2≤- 40/ PB ≤-1/2à 20≤ PB ≤80.
c), d), e)
Range of values for the amount of available corn
Range of values for the amount of available hops
Range of values for the amount of available malt
The basis current still remain optimal, if
A change in RHS for C1 is between -10 and +5
A change in RHS for C2 is between -3.33 and +INFINITY
A change in RHS for C3 is between -20 and +10
Shadow price for C1, C2, and C3:
For C1: new RHS = 40+D
Optimal solution is at the intersection of C1 and C3
C1à ALE+2BEER=40+D
C3à 2ALE+BEER=40
ALE = 13.33-D/3 and BEER = 13.33+2D/3
Z = 40*(13.33-D/3)+50*(13.33+2D/3) = 1200+20 Dà shadow price of C1 = 20
For C2: new RHS = 30+D
Optimal solution is at the intersection of C1 and C3
C1à ALE+2BEER=40
C3à 2ALE+BEER=40
ALE = 13.33 and BEER = 13.33
Z = 40*(13.33)+50*(13.33) = 1200+0Dà shadow price of C2 = 0
For C3: new RHS = 40+D
Optimal solution is at the intersection of C1 and C3
C1à ALE+2BEER=40
C3à 2ALE+BEER=40+D
ALE = 13.33+2D/3 and BEER = 13.33-D/3
Z = 40*(13.33+2D/3)+50*(13.33-D/3) = 1200+10Dà shadow price of C3 = 10
f) 1 lb = 16 oz
C1 à 16ALE+32BEER<=640
C2 à 16ALE+16ALE <= 480
C3 à 32ALE+16BEER<=640
C4 à ALE>=0
C5 à BEER>=0
Shadow price for C1 = 20/16 = 1.25
Shadow price for C2 = 0/16 = 0
Shadow price for C3 = 10/16 = 0.625
g)
Look at slope of each constraint and slope of isoprofit at price of ALE = PA
and price of BEER = PB = 50
Slope of C1 = -2
Slope of C2 = -1
Slope of C3 = -1/2
Slope of isoprofit = - PA/ PB =- PA/ 50
The opt solution is at (0, 20) if slope of – PA /50 ≥ -1/2
The opt solution is at (13.33, 13.33) if slope of -1/2≤– PA /50≤ -2
The opt solution is at (20, 0) if slope of – PA /50 ≥ -2
Value of p / Optimal z-value0≤ PA ≤25 / PA (0)+50(20)=$1000
25≤ PA ≤ 100 / PA (13.33)+50(13.33)=666.67+13.33 PA
PA ≥ 100 / PA (20)+50(0)=20 PA
h)
Ranges of RHS for C1 (20, 50)à If the available of corn is between 20 and 50, the current basis remains optimal and shadow price of corn constraint is 20.
Z = 1200+20 D = 400+20RHScorn, D is between -20 and +10 or RHSCorn is between 20 and 50.
If the available of corn is less than 20 the current basis is no longer optimal. The new optimal is where C1 and C5 are binding.
For C1: new RHS = 40+D
Optimal solution is at the intersection of C1 and C5
C1à ALE+2BEER=40+D
C5à BEER=0
ALE = 40+D
Z = 40*(40+D) +50*(0) = 1600+40D = 40*RHSCorn
when D <-20 or RHSCorn is between 0 and 20.
If the available of corn is greater than 50 the current basis is no longer optimal. The new optimal is where C2 and C3 are binding.
For C1: new RHS = 40+D <10
Optimal solution is at the intersection of C2 and C3
C1à ALE+2BEER=40+D
C2à ALE+BEER=30
C3à2ALE+BEER=40
ALE = 10, BEER = 20
Z = 40*(10) +50*(20) = 1400 when D >10 or RHS is greater than 50.
i)
Ranges of RHS for C2 (26.66, INFINITY)à If the available of hops is greater than 26.66 5, the current basis remains optimal and shadow price of corn constraint is 0.
Z = 1200, D is between -3.33 and +INFINITY or RHSHops is greater than 26.66.
If the available of hops is less than 26.66, the current basis is no longer optimal.
20<RHSHops<26.66, the new optimal is where C2 and C3 are binding.
C2à ALE+BEER=30+D
C3à 2ALE+BEER=40
ALE = 10-D, BEER = 20+2D
Z = 1400+60D = 60*RHSCorn -400 when -10<D<-3.33 or RHSHops is between 20 and 26.66.
If the available of hops is less than 20, the current basis is also no longer optimal.
RHSHops<20, the new optimal is where C2 and C5 are binding.
C2à ALE+BEER=30+D
C5à BEER=0
ALE = 30+D
Z = 40*(30+D)=1200+40D = 40* RHSHops when D<-10or RHSCorn is less than 20.
j)
Ranges of RHS for C3 (20, 50)à If the available of malt is between 20 and 50, the current basis remains optimal and shadow price of malt constraint is 10.
Z = 1200+10 D = 800+10RHSmalt, D is between -20 and +10 or RHSCorn is between 20 and 50.
If the available of malt is less than 20 the current basis is no longer optimal. The new optimal is where C3 and C4 are binding.
C3à 2ALE+BEER=40+D
C4à ALE=0
BEER = 40+D
Z = 50(40+D) = 2000+50D or 50* RHSMalt when D<-20 or RHSMalt is less than 20.
If the available of malt is greater than 50 the current basis is no longer optimal. The new optimal is where C1 and C2 are binding.
C1à ALE+2BEER=40
C2à ALE+BEER=30
ALE = 20, BEER = 10
Z = 1300 when D>10 or RHSMalt is greater than 50.
3. Problem 7
Unit of obj value is in thousand dollar
a) Coef of TM changes from $5 to 55-48=$7.
From fig 22
Obj coef ranges for TB
Current coef = 5 Allowable increase = infinity Allowable decrease = 4
Ranges are between 1 and infinity.
Since the change in TM coef is 2, the current basic is still optimal
and optimal solution is unchanged (SM = 45, TM = 0, SB = 5, TB = 50).
new opt z-value/profit = (32*45)+(55*0)+(5*5)+(7*50)=1815à$1815000
b)
Giapetto would be willing to pay
For extra 100 board feet of lumber = (dual price of row 2)/10 = 0à =$0
For extra 100 labor hours = (dual price of row 3)/10 = 13.50/10=1.35à = 1.35*1000 =$1350
c) if 60,000 labor available.
RHS for labor constraint changes from 90 to 60.
From fig 22
RHS ranges for row 3
Current RHS = 90 Allowable increase = 6.666667 Allowable decrease = 90
Dual price = 13.5
Ranges are between 0 and 96.666667.
Since new RHS = 60 which is in the ranges, therefore current basis is still optimal,
For Max problem: new opt z-value = old opt z-value + (constraint shadow price) Db
Db = -30
new opt z-value/profit = 1715 + (13.5*-30) = 1310à $1310000
d) ) if 40,000 trains can be sold.
RHS for demand for train constraint changes from 50 to 40.
From fig 22
RHS ranges for row 5
Current RHS = 50 Allowable increase = infinity Allowable decrease = 50
Dual price = 5
Ranges are between 0 and infinity.
Since new RHS = 40 which is in the ranges, therefore current basis is still optimal,
For Max problem: new opt z-value = old opt z-value + (constraint shadow price) Db
Db = -10
new opt z-value/profit = 1715 + (5*-10) = 1665à$1665000
4. Problem 13
a) Coef of X11 changes from $140 to 200-70=$130.
From fig 23
Obj coef ranges for X11
Current coef = 140 Allowable increase = infinity Allowable decrease = 20
Ranges are between 120 and infinity.
Since the change in X11 coef is -10, the current basic is still optimal and optimal solution is unchanged (X11 = 10, X22 = 11.666670, X12=X13=X21=X23=L=0).
new opt z-value/profit = (130*10)+(120*0)+(40*0)+(70*0)+(80*11.66667)+(30*0)-(20*0)=$2233.3336
b) Coef of L changes from $20 to 4.
From fig 23
Obj coef ranges for L
Current coef = -20 Allowable increase = 19.73333 Allowable decrease = infinity Ranges are between - infinity and -0.26667.
Since the change in L coef is -16, the current basic is still optimal and optimal solution is unchanged (X11 = 10, X22 = 11.666670, X12=X13=X21=X23=L=0). Not purchase
new opt z-value/profit = (140*10)+(120*0)+(40*0)+(70*0)+(80*11.66667)+(30*0)-(4*0)=$2333.33 (same profit)
c) RHS for row 2 change for +5, RHS is still in the ranges. The current basis is still optimal.
Company would be willing to pay
For extra capacity of 5000 tools = (dual price of row 2)*5 = 86.67*5=$433.35>$400
So company would love to take this offer.
d) If 5 more extra hour available.
RHS for labor constraint changes from 5500 to 5505
From fig 23
RHS ranges for row 4
Current RHS = 5500 Allowable increase = 100 Allowable decrease = 3500
Dual price = .266667
Ranges are between 2000 and 5600
Since new RHS = 5505 which is in the ranges, therefore current basis is still optimal,
For Max problem: new opt z-value = old opt z-value + (constraint shadow price) Db
Db = +5
new opt z-value/profit = 2333.333 + (0.266667*5) = $2334.6664
5. Problem 15
a) To change the decision variable value of W from 0, our current basis needs to be changed. And the allowance is +264.7058. So we need to add this change into profit from an acre of wheat grown. An acre can produce 50 bushel. So the increasing price is 264.7058/50 = 5.294116 per bushels.
Or we can think of in term of dual price. If W increase from 0 to 1, it cost Old Macdonald’s = dual price of W = 264.7058. This needs to be taken care by the price of wheat.
Increasing price of wheat = 264.7058/50 = 5.294116 per bushels
Price of wheat = 30+5.294116 = $35.294116
b) Old McDonald would be willing to pay
For extra hour of labor = (dual price of row 8) = 58.82353
Or dual price of row7+$15= $43.82353+15 = 58.82353
c) Old McDonald would be willing to pay
For extra bushel of alfalfa = (dual price of row 4) = $11.764710
This extra of alfalfa can be sold or devoted to beef.
This question does not ask for the case of increasing the sale of alfalfa.
d) If alfalfa sold for $20, Coef of AS changes from 200 to 20.
Obj coef ranges for AS
Current coef = 200 Allowable increase = infinity Allowable decrease = 188.235300
Coef of AS changes = 20-200 = -180 >-188.2353à current basis remains optimal.
Optimal Solutions unchanged (W=0, AS=1000, B=35.29412, L=2000, AB=176.4706, A=11.76471).
New profit = (1500*0)+(20*1000)+(3000*35.29412)-(15*2000) = $95882.36