Question

3. Consider the following linear program:

MIN 6x₁ + 9x₂ ($ cost)

s.t. x₁ +2x₂ ≤8

10x₁ + 7.5x₂ ≥ 30

x₂ ≥ 2

x₁,x₂ ≥0

The Management Scientist provided the following solution output:

OPTIMAL SOLUTION

Objective Function Value = 27.000

Variable	Value	Reduced Cost
X1	1.500	0.000
X2	2.000	0.000

Constraint	Slack/Surplus	Dual Price
1	2.500	0.000
2	0.000	−0.600
3	0.000	−4.500

OBJECTIVE COEFFICIENT RANGES

Variable	Lower Limit	Current Value	Upper Limit
X1	0.000	6.000	12.000
X2	4.500	9.000	No Upper Limit

RIGHT HAND SIDE RANGES

Constraint	Lower Limit	Current Value	Upper Limit
1	5.500	8.000	No Upper Limit
2	15.000	30.000	55.000
3	0.000	2.000	4.000

A. What is the optimal solution including the optimal value of the objective function?

B .Suppose the unit cost of x1 is decreased to $4. Is the above solution still optimal? What is

the value of the objective function when this unit cost is decreased to $4?

C. How much can the unit cost of x2 be decreased without concern for the optimal solution

changing?

D. If simultaneously the cost of x1 was raised to $7.5 and the cost of x2 was reduced to $6,

would the current solution still remain optimal?

E. If the right-hand side of constraint 3 is increased by 1, what will be the effect on the

optimal solution?

Answer 1

A

The optimal solution is X1= 1.5 and X2= 2. This makes the objective function value as

6*1.5 + 9*2 = 27

It is found in the variable table and their corresponding values

B

Yes. The third table "objective coefficient range" shows that the lower limit for X1 is 0. The current value is 6 and this means between 0 to 6 the optimal solution will not change. This means X1 will remain as 1.5 and X2 will remain as 2 at the optimal solution. This means the objective function value will be

4*1.5 + 9*2 = 24

C

X2 unit cost is denoted by the objective function coefficient. This is given in the third table. We can see that the lower limit is 4.5 for the X2. This means the unit cost can be 4.5 and there will be no change in the optimal solution.

D

In this problem we have two binding constraings (2 and 3). If we change the coefficnet (cost) of X1 and X2, we still need to satisfy these constraints. And this would make the value of X2 = 2 if possible. Testing it out on the equation we find that the previous values of 1.5 and 2 satisfies all the conditions and remains as the optimal solution.

Thus if we simultaneously increase cost of X1 to 7.5 and decrease the cost o X2 to 6 then the otimal solution remains the same.

E

The dual price of constraint 3 is -4.5 This means if we increase the RHS by 1, the optimal solution value will reduce by 4.5