- a)
Max x1 + x2 St x1 + x2 - s1 = 3 2x1 + x2 + s2 = 12 x1 + 2x2 + s3 = 12 x1, x2, s1, s2, s3 >=0 - b)
a: x1=0 x2=3 s1=0 s2=9 s3=6 b: x1=3 x2=0 s1=0 s2=6 s3=9 c: x1=6 x2=0 s1=3 s2=0 s3=6 d: x1=4 x2=4 s1=5 s2=0 s3=0 e: x1=0 x2=6 s1=3 s2=6 s3=0None are degenerate. We have three constraints and at every corner precisely three variables have non-zero values. - c) Adding constraint x1 + x2 <= 8 increases the number of constraints to four and the number of variables to six (s4 is the new slack). For a non-degenerate basic solution, we must have four non-zero values. At every corner point above except point d, s4 has a positive value thus the number of non-zero values is four. The new constraint happens to pass through point d (thus s4=0) and leaves the number of non-zero values at three . Therefore point d is a degenerate basic feasible solution.
3x1 - 2x2 - s = 6
- a) i) s = -6; ii) s = 0; iii) s = 1.
- b) i) is infeasible ii) and iii) are feasible
[go back] [Any questions?]
- a) exactly 30 of the 80 variables will be non-zero.
- b) less than 30 of the 80 variables will be non-zero.
[go back] [Any questions?]
- The dual price of an inactive constraint is zero . This follows from the fact than when an inactive constraint moves, only the associated slack/surplus changes and leaves the solution and the OV unchanged. See RHS section of Sensitivity Principles.
- The dual price of an active constraint is generally
non-zero. Since the dual price
measures the rate of improvement in OV due to a change in the RHS
it can be positive or negative.
Consider an active "<=" constraint. Increasing the RHS loosens the constraint and generally helps the OV, regardless of Max or Min. Therefore an increase in the RHS is accompanied by a corresponding positive improvement in the OV. Therefore, the dual price in this case is positive.
For a ">=" type active constraint, increasing the RHS tightens the constraint, and may cause a deterioration (negative improvement ) of the OV. Thus, in general, dual price of a ">=" type active constraint will be negative.
[go back] [Any questions?]
- a) No effect. Allowable increase is infinity and dual price is zero.
- b) This is a >= type. Tightening means increasing. The allowable increase is 6.5. Hence it can be increased by 6.5 units.
- c) Dept B is row 5. The dual price is 175. This means the rate of improvement (increase here) due to change in the RHS of this constraint is $175. The allowable increase is 73.33, this means the RHS can increase by as much as 73.33 without changing the dual price. Hence the change in the OV will be an increase of 50* 175 = $8750.
- a) Since the increase of $1000 in the coefficient of F is within the allowable limit, the solution: E = 4.5 F= 7.0 does not change.
- b) The Rate of change in the OV due to a change in the OFC of a variable is given by the current value of that variable. In this case it is 7.0. Thus an increase of a $1000 in the OFC of F will produce a $7,000 increase in the OV. (Each of the 7 units of F will fetch an extra $1,000).