Question

Operations Research

Problem 2. Consider the following program: Minimize 2 22 subject to+ x2 s2 2x1 + 3x2 21 xi r2 21 Please solve the problem graphically and perform sensitivity analysis (along the lines of Supple- mentary text): (a) determine the amount of slack (or unused surplus) in the constraints at the optimal solu tion; )etie shadow prices/reduced s ociated with the constraints (c) for the binding constraints, determine the ranges for the right-hand side coefficients such that the constraints remain binding if the coefficients are changed one at a time; (d) determine the ranges for the cost coefficients (the coefficients in the objective functions) such that the optimal solution does not change if we vary the coefficients one at a time

Answer 1

Solution using graphical method is following:

Objective function: Min Z-2x1 + 1x2 Constraints: 1x1 1x2 2 2x13x2 s 21 2x1 -1x2 s9 1x1 0x222 0x11x2 2 1 x1, x2 20 - C1 - C2 - C3 C4 --C5 x1-axis and x2-axis Tabulate values of x1 & x2 for above constraints and plot them on the graph ーCl-C2-C3-C4-C5 Obj (z) 10.5 6 4.5 C4 2 0 Feasible Region 10 0 0 Obj (Z) 0 1 2 34 5 6 789 10 x1 4.5 Note that C3 and Obj (Z) coincide The yellow shaded region in the graph is the feasible region Corner Points Obj. (Z) C1, C2 C2, C3 C3, C5 C5, C4 C4, C1 Optimal Solution Optimal Solution 6 9 9 2 2 4

There are multiple optimal solutions possible along C3 line segment. Two of the possible solutions are shown in the above table.

(a) Amount of slack or surplus in each constraint are following:

Constraint 1 : 2 - (-1*5+1*1) = 6

Constraint 2 : 21 - (2*5+3*1) = 8

Constraint 3 : 9 - (2*5-1*1) = 0

Constraint 4 : (1*5+0*3) - 2 = 3

Constraint 5 : (0*5+1*1) - 1 = 0

(b) At optimal solution (x1=5, x2=1), constraint 3 is binding.

If the RH side of constraint 3 is increased by 1 unit, the optimal point shifts to the right as shown in the following graph

ーCl-C2-C3-C4-C5 Obj (Z) 10 6 0 1 2 3 4 5 6 78 9 10 x1

The new optimal solution is: x1 = 5.5, x2 = 1

New objective value = -2*5.5+1*1 = -10

objective value improved by 1

So shadow price of constraint 3 = 1

(c) We see that, if the RH side of the binding constraint (3) is increased to 17, then it ceases to be a binding constraint. Also, if its RH side is decreased to 3, then also it ceases to be binding.

ーCl-C2-C3-C4-C5 Obj (Z) 10 6 0 1 2 3 4 5 6 78 9 10 x1

ーCl-C2-C3-C4-C5 Obj (Z) 10 6 0 0 1 2 3 4 5 6 78 9 10 x1

Similarly, ranges for all the constraints are determined, which are following:

Constraint	Lower limit	Upper limit
1	-4	infinity
2	13	infinity
3	3	17
4	-infinity	5
5	0	3

(d) Ranges for objective coefficients are determined by changing coefficient of one variable at a time, while keeping the other one fixed, such that slope of the objective function remains between the slope of binding constraints.

Resulting ranges of the objective function coefficients are following:

Variable	Lower limit	Upper limit
x1	-2	0
x2	1	infinity