Differential Equations Exam 1 Review

Review Material, Exam 1, Ops Research The exam will cover material from Chapter 3 (we skipped 3.6, 3.7), up through section 4.8. Section 4.9 may be used to help with LINDO, and we skipped 4.10, but we did look at 4.11 (degeneracy). Background Material: Linear Algebra Though these may not be asked explicitly, you should be able to do the following (and may be part of solutions): 1. Be able to solve Ax = b for different types of matrices (if A is square and invertible, and if it is tall and full rank, tall and not full rank, wide and full rank, wide and not full rank). 2. Be able to discuss the solution to Ax = b in terms of the row space, the column space and the null space of A. 3. Be able to compute the determinant and inverse of a matrix A 4. Note that our book uses “ERO” for elementary row operation. 5. Define what it means for a set of vectors to be linearly independent. 6. Be able to solve for a basis for the row space, column space and null space for a given matrix A. Definitions: Linear program, standard form of a linear program, objective function, constraints (binding and non-binding), extreme point, isoprofit line, feasible region, unrestricted variable (URS), BFS, adjacent BFS, slack/surplus (or excess) variables, basic solution, BFS, BV, NBV, direction of unboundedness, Convex set, convex combination. The word “degenerate” is used in two distinct cases: See the top of p. 134 for what it means for a linear program to be degenerate. In class, we said that a BFS is degenerate if one of the basic variables (for the optimal solution) is zero. Skills 1. Translate unrestricted variables so that all variables are non-negative. 2. Be able to show that a given set is convex, use convexity in other arguments (See review questions below for examples). 3. Be able to set up and solve an LP graphically. Given the objective function, be able to state the direction in which the function increases (or decreases) the fastest. 4. Be able to set up an LP generally, and of specific types: A diet problem, a work scheduling problem, a production process model, blending, and multiperiod problems (like the sailboat example). 5. Be able to translate a LP into standard form given “less than or equal to” constraints, “greater than or equal to” constraints, and change the variables so that they are all non-negative. 6. Be able to write the simplex tableau from the linear program (for both a maximization and a minimization problem). 7. Be able to solve a linear program (a maximization problem with “less than or equal to” constraints) using the Simplex Method. 8. Given a tableau, be able to tell if it is a terminal tableau, and interpret what the solution is (unique, multiple, unbounded). 9. (For something that might be take home) Be able to use either LINGO or a spreadsheet program to solve an LP. 1 Theorems: • Theorem 1 says that extreme points are the same BFS (and are the same as corner points). • Theorem 2: The Representation Theorem Says that any feasible point can be written as d+ N X σi bi i=1 where d is a direction of unboundedness and the sum is a convex combination of the corner points of the feasible set. • Theorem 3: The Fundamental Theorem of Linear Programming If an LP has an optimal solution, then it has an optimal BFS (or corner point, or extreme point). Review Questions 1. What are the four possible outcomes when solving a linear program? Hint: The first is that there is a unique solution to the LP. 2. The following are to be sure you understand the process of constructing a linear program: (a) Draw a production process diagram and set up the LP for Exercise 6, p. 98 (Sect. 3.9). (b) Exercise 2, 31 Chapter 3 review (Be sure you can solve an LP graphically) (c) Exercise 6, 18 Chapter 3 review (A ton is 2000 lbs) (d) Exercise 22, Chapter 3 review. Hint: Consider using a triple index on your variables. (e) Exercise 47, 53 in Chapter 3 review. 3. 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. 4. Consider again the “Wyndoor” company example we looked at in class: min z = st 3x1 + 5x2 x1 ≤ 4 2x2 ≤ 12 3x1 + 2x2 ≤ 18 with x1 , x2 both non-negative. (a) Rewrite so that it is in standard form. (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? (c) Find the basic feasible solution obtained by taking s1 , s3 as the non-basic variables. 5. Consider Figure 1, with points A(1, 1), B(1, 4) and C(6, 3), D(4, 2) and E(4, 3). 2 Figure 1: Figure for the convex combinations, Exercise 6. • Write the point E as a convex combination of points A, B and C. • Can E be written as a convex combination of A, B and D? If so, construct it. • Can A be written as a linear combination of A, B and D? If so, construct it. 6. Draw the feasible set corresponding to the following inequalities: x1 + x2 ≤ 6, x1 − x2 ≤ 2 x1 ≤ 3, x2 ≤ 6 with x1 , x2 non-negative. (a) Find the set of extreme points. (b) Write the vector [1, 1]T as a convex combination of the extreme points. (c) True or False: The extreme points of the region can be found by making exactly two of the constraints binding, then solve. (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. 7. 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. (b) Set up the system you would solve in order to write p in the form given in Theorem 2 above (provide a specific vector d). 8. Finish the definition: Two basic feasible solutions are said to be adjacent if: 9. 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. 10. 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). 11. For an LP in standard form (see above), prove that the vector d is a direction of unboundedness iff Ad = 0 and d ≥ 0. 12. Show that the set of optimal solutions to an LP (assume in standard form) is convex. 13. Let a feasible region be defined by the system of inequalities below: −x1 + 2x2 −x1 + x2 x2 x1 , x2 ≥ 0 ≤6 ≤2 ≥1 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). 3 14. Let a feasible region be defined by the system of inequalities below: −x1 + x2 x1 − x2 x1 + x2 x1 , x2 ≥ 0 ≤2 ≤1 ≤5 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). 15. Suppose that λ1 ≤ λ2 ≤ · · · λn , and let σ1 , · · · , σn be non-negative constants so that n X σi = 1. Show i=1 that λ1 ≤ σ1 λ1 + σ2 λ2 + · · · σn λn ≤ λn 16. Show that, if x is in the convex hull of vectors b1 , · · · bk , then for any constant vector c,  cT x ≤ max cT bi i 17. True or False, and explain: The Simplex Method will always choose a basic feasible solution that is adjacent to the current BFS. 18. Given the current tableau (with variables labeled above the respective columns), answer the questions below. x1 x2 s1 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. (b) Give the current BFS. (c) Directly from the tableau, can I increase x2 from 0 to 1 and remain feasible? Can I increase it to 4? (d) If x2 is increased from 0 to 1, compute the new value of z, x1 , s1 (assuming s2 stays zero). (e) Write the objective function and all variables in terms of the non-basic (or free) variables, and then put them in vector form. 4