Section 4.5 Multple, Unbounded, and No Solutions
Section 4.5
1.The -20 in the last column with nonnegative entries in the rest of the first row indicates no feasible solutions.
2.The zero at the bottom of the third column indicates a multiple solution.
3.There is an unbounded feasible region, so no solution, because all entries in column 4 are negative.
4.The third row indicates no feasible solution because the last entry is negative and all other entries are nonnegative.
5.
This gives maximum of 210 at (5, 9)
This gives maximium of 210 also at (10, 4)
Maximum z = 210 at (5, 9), (10, 4), and on the line segment between.
6.
Maximum = 375 at (25, 0)
Maximum = 375 also at (21, 6)
Maximum z = 375 at (25, 0), (21, 6), and on the line segment between.
7.
Maximum = 40 at (5, 5, 2.5)
Maximum = 40 also at (20/3, 20/3, 0)
Maximum z = 40 at(5, 5, 2.5), (20/3, 20/3, 0), and on the line segment between.
8.
Maximum = 800 at (15, 5, 0)
Maximum = 800 also at (15/2, 5/2, 20)
Maximum z = 800 at (15, 5, 0), (15/2, 5/2, 20), and on the line segment between.
9.
All entries in column 1 are negative, unbounded feasible region
10.
All entries in column 1 are negative, unbounded feasible region
11.
All entries in column 2 are negative, unbounded feasible region
12.
All entries in column 5 are negative, unbounded feasible region
13.
Pivoting leads to a row with a negative entry in row 2 of the last column and all other entries in the row are nonnegative. Thus, there is no feasible solution.
14.
Pivoting leads to a row with a negative entry in row 1 of the last column and all other entries in the row are nonnegative. Thus, there is no feasible solution.
15.
Pivoting leads to a row with a negative entry the last column of row 2 and all other entries in the row are nonnegative. Thus, there is no feasible solution.
16.
Pivoting leads to a row with a negative entry in the last column of row 2 and all other entries in the row are nonnegative. Thus, there is no feasible solution.
17.
All entries in column 1 are negative, unbounded feasible region
18.
Column 4 indicates multiple solutions.
Multiple solutions: z = 90 at (3, 5), (0, 10), and on the line segment between.
19.
The last entry in row 1 is negative and the rest of the row is nonnegative, no feasible solution
20.
The last entry in row 2 is negative and the rest of the row is nonnegative, no feasible solution
21.
The last entry in row 1 is negative and the rest of the row is nonnegative, no feasible solution
22.
All entries of column 1 are negative, unbounded feasible region
23.
The last entry in row 1 is negative and the rest of the row is nonnegative, no feasible solution
24.
All entries of column 5 are negative, unbounded feasible region
25.
Column 6 indicates multiple solutions.
Multiple solutions, minimum z = 51 at (51/4, 15/2, 3), (24, 0, 3), and points on the line segment between.
26.
Column 4 indicates multiple solutions.
Multiple solutions: minimum z = 160 at (12, 4, 8), (0, 0, 40) and points between.
27.
All entries in column 1 are negative, unbounded feasible region
28.Let x = number of Gadgets, y = number of Widgets.
Minimize z = 0.10x + 0.20y, subject to
x + y ³ 4000
2.5x + 3y ³ 12,000
0.20x + 0.25y ² 900
x ³ 0, y ³ 0
The last entry in row 3 is negative and the rest of the row is nonnegative, no feasible solution
29.Let x = number of Petite, y = number of Deluxe.
Maximize z = 5x + 6y subject to
x + 2y ² 3950
4x + 3y ² 9575
y ³ 2000
x ³ 0, y ³ 0
The last entry in row 1 is negative and the rest of the row is nonnegative, no feasible solution
30.Let x = number of cartons of regular cola, y = number of cartons of diet cola
Maximize profit z = 0.15x + 0.17y subject to
x + y ³ 5000 (required production)
1.1x + 1.3y ² 5400 (operating budget)
x ³ 0, y ³ 0
Row 2 indicates no feasible solution because the last entry is negative and all other entries in the row are nonnegative.
31.Let x = amount invested in stocks and y = amount invested in bonds.
Maximize expected return z = 0.10x + 0.07y subject to
+ y ³ 10,000 (amount invested)
x ³ 5000 + y (5000 more in stocks than bonds)
x ³ 0, y ³ 0
The simplex tableau is
Column 3 contains all negative entries which indicates an unbounded feasible region so there is no maximum expected return.
32.Let x1 = number of packages that Alex packs, x2 = number of packages that Blake packs,
x3 = number of packages that Cindy packs.
Maximize earnings. z = 2.00x1 + 2.50x2 + 3.00x3 subject to
6x1 + 8x2 + 72 ² 9x3 (Number of fiction books)
9x1 + 9x2 ³ 90 + 12x3 (Number of non-fiction books)
x2 ² x1 + 10
x1 ³ 0, x2 ³ 0, x3 ³ 0
We rewrite the constraints as
6x1 + 8x2 – 9x3 ² -72
9x1 + 9x2 – 12x3 ³ 90
-x1 + x2 ² 10
The initial simplex tableau isPivot on –9 in row 2, column 1 gives the Tableau
Since all entries in column 3 are negative the feasible region is unbounded and there is no solution.
33.Let x1 = number units of food A, x2 = number units of food B, x3 = number units of food C.
Minimize cost z = 1.40x1 + x2 + 1.50x3 subject to
15x1 + 10x2 + 23x3 ³ 80 (protein)
20x1 + 30x2 + 11x3 ³ 95 (carbohydrates)
200x1 + 160x2 + 160x3 ³ 1400 (calories)
10x1 + 5x2 + 6x3 ² 40 (fat)
x1 ³ 0, x2 ³ 0, x3 ³ 0
Notice row 3. The last entry is negative and all other entries are nonnegative. This indicates no feasible solution.
34.Let x1 = number of packets of type I, x2 = number of packets of type II, x3 = number of packets of type III.
Maximize profit z = 6x1 + 5x2 + 2x3 subject to
5x1 + 5x2 + 4x3 ² 200 (Number of caps)
10x1 + 6x2 + 5x3 ² 300 (Number of pairs of socks)
2x1 + 3x2 + 6x3 ² 210 (Number of T-shirts)
4x1 + 3x2 ² 60 (Number of shoes)
x1 ³ 0, x2 ³ 0, x3 ³ 0.
The initial simplex tableau is
We now pivot in the usual manner
Basic solution (15, 0, 0) z = 90
For the next pivot use either row 2 or row 3. We use row 2 and obtain
Basic solution (15, 0, 30) z = 150
Use 3.3 in row 3, column 2 as the pivot element because the ratio was zero, 0 divided by a positive number.
Basic solution (15, 0, 30) z = 150
This is an optimal solution.
Notice the zero in the last row of column 5. This is a signal that multiple solutions may exist. Use column 5, row 1 for the pivot.
1
Section 4.6 What’s Happening
Basic solution (0, 20, 25) z = 150
Thus, a maximum profit of $150 is possible if Andrea orders 15 of package I and 30 of package III or 20 of package II and 25 of package III. Actually, if Andrea can find points with integer coordinates on the line segment between (15, 0, 30) and (0, 20, 25), then those points on that line segment will yield maximum profit.
Section 4.6
1.(a)For (0, 0), s1 = 17. For (2, 2) s1 = 3. For (5, 10), s1 = -33. For (2, 1), s1 = 6. For (2, 3), s1 = 0.
(b)(0, 0), (2, 2), (2, 1), and (2, 3) are in the feasible region.
(c)(2, 3) is on the line.
2.For (0, 5), s1 = 0. For (2, 2), s1 = 3. For (1.5, 3), s1 = 1. For (2.5, 2), s1 = 0.
3.Let x2 = 0, s2 = 0 in the second constraint to obtain 5x1 = 30,
x1 = 6. Thus, the corner point is (6, 0).
4.Let s1 = 0 and s2 = 0 in the constraints. We then have
x + 2y = 28
2x + y = 26
which we solve.
2x + 4y = 56
2x + y = 26
3y = 30
y = 10
Then x + 2(10) = 28 gives x = 8 so the corner point is (8, 10).
5.For (0, 0, 0), s1 = 40. For (1, 2, 3), s1 = 26. 6.For (1, 1, 1), s1 = 22 and s2 = 17.
For (0, 10, 0), s1 = 0. For (4, 2, 7), s1 = 13.For (2, 1, 5), s1 = 0 and s2 = 0.
For (0, 4, 1), s1 = 21 and s2 = 0
For (5, 10, 2), s1 = 0 and s2 = -45
7. Is point onIs point in
(5, 10) 15 32 18 No Yes
(8, 10) 12 14 -3 No No
(5, 13) 0 29 0 Yes Yes
(11, 13) -6 -7 -42 No No
(10, 12) 0 0 -29 No No
(15, 11) 0 -29 -58 No No
8.(a)x3(b)x1(c)x1
9.(i)(a)x1 = 0, x2 = 0, s1 = 900, s2 = 2800, z = 0
(b)Intersection of x1 = 0 and x2 = 0
(ii)(a)x1 = 180, x2 = 0, s1 = 0, s2 = 1360, z = 540
(b)Intersection of 5x1 + 2x2 = 900 and x2 = 0
(iii)(a)x1 = 100, x2 = 200, s1 = 0, s2 = 0, z = 700
(b)Intersection of 5x1 + 2x2 = 900 and
8x1 + 10x2 = 2800
10.(a)x2 = 48/5(b)x2 = 42/5(c)x1 = 48
11.(a)For (3, 5) to be on the boundary line s1 = 0 and
6(3) + 4(5) = 24. Since the latter is false, (3, 5) is not on the boundary line.
(b)For (3, 5) to be in the feasible region, 6(3)+4(5)+ s1 = 24 for some nonnegative value ofs1. However, the equation is true only when s1=14 so (3, 5) cannot be in the feasible region.
12.(a)For (3, 7) to be on the boundary line s2 = 0 and 8(3) + 5(7) = 59. Since the latter is true, (3, 7) is on the boundary line.
(b)For (2, 4) to be in the feasible region 8(2) + 5(4) + s2 = 59 for a nonnegative value of s2. This equation is true when s2 = 23 so (2, 4) might be in the feasible region. Other constraints might exclude it.
13.(a)Both x2 ² 36/7 and x2 ² 32/5 must hold, so x2 must be the smaller, 36/7.
(b)x1 ² 6 and x1 ² 16, so x1 is the smaller, 6.
14.If x1= 0, 5x2 + x3 + s1 = 45
x2 = (45 - x3 -s1)/5
x2 = (45 - x3 - s1)/5 is largest when x3 = s1 = 0, so x2 = 9.
15.Initial tableau
Corner (0, 0), z = 0, slack (50, 90, 105, 20)
Tableau 1Tableau 2
Corner (0, 5), z = 100, slack (0, 65, 80, 20)Corner (10, 12), z = 410, slack (0, 0, 5, 10)
Tableau 3Tableau 4
Corner (15, 9), z = 435, slack (65, 0, 0, 5)Optimal solution reached
Corner (20, 5), z = 440, slack (140, 5, 0, 0)
Corner Value IncreaseSlack
(x,y) of z in z(s1, s2, s3, s4 )
(0, 0) 0 (50, 90, 105, 20)
(0, 5) 100 100(0, 65, 80, 20)
(10, 12) 410 310(0, 0, 5, 10)
(15, 9) 435 25(65, 0, 0, 5)
(20, 5) 440 5(140, 5, 0, 0)
16.Initial tableau
Tableau 1Tableau 2
Corner (0, 5), z = 100, slack (0, 65, 80, 20)Optimal solution reached
Corner (10, 12), z = 350, slack (0, 0, 5, 10)
Corner Value IncreaseSlack
(x,y) of z in z(s1, s2, s3, s4)
(0, 0) 0 (50, 90, 105, 20)
(0, 5) 100 100(0, 65, 80, 20)
(10, 12) 350 250(0, 0, 5, 10)
17.Initial tableau
Corner (0, 0), z = 0 slack (36, 45, 46)
Tableau 1Tableau 2
Corner (0, 6, 0), z = 144, slack (0, 9, 10)Corner (2.5, 5.583, 0), z = 159, slack (0, 4, 0)
Tableau 3
Corner (3, 5, 1), z = 163, slack (0, 0, 0)
Optimal solution
Corner Value Increase Slack
(x1, x2, x3) of z in z (s1, s2, s3)
(0, 0, 0) 0 (36, 45, 46)
(0, 6, 0) 144 144 (0, 9, 10)
(2.5, 5.583, 0) 159 15 (0, 4, 0)
(3, 5, 1) 163 4 (0, 0, 0)
18.Initial tableau
Corner (0, 0, 0), z = 0, slack (100, 100, 100)
Tableau 1Tableau 2
Corner (50, 0, 0), z = 1100, slack (0, 50, 0)Corner (50, 0, 0), z = 1100, slack (0, 50, 0)
Tableau 3
Corner (20, 20, 20), z = 1200, slack (0, 0, 0)
Corner Value IncreaseSlack
(x1, x2, x3) of z in z(s1, s2, s3)
(0, 0, 0) 0 (100, 100, 100)
(50, 0, 0) 1100 1100(0, 50, 0)
(20, 20, 20) 1200 100(0, 0, 0)
19.Initial Tableau
Corner (0, 0, 0), z = 0, slack (330, 330, 132)
Tableau 1Tableau 2
Corner (0, 0, 132), z = 396, slack (66, 66, 0)Corner (0, 11, 154), z = 484, slack (11, 0, 0)
Tableau 3
Corner (6, 6, 156), z = 486, slack (0, 0, 0)
Corner Value IncreaseSlack
(x1, x2, x3) of z in z(s1, s2, s3)
(0, 0, 0) 0 (330, 330, 132)
(0, 0, 132) 396 396 (66, 66, 0)
(0, 11, 154) 484 88 (11, 0, 0)
(6, 6, 156) 486 2 (0, 0, 0)
20.Recall the following properties of the simplex method.
1.The simplex method starts at the origin (0, 0) in this case.
2.A pivot moves to an adjacent corner. In this case the first pivot moves to either (0, 5) or
(20, 0) from (0, 0).
3.The choices of the next corner depends on the coefficients of the objective function, 17 and 20 for z = 17x + 20y.
4.For the same increase in x and y, the term 20y will increase more than the term 17x so the y column is chosen for the pivot column. Notice in this case the simplex method can move from (0, 0) to either (0, 5) or (20, 0) In case of moving to (0, 5) y increases by 5 and in moving to (20, 0) x increases by 20. Thus, choice is not between two corner points with equal increases in x and y. Because x in (20, 0) increases four times of what y increases in (0, 5), the corner (20, 0) will give a larger increase in z than (0, 5). However, the simplex method does not know what the adjacent corners are before pivoting. Without information about which variable will increase the most, the simplex method uses the best guess of choosing the variable that gives the greatest increase in z for each unit change.
21.There is no change in z because the the process remains at that corner point but changes from one boundary line to another at that point.
1