Operations Research Solutions to Review Questions, Exam 1

Solutions to Review Questions, Exam 1 1. What are the four assumptions for a linear program? • Proportionality: The contribution to both the objective function and the constraints from a decision variable needs to be proportional- In the form of a constant times the variable. That means, no discounts for selling more, no fixed costs, etc. • Additive: The contribution to both the objective function and the constraints from variables x1 , x2 (or more) must be additive, or c1 x1 +c2 x2 . For example, you cannot have the contribution be a product of variables. The first two items ensures that the linear program is “linear” in both the objective function and constraints. • Divisibility: We assume decision variables take on real numbers (not only integers, for example). • Predictability: All constants are known- We do not use a probability distribution for costs, for example. 2. What are the four possible outcomes when solving a linear program? Hint: The first is that there is a unique solution to the LP. SOLUTION: • No solution - The feasible set is empty. • A unique solution (either with or without an unbounded feasible set). • An unbounded solution - The feasible set is unbounded. • An infinite number of solutions - Either by an unbounded set or the isoprofit lines are coincident with a boundary at the optimum. 3. The following are to be sure you understand the process of constructing a linear program: (a) Exercise 2, 31 Chapter 3 review SOLUTIONS: Be sure you can do these graphically. • Exercise 2: The optimal value is 69/7, where we have 36/7 chocolate cake and 66/7 vanilla (yes, the “divisibility” assumption is violated here). • Exercise 31: The LP is unbounded (no solution). (b) Exercise 6, 18 Chapter 3 review (A ton is 2000 lbs) SOLUTIONS: Be sure you introduce your variables! 6. Let x1 be the pounds of Alloy 1 used to produce one ton of steel and x2 be the pounds of Alloy 2. Then the objective function is: min z = 190/2000x1 + 200/2000x2 With: – Carbon constraints: 0.03x1 + 0.04x2 ≥ (0.032)(2000) 1 0.03x1 + 0.04x2 ≤ (0.035)(2000) – Silicon: 0.02x1 +0.025x2 ≥ (0.018)(2000) 0.02x1 +0.025x2 ≤ (0.025)(2000) – Lastly, nickel: 0.01x1 + 0.015x2 ≥ 18 0.01x1 + 0.015x2 ≤ 24 – Tensile strength: 42, 000x1 + 50, 000x2 ≥ 45, 000 2, 000 – Relationship between variables: x1 + x2 = 2000 – Non-negative: x1,2 ≥ 0. 18. An interesting application of “blending”- The solution is attached on the last page (a little lengthy to get it set up). (c) Exercise 22, Chapter 3 review. Hint: Consider using a triple index on your variables. SOLUTION: Let xijk is the units of product 1, machine i, month j, for sale in month k. Let yijk is the units of product 2, machine i, month j, for sale in month k. In order to simplify things, we note some quantities that are useful: • • • • Amount Amount Amount Amount of of of of Product Product Product Product 1 2 1 2 for for for for sale sale sale sale in in in in Month Month Month Month 1: 1: 2: 2: x111 + x211 y111 + y211 x112 + x212 + x122 + x222 y112 + y212 + y122 + y222 Then we have the objective function to maximize: 55(x111 +x211 )+12(x112 +x212 +x122 +x222 )+65(y111 +y211 )+32(y112 +y212 +y122 +y222 ) For constraints, here are Machine 1 hour constraints (for Months 1, 2): 4(x111 + x112 ) + 7(y111 + y112 ) ≤ 500 4x122 + 7y122 ≤ 500 Similarly, for Machine 2: 3(x211 + x212 ) + 4(y211 + y212 ) ≤ 500 3x222 + 4y122 ≤ 500 Sales constraints (Month 1, then Month 2): x111 + x211 ≤ 100 x112 + x212 + x122 + x222 ≤ 190 y111 + y211 ≤ 140 y112 + y212 + y122 + y222 ≤ 130 Also, all variables are non-negative. (d) Exercise 47, Ch 3 Review: To get started, we might take xij = Number of workers getting i and j off, i < j where Sunday is Day 1, Monday is Day 2, etc. We want to optimize the number of workers having consecutive days off: max z = x12 + x17 + x23 + x34 + x45 + x56 + x67 subject to the day constraints (see the back of the text). 2 (e) Exercise 12, Ch 4 Review (Set up the LP just for “set 1”, and do not solve) SOLUTION: First the variables- Let xi be the number of product i produced. Going off Table 70, we see the resource constraints (before anything extra is paid for): 1.5x1 + 3x2 + 2x3 ≤ 900 Labor 2x1 + 3x2 + 4x3 ≤ 1600 Lumber 3x1 + 2x2 + 2x3 ≤ 1550 Paint Let si be the left over amount of labor, lumber, or paint (respectively) we’ll have and ei be the amount of labor, lumber, or paint that is beyond our available resources that we have to purchase. Then the constraints change, and rearranging the constraints to match our priorities, 1.5x1 + 3x2 + 2x3 + s1 − e1 = 900 3x1 + 2x2 + 2x3 + s3 − e3 = 1550 2x1 + 3x2 + 4x3 + s2 − e2 = 1600 Labor Paint Lumber Now that these excess variables are available, we can write our “profit” constraint (we’ll use s4 , e4 for our new constraint) (26 − 10)x1 + (28 − 6)x2 + (31 − 7)x3 − 6e1 − 3e2 − 2e3 + s4 − e4 = 10500 Now for our priorities: Using Pi , we initially want to maximize P1 e4 to get at least 10500 profit, then minimize additional labor, P2 e1 , then minimize additional paint, P3 e3 , then minimize additional lumber, P4 e2 . (f) Exercise 17, Ch 4 Review. Given the table (Table 74) below, and assuming we started with a maximization problem, x1 x2 x3 x4 x5 rhs −c 2 0 0 0 10 −1 a1 1 0 0 4 1 a2 −4 0 1 0 a3 3 0 0 1 b i. What conditions on the constants would make the current solution optimal? SOLUTION: Make c ≤ 0 and b ≥ 0. ii. What conditions on the constants would make the current solution optimal, with alternate optimal solutions? SOLUTION: Make c = 0 and b ≥ 0. Furthermore, we would need to be able to pivot into Column 1, so that one or both of a2 , a3 would need to be greater than 0 so that we can successfully complete the pivot. iii. What conditions on the constants would make the current tableau represent an unbounded solution (assume b ≥ 0). SOLUTION: If c > 0 and we cannot pivot (meaning a2 ≤ 0 and a3 ≤ 0), then the LP is unbounded. (g) Exercise 2, Section 4.16: 3 Let xi be the number of lots purchased from supplier i. The objective function for the goal programming problem would be: min z = 10s1 + 6s2 + 4s3 + e4 Given the constraints (or now goals): 60x1 + 50x2 + 40x3 + s1 − e1 20x1 + 35x2 + 20x3 + s2 − e2 20x1 + 15x2 + 40x3 + s3 − e3 400x1 + 300x2 + 250x3 + s4 − e4 = 5000 = 3000 = 1000 = 28000 where all variables are non-negative. In terms of your initial tableau, we would have: rhs x1 x2 x3 s1 e1 s2 e2 s3 e3 s4 e4 0 0 0 10 0 6 0 4 0 0 1 0 60 50 40 1 −1 0 0 0 0 0 0 5000 20 35 20 0 0 1 −1 0 0 0 0 3000 20 15 40 0 0 0 0 1 −1 0 0 1000 400 300 250 0 0 0 0 0 0 1 −1 28000 (h) Section 4.16, 4(a): The objective function would be: min z = s1 + 2e1 + 5s2 + 5s3 + s4 Given the constraints: 4x1 + 2x2 + s1 − e1 x1 + s 2 − e 2 x2 + s 3 − e 3 4x1 + 2x2 + s4 − e4 = 32 Labor constraint = 7 Product 1 constraint = 10 Product 2 constraint = 48 Profit constraint All variables are non-negative. 4. Convert the following LP to one in standard form. Write the result in matrix-vector form, giving x, c, A, b (from our formulation). min z = 3x − 4y + 2z st 2x − 4y ≥ 4 x + z ≥ −5 y+z ≤1 x+y+z =3 with x ≥ 0, y is URS, z ≥ 0. SOLUTUION: Let x = [x, y + , y − , z, e1 , s1 , s2 ]T . Then  2 −4 4 0 −1 0 0  −1 0 0 −1 0 1 0 c = [3, −4, 4, 2, 0, 0, 0]T A=  0 1 −1 1 0 0 1 1 1 −1 1 0 0 0 4       4  5   b=  1  3 5. Suppose the BFS for an optimal tableau is degenerate and a NBV in Row 0 has a zero coefficient. Show by example that either of the following could occur: • The LP has more than one optimal solution. SOLUTION: Multiple ways of answering. In the tableau below, we can still pivot into Column 3 to get a new solution. 0 0 0 1 5 1 0 1 1 3 0 1 2 1 1 • The LP has a unique optimal solution. SOLUTION: Changing the tableau above, we just need to make sure we cannot pivot into Col 3. For example, 0 0 0 1 5 1 0 −1 1 3 0 1 −2 1 1 6. Consider again the “Wyndoor” company example we looked at in class: min z = 3x1 + 5x2 st x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 with x1 , x2 both non-negative. (a) Rewrite so that it is in standard form. SOLUTION: Define the extra variables x3 , x4 , x5 . Using the extra variables in order, the constraints become: x1 + x3 2x2 + 3x1 + 2x2 + x4 x5 =4 = 12 = 18 And from this, it is easy to read off the coefficient matrix A. (b) Let s1 , s2 , s3 be the extra variables introduced in the last answer. Is the following a basic solution? Is it a basic feasible solution? x1 = 0, x2 = 6, s1 = 4, s2 = 0, s3 = 6 Which variables are BV, and which are NBV? SOLUTION: The matrix A has rank 3. If the solution has n − m = 5 − 3 = 2 zeros (and it is a solution), then it is a basic solution: Yes, this is a basic solution. It is also a basic feasible solution since every entry of the basic solution is non-negative. The variables x2 , x3 and x5 are the basic variables (BV) and the variables x1 and x4 are NBV. 5 (c) Find the basic feasible solution obtained by taking s1 , s3 as the non-basic variables. In this case, we can row reduce the augmented matrix (remove columns 3 and 5 from the original):     1 0 0 4 1 0 0 4  0 2 1 12  −→  0 1 0 3  3 2 0 18 0 0 1 6 In this case, we have the (full) solution: x1 = 4, x2 = 3, x3 = 0, x4 = 6, x5 = 0 7. Draw the feasible set corresponding to the following inequalities: x1 + x2 ≤ 6, x1 − x2 ≤ 2 x1 ≤ 3, x2 ≤ 6 with x1 , x2 non-negative. Figure 1: Figure for Question 10 (a) Find the set of extreme points. SOLUTION: (0, 0), (0, 6), (2, 0), (3, 3), (3, 1). (b) Write the vector [1, 1]T as a convex combination of the extreme points. SOLUTION: Since I get to choose, let’s make it easy:             1 3 2 0 2 3 1 0 = + +0 +0 +0 6 0 1 1 3 3 3 0 Or, a little more complex:             1 0 1 2 1 0 1 3 3 + + +0 +0 = 1 3 1 6 6 2 0 3 0 (c) True or False: The extreme points of the region can be found by making exactly two of the constraints binding, then solve. SOLUTION: If we follow this recipe, we will get extreme points, but we’ll also get non-feasible points (for example, the point (3, 6)). Therefore, FALSE. 6 (d) If the objective function is to maximize 2x1 + x2 , then (a) how might I change that into a minimization problem, and (b) solve it. SOLUTION: For part (a), we convert it by minimizing −z, or min −2x1 − x2 . For part (b), solve it graphically to get that the maximum occurs at (3, 3) and the maximum is 9. 8. Consider the unbounded feasible region defined by x1 − 2x2 ≤ 4, −x1 + x2 ≤ 3 with x1 , x2 non-negative. Consider the vector p = [5, 2]. (a) Show that p is in the feasible region. SOLUTION: Substitute the values into the constraints to see that they are both valid. (b) Set up the system you would solve in order to write p in the form given in Theorem 2 (provide a specific vector d). NOTE: Sorry about the vagueness of the question... It is not clear what is being asked here. Go ahead and write the representation using two dimensions, then try to convert those to the four dimensional representation by writing the appropriate equations. SOLUTION: Directions of unboundedness can have “slopes” between 1/2 and 1, so we could choose d = [1, 1]T (so the vector has slope 1). We can construct the line through (5, 2) with slope 1 (which is y = x − 3) and see where it connects with the convex hull of the extreme points. We note that y = x − 3 intersects the line segment between (0, 0) and (4, 0) at the point (3, 0), so we can now write       5 3 2 = + 2 0 2 where we’ll take (2, 2) as the direction of unboundedness. As we noted before, (3, 0) is a convex combination of (0, 0) and (4, 0): 3 1 (3, 0) = (0, 0) + (4, 0) 4 4 Therefore, in column vector format (you can do it either way):         1 0 3 4 2 5 = + + 0 0 2 2 4 4 Now, to put these vectors in the right dimension for Theorem 2, we need to write our constraints as Ax = b, or x1 − 2x2 + s1 = 4 −x1 + x2 + s2 = 3 7 The points (0, 0), (4, 0), and (5, 2) are all feasible, so we use the basic equations above to solve for s1 , s2 :       0 4 5  0   0   2   ,  ,    4   0   5  3 7 6 For the direction of unboundedness (2, 2), we set the equations to zero:   2  x1 − 2x2 + s1 = 0 2   ⇒   4  −x1 + x2 + s2 = 0 0 And we can verify these:    0 5  2  1 0  =   5  4 4 3 6     4 2  3 0   2 +  +  4 0   4 7 0     9. Consider Figure 2, with points A(1, 1), B(1, 4) and C(6, 3), D(4, 2) and E(4, 3). Figure 2: Figure for the convex combinations, Exercise 9. • Write the point E as a convex combination of points A, B and C. SOLUTION: First we’ll find the point
of intersection between line AE and BC. 58 43 Call it E 0 . We found it to be E 0 13 , 13 (Sorry about the fractions!). By the time we’re done, you should have:          13 4 1 9 6 2 1 4 = + + 3 15 1 15 13 4 13 3 • Can E be written as a convex combination of A, B and D? If so, construct it. SOLUTION: No. The point E is above the convex hull of A, B and D (which is the triangle whose vertices are at A, B, D). 8 • Can A be written as a linear combination of A, B and D? If so, construct it. SOLUTION: Obvious typo there- I meant to say E can be written ... Using E, we can set up the matrix and solve:   1 1 4 4 ⇒ 1 4 3 2 If the coefficients for the linear combination are c1 , c2 , c3 , we find them to be: C1 = 14 − 13 C 3 3 3 C2 = − 23 + 13 C3 C3 = C3 Therefore, there are an infinite number of ways to make this linear combination (which was expected, since three vectors in IR2 are not linearly independent). 10. Finish the definition: Two basic feasible solutions are said to be adjacent if: SOLUTION: Two basic feasible solutions are adjacent if they share all but one basic variable. 11. Let d be a direction of unboundedness. Using the definition, prove that this means that rd is also a direction of unboundedness, for any constant r ≥ 0. SOLUTION: We assume an LP in standard form, so our set S = {x|Ax = b}. Then, d 6= 0 is a direction of unboundedness for S if x + λd ∈ S for all x ∈ S and λ ≥ 0. Therefore, in what is given, we can let u = rd and show that u is a direction of unboundedness: Let x be any point of S and λ ≥ 0. Then: x + λu = x + (λr) d which must be in S since d was a direction of unboundedness. 12. If C is a convex set, then d 6= 0 is a direction of unboundedness for C iff x + d ∈ C for all x ∈ C (Use the definition of unboundedness). SOLUTION: We have two directions• d 6= 0 is a direction of unboundedness for C implies x + d ∈ C is trivially true, since we can just make λ = 1. • We now show that, if x+d ∈ C for all x ∈ C, then d is a direction of unboundedness for C: Let x0 be any point in S, and λ ≥ 0. Then show that x0 + λd ∈ S. Let λ = N + α, where N is a non-negative integer, and 0 ≤ α < 1. Then x0 + λd = x0 + (N + α)d = (x0 + d) + ((N − 1) + α)d Now, since x1 = x0 + d, then x1 ∈ C, we can write this as: x1 + d + ((N − 2) + α)d and so on. Therefore, we have that x0 + N d ∈ S Finally, since x0 + N d + d ∈ C, then because C is convex, so will the vector x0 + N d + αd ∈ C. 9 13. For an LP in standard form (see above), prove that the vector d is a direction of unboundedness iff Ad = 0 and d ≥ 0. Solution: • Show that if Ad = 0, with d ≥ 0, then d is a direction of unboundedness. Note that this means we have to show that y = x + λd ∈ S for every λ. Let x be in the feasible set, x ∈ S so that x ≥ 0. Now, Ay = A (x + λd) = Ax + λAd = b + 0 = b Wait! We’re not done- Check that y ≥ 0 (it is since λ, x, d ≥ 0). • Now go in the reverse: Suppose that we know that d is a direction of unboundedness. We show that Ad = 0 and d ≥ 0. Let x be in the feasible set. One path we could take is to suppose that, by way of contradiction, that Ad 6= 0. Then A (x + λd) = Ax + λAd = b + λk 6= b But then x + λd is not an element of S (contradiction). The other part: Is d ≥ 0? If not, then at least one coordinate di < 0. But then it is possible to find λ so that the ith coordinate of x + λd is negative (contradiction). 14. Show that the set of optimal solutions to an LP (assume in standard form) is convex.  SOLUTION: Define S = x|Ax = b, cT x = L Now, let y1 , y2 ∈ S. We show that all points on the line segment between them is also in S. Let y be a point between- Then there is a 0 ≤ t ≤ 1 so that: y = ty1 + (1 − t)y2 Now, y is also feasible, since Ay = tAy1 + (1 − t)Ay2 = tb + (1 − t)b = b And y will give the same optimal value, cT y = tcT y1 + (1 − t)cT y2 = tL + (1 − t)L = L 15. Let a feasible region be defined by the system of inequalities below: −x1 + 2x2 ≤ 6 −x1 + x2 ≤ 2 x2 ≥ 1 x1 , x2 ≥ 0 The point (4, 3) is in the feasible region. Find vectors d and b1 , · · · bk and constants σi so that the Representation Theorem is satisfied (NOTE: Your vector x from that theorem is more than two dimensional). 10 SOLUTION: Graphing the region in 2-d, we see that the extreme points are:       0 0 2 b1 = , b2 = , b3 = 1 2 4 And d can be any vector pointing outwards with a slope between 0 and 1/2. The easiest method to get the representation is to “aim backwards” at an extreme point, but using a vector that will be an allowable d. In this case, we can write:       0 4 4 = + 3 2 1 where the vector (4, 1) has slope 1/4, so it is allowable. To write our system in 5 dimensions, we go back to the standard form: −x1 + 2x2 + s1 = 6 −x1 + x2 + s2 = 2 x2 − e 1 = 1 so that, given x1 , x2 , we can compute the other variables- for vectors that are feasible. For vectors that are in the direction of unboundedness, remember to rewrite the equations replacing (6, 2, 1) by (0, 0, 0). Therefore,       4 0 4  3   2   1         4 = 2 + 2         3   0   3  2 1 1 16. Let a feasible region be defined by the system of inequalities below: −x1 + x2 ≤ 2 x1 − x 2 ≤ 1 x1 + x2 ≤ 5 x1 , x2 ≥ 0 The point (2, 2) is in the feasible region. Find vectors d and b1 , · · · bk and constants σi so that the Representation Theorem is satisfied (NOTE: Your vector x from that theorem is more than two dimensional). SOLUTION: The point given is between two extreme points, [0, 2]T and [3, 2]T . Therefore, in two dimensions we have       1 2 0 3 =t + (1 − t) ⇒ t= 2 2 2 3 11 We also get the matrix A in standard form, with column variables (in order): x1 , x2 , s1 , s2 , s3 , and   −1 1 1 0 0 s 1 = x1 − x2 + 2 s2 = −x1 + x2 + 1 A =  1 −1 0 1 0  ⇒ 1 1 0 0 1 s3 = −x1 − x2 + 5 From which we get:       2 2 2 1 1      1 =   3   0 2 0 3 3      2 +   3   3 2 3 0 0       17. True or False, and explain: The Simplex Method will always choose a basic feasible solution that is adjacent to the current BFS. SOLUTION: That is true. It is because we will only replace one of the current basic variables with a new variable, therefore, the new BFS will keep all but one of the current set of basic variables. 18. Given the current tableau (with variables labeled above the respective columns), answer the questions below. x1 x2 s 1 s2 rhs 0 −1 0 2 24 0 1/3 1 −1/3 1 1 2/3 0 1/3 4 (a) Is the tableau optimal (and did your answer depend on whether we are maximizing or minimizing)? For the remaining questions, you may assume we are maximizing. ANSWER: This tableau is not optimal for either. If we were minimizing, we could still pivot using s2 . If we were maximizing, we could still pivot in x2 . (b) Give the current BFS. ANSWER: The current BFS is x1 = 4, x2 = 0, s1 = 1 and s2 = 0. (c) Directly from the tableau, can I increase x2 from 0 to 1 and remain feasible? Can I increase it to 4? ANSWER: From the ratio test, x2 can be increased to 3 in the first, and 6 in the second. However, increasing it to 4 would violate the first constraint. Summary: I can increase x2 from 0 to 1, but not to 4. (d) If x2 is increased from 0 to 1, compute the new value of z, x1 , s1 (assuming s2 stays zero). SOLUTION: 2 10 s1 = z = 25 x1 = 3 3 (e) Write the objective function and all variables in terms of the non-basic (or free) variables, and then put them in vector form. 12 SOLUTION: For the current tableau, z = 24 + x2 − 2s2 , with       x1 = 4 − 2/3x2 − 1/3s2 4 −2 −1  0  x2  1  s 2  0  x2 = x2      ⇒ x=  1  + 3  −1  + 3  1  s1 = 1 − 1/3x2 + 1/3s2 s2 = s2 0 0 0 19. Solve first using big-M, then repeat using the two-phase method. max z = 5x1 −x2 st 2x1 +x2 x1 +x2 x2 x1 , x2 =6 ≤4 ≤3 ≥0 SOLUTION: This is Exercise 3 from the Chapter 4 Review. Below we’ll list the initial tableau, the end of Phase I, and the final tableau. There will be two Row 0’s (the top one for the Big-M, the second one for two-phase): x1 x2 s1 s2 a1 rhs −5 1 0 0 M 0 0 0 0 0 1 0 2 1 0 0 1 6 1 1 1 0 0 4 5 1 2 0 1 0 x1 0 0 1 0 0 ⇒ x2 s 1 s 2 a1 rhs 7/2 0 0 5/2 + M 15 0 0 0 1 0 1/2 0 0 1/2 3 1/2 1 0 −1/2 1 2 3/2 0 1 −1/2 On the left, we re-write the Row 0 to start Phase Two, and the left is what we get after making x1 basic again. x1 0 −5 1 0 0 x2 s 1 s 2 a1 rhs 7/2 0 0 5/2 + M 15 0 1 0 0 1 1/2 0 0 1/2 3 1 1/2 1 0 −1/2 2 3/2 0 1 −1/2 ⇒ x1 0 0 1 0 0 x2 s 1 s 2 a1 rhs 7/2 0 0 5/2 + M 15 7/2 0 0 7/2 15 1/2 0 0 1/2 3 1 1/2 1 0 −1/2 2 3/2 0 1 −1/2 In both cases, we have a unique optimal solution: x1 = 3, x2 = 0, with z = 15. 20. Using the big-M method on a maximization problem, I got the following tableau: x3 a1 a2 x1 x2 x3 s1 e1 e2 a1 a2 rhs −1/2 + 2M −5/2 + M M 1/2 + M M M 0 0 2 − 3M 1/2 1/2 1 1/2 0 0 0 0 2 −3/2 −1/2 0 −1/2 −1 0 1 0 2 −1/2 −1/2 0 −1/2 0 −1 0 1 1 Should I stop or should I go? If I stop, what should I conclude? SOLUTION: Stop- Remember that M is a very large positive number, so there is nowhere left to pivot. Because the artificial variable is still a basic variable, that means the original feasible set is empty (no solution to the original problem). 13 21. Here’s a tableau that we’ve obtained from using the Simplex Method. Answer the questions below about it. x1 x2 x3 s1 s2 s3 rhs 1 0 0 0 3 −2 50 4 0 0 1 −1 0 5 1 1 0 0 1 −2 10 0 0 1 0 1 −1 15 (a) Is this tableau terminal (has the Simplex Method stopped)? If so, interpret the solution shown. If not, continue until you stop. SOLUTION: Yes, this is a terminal solution. The LP is unbounded. (b) Write down the system of equations that this tableau represents (be sure to write BVs in terms of NBVs). SOLUTION: The basic variables are x2 , x3 and s1 . x1 x2 x3 s1 s2 s3 = x1 = 10 −x1 −s2 +2s3 = 15 −s2 +s3 = 5 −4x1 +s2 = s2 = s3 The objective function is given by: z = 50 − x1 − 3s2 + 2s3 . (c) Given the tableau shown, the current basic variables are s1 , x2 , x3 . Is it possible that the previous set of basic variables were: s1 , s2 , x3 ? To see, compute the previous Row 0. (Hint: You want to replace or substitute x2 with s2 as basic). SOLUTION: In replacing x2 with s2 , we can use the second equation, and switch them: s2 = 10 − x1 − x2 + 2s3 The new objective function would then be: z = 50 − x1 − 3(10 − x1 − x2 + 2s3 ) + 2s3 = 20 + 2x1 + 3x2 − 4s3 Therefore, the previous Row 0 would have been: [−2 − 3 0 0 0 − 4], so yes, that is a possibility. 14