Question

2. The following linear programming problem has been solved by The Management Scientist. Use the output to answer the questions.

LINEAR PROGRAMMING PROBLEM

MAX 25X1+30X2+15X3

S.T. 1) 4X1+5X2+8X3<1200

2) 9X1+15X2+3X3<1500

OPTIMAL SOLUTION

Objective Function Value = 4700.000

Variable Variable Reduced Cost

X1 140.000   0.000

X2 0.000 10.000

X3 80.000 0.000

Constraint   Slack/Surplus Dual Price

1   0.000   1.000

2 0.000 2.333

OBJECTIVE COEFFICIENT RANGES

Variable   Lower Limit Current Value Upper Limit

X1 19.286 25.000 45.000

X2 No Lower Limit 30.000 40.000

X3 8.333 15.000 50.000

RIGHT HAND SIDE RANGES

Constraint   Lower Limit Current Value Upper Limit

1    666.667 1200.000 4000.000
2 450.000 1500.000 2700.000

a. Give the complete optimal solution. b. Which constraints are binding?

b. Which constraints are binding?

c. What is the dual price for the second constraint? What interpretation does this have?

d. Over what range can the objective function coefficient of x2 vary before a new solution point

becomes optimal?

e. By how much can the amount of resource 2 decrease before the dual price will change?

f. What would happen if the first constraint's right-hand side increased by 700 and the second's

decreased by 350?

Answer 1

a) The optimal solution is following:

X1 = 140

X2 = 0

X3 = 80

Objective value = 4700

b) Slack/surplus for both constraints is 0. So both constraints are binding.

c) Dual price for second constraint is 2.33. It means a unit increase in RHS of this constraint will increase the objective value by 2.33 units

d) Range of optimality for objective coefficnt of x2 is no lower limit to 40 (upper limit)

e) lower limit for resource 2 is 450. Therefore, resource 2 can be decreased by 1500-450 = 1050.

f) Using 100% rule, total change as percent of respective allowable change = 700/2800+350/1050 = 58.3 %

This is less than 100% . So, dual prices will remain valid.