MATH 3170 6.00 A SU 2013
Solutions to selected problems from Sections 4.11-4.14 and 4.16
4.11.2
-z x1 x2 s1 s2 RHS
1 -1 -1 0 0 0
0 1 1 1 0 1* Enter x1 in row 1
0 1 1 0 1 0
-z x1 x2 s1 s2 RHS
1 0 0 1 0 1
0 1 1 1 0 1
0 0 2 1 1 1
This is an optimal tableau with an optimal solution being x1 = 1, x2 = 0.
4.11.4
Here are the pivots:
Z / X1 / X2 / X3 / X4 / S1 / S2 / S3 / RHS1 / 3 / -1 / 6 / 0 / 0 / 0 / 0 / 0
0 / 9 / 1 / -9 / -2 / 1 / 0 / 0 / 0
0 / 1 / 1/3 / -2 / -1/3 / 0 / 1 / 0 / 0
0 / -9 / -1 / 9 / 2 / 0 / 0 / 1 / 1
BV={S1,S2,S3}.
X2 now enters in Row 1 yielding the following tableau.
Z / X1 / X2 / X3 / X4 / S1 / S2 / S3 / RHS1 / 12 / 0 / -3 / -2 / 1 / 0 / 0 / 0
0 / 9 / 1 / -9 / -2 / 1 / 0 / 0 / 0
0 / -2 / 0 / 1 / 1/3 / -1/3 / 1 / 0 / 0
0 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 1
BV={X2,S2,S3}.
We now enter X3 into the basis in Row 2.
Z / X1 / X2 / X3 / X4 / S1 / S2 / S3 / RHS1 / 6 / 0 / 0 / -1 / 0 / 3 / 0 / 0
0 / -9 / 1 / 0 / 1 / -2 / 9 / 0 / 0
0 / -2 / 0 / 1 / 1/3 / -1/3 / 1 / 0 / 0
0 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 1
BV={X2,X3,S3}.
We now enter X4 into the basis in Row 1.
Z / X1 / X2 / X3 / X4 / S1 / S2 / S3 / RHS1 / -3 / 1 / 0 / 0 / -2 / 12 / 0 / 0
0 / -9 / 1 / 0 / 1 / -2 / 9 / 0 / 0
0 / 1 / -1/3 / 1 / 0 / 1/3 / -2 / 0 / 0
0 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 1
BV={X4,X3,S3}.
X1 now enters basis in Row 2.
Z / X1 / X2 / X3 / X4 / S1 / S2 / S3 / RHS1 / 0 / 0 / 3 / 0 / -1 / 6 / 0 / 0
0 / 0 / -2 / 9 / 1 / 1 / -9 / 0 / 0
0 / 1 / -1/3 / 1 / 0 / 1/3 / -2 / 0 / 0
0 / 0 / 0 / 0 / 0 / 1 / 0 / 1 / 1
BV={X4,X1,S3}.
We now choose to enter S1 in Row 1.
Z / X1 / X2 / X3 / X4 / S1 / S2 / S3 / RHS1 / 0 / -2 / 12 / 1 / 0 / -3 / 0 / 0
0 / 0 / -2 / 9 / 1 / 1 / -9 / 0 / 0
0 / 1 / 1/3 / -2 / -1/3 / 0 / 1 / 0 / 0
0 / 0 / 2 / -9 / -1 / 0 / 9 / 1 / 1
BV={S1,X1,S3}.
S2 would now enter basis in Row 2. This will bring us back to the initial tableau, so cycling has occurred.
4.12.2
After adding slack, excess and artificial variables, we obtain the following:
min z = 2x1 + 3x2 + Ma1
s.t. 2x1 + x2 e1 + a1 = 4
x1 + x2 + s2 = 1
with all variables nonnegative. After eliminating a1 from -z +2x1 +3x2 +Ma1 = 0 we obtain -z +(2 2M)x1 + (-M+3)x2 + Me1 = -4M. Proceeding with the simplex we obtain
-z x1 x2 e1 s2 a1 RHS
______
1 -2M+2 -M+3 M 0 0 -4M
______
0 2 1 1 0 1 4
______
0 1 1 0 1 0 1
______
x1 enters and a1 leaves.
______
1 0 2 1 0 M-1 -4
______
0 1 1/2 1/2 0 1/2 2
______
0 0 3/2 1/2 1 1/2 3
______
Note that we could have omitted the column of a1 since it turns nonbasic in the above iteration.
This is an optimal tableau with optimal solution x1 = 2, s2 = 3,
e1 = x2 = 0.
4.12.5
Initial tableau is
-Z / X1 / X2 / X3 / A1 / A2 / RHS1 / -3M+1 / -2M+1 / -3M / 0 / 0 / -6M
0 / 2 / 1 / 1 / 1 / 0 / 4
0 / 1 / 1 / 2 / 0 / 1 / 2
We now enter X3 in the basis in row 2:
-Z / X1 / X2 / X3 / A1 / A2 / RHS1 / -3M/2+1 / -M/2+1 / 0 / 0 / 3M/2 / -3M
0 / 3/2 / 1/2 / 0 / 1 / -1/2 / 3
0 / 1/2 / 1/2 / 1 / 0 / 1/2 / 1
The column of A2 could have been omitted since it is a non-basic artificial variable. We now enter X1 in the basis in row 2. This is done according to the smallest subscript rule when there is a tie in choosing the leaving variable. Both X3 and A1 are candidates for leaving variable; X3 is chosen since it precedes A1 in our ordering of the variables.
-Z / X1 / X2 / X3 / A1 / A2 / RHS1 / 0 / M / -2+3M / 0 / -1+3M / -2
0 / 0 / -1 / -3 / 1 / -2 / 0
0 / 1 / 1 / 2 / 0 / 1 / 2
This optimal tableau yields the optimal solution X1=2, X2=X3=0 with Z=2 for the original problem, since all the artificial variables are now zero (A2 is non-basic, A1 is basic but degenerate).
Note that if we leave A1 in the second iteration, we would obtain another optimal tableau for the basis {X1,X3}. Both bases {X1,X3} and {A1,X1} correspond to the same optimal BFS (of the Big M problem) since the problem is degenerate. Both cases correspond to the same optimal solution for the original problem: (2,0,0).
4.13.3
As explained in the solution to Problem 3, Section 4.10 we may omit the x1 + x23 constraint. Then the row 0 for phase I is w a2 = 0. Eliminating a2 from consideration we obtain w + x1 + x2 = 3. Phase I now proceeds as follows:
w x1 x2 s1 a2 RHS
______
1 1 1 0 0 3
______
0 2 1 1 0 4
______
0 1 1 0 1 3
______
______
1 0 1/2 1/2 0 1
______
0 1 1/2 1/2 0 2
______
0 0 1/2 1/2 1 1
______
w x1 x2 s1 a2 RHS
______
1 0 0 0 1 0
______
0 1 0 1 1 1
______
0 0 1 1 2 2
______
This is an optimal Phase I tableau. Eliminating x1 and x2 from z 3x1 x2 = 0 we obtain z + 2s1 = 5, which is an optimal tableau. Thus the optimal solution to the original LP is z =5, x1=1, x2=2.
4.13.4
Eliminating a1 and a2 from w a1 a2 = 0 we obtain w + 5x1 + 3x2 e1 = 10. Proceeding with
Phase I, we obtain
w x1 x2 e1 a1 a2 RHS
______
1 5 3 1 0 0 10
______
0 2 1 1 1 0 6
______
0 3 2 0 0 1 4
______
w x1 x2 e1 a1 a2 RHS
______
1 0 1/3 1 0 5/3 10/3
______
0 0 1/3 1 1 2/3 10/3
______
0 1 2/3 0 0 1/3 4/3
______
This is an optimal Phase I tableau. However, the optimal wvalue is 10/3, which is >0. Thus the original LP has no feasible solution.
4.13.5
Initial Phase I Tableau is
W / X1 / X2 / X3 / A1 / A2 / RHS1 / 3 / 2 / 3 / 0 / 0 / 6
0 / 2 / 1 / 1 / 1 / 0 / 4
0 / 1 / 1 / 2 / 0 / 1 / 2
X1 enters the basis in Row 1 yielding
W / X1 / X2 / X3 / A1 / A2 / RHS1 / 0 / 1/2 / 3/2 / -3/2 / 0 / 0
0 / 1 / 1/2 / 1/2 / 1/2 / 0 / 2
0 / 0 / 1/2 / 3/2 / -1/2 / 1 / 0
This completes Phase I. This is Case III so we now drop the A1 column and begin Phase II with A2 as a basic variable.
Z / X1 / X2 / X3 / A2 / RHS1 / 0 / -1/2 / 1/2 / 0 / 2
0 / 1 / 1/2 / 1/2 / 0 / 2
0 / 0 / 1/2 / 3/2 / 1 / 0
X2 now enters basis in Row 2 yielding the following optimal tableau:
Z / X1 / X2 / X3 / A2 / RHS1 / 0 / 0 / 2 / 1 / 2
0 / 1 / 0 / -1 / -1 / 2
0 / 0 / 1 / 3 / 2 / 0
The optimal solution is Z=2, X1=2, X2=X3=0.
4.13.6
The initial Phase I tableau is as follows:
W / X1 / X2 / A1 / A2 / RHS1 / 3 / 3 / 0 / 0 / 6
0 / 1 / 1 / 1 / 0 / 2
0 / 2 / 2 / 0 / 1 / 4
We now arbitrarily choose to enter X1 in Row 2 yielding the following optimal Phase I tableau:
W / X1 / X2 / A1 / A2 / RHS1 / 0 / 0 / 0 / -3/2 / 0
0 / 0 / 0 / 1 / -1/2 / 0
0 / 1 / 1 / 0 / 1/2 / 2
This is an instance of Case III so we drop A2 from the basis. Our Row 0 for Phase 2 is
Z=2. This means there is no way to change Z by pivoting so current solution must be optimal. Our optimal solution is therefore Z =2, X1=2
4.13.7
Any feasible solution to the original LP will have w = 0 in the Phase I LP. Thus if the original LP has more than one feasible solution, then the Phase I LP will have alternative optimal solutions.
4.14.4
max z = z' + z''
s.t. 4x1 + x24
2x1 x2
2x1 3x2 = z' z''
All variables nonnegative
First note that in any basic feasible solution, z' and z'' cannot both be positive. Then observe that if 2x1 3x2>0, then z'' = 0 and the objective function will equal z' + z'' = z' = 2x1 3x2 = |2x1 3x2| while if 2x1 3x2<0, z' = 0 and z'' = |2x1 3x2|, so the objective function will equal z' + z'' = z'' = |2x1 3x2|.
4.16.6
Let xip = hours partners work on job i
xis = hours seniors work on job i
xij = hours juniors work on job i
ph = partners hired
sh = seniors hired
jh = juniors hired
min P1s1- + P2s2+ + P3s3+ + P4s4+
st 160x1p + 120x2p + 110x3p + 120x1s + 90x2s + 70x3s + 50x2j + 40x3j + s1- - s1+ =68,000
ph + s2- - s2+ = 1
sh + s3- - s3+ = 3
jh + s4- - s4+ = 5
x1p + x2p + x3p5(40) + 40ph
x1s + x2s + x3s5(40) + 40sh
x2j + x3j5(40) + 40jh
x1p + x1s = 500
x2p + x2s + x2j = 300
x3p + x3s + x3j = 100
All variables nonnegative
4.16.7
Let xim = Number of students taking marketing from professor i; xif = number of students taking finance from professor i; xip = number of students taking production from professor i; xis = number of students taking statistics from professor i. Then we wish to solve the following problem:
min s1- + s2- + s3- + s4-
st 7x1m + 7x2m + 3x3m + 5x4m + s1- - s1+ = 1200
5x1f + 8x2f + 5x3f + 5x4f + s2- - s2+ = 1200
8x1p + 9x2p + 7x3p + 6x4p + s3- - s3+ = 1200
2x1s + 4x2s + 9x3s + 7x4s + s4- - s4+ = 1200
x1m + x2m + x3m + x4m = 200
x1f + x2f + x3f + x4f = 200
x1p + x2p + x3p + x4p = 200
x1s + x2s + x3s + x4s = 200
x1m + x1f + x1p + x1s = 200
x2m + x2f + x2p + x2s = 200
x3m + x3f + x3p + x3s = 200
x4m + x4f + x4p + x4s = 200
All variables nonnegative
We assume that it is okay to have the average “effectiveness” to be above 6 for any course. But since the question does not explicitly say so, we will also accept s1- + s2- + s3- + s4- + s1+ + s2+ + s3+ + s4+ as a correct objective function (so that high effectiveness is also penalized).
Chapter 4 Review Problem #19
Let xs be the variable entering the basis and xr the variable leaving the basis. Then
(Coefficient of xs in Current Row 0) <0
(Coefficient of xr in Current Row 0) = 0
(Coefficient of xr in Pivot Row) = 1
(Coefficient of xs in Pivot Row) > 0
After the pivot,
(Coefficient of xr in New Row 0) =
(Coefficient of xs in Current Row 0)
- >0
(Coefficient of xs in Current Pivot Row)
Thus, after the pivot, xr will have a positive coefficient in row 0 and will not reenter the basis. On a later pivot, however, it is possible that xr may have a negative coefficient in Row 0 and again reenter the basis.