Question

1. Consider the following linear program: min 85 + 3M s. t. | 505 + 100M < 1,200,000 5S + 4M > 60,000 M > 3,000 SM 20 a. Find the optimal solution. b. Specify the objective function coefficient ranges, and interpret the ranges. c. Suppose one OFC increases from 8 to 12 and another OFC increases from 3 to 3.5. Would the optimal solution change? d. Identify each of the right-hand-side ranges, and interpret these ranges. e. What is the dual price for each constraint? Interpret each (i.e., use the dual prices and the right- hand-side range to discuss the effect of changes of the right-hand side values). f. Which constraints are binding? g. What are the dual prices for nonbinding constraints? Why? h. (bonus question) Can you see how the OFCs, reduced prices, and dual prices are related?

Answer 1

Create the spreadsheet model as follows:

@fx D3 A =SUMPRODUCT(B3:03,$B$9:$C$9) D E F G B C H I J K L M N S Solver Parameters Min 30,0 50531 100 0,0 Value Of: 0 0,0 0,0 <= >= >= 1,200,000 60,000 3,000 Set Objective: To: Max Min By Changing Variable Cells: $B$9:$C$9 Subject to the Constraints: $D$5 < = $F$5 $D$6:$D$7 >= $F$6:$F$7 1 Result: Add Change Delete Reset All Make Unconstrained variables Non-Negative Select a Solving Method: Simplex LP Options Solving Method Select the IPOPT Nonlinear engine for Solver Problems that are smooth nonlinear. Select the LP Simplex engine for linear Solver Problems. Solve | Close

EXCEL FORMULAS:

D3 =SUMPRODUCT(B3:C3,$B$9:$C$9) copy to D5:D7

---------------------

Click Solve on "Solver Parameters" to generate the optimal solution.

After the solution is generated, select Sensitivity (to generate sensitivity report) on the next notification screen.

Then Click OK

@fx D3 AB =SUMPRODUCT(B3:03,$B$9:$C$9) D E F G C H I J K L M N 0 S Solver Results Min 62,000 1,200,000 60,000 10,000 <= 1,200,000 >= 60,000 >= 3,000 Solver found a solution. All constraints and optimality conditions are satisfied. Reports Answer Keep Solver Solution Sensitivity Limits Restore Original Values 1 Result: 4,000 10,000 Return to Solver Parameters Dialog OK | Cancel Reports Create the type of report that you specify, and place each report on a separate sheet in the workbook.

Sensitivity report is following:

Variable Cells Reduced Cost Cell Name $B$9 Result: S $C$9 Result: M Final Value 4000 10000 Objective Allowable Allowable Coefficient increase Decrease 8 1E+30 4.25 3 3.4 1E+30 0 0 Constraints Name Cell $D$5 $D$6 $D$7 Final Value 1200000 60000 10000 Shadow Price -0.056666667 2.166666667 0 Constraint Allowable Allowable R.H. Side Increase Decrease 1200000 300000 420000 60000 42000 12000 3000 70001E+30

a)

Optimal solution:

S = 4,000

M = 10,000

Objective value = 62,000

b)

Refer sensitivity report, objective function coefficient ranges are obtained by adding the allowable increase and subtracting the allowable decrease from the objective coefficient.

Optimality range for objective function coefficient of S: 8-4.25=3.75 to 8+infinity=infinity (in sensitivity report, 1E+30 means infinity)

Optimality range for objective function coefficient of M: 3-infinity=-infinity to 3+3.4=6.4

c)

Using 100% rule,

Sum of changes as percentage of respective allowable change = (12-8)/infinity+(3.5-3)/3.4 = 0%+14.7% = 14.7 %

This is less than 100%, therefore, optimal solution will NOT change.

d)

Refer sensitivity report, Right hand side (RHS) ranges are obtained by adding the allowable increase to and subtracting the allowable decrease from the Constraint R.H. Side

Optimality range for RHS of constraint 1: 1200000-420000=780000 to 1200000+300000=1500000

Optimality range for RHS of constraint 2: 60000-12000=48000 to 60000+42000=102000

Optimality range for RHS of constraint 3: 3000-infinity=-infinity to 3000+7000=10000

e)

Dual price or Shadow prices can be read directly from the sensitivity report,

Dual price of constraint 1 = -0.05667

Dual price of constraint 2 = 2.1667

Dual price of constraint 3 = 0

Interpretation: Dual price is the change in objective function value, by changing the R.H.Side of the constraint by 1 unit, as long as such change is within the Right-Hand Side range. For example, if one unit is increased in the R.H. Side of constraint 1, then objective function value will decrease by 0.05667, because the change of 1 unit in the RHS of the constraint is within the allowable range as determined in part (d)

f)

Constraints having non-zero Shadow price are binding, because their Final Value is equal to the Constraint R.H. Side.

So, Constraints 1 and 2 are binding constraints.

g)

Dual prices for non-binding constraints are 0

because, these constraints have a non-zero slack or surplus. Therefore, a change in their R.H.Side does not affect the optimal solution and objective function value.