MATH 3170 6.00 A SU 2012
Solutions to selected problems from Sections 4.4-4.10
4.4.1
From Figure 2 of Chapter 3 we see that the extreme points of the feasible region are:
Basic Feasible Solution
H = (0, 0), s1 = 100, s2 = 80, s3 = 40 x1 = x2 = x3 = 0
E = (40, 0), x1 = 40, s1 = 20, s2 = 40 x2 = x3 = s3 = 0
F = (40, 20), x1 = 40, x2 = 20, s2 = 20 x3 = s1 = s3 = 0
G = (20, 60), x1 = 20, x2 = 60, s3 = 20 x3 = s1 = s2 = 0
D = (0, 80), s1 = 20, x2 = 80, s3 = 40 s2 = x1 = x3 = 0
4.4.4
Let σA = 1/6, σC = 1/3 and σB = ½. Then
Please note that the solution to similar question was given in the class.
4.4.7
The direction of unboundedness is any direction (note that there may exist an infinite number of them) between the isoprofit line, which has slope 2, and the line representing the constraint x1 + x2 <=1, which has slope 1.
For example, is a direction of unboundedness.
As we move in this direction z increases unboundedly and we stay in the feasible region. Of course, there are other directions of unboundedness.
4.5.3
z x1 x2 x3 s1 s2 s3 RHS Ratio
1 2 1 1 0 0 0 0
0 3 1 1 1 0 0 60 20
0 1 1 2 0 1 0 10 10* Enter x1 in row 2
0 1 1 1 0 0 1 20 20
1 0 1 3 0 2 0 20
0 0 4 5 1 3 0 30 15/2
0 1 1 2 0 1 0 10 None
0 0 2 3 0 1 1 10 5* Enter x2 in row 3
------
z x1 x2 x3 s1 s2 s3 RHS Ratio
1 0 0 3/2 0 3/2 1/2 25
0 0 0 1 1 1 2 10
0 1 0 1/2 0 1/2 1/2 15
0 0 1 3/2 0 1/2 1/2 5
This is an optimal tableau with optimal solution z = 25,
s1 = 10, x1 = 15, x2 = 5, s2 = s3 = 0.
4.5.5
Initial Tableau
z / X1 / X2 / S1 / S2 / S3 / RHS1 / -1 / -1 / 0 / 0 / 0 / 0
0 / 4 / 1 / 1 / 0 / 0 / 100
0 / 1 / 1 / 0 / 1 / 0 / 80
0 / 1 / 0 / 0 / 0 / 1 / 40
We could choose to enter either X1 or X2 into the basis. We arbitrarily choose to enter X2 into basis. Row 2 is the pivot row yielding the following (optimal) tableau.
z / X1 / X2 / S1 / S2 / S3 / RHS1 / 0 / 0 / 0 / 1 / 0 / 80
0 / 3 / 0 / 1 / -1 / 0 / 20
0 / 1 / 1 / 0 / 1 / 0 / 80
0 / 1 / 0 / 0 / 0 / 1 / 40
Optimal solution is x1=0, x2=80, s1=20, s2=0, s3=40 with optimal value 80.
Alternatively, if you choose to enter X1 from the initial tableau (according to the smallest subscript rule), we would get the following tableau:
z / X1 / X2 / S1 / S2 / S3 / RHS1 / 0 / -3/4 / 1/4 / 0 / 0 / 25
0 / 1 / 1/4 / 1/4 / 0 / 0 / 25
0 / 0 / 3/4 / -1/4 / 1 / 0 / 55
0 / 0 / -1/4 / -1/4 / 0 / 1 / 15
We then have to enter X2, to get the following optimal tableau:
z / X1 / X2 / S1 / S2 / S3 / RHS1 / 0 / 0 / 0 / 1 / 0 / 80
0 / 1 / 0 / 1/3 / -1/3 / 0 / 20/3
0 / 0 / 1 / -1/3 / 4/3 / 0 / 220/3
0 / 0 / 0 / -1/3 / 1/3 / 1 / 100/3
Optimal solution is x1=20/3, x2=220/3, s1=s2=0, s3=100/3 with optimal
value 80. This is another optimal solution. If you want, you may
carry out an extra iteration by entering s1 and leaving x1, to get
back the other optimal tableau (the second one above).
This problem shows that the smallest subscript rule may not always
yield the most efficient way of solving an LP problem.
4.6.1
z x1 x2 s1 s2 s3 RHS Ratio
1 4 1 0 0 0 0
0 2 1 1 0 0 8 8
0 0 1 0 1 0 5 5* Enter x2 in row 2
0 1 1 0 0 1 4 None
1 4 0 0 1 0 5
0 2 0 1 1 0 3
0 0 1 0 1 0 5
0 1 0 0 1 1 9
The current tableau is optimal because each variable has a non-positive coefficient in the current tableau. Thus the optimal solution to the LP is z = 5, s1 = 3, x2 = 5, s3 = 9,
x1 = s2 = 0. Observe that the optimal objective function value for an LP can be negative.
4.6.4
Z / X1 / X2 / S1 / S2 / RHS1 / 3 / -8 / 0 / 0 / 0
0 / 4 / 2 / 1 / 0 / 12
0 / 2 / 3 / 0 / 1 / 6
X1 enters the basis. We arbitrarily choose to enter X1 in row 2. The resulting optimal tableau follows:
Z / X1 / X2 / S1 / S2 / RHS1 / 0 / -12.5 / 0 / -1.5 / -9
0 / 0 / -4 / 1 / -2 / 0
0 / 1 / 1.5 / 0 / .5 / 3
The LP’s optimal solution is Z = -9, X1=3, X2=0.
4.7.2
z x1 x2 s1 s2 RHS Ratio
1 3 6 0 0 0
0 5 7 1 0 35 5
0 1 2 0 1 2 1* Enter x2 in row 2
1 0 0 0 3 6
0 17/2 0 1 7/2 28
0 1/2 1 0 1/2 1
This is an optimal tableau with optimal solution z = 6,
s1 = 28, x2 = 1, s2 = x1 = 0. Since the non-basic variable x1 has a zero coefficient in Row 0 we can enter x1 into the basis to obtain the alternative optimal solution z = 6,
x1 = 56/17, x2 = 45/17. By averaging these two optimal solutions, a third optimal solution may be obtained. This yields the optimal solution z = 6, x1 = 28/17, x2 = 31/17.
4.7.9
Clearly any bfs having x5=0 is optimal. If you follow the simplex method, the initial tableau is already optimal. Carry out two more extra iterations will give you two more bfs’s:
Thus the set of all optimal solutions may be written in the form
a + b + c = ,
where a0, b0, c>=0, and a+bc=1.
4.8.4
We wish to solve
max z = x1 0.25x2
st x1 0.25x2³0 (dollar constraint)
3x1 + x2³0 (franc constraint)
x1, x2³0
z x1 x2 s1 s2 RHS
1 1 0.25 0 0 0
0 1 0.25 1 0 0
0 3 1 0 1 0
x1 enters the basis
z x1 x2 s1 s2 RHS
1 0 1/12 0 1/3 0
0 0 1/12 1 1/3 0
0 1 1/3 0 1/3 0
The x2 column now indicates the LP problem is unbounded.
4.8.6
-Z / X1 / X2 / S1 / S2 / RHS1 / -1 / -3 / 0 / 0 / 0
0 / 1 / -2 / 1 / 0 / 4
0 / -1 / 1 / 0 / 1 / 3
X2 enters the basis in ROW 2 yielding the following tableau:
-Z / X1 / X2 / S1 / S2 / RHS1 / -4 / 0 / 0 / 3 / 9
0 / -1 / 0 / 1 / 2 / 10
0 / -1 / 1 / 0 / 1 / 3
We would like to enter X1 into the basis but there is no row in which X1 has a positive coefficient. Therefore, the LP is unbounded.
4.10.4
Here is just one suggestion:
MODEL:
SETS:
PRODUCTS/1..3/:MADE,PROFIT;
RESOURCES/1..3/:AVAIL;
RESPRO(RESOURCES,PRODUCTS):USAGE;
ENDSETS
MAX=@SUM(PRODUCTS(I):PROFIT(I)*MADE(I));
@FOR(RESOURCES(I):@SUM(PRODUCTS(J):USAGE(I,J))* MADE(J)<=AVAIL(I));
DATA:
PROFIT= 800,1500,2500;
AVAIL=50,10 150;
USAGE= 2,3,5
0.3,0.7,0.2
10,12,20;
ENDDATA
END