Those damn interns

Problem Definition

You are the production manager of a company. You have used the following programming model to define the optimal production plan. The problem is expressed in the standard form. Objective function:

\(\max z = 3*x_1 + 4*x_2 - M*a_1 + 0*s_2 + 0*s_3\)

s.t

\(x_1 + 0*x_2 + a_1 + 0*s_2 + 0*s_3 = 18\)

\(20*x_1 + 40*x_2 + 0*a_1 + s_2 + 0*s_3 = 1000\)

\(26.67*x_1 + 20*x_2 + 0*a_1 + 0*s_2 + s_3 = 800\)

where M is a very large number and artificial and slack variables are indexed in order of appearance.

The intern submitted the following data describing the solution obtained by a solver. This solver provides the solution of both the primal and the dual and a sensitivity analysis in a table, but your intern handled you the following handwritten report:

X1 -> Solution value: 18 Reduced Cost: ? Status: basic Objective coefficient: ? Objective Lower Bound: -Inf Objective Upper Bound: 5.334

X2 -> Solution value: 15.997 Reduced Cost: ? Status: ? Objective coefficient: 4 Objective Lower Bound: 2.2497 Objective Upper Bound: Inf

A1-> RHS= 18 Slack = 0 Sense = ? Shadow price= -2.334 Min RHS= 17.9964 Max RHS= 29.9963

S2-> RHS= 1000 Slack = 0.12 Sense = less or equal Shadow price= 0 Min RHS= 999. Max RHS= Inf

S3-> RHS= ? Slack = ? Sense = less or equal Shadow price= 0 Min RHS= 480.06 Max RHS= 800.06

a. You analise the solution and notice that there are some missing values noted as ? (You are going to fire this intern!). Write down the values missing in the solution. Motivate your response in each case.

For decision variable \(x_1\) Since the value is non-zero (it is a basic decision variable), by complementary slackness, the reduced cost is 0. The objective function indicates that the objective coefficient is 3.

For decision variable \(x_1\) Also, by complementary slackness, the reduced cost is 0 and since the value is greater than zero, the decision variable is basic.

For slack, \(a_1\) If we note the coefficient in the objective function, (-M) we know that this is an artificial variable that must be always 0 and the sense is ‘equal’.

For \(s_3\), The Right Hand Side for the third constraint is 800 looking at the problem.

We can calculate the slack by substituting the values of X1 and X2 in the expression:

26.67X1+20X2+0A1+0S2+S3=800 26.67·18 + 20·15.997 + S3 = 800 S3 = 0

We could have also argued that since the solution is a Feasible Basic Solution, only 3 decision variables (in this case X1, X2, and S2) can be basic (as many as constraints) and therefore S3 must be non-basic (0).

b. Which of the two decision variables has a larger contribution to the optimal solution? Motivate your response (1 point).

If we multiply the value times the objective function:

\(3·x_1 = 3·18 = 54\)

\(4·x_2 = 4·15.997 = 63.998\)

Clearly \(x_2\) has a larger contribution to the objective function

c. The first constraint determines the value of one of the decision variables (\(x_1\)). What would happen to the objective function if the right hand side of this constraint changes to 19? and to 31? Motivate your response

The maximum RHS for the first constraint is 29.993. If the RHS changes to 19, the basic decision variables would remain the same, although the values in the optimal solution might change. If the value changes to 31 then the basic decision variables would certainly change.

d. What would happen to the solution if the objective function coefficient of X1 changes to 5? And what if the coefficient of X2 changes to 3? Motivate your response

The Upper bound for the objective coefficient of \(x_1\) is 5.334 and therefore, the solution would not change if the objective 5 increased to 5.

The lower bound for the objective coefficient of \(x_2\) is 2.2497 and therefore, the solution would not change if the coefficient decreases down to 3.