Linear Programming Class Notes 2003

Linear Programming Class Notes 1 A Quick Example Let f (x, y) = x + y. Find the maximum of f given that 5x + 3y ≤ 15 x ≥0 y ≥0 To solve this problem, we consider a graph of the set of points that satisfy all the constraints. In Figure 1, we see that the set of points that satisfy all the constraints (found by plotting 5x + 3y = 15, x = 0, y = 0) is a triangle. Now Figure 1: The set of all points that satisfy all of the constraints in our first example. This set is called the feasible set. consider a plot of x + y = k for different values of k. Then: 1. Any point on this line gives the same value for f (x, y) (which is k). 2. Increasing k means that we shift the line upwards. 3. To find the maximum, we shift up as high as we can with the condition that the line still intersects the triangle. In this case, it is easy to see that the maximum occurs at (0, 5) (which also gives k = 5). These are the types of problems we will consider in this chapter. 1 2 Theoretical Background A linear program (LP) is a problem of the form: Maximize (or Minimize) f (x) = T c1 x1 + c2 x2 + . . . + cn xn (or f (x) = c x) subject to the constraints that: a11 x1 a21 x1 .. . +a12 x2 +a22 x2 +... +... +a1n xn +a2n xn .. . ≤ b1 ≤ b2 .. . am1 x1 +am2 x2 + . . . +amn xn ≤ bn and xi ≥ 0 for all i. More compactly, we can write the constraints as Ax ≤ b. It is normal to simply assume all variables are positive, and not to include them in the system of equations, although this could be done. Some definitions: 1. The function f : Rn → R is called the objective function. 2. A point that satisfies all of the constraints is called a feasible solution. 3. The set of all points that satisfy all constraints is called the feasible set, or polytope. 4. Suppose we have x ∈ Rn . A vertex of the polytope is the intersection of n constraints. A vertex is a single point, and can be found by converting the n inequality constraints to n equalities (when this happens, the constraints are said to be tight). 5. An −neighborhood about a point a ∈ Rn is the set of points that have distance less than  to a: N (a) = {x | kx − ak2 < } 6. A point x is called an interior point of a set S if there exists an N (x) that is totally contained in S. 7. A point x is called a boundary point of a set S if any ball about x contains both points of S and points not in S. 8. A set S is Rn is said to be bounded if S can be completely contained within a ball with finite radius about the origin. 9. A set S is closed if it contains all of its boundary points. Class Exercise: From the last example, identify the feasible set, the set of boundary points, the set of interior points. Identify the vertices, and which constraints were tight to form each vertex. Class Exercise: In R, R2 and R3 , give examples of sets that are closed and not closed. Class Exercise: If x ∈ R3 , then each tight constraint is a plane which cuts 3-d into two regions. Given any three planes, do they necessarily define a vertex? 2 2.1 A Reminder of some Calculus Before continuing farther, let us put this material into context. Linear programming is an optimization problem, therefore the Extreme Value Theorem (EVT) of Calculus will come into play. In one dimension, y = f (x), the EVT says that: Let f be continuous on [a, b]. Then f attains a global maximum and a global minimum on [a, b]. This occurs at either (i) a critical point1 of f or (ii) at an endpoint. If f is a function of more than one variable, then we make the appropriate conversions: 1. The domain changes from an interval to a closed, bounded region. 2. Change f 0 (x) to the gradient of f 3. Change the endpoints to the boundary points. We are able to go even farther, since our function f is especially simple: If f (x1 , . . . , xn ) = c1 x1 + c2 x2 + . . . cn xn , then the gradient is just the vector c. Therefore, we won’t be considering the critical points of f - only the boundary points. We summarize this with the following theorem: Theorem: Let D = {x ∈ Rn | Ax ≤ b} be not empty, closed, and bounded. Then the LP problem has a solution, and that solution lies along the boundary of D. The boundary, ∂D, is contained within the set made up when each single inequality is changed to an equality. Then: ∂D ⊂ {x ∈ Rn | (Ax)i = bi , i = 1, 2, . . . , n} In our first example, the boundary was made up of a subset of the set of points where x = 0, y = 0, and 5x + 3y = 15. Notice that we cannot say that the boundary is made up of points from Ax = b, although that may be possible recall that the solution set to Ax = b has three possibilities. 2.2 The (Non-empty) Feasible Set is Convex Before continuing, you might recall the definition of a convex set: Let x1 and x2 be any two points of the set (in Rn ). Then any point on the line between, denoted: x = tx1 + (1 − t)x2 , 0 ≤ t ≤ 1 is also in the set. Figure 2 shows some shapes- determine visually which are convex and which are not. 1 Recall that a critical point of f is where f 0 (x) = 0 or where f 0 (x) does not exist 3 Let us show that D is convex, which follows from the linearity of Ax: We show that, if x1 and x2 are in D, then so is any point in between. Here we go: let x1 and x2 be in D. Then it follows that Ax1 ≤ b, Given that x = tx1 + (1 − t)x2 , Ax2 ≤ b 0 ≤ t ≤ 1, we show that Ax ≤ b: Ax = A(tx1 + (1 − t)x2 ) = tAx1 + (1 − t)Ax2 ≤ tb + (1 − t)b = b Therefore, for any two points in D, the line segment connecting them is also in D. Is it always possible to write a given point x ∈ D in terms of two other points; that is, as tx1 + (1 − t)x2 , where 0 < t < 1? If we restrict ourselves to the plane, you can convince yourself that just about every point can be written as point in between two others. But can a corner point (vertex) be written that way? No- See Exercises (1) and (2). Let l be any line passing through the convex set D. What kinds of line segments will be produced by intersecting l with D? We’ll have one of three choices: • A closed line segment • A ray. • All the points on l. The second two choices might occur if D is unbounded. If D is bounded, we will only have the first choice (see Exercise 5). Consider the maximization/minimization of f (x) = cT x restricted to the line l. To be more precise, let us take l as the line defined through two arbitrary (but fixed) points u and v, l = {x | x = tu + (1 − t)v, for some t ∈ R} Figure 2: Which of the sets are convex? 4 If we restrict the domain of f to the line l, we get (by substitution): f (x) = cT (tu + (1 − t)v) = t(cT u − cT v) + cT v (1) so that we can now write f (restricted to the line l) very simply as f (t) = mt + b for scalars m and b. Now it is a simple matter to describe where f has a maximum or minimumits graph is a line, so it is either strictly increasing (m > 0), strictly decreasing (m < 0), or it is a horizontal (m = 0). In all cases the maximum and minimum of f occur at the endpoints (if there are endpoints). In particular, this shows that if D is a bounded set made up of vertices and edges, the max/min of f must occur at a vertex. This is summarized by the following theorem: The Fundamental Theorem of Linear Programming. Given an LP problem with a nonempty, bounded feasible set D, the maximum and minimum of f occurs at a vertex in D. This gives us a new method for finding the optimal value of f - we could examine all of the edge intersections. In our first example, we can list them: (0, 0), (3, 0), (0, 5) The maximum value of x+y occurs at (0, 5). In the plane, these are combinations of two equations at a time. If we were in three dimensions, this would mean taking three equations at a time, and so on. To summarize, we have shown that the solution to the LP problem exists if D is not empty, closed and bounded. We have also shown that D is a convex set, and that the solution will be found at an intersection of two or more of the edges. Is it possible that the LP problem has no solution? Yes- it might be that all the constraints cannot be satisfied simultaneously, in which case D is the empty set. It might also happen that D is not bounded. Let’s consider a third technique for solving a linear programming problem. We illustrate this with the following example: Maximize 30x1 + 40x2 so that: x1 ≤ 90, x2 ≤ 60, 5x1 + 6x2 ≤ 600, xi ≥ 0 We will change the inequality constraints to equality constraints and we’ll ignore (for the time being) that all the variables are positive. We do this by introducing new variables, x3 , x4 , x5 ≥ 0 so that: x1 + 5x1 + x3 x2 + 6x2 + x4 x5 = 60 = 90 = 600 The new variables are called slack variables. To be feasible, any x must satisfy these equations. We have three equations in 5 unknowns, so we must have at 5 least 2 free variables. Solving this system using row reduction, we get:   1 0 0 −6/5 1/5 48  0 1 0 1 0 60  0 0 1 6/5 −1/5 42 From this, we can write the solution as: x1 x2 x3 x4 x5 6 = 5 x4 − = −x4 + = − 56 x4 + = x4 = 1 5 x5 + 48 60 1 5 x5 + 42 x5 or in vector form as:        x1 6/5 −1/5  x2   −1   0           x3  =  −6/5  x4 +  1/5  x5 +          x4   1   0   x5 0 1 48 60 42 0 0       SIDE REMARK: As a reminder, the solution of Ax = b can always be written as: x = xh + xp where xh ∈ Null(A) and xp is the particular part of the solution (it could be written in terms of the row space, but in our example its not). In this last example, the first two vectors form a basis for the nullspace of A. Returning now, substitution of our general solution back into f gives us:   6 1 f (x1 , x2 ) = 30x1 + 40x2 = 30 x4 − x5 + 48 + 40(−x4 + 60) 5 5 = −4x4 − 6x5 + 3840 Since x4 , x5 ≥ 0, the optimal value is 3840, given when x4 = x5 = 0 and x1 = 48, x2 = 60, x3 = 42. From this, we get that the optimal value is obtained at the intersection of x2 = 60 and 5x1 + 6x2 = 600, and x1 is 42 units (the value of x3 ) below its maximum of 90. In this example, we have also seen that slack variables and the free variables are different- slack variables may or may not be free variables. Does this always work? Consider the next example: EXAMPLE: Minimize f (x1 , x2 , x3 , x4 ) = x1 + 2x2 + 3x3 + 4x4 (xi ≥ 0) so that: x1 + x2 + x3 + x4 x1 + x3 − 3x4 6 =1 = 21 Straight Gaussian elimination as we did before gives x3 , x4 as free variables, and x1 = −x3 + 3x4 + x2 = −4x4 − 3 2 1 2 and substitution into f gives: 2x3 +5x4 + 52 , so that the minimum of 52 is achieved when x3 = x4 = 0. We have two problems here: x2 is no longer feasible (look at the equation for x2 again- remember that it must be nonnegative), and this is not the correct answer, which is 11 8 obtained from making x2 and x3 the free variables (and subsequently setting them to zero). What happened? The problem is that we are free to choose any two variables to be the free variables. That is, we can rearrange the columns of the matrix A and have an equivalent system of equations (we’re just rearranging the order in which they appear), but Gaussian elimination (without pivoting) chooses the variables in the order that they are given in the equation (in this example, we are forced to use x3 and x4 as free variables). In linear algebra, this was not an issue since the goal was to obtain any representation of the basis for the nullspace of A. Now we see what is at the heart of linear programming: We need to find the right combination of variables to be the free variables, and this list of free variables may or may not contain slack variables. Linear programming was constructed with real world problems in mindproblems that might involve thousands of variables. In such a case, graphical analysis is impossible, and the total number of intersections may be quite large. We will need a better, faster method to solve the problem- this will be the simplex method. This method has been programmed in most mathematical software packages like Maple and Matlab’s optimization toolbox, and works by trying to choose the right combination of variables to be the free variables. 3 The Simplex Method The Simplex algorithm works by using the vertices of the polytope. Given that we are currently on a feasible vertex, then we check the neighboring vertices and choose the one that increases the objective function. Sounds simple, but there are some difficulties in practical implementation. Here are a few things that can happen: 1. We have to find a feasible solution (if one exists). 2. We have to be able to determine if D is unbounded. 3. We have to find a feasible vertex (we could use a brute force technique and find all of them- but this may take a long time!). 4. Neighboring vertices might not be feasible. 5. If more than n tight constraints intersect at the same point, it is possible that the method will go into an infinite loop. 7 4 Exercises 1. Let D be the set of points satisfying some constraints, Ax ≤ b. Let R, S be two points interior to D so that they satisfy: Ax < b Show directly that, any point in between R and S must also satisfy the strict inequalities. This shows that any point in between two interior points is also interior. 2. Let D be as defined previously. Let R, S be two points in D that satisfy the equations: (Ax)j = bj , for some j (Ax)i < bi , i 6= j Show that, for any point in between R and S, it also must satisfy the same constraints- only one equality, the rest strict inequalities. This shows that a vertex (which satisfies at least two equality constraints) cannot be written as a point interior to two others. 3. True or False, and explain (for example, if false, provide a counterexample): (a) The following two sets are equal: • The set of points where at least one constraint is an equality. • The set of boundary points. (b) The following two sets are equal: Suppose we have n constraints • The set of all vertices. • The set of all solutions to n rows being equal (that is, all of the possible solutions to all of the possible n equality constraints). (c) It is possible that there are an infinite number of solutions to an LP problem. (d) The intersection of a line l with a set D constructed by the points Ax ≤ b could be two distinct line segments. 4. From Calculus, if f : Rn → R, and we are at a point in the domain a, which direction increases f the fastest? Show this by using a representation of the dot product, and refer to Equation 1. 5. Use the result from the previous section and the graph in Figure 1 to show which direction you should travel if you begin at the point (0, 1) and you want to increase the value of f . 6. In Figure 3, how many vertices are there? How many are actually feasible? How many variables would be in the objective function? How many constraints? 8 Figure 3: The shaded region is the feasible region. This is for Question 6. 9