Question

Consider the following linear program: Max 2X + 3Y s.t. 5X +5Y ≤ 400 -1X+ 1Y ≥ 10 1X + 3Y ≥ 90 X, Y ≥ 0

a. Use the graphical solution procedure to find the optimal solution.

b. Conduct a sensitivity analysis to determine the range of optimality for the objective function coefficients X & Y.

c. What are the binding constraints?  

d. If the right-hand-side of the binding constraints are marginally increased, what will be the Dual Value?

Answer 1

(a)

Problem is

MAX zx = 2 x1 + 3 x2

subject to

5 x1 + 5 x2 ≤ 4000 - x1 + x2 ≥ 10 x1 + 3 x2 ≥ 90

and x1,x2≥0;

Hint to draw constraints

1. To draw constraint 5x1+5x2≤4000→(1)
Treat it as 5x1+5x2=4000

When x1=0 then x2=?
⇒5(0)+5x2=4000
⇒5x2=4000
⇒x2=40005=800

When x2=0 then x1=?
⇒5x1+5(0)=4000
⇒5x1=4000
⇒x1=40005=800

x1	0	800
x2	800	0

2. To draw constraint -x1+x2≥10→(2)
Treat it as -x1+x2=10

When x1=0 then x2=?
⇒-(0)+x2=10
⇒x2=10

When x2=0 then x1=?
⇒-x1+(0)=10
⇒-x1=10
⇒x1=-10

x1	0	-10
x2	10	0

3. To draw constraint x1+3x2≥90→(3)
Treat it as x1+3x2=90

When x1=0 then x2=?
⇒(0)+3x2=90
⇒3x2=90
⇒x2=903=30

When x2=0 then x1=?
⇒x1+3(0)=90
⇒x1=90

x1	0	90
x2	30	0

The value of the objective function at each of these extreme points is as follows:

Extreme Point Coordinates (x1,x2)	Lines through Extreme Point	Objective function value z=2x1+3x2
A(0,30)	3→x1+3x2≥90 4→x1≥0	2(0)+3(30)=90
B(0,800)	1→5x1+5x2≤4000 4→x1≥0	2(0)+3(800)=2400
C(395,405)	1→5x1+5x2≤4000 2→-x1+x2≥10	2(395)+3(405)=2005
D(15,25)	2→-x1+x2≥10 3→x1+3x2≥90	2(15)+3(25)=105

The maximum value of the objective function z=2400 occurs at the extreme point (0,800).
Hence, the optimal solution to the given LP problem is : x1=0,x2=800 and max z=2400.

(b)

Range of optimality for objective function coefficient X=Objective function coefficient -Allowable decrease to Objective function coefficient +Allowable increase

=2-infinity to 2+1

= -infinity to 3  

Range of optimality for objective function coefficient Y=Objective function coefficient -Allowable decrease to Objective function coefficient +Allowable increase

=3-1 to 3+infinity

= 2 to infinity

Sensitivity report :

(c)

The binding constraints are the ones that have one or more feasible optimal solutions on their equation. Hence, a binding solution is the one that contributes to the feasible region and the optimal solution and feasible region changes with changes in binding constraints.

Hence, in the above solutions, all the constraints are contributing except X2 >= 0

Hence, binding constraints are,

5x1 + 5x2 <= 400
-x1 + x2 >= 10
x1 + 3x2 >= 90
X1 >= 0

(d) From the answer report,constraint 1 is binding.

If the RHS of constraint is marginally increased ,the dual price will remain same and is equal to 0.6.

Sensitivity report with allowable increase =infinity(very high value) and shadow price/dual price=0