Linear Programming Class Notes 2016

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. 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, 1 Recall that a critical point of f is where Ax2 ≤ b f 0 (x) 3 = 0 or where f 0 (x) does not exist Given that x = tx1 + (1 − t)x2 , 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} 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) 4 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. Is it possible that the solution to the LP problem is not unique? Yes- Consider our very first example. Suppose now that the isclines of f have the same slope as the hypotenuse of the triangle. Then the function has a maximum at every point of the hypotenuse that lies in the feasible region. For two dimensional problems, we will focus on our geometric technique for finding the max/min- Draw the feasible set, then draw isoclines of f . 3 Drawing the Feasible Set Maple has a nice feature that allows us to draw the feasible set for a two dimensional problem. We’ll use inequal from the plots library (that is, type with(plots): before using inequal). Here’s an example: >> with(plots): >> inequal( { x+y>=1/2, x-y<=1,y<=2,x>=0,y>=0}, x=-3..3, y=-3..3, optionsfeasible=(color=yellow), optionsexcluded=(color=white) ); 4 Matlab’s Optimization Toolbox We can solve higher dimensional problems using Matlab’s optimization toolbox. The relevant command is linprog. The function linprog solves the following general problem: cT x min x (2) such that: Ax ≤ b Aeq x = beq Optional Argument lb ≤ x ≤ ub Optional Argument We will call linprog one of several ways, depending on what we want to input, and what we want to output. Here’s a basic example: 5 4.1 Worked Example You have $60,000.00 to invest in Certificates of Deposit (CDs) and mutual funds. The CDs pay an annual yield of 5%. The mutual funds pay an annual yield of 9%, with a minimum investment of $10,000.00. As a safety net, you decide that you need to put in at least twice as much into CDs as mutual funds. How much should you invest in each in order to maximize your annual yield? SOLUTION: First, our variables: Let x1 be the amount we invest in CDs, and let x2 be the amount in mutual funds. We want to maximize our annual yield, which is 0.05x1 + 0.09x2 . We have the following constraints, taken as they appear in the description: • x1 + x2 ≤ 60000 • x2 ≥ 10000 • x1 ≥ 2x2 We of course need x1 , x2 to be non-negative. This gives the following LP problem: max 0.05x1 + 0.09x2 such that Ax ≤ b, where x1 ,x2    A=    1 1 0 −1   −1 2   −1 0  0 −1    b=   60000 −10000 0 0 0       And in Matlab: >> >> >> >> A=[1 1;0 -1;-1 2;-1 0;0 -1]; b=[60000;-10000;0;0;0]; c=[-0.05 -0.09]; [f,fopt]=linprog(c,A,b) The output argument f will return the minimizer (the value of the domain where the minimum occurs). The argument fopt will return the value of the minimum. The solution is $40,000 for CDs, $20,000 for mutual funds, and we get a maximum annual yield of $3800.00 We can also determine which of the inequalities were “tight” and which were not. If f is the minimizer, then Af gives the values of the constraints at the minimizer- Compute Af and see which values occurred at the boundary, and which were in the interior. In this case, we should see that the first and third constraints were tight, but the second was not. 6 4.2 Other Matlab Arguments The full linprog command, with most of the options is: [f,fopt,exitflag,output]=linprog(c,A,b,Aeq,beq,LB,UB) The inputs were described in our general equation 2. The outputs are: • f is the minimizer. • f opt is the value of the minimum. • exitflag is an integer describing why Matlab terminated the program (See help linprog for a description). • output is a Matlab structure with the details for how Matlab arrived at the solution. We don’t need to specify all the input arguments. For example, another way to set up our example problem would be to separate the non-negative constraints on the decision variables so that:     1 1 60000 A =  0 −1  b =  −10000  −1 2 0 and set lb=[0;0];. Call Matlab: [f,fopt,exitflag,options]=linprog(c,A,b,[],[],lb); In this case, exitflag= 1, which means that the program terminated normally at a solution. The options structure says that it took 5 iterations to come to the solution. 5 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 , 7 i 6= j Figure 2: The shaded region is the feasible region. This is for Question 6. 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. In Figure 2, how many vertices are there? How many are actually feasible? How many variables would be in the objective function? How many constraints? 8 5. First, solve the problem below by graphing the feasible region by hand or using Maple, then draw in several isoclines of the objective function. Verify your solution using Matlab: A dog breeder feeds her dogs a combination of two types of food, A and B. She is concerned that her dogs require a certain combination of 4 nutritional factors, a, b, c, d each month. The chart below shows the amount of each factor per bag of food, together with the minimum nutritional requirements: a b c d A 3 2 1 2 B 2 4 3 1 Min Req 28 30 20 25 The costs per bag are $50.00 for A, $40.00 for B. How many bags of each type of dog food should she blend to get the minimum monthly nutritional requirements, and minimize her cost? At the minimum, which constraints are tight, and which are not? 6. First, solve the problem below by graphing the feasible region by hand or using Maple, then draw in several isoclines of the objective function. Verify your solution using Matlab: Its time to reinvest some maturing funds. You have $55000.00 to invest in Doug’s fund and Mary’s fund. Doug’s fund is cheaper at $200.00 per note with an expected return of 9%. Mary’s fund has a buy in of $300.00 per note with an expected return of 15%. However, Mary’s fund is riskier than Doug’s fund- For diversification of your portfolio, you want to buy at least twice as much into Doug’s fund as Mary’s. There are currently 200 notes available for Doug’s fund and 100 notes for Mary’s fund. How much of each should you buy? 7. First, solve the problem below by graphing the feasible region by hand or using Maple, then draw in several isoclines of the objective function. Verify your solution using Matlab: Shady Lane Grass Seed Company sells two brands, Evergreen and QuickGreen in its grass seed business. Each bag contains certain combinations of Fescue, Rye and Bluegrass seed, as summarized in the table (in pounds per bag), as well as the total number of pounds of each type of grass seed that the company normally stocks: Evergreen QuickGreen Total Avail Fescue 3 2 1200 9 Rye 1 2 800 Bluegrass 1 1 450 If the company can sell Evergreen for $2.00 of profit per bag, and $3.00 of profit on QuickGreen, how many bags of each should the company produce to maximize its profit? 8. The following is not strictly a linear programming problem, but we will use the following when we use a linear program to find a line of best fit. Definition: Let x be a vector in IRn . The p−norm for x is defined as: 1/p kxkp = (|x1 |p + |x2 |p + . . . |xn |p ) (a) Find the 2−, 3−, and 10−norms of x = [3, −1]T . Guess at what the norm is as p → ∞. (b) If x ∈ IR2 , use Maple to plot the set of points where kxkp = 1 for p = 1, 2, 3 and 10. What do you notice about the shapes of these (closed) neighborhoods about the origin? What will the shape be as p → ∞? Compare your answer with the following definition of the ∞ norm: kxk∞ = max |xi | i 10