Chapter 9 Linear Programming 9.1 Systems of Linear Inequalities 9.2 Linear Programming Involving Two Variables 9.3 The Simplex Method: Maximization 9.4 The Simplex Method: Minimization 9.5 The Simplex Method: Mixed Constraints 9.6 Homework 3 9.1 9.1 Systems of Linear Inequalities Linear inequalities ( ): For example, 3x 2y < 6 and x + y 6 are linear inequalit ies involving two variables Solution of an inequality: An ordered pair (a, b) is a solution of an inequality in x and y if the inequality is true when a and b are substituted for x and y, respectively
The graph of an inequality: The collection of all solutions of the inequality 9.2 Ex 1: Sketch the graph of the inequalities (a) x > 2 and (b) y 3 Sol: Step 1: Replace the inequality sign with an equal sign, and sketch the graph of the corresponding equation, e.g., x = 2 Step 2: Test one points in each of the regions separated by the corresponding equation in step 1. If the point satisfies the inequality, then shade the entire region to denote that every point in the region satisfies the inequality Notes: The corresponding equation separates the plane into two regions, and one of the following two statements is true
(1) All points in the region are solutions of inequality (2) No points in the region are solutions of the inequality 9.3 It is common to test the point of origin due to the least computational effort The solutions of x > 2 are points lying to the right of x = 2 (A dashed line is used for > or <) The solutions of y 3 are points lying below (or on) the line of y = 3 (A solid line is used for or ) 9.4 Ex 2:
Sketch the graph of the inequalities x y < 2 Sol: Draw the graph of the corresponding equation x y = 2 first Because the origin (0, 0) satisfies the inequality, the solution region is the halfplane lying above (or to the left of) the line x y = 2 9.5 Systems of linear inequalities: For example, x y 12 3 x 4 y 15 x 0 y 0 is a system of linear inequalities
Solution of a system of inequalities: A solution is an ordered pair (x, y) satisfying each inequality in the system The graph of a system of inequalities: The collection of all solutions of the system 9.6 Ex 3: Solving a system of inequalities Sketch the graph and label the vertexes ( ) of the solutio n set of the system shown below x y 2 x2 y 3 Sol: Vertex A(2, 4): the intersection of x y = 2 and x = 2
Vertex B(5, 3): the intersection of x y = 2 and y = 3 Vertex C(2, 3): the intersection of x = 2 and y = 3 9.7 Notes: For complicated regions, two border lines could intersect at a point that is not a vertex of the solution region 9.8 Notes: The system might have no solution or the solution set of a system can be unbounded No solution Solution region is unbounded x y 3 x y 1
x 2y 3 x y 3 9.9 Keywords in Section 9.1: linear inequalities: solution of an inequality: systems of linear inequalities: solution of a system of inequalities:
vertexes: 9.10 9.2 Linear Programming Involving Two Variables Linear programming problems ( ) The linear programming problem is a type of optimization problem consisting of a linear objective function ( ) and a system of linear inequalities called co nstraints Note: The objective function gives the quantity that is to be maximized (or minimized), and the constraints determine the set of feasible solutions Many applications in business and economics involve a process called optimization ( ), e.g., to find the minimum cost, the maximum profit, or the minimum consumption of resources The linear programming problem is one of the simplest and most
widely used optimization problems 9.11 Ex 1: Solving a linear programming problem Find the maximum value of z = 3x + 2y subject to the constrai nts listed below x 0 Sol: y 0 x 2 y 4 x y 1 At (0, 0): z = 3(0) + 2(0) = 0 At (1, 0): z = 3(1) + 2(0) = 3 At (2, 1): z = 3(2) + 2(1) = 8 At (0, 2): z = 3(0) + 2(2) = 4 (maximum value of
z) Try testing some interior points in the region. You will see that corresponding value of z are less than 8 9.12 Why the maximum value of the objective function must occur at a vertex? Consider to rewrite the objective function in the form 3 z y x 2 2 First, the above equation represents a family of parallel lines given different values of z, each of which is with the slope to be 3/2 Second, if you want to find the
maximum value of z for the solution region, it is equivalent to find the line with the largest y-intercept Finally, it is obvious that such a line must pass through one (or more) of the 9.13 vertexes of the solution region Note: The linear programming problem involving two variables can be solved by the graphical method ( ): 1. Sketch the region corresponding to the system of constraints (The points inside or on the boundary of the region are called feasible solutions) 2. Find the vertexes of the region 3. Test the objective function at each of the vertexes and select th e values of the variables that optimize the objective function (For a bounded region, both a minimum and maximum value will exist at v ertexes. For an unbounded region, if an optimal solution exists, it must occur at a vertex) 9.14
Ex 2: Solving a linear programming problem Sol: Find the maximum value of z = 4x + 6y, where x 0 and y 0, subject to the constraints x y 11 x y 27 2 x 5 y 90 At (0, 0): z = 4(0) + 6(0) = 0 At (0, 11): z = 4(1) + 6(11) = 66 At (5, 16): z = 4(5) + 6(16) = 116 At (15, 12): z = 4(15) + 6(12) = 132 At (27, 0): z = 4(27) + 6(0) = 108 So the maximum value of z is 132, and this occurs when x = 15 and y = 12 9.15
Ex 3: Minimizing an objective function Find the minimum value of the objective function z = 5x + 7y, where x 0 and y 0, subject to the constraints 2 x 3 6 3 x y 15 x y 4 2 x 5 y 27 9.16 Sol: At (0, 2): z = 5(0) + 7(2) = 14 At (0, 4): z = 5(0) + 7(4) = 28 At (1, 5): z = 5(1) + 7(5) = 40 At (6, 3): z = 5(6) + 7(3) = 51 At (5, 0): z = 5(5) + 7(0) = 25 At (3, 0): z = 5(3) + 7(0) = 15 So the minimum value of z is 14, and this occurs when x = 0 and y = 2 9.17
Ex: The maximum (or minimum) value occurs at two different v ertexes To maximize the objective function z = 2x + 2y given the foll owing shaded region At (0, 0): z = 2(0) + 2(0) = 0 At (0, 4): z = 2(0) + 2(4) = 8 At (2, 4): z = 2(2) + 2(4) = 12 (maximum value of z) At (5, 1): z = 2(5) + 2(1) = 12 (maximum value of z) At (5, 0): z = 2(5) + 2(0) = 10 The maximum value occurs not only at the vertexes (2, 4) and (5, 1), but also occurs at any point on the line segment connecting these two vertexes 9.18 Ex: An unbounded region
To maximize the objective function z = 4x + 2y given the foll owing shaded region For this unbounded region, there is no maximum value of z. By choosing points (x, 0) for x 4, you can obtain values of z = 4(x) + 2(0) = 4x that are as large as you want 9.19 Ex 5: An application: minimum cost The liquid portion of a diet is to provide at least 300 calories, 36 units of vitamin A, and 90 units of vitamin C daily. A cup of diet ary drink X provides 60 calories, 12 units of vitamin A, and 10 u nits of vitamin C. A cup of dietary drink Y provides 60 calories, 6 units of vitamin A, and 30 units of vitamin C. Now suppose the dietary drink X cost $.12 per cup and drink Y c osts $.15 per cup. How many cups of each drink should be consu med each day to minimize the cost and still meet the stated daily requirements?
9.20 Sol: For calories: 60 x 60 y 300 For vitamin A: 12 x 6 y 36 For vitamin C: 10 x 30 y 90 constraints x 0 y 0 The cost C : C 0.12 x 0.15 y objective function At (0, 6): C = 0.12(0) + 0.15(6) = 0.90 At (1, 4): C = 0.12(1) + 0.15(4) = 0.72 At (3, 2): C = 0.12(3) + 0.15(2) = 0.66 At (9, 0): C = 0.12(9) + 0.15(0) = 1.08
So the minimum cost is $.66 per day, and this occurs when 3 cups of drink X and 2 cups of drink Y are consumed each day 9.21 Keywords in Section 9.2: linear programming problems: graphical method: 9.22 9.3 The Simplex Method: Maximization The graphical method is convenient to solve linear programmi ng problems involving only two variables. However, for proble
ms involving more than two variables or problems involving lar ge numbers of constraints, it is better to use a more systematic s olution, which is called the simplex method Slack variables (for smaller-than-or-equal-to constraints) ( ) x1 x2 11 x1 x2 27 2 x1 5 x2 90 x1 x2 s1 x1 x2 2 x1 5 x2 11 s2 27 s3 90 The nonnegative numbers s1, s2, and s3 are called slack variables because they represent the slackness in each inequality
9.23 Standard form of a maximization problem A linear programming problem is in standard form if it seek s to maximize the objective function z = c1x1 + c2x2 + + cn xn subject to the smaller-than-or-equal-to constraints a11 x1 a12 x2 a1n xn b1 a21 x1
a22 x2 a2 n xn b2 am1 x1 am 2 x2 amn xn bm where bi 0 and xi 0. After adding slack variables, the corr esponding system of constraint equations is
a11 x1 a12 x2 a1n xn s1 a21 x1 a22 x2 a2 n xn am1 x1
am 2 x2 amn xn b1 s2 b2 sm bm 9.24
Note: For the standard form of a maximization problem, the c onstraints involve only the smaller-than-or-equal-to signs and all xi 0 and all bi 0 Basic solution ( ): A basic solution is a solution (x1, x2,, xn, s1, s2,, sm) for a linear programming problem in standard form in which at most m variables are nonzero The variables that are nonzero are called basic variables ( ), and the variables that are zero are called nonbasic v ariables ( ) 9.25 Simplex tableau ( ): This tableau consists of the augmented matrix correspondin g to the constraint equations together with slack variables a nd the objective function in the following form c1 x1 c2 x2 cn xn (0) s1 (0) s2 (0) sm z 0 Ex: z 4 x1 6 x2
x1 x2 x1 2 x1 x2 5 x2 objective function to be maximized s1 s2 s3 11 27 90 constraints
The corresponding simplex tableau is current z-value 9.26 Note: For this initial simplex tableau, the basic variables ar e s1, s2, and s3, and the nonbasic variables are x1 and x2, i.e., x 1 = x2 = 0. As a consequence, the coefficient 1s for s1, s2, and s3 are similar to leading 1s and these basic variables have init ial values of s1 = 11, s2 = 27, and s3 = 90 Note: The initial solution for the simplex tableau is (x1, x2, s1, s2, s3) = (0, 0, 11, 27, 90) and for the objective function, the current z-value is 4(0) + 6 (0) = 0
Optimality check: Observing the bottom row of the tableau, if any of these entries (except the current z-value) are negative, t he current solution is not optimal (so the initial values for (x1, x2, s1, s2, s3) are not optimal) 9.27 Iteration of Simplex Method: An improvement process for finding larger z-value, which brings a new nonbasic variable into the solut ion, the entering variable ( ), and in the meanwhile on e of the current basic variables (the departing variable ( )) must leave 1. The entering variable corresponds to the smallest (the most ne gative) entry in the bottom row of the tableau 2. The departing variable corresponds to the smallest nonnegativ e ratio of bi/aij in the column j determined by the entering variable 3. The entry in the simplex tableau in the entering variables colu mn and the departing variables row is called the pivot entry 4. Use elementary row operations so that the pivot entry is 1, and all other entries in the entering variable column are 0 9.28
Ex 1: Pivoting to find an improved solution Use the simplex method to find an improved solution for the lin ear programming problem represented by the tableau shown bel ow Since 6 is the smallest entry in the bottom row, we choose x2 to be the entering variable Because the objective function is z = 4x1 + 6x2, a unit increase in x2 produce an increase of 6 in z, whereas a unit increase in x1 produces an increase of only 4 in z. Thus, adjusting x2 brings larger improvement for finding a larger z-value 9.29 To find the departing variable, identify the row with the smallest
nonnegative bi/aij for the entering variables column, i.e., for j = 2 and examine b1/a12, b2/a22, and b3/a32 11 27 90 11, 27, and 18 1 1 5 (Since 11 is the smallest nonnegative ratio, we choose s1 as the departing variable) 9.30 G.-J. E. for the 2nd column
This process is called pivoting Therefore, the new tableau now becomes as follows Note: x2 has replaced s1 to be a basic variable and the improved solution is (x1, x2, s1, s2, s3) = (0, 11, 0, 16, 35) with a z-value of 9.31 The improved solution is not yet optimal because the bottom row still has a negative entry Since 10 is the smallest number in the bottom row, we choose x1 as the entering variable Moreover, the smallest nonnegative ratio among 11/(1) = 11, 16/2 = 8, and 35/7 = 5 is 5, so s3 is the departing variable and a31 is the pivot entry pivot entry 9.32 So, the new tableau is as follows
(x1, x2, s1, s2, s3) = (5, 16, 0, 6, 0) with a z-value of 4x1 + 6x2 = 4(5) + 6(16) = 116 Following the same rule, we can identify s1 to be the entering variable and s2 to be the departing variable 9.33 By performing one more iteration of the simplex method, you can obtain the following tableau In this tableau, there are no negative elements in the bottom row. So, the optimal solution is determined to be (x1, x2, s1, s2, s3) = (15, 12, 14, 0, 0) with z = 4x1 + 6x2 = 4(15) + 6(12) = 132 9.34 Note: For the linear programming problem in Example 1
involving two variables, you could also employ the graphical method to solve this problem as follows Note that each iteration in the simplex method corresponds to moving from a given vertex to an adjacent vertex with an improved z-value (0, 0) (0,11) (5,16) (15,12) z 0 z 66 z 116 z 132 In addition, why we choose (x1, x2, s1, s2, s3) = (0, 0, b1, b2, b3) = (0, 0, 11, 27, 90) as the initial basic solution is that (x1, x2) = (0, 0) must be a vertex of the feasible solution region because all xi 0 in the standard form of 9.35
(x1, x2) = (0, 0) (intersection of x = 0 and y = 0) x 0 nonbasic: 1 x2 0 x1 x2 (0) (0) 0 11 s1 11 basic: x1 x2 (0) (0) 0 27 s2 27 2 x 5 x 2(0) 5(0) 0 90 s 90 2 3 1 (x1, x2) = (0, 11) (intersection of x = 0 and x + y = 11) x1 0 nonbasic: s1 0 x1 x2 11
x2 11 basic: x1 x2 (0) (11) 11 27 s2 16 2 x 5 x 2(0) 5(11) 55 90 s 35 2 3 1 (x1, x2) = (5, 16) (intersection of x + y = 11 and 2x + 5y = 90) s 0 x1 x2 11 nonbasic: 1 s3 0 2 x1 5 x2 90 x1 5 basic: x2 16 x x (5) (16) 21 27 s 6
2 1 2 (x1, x2) = (15, 12) (intersection of x + y = 27 and 2x + 5y = 90) s 0 x1 x2 27 nonbasic: 2 s3 0 2 x1 5 x2 90 x1 15 basic: x2 12 x x (15) (12) 3 11 s 14 1 1 2 The above analysis shows that two nonbasic variables represent two straight lines (corresponding equations) that determine the vertex we examine The intuition of the simplex method is to test different combinations of nonbasic variables, which 9.36 is equivalent to testing different vertexes of the solution region
Ex 2: The simplex method with three variables Use the simplex method to find the maximum value of z = 2x1 x2 + 2x3, subject to the constraints 2 x1 x1 x2 2 x2 x2 2 x3 2 x3 10 20 5 where x1 0, x2 0, and x3 0 Sol: First, construct the initial simplex tableau with the initial
basic solution (x1, x2, x3, s1, s2, s3) = (0, 0, 0, 10, 20, 5) 9.37 Note that the tie occurs when choosing the entering variable. Here we arbitrarily choose x3 as the entering variable 9.38 So the optimal solution is (x1, x2, x3, s1, s2, s3) = (5, 0, 5/2, 0, 20, 0) with z = 2x1 x2 + 2x3 = 2(5) (0) + 2(5/2) = 15 Note: Since s1 = s3 = 0, the optimal solution satisfies the first and third constraints. The result of s2 = 20 indicates that the second constraint has a slack of 20 9.39
Ex 3: The simplex method with equality constraints Use the simplex method to find the maximum value of z = 3x1 + 2x2 + x3, subject to the constraints 4 x1 2 x1 x1 x2 3x2 2 x2 x3 x3 3 x3 where x1 0, x2 0, and x3 0 Sol: 30 60 40
The initial basic solution is (x1, x2, x3, s1, s2, s3) = (0, 0, 0, 30, 60, 40) The variable s1 is an artificial variable, rather than a slack variable Since the first constraint is an equality, s1 in the optimal solution must be zero, i.e., s1 must be the nonbasic variable and thus 9.40 be 0 in the optimal solution 9.41 So the optimal solution is (x1, x2, x3, s1, s2, s3) = (3, 18, 0, 0, 0, 1) with z = 3x1 + 2x2 + x3 = 3(3) + 2(18) + 1(0) = 45 Note: Since s1 is not a basic variable and thus s1 = 0 in the optimal solution, this solution satisfies the first constraints (4(3) + 1(18) + 1(0) = 30)
9.42 Ex 4: A business application: maximum profit A manufacturer produces three types of plastic fixtures ( ). The times required for molding ( ), trimming ( ), and packaging are presented as follows. (Times and profit s are displayed in hours and dollars for per dozen fixtures) How many dozen of each type of fixture should be produced to obtain a maximum profit? 9.43 Sol: Let x1, x2, x3 represent the numbers of dozens of types A, B, and C fixtures, respectively. The objective function is expressed as profit = P = 11x1 + 16x2 + 15x3, subject to the constraints x1 2 x1
3 1 x1 2 2 x2 2 x2 3 1 x2 3 2 x3 3
12000 x3 4600 1 x3 2 2400 where x1 0, x2 0, and x3 0 9.44 Apply the simplex method with the initial basic solution (x1, x2, x3, s1, s2, s3) = (0, 0, 0, 12000, 4600, 2400)
9.45 So the optimal solution is (x1, x2, x3, s1, s2, s3) = (600, 5100, 800, 0, 0, 0) with the maximum profit to be $100,200 9.46 Ex 5: A business application: media selection The advertising alternatives for a company include television, r adio, and newspaper advertisements. The costs and estimates of audience coverage are provided as follows Moreover, in order to balance the advertising among the three t ypes of media, no more than half of the total number of advertis ements should occur on the radio, no more than 10 advertiseme nts should occur on the newspaper, and at least 10% should occ ur on the television. The weekly advertising budget is $18,200. How many advertisements should be run on each media to max imize the total audience? 9.47
Sol: Let x1, x2, x3 represent the numbers of advertisements in televisi on, newspaper, and radio, respectively. The objective function i s expressed as z = 100000x1 + 40000x2 + 18000x3, where x1 0, x2 0, and x3 0, and subject to the constraints 2000 x1 600 x2 300 x3 x2 10 0.5( x1 x2 x3 ) x3 x1
18200 0.1( x1 x2 x3 ) 20 x1 6 x2 x1 x2 x2 9 x1 x2
3 x3 182 x3 10 0 x3 0 9.48 Apply the simplex method with the initial basic solution (x1, x2,
x3, s1, s2, s3, s4)= (0, 0, 0, 182, 10, 0, 0) 9.49 So the optimal solution is (x1, x2, x3, s1, s2, s3, s4) = (4, 10, 14, 0, 0, 0, 12) with the maximum weekly audience to be 1,052,000 9.50 Keywords in Section 9.3: simplex method: slack variable: basic solution:
basic variable: nonbasic variable: simplex tableau: entering variable: departing variable: artificial variable: 9.51
9.4 The Simplex Method: Minimization In Section 9.3, the simplex method is applied only to linear pr ogramming problems in standard form where the objective fu nction is maximized. In this section, we will study the minimi zation problem Standard form for a minimization problem If w = c1x1 + c2x2 + + cnxn is to be minimized, subject to th e constraints a11 x1 a12 x2 a21 x1
a22 x2 am1 x1 am 2 x2 where xi 0 and bi 0 a1n xn b1 a2 n xn b2
amn xn bm Note that in the standard form for maximization problems, those are signs (see Slide 9.24) 9.52 To find the Dual Maximization Problem (corresponding to the m inimization problem that we want to solve) Considering Example 5 in Section 9.2, we want to minimize w 0.12 x1 0.15 x2 , subject to the constraints 60 x1 60 x2 300 12 x1 6 x2 36 10 x1 30 x2 90 where x1 0 and x2 0 We cannot apply directly the simplex method because the simplex method
introduced in Section 9.3 is for maximization problems There is a dual relationship between minimization problems in standard form and maximization problems in standard form 9.53 The steps to convert this problem into a maximization problem 1. Form the augmented matrix as follows constraints for the minimization problem objective function for the minimization problem 2. Find the transpose of this matrix constraints for the dual maximization problem
objective function for the dual maximization problem 3. Interpret the transposed matrix as a maximization problem 9.54 The corresponding maximization problem is called the dual maximization problem of the original minimization problem, which is as follows Find the maximum value of z 300 y1 36 y2 90 y3 , subject to the constraints 60 y1 12 y2 10 y3 0.12 60 y1 6 y2 30 y3 0.15 where y1 0, y2 0, and y3 0 The solution of the original minimization problem can be found by applying the simplex method to the new dual maximization problem 9.55 Apply the simplex method with the initial basic solution (y1, y2, y3, s1, s2) = (0, 0, 0, 0.12, 0.15)
9.56 So the optimal solution is (y1, y2, y3, s1, s2) = (7/4000, 0, 3/2000, 0, 0) with the maximum value to be 300(7/4000)+36(0)+90(3/2000) = 33/50 = 0.66 The optimal values of xis for the original minimization can be obtained from the entries in the bottom row corresponding to slack variable columns, i.e., x1 = 3 and x2 = 2 The minimum value for the original objective function is 0.12(3)+0.15(2) = 0.66, which is exactly the maximum value for the dual maximization problem (It is the same as that derived by the graphical method in Sec. 9.2) This dual relationship is called the von Neumann Duality Principle, introduced by the American mathematician John von Neumann (1903- 9.57 Ex 1: Solving a minimization problem Find the minimum value of w = 3x1 + 2x2, subject to the constra ints 2 x1
x1 x2 x2 6 4 where x1 0 and x2 0 Sol: 1. The augmented matrix corresponding the this minimization problem 9.58 2. Derive the matrix corresponding to the dual maximization problem by taking transpose The above augmented matrix implies the following maximization problem: Find the maximum value of z = 6y1+ 4y2, subject to the constraints 2 y1
y1 y2 y2 3 2 where y1 0 and y2 0 9.59 Apply the simplex method with the initial basic solution (y1, y2, s1, s2)= (0, 0, 3, 2) 9.60 From this final simplex tableau, you can see the maximum value of z is 10. So the solution of the original minimization problem is w =10, and this occurs when (x1, x2) = (2, 2)
9.61 Ex 2: Solving a minimization problem Find the minimum value of w = 2x1 + 10x2 + 8x3, subject to the constraints x1 x1 x2 x2 2 x2 x3 2 x3 2 x3 6
8 4 where x1 0, x2 0, and x3 0 Sol: First, transpose the augmented matrix transpose 9.62 The corresponding maximization problem: Find the maximum value of z = 6y1 + 8y2 + 4y3, subject to the constraints y1 y1 y1 y2 2 y2
y3 2 y3 2 y3 2 10 8 where y1 0, y2 0, and y3 0 The initial simplex tableau 9.63 From the last row of this final simplex tableau, you can see the maximum value of z is 36. So the solution of the original minimization problem is w =36, and this occurs when (x1, x2 , x2) = (2, 0, 4) 9.64 Ex 3: A business application: minimum cost
A small petroleum company owns two refineries. Refinery 1 co sts $20,000 per day to operate, and it can produce 400 barrels o f high-grade oil, 300 barrels of medium-grade oil, and 200 barr els of low-grade oil each day. Refinery 2 is newer and more mo dern. It costs $25,000 per day to operate, and it can produce $3 00 barrels of high-grade oil, 400 barrels of medium-grade oil, a nd 500 barrels of low-grade oil each day The company has orders totaling 25,000 barrels of high-gra de oil, 27,000 barrels of medium-grade oil, and 30,000 barrels of low-grade oil. How many days should this petroleum compa ny run each refinery to minimize its costs and still refine enoug h oil to meet its orders? 9.65 Sol: Let x1 and x2 represent the numbers of days on which the two refi neries are operated. Then the total cost is represented by C = 20,000x1 + 25,000x2, and the constraints are 400 x1 300 x1 200 x1
300 x2 400 x2 500 x2 25, 000 (high-grade oil) 27, 000 (medium-grade oil) 30, 000 (low-grade oil) where x1 0 and x2 0 transpose 9.66 Now apply the simplex method to the dual problem 9.67 From this final simplex tableau, you can see the solution for the original minimization problem is C = $ 1,750,000 and this occurs when x1 = 25 and x2 =
50, i.e., the two refineries should be operated for 25 and 50 days, respectively 9.68 Keywords in Section 9.4: dual maximization problem: 9.69 9.5 The Simplex Method: Mixed Constraints In Sections 9.3 and 9.4, we learn how to solve linear program ming problems in the standard forms, i.e., the constraints for the maximization problem involve only inequalities, and the constraints for the minimization problem involve only
inequalities Mixed-constraint problems: the constraints involve both type s of inequalities For example, find the maximum value of z = x1 + x2 + 2x3, sub ject to the constraints 2 x1 x2 2 x1 x2 x1 x3 x3 where x1 0, x2 0, and x3 0 50 36 10 Because of these two inequalities, this is not the standard form for a maximization problem
9.70 For the first inequality, it does involve inequalities, so we add a slack variable to form the equation as before 2 x1 x3 s1 50 For the last two inequalities, a new type of variable, called a surplus variable ( ), is introduced as follows 2 x1 x1
x2 x2 x3 s2 s3 36 = 10 Note: The variable s2 and s3 are called the surplus variables because they represent the amounts by which the left sides of the inequalities exceed the right sides Note: The surplus variables as well as the slack variables must be nonnegative, i.e., s1 0, s2 0, and s3 0 in the above case 9.71
The initial simplex tableau can be formed as follows Note: According to the rules introduced in the Section 9.3, the initial basic solution is (x1, x2, x3, s1, s2, s3) = (0, 0, 0, 50, 36, 10), which is not a feasible solution because the values of the two surplus variables are negative In other words, the point (x1, x2, x3) = (0, 0, 0) is not an vertex of the feasible solution region (In fact, (0, 0, 0) is not even in the feasible solution region) So, we cannot apply the simplex method directly from this initial basic solution 9.72
We need to use the trial and error method ( ) to find a feasible solution for the initial basic solution for the simplex method, that is, arbitrarily choosing new entering variable to replace the negative surplus variables (It is equivalent to jump from the intersection of x1 = 0, x2 = 0, and x3 = 0 to the intersection of other three corresponding equations) Note: Here we choose x3 as the entering variable and s3 as the departing variable arbitrarily, i.e., we do not follow the pivoting process introduced on Slide 9.28 to select the entering and departing variables 9.73 After pivoting, the new simplex tableau is as follows It means that we consider the intersection of x1 = 0, x2 = 0, and x1 + x3 = 10
(because s3 = 0) The current solution (x1, x2, x3, s1, s2, s3) = (0, 0, 10, 40, 36, 0) is not feasible because the value of s2 is still negative So we choose x2 as the entering variable and s2 as the departing variable and pivot to obtain the following simplex tableau 9.74 The above tableau suggests that we consider the intersection of x1 = 0, 2x1 + x2 = 36 (because s2 = 0), and x1 + x3 = 10 (because s3 = 0) We finally obtain a feasible solution, which is (x1, x2, x3, s1, s2, s3) = (0, 36, 10, 4, 0, 0) From here on, you can apply the simplex method as usual, i.e., we choose s3 as the entering variable because of its smallest entry in the bottom row, and then compare bi/aij in the entering variable
column to find s to be the departing variable 9.75 After pivoting, you can obtain the following simplex tableau Note that it is the final tableau because it represents a feasible solution and there are no negative entries in the bottom row So, you can conclude that the maximum value of z = 64 and this occur when (x1, x2, x3, s1, s2, s3)= (0, 36, 14, 0, 0, 4) 9.76
For the minimization problem with mixed-constraints, the situation is more difficult because we cannot apply the dual principle to find the corresponding maximization problem if there are mixed constraints Another technique is introduced to change a mixed-constraint minimization problem to a mixed-constraint maximization problem by multiplying each coefficient in the objective function by 1 This technique is demonstrated in the next example 9.77 Ex 2: A minimization problem with mixed constraints Find the minimum value of w = 4x1 + 2x2 + x3, subject to the co nstraints 2 x1 3x1 x1
3x2 x2 4 x2 4 x3 5 x3 3x3 14 4 6 where x1 0, x2 0, and x3 0 Sol: First, rewrite the objective function by multiplying each of its coefficients by 1, i.e., z = 4x1 2x2 x3 (maximizing this new objective function is equivalent to minimizing the original objective function) 9.78 Next, add a slack variable to the first inequality and subtract sur plus variables from the second and third inequalities, and the in itial simplex tableau is as follows
Note that there is no negative entry in the bottom row because it contains the negatives of the coefficients of the new objective function The current solution (x1, x2, x3, s1, s2, s3) = (0, 0, 0, 14, 4, 6) is not a feasible solution So, what we need to do is to arbitrarily choose the entering and departing variables to find a feasible solution Here we choose x2 as the entering variable and s2 as the departing variable 9.79 The current solution (x1, x2, x3, s1, s2, s3) = (0, 4, 0, 2, 0, 10) is a feasible solution. From now on, we can apply the standard simplex method We choose x3 as the entering variable because 9 is the smallest entry in the bottom row and choose s3 as the departing variable because b3/a33 is the smallest nonnegative ratio in the third column After pivoting, we can obtain the following simplex tableau 9.80 After pivoting around a25, we can obtain the following simplex tableau The maximum value of the new objective function is z = 2, so
the minimum value of the original objective function is w = 2. This occurs when x1 = 0, x2 = 0, and x3 = 2 The solution of x3 is according to the third row since it is a basic variables, and x1 = 0 and x2 = 0 are due to the fact that they are nonbasic variables 9.81 Ex 3: A business application: minimum shipment costs An automobile company has two factories. One factory has 400 cars (of a certain model) in stock and the other factory has 300 cars (of the same model) in stock. Two customers order this car model. The first customer needs 200 cars, and the second custo mer needs 300 cars. The costs of shipping cars from the two fac tories to the customers are shown in the following table. How should the company ship the cars in order to minimize the shipping costs? 9.82 Sol: Let x1 and x2 represent the numbers of cars shipped from factory
1 to the first and second customers, respectively. The total cost o f shipping to be minimized is C = 30x1 + 25x2 + 36(200 x1) + 30(300 x2) = 16,200 6x1 5x2 and the constraints are x1 x2 400 (There are only 400 cars in factory 1) (200 x1 ) (300 x2 ) 300 (There are only 300 cars in factory 2) x1 200 (The max. number of cars from factory 1 to customer 1 is 200) x2 300 (The max. number of cars from factory 1 to customer 2 is 300) where x1 0 and x2 0 and the second inequality can be rewritt en as x1 + x2 200 9.83 Multiply the objective function by 1 to convert it into a maxim ization problem, i.e., to maximize z = 6x1 + 5x2 16,200. So, th e initial simplex tableau is as follows The current solution (x1, x2, s1, s2, s3, s4) = (0, 0, 400, 200, 200, 300) and the current z-value is 16,200 Since the current solution is not a feasible solution (due to the negative value of s2), in addition to choosing s2 as the departing variable, we
arbitrarily choose x1 to be the entering variable 9.84 After pivoting, we can obtain the following simplex tableau The current solution (x1, x2, s1, s2, s3, s4) = (200, 0, 200, 0, 0, 300) is a feasible solution So, from now on, we can apply the standard simplex method. Following the rule on Slide 9.28, we choose s2 as the entering variable and s3 as the departing variable 9.85 After pivoting, we can obtain the following simplex tableau Following the rule on Slide 9.28, we choose x2 as the entering variable and s1 as the departing variable. After pivoting around the entry a12, we can obtain the following simplex tableau 9.86 Since all entries except the z-value in the bottom row are nonnegative, it is the final simplex tableau
The minimum shipping cost is $14,000, and this occurs when x1 = 200 and x2 = 200, i.e., the numbers of cars shipped from the two factories are as follows 9.87 Linear Programming under xi 0 and bi 0 problems in standard Min. problems in standard Max. form, i.e., involving only in constraints 1. Add slack variables to form constraint equations 2. Perform the simplex method Max. problems with mixed constraints 1. Add slack variables and subtract surplus variables to form constraint equations
2. Try to find a feasible solution by trial and error 3. Apply the simplex method dual transformation form, i.e., involving only in constraints There are two kinds of methods to solve this problem Min. problems with mixed constraints 1. Multiply the objective function by 1 to convert it into a max. problem 2. Add slack variables and subtract surplus variables to form constraint equations 3. Try to find a feasible solution by trial and error 4. Apply the simplex method
9.88 Exercise in Section 9.4 on Slide 9.53: Do not apply the dual prin ciple to solving the minimization problem in standard form We want to minimize w 0.12 x1 0.15 x2 , subject to the constraint s 60 x1 60 x2 300 12 x1 6 x2 36 10 x1 30 x2 90 where x1 0 and x2 0 Sol: First, rewrite the objective function by multiplying each of its coefficients by 1, i.e., z = 0.12x1 0.15x2 (maximizing this new objective function is equivalent to minimizing the original objective function) 9.89 Next, subtract surplus variables for these three inequalities, and the initial simplex tableau is as follows x1
60 x2 60 s1 s2 1 0 s3 0 b Basic Variables 300 s1 12 6 0 1
0 36 s2 0 0 0 0 1 0 90 0 s3 10 30 0.12 0.15
The current solution (x1, x2, s1, s2, s3) = (0, 0, 300, 36, 90) is not a feasible solution What we need to do is to arbitrarily choose the entering variables and choose negative surplus variables as the departing variables to find a feasible solution Here we choose x2 as the entering variable and s2 as the departing variable 9.90 After pivoting, we can obtain the following simplex tableau x1 x2 s1 s2 s3 b
Basic Variables 60 0 1 10 0 60 s1 0 6 x2 2
1 0 50 0 0 0.18 0 0 1 6 5 0.15 6
1 90 0 s3 0.9 The current solution (x1, x2, s1, s2, s3) = (0, 6, 60, 0, 90) is a feasible solution. From now on, we can apply the standard simplex method We choose x1 as the entering variable because 0.18 is the smallest (or the most negative) entry in the bottom row except the z-value and choose s1 as the departing variable because b1/a11 is the smallest nonnegative ratio in the first column After performing the pivoting process based on a11, we can obtain the following9.91 x1 x2 1 0
0 1 0 0 0 0 x1 x2 1 0 0 1
0 0 0 0 s1 1 60 1 30 5 6 0.18 60 s1 3 120 1 120
1 4 0.21 120 s2 s3 b Basic Variables 1 0 1 6 1 0 4 6 20
1 40 6 0.03 0 0.72 6 x1 s2 0 0 1 0 s3 b 1
3 20 1 2 20 6 12 20 0.03 0.66 20 x2 s3 Basic Variables Since all entries except the z-value x1 x2 s2 on the bottom row is nonnegative, it is the final simplex tableau
The minimum value for w is 0.66, and this occurs when x1 = 3 and x2 =2 This method can generate the same result as that in the method combining the dual transformation and the standard simplex method (comparing to Slide 9.57) 9.92 Keywords in Section 9.5: mixed-constraint problems: surplus variable: 9.93 9.6 Homework 3
Solving the linear programming problem by the function Solver in Excel (see Homework3_Portfolio_frontier.xls) Not only linear programming problems ( ) but als o nonlinear programming problems can be solved by Solver The nonlinear programming problem ( ) means the objective function and/or one or more constraints are nonline ar The quadratic programming problem ( ) is a spec ial case of the nonlinear programming problem, in which the obj ective function contains squared terms and the constraints are all linear Finding the portfolio frontier is a quadratic programming proble m 9.94
Portfolio frontier problem: Given an expected portfolio return , find the optimal weights on assets to construct a portfolio wi th a minimum variance For a portfolio return rp = w1r1 + w2r2 + + wnrn, given any s pecified value of E(rp), the portfolio frontier problem is to sol ve optimal weights w1, w2,, wn in the following quadratic pr ogramming problem: n n n n min P2 wi w j cov(ri , rj ) wi w j i j i , j w1 ,, wn i 1 j 1
i 1 j 1 s.t. w1 E ( r1 ) w2 E (r2 ) wn E ( rn ) E ( rp ) w1 w2 wn 1 * Suppose the expected returns E(ri) and variances and covariance among individual assets cov(ri, rj) are known 9.95 Homework 3 (10 points) Find the portfolio frontier based on at least 5 stocks in S&P 500, i.e., solve the above quadratic programming problem for n 5
Note that ris of all stocks are total returns, so you need to find adjusted closing prices or adjusted returns Today is assumed to be July 1st, 2018 and you need to find one-year historical returns for each stock Estimate the expected values and standard deviations for ris of all stocks and the correlations among the ris of all stocks as well, i.e., to calculate sample averages (for estimating E(ri)) , i, and ij from the historical data Annualization: daily average return 252 = annual average return; daily s.d. sqrt(252) = annual s.d. For different portfolio returns, e.g., E(rp) = 0, 1%, 2%,, 40%, solve wi for each E(rp) by the function Solver in Excel For each solution set of wi, plot a point according to the portfolio return 9.96 Bonus:
Compare the portfolio frontiers of at least three industries (1 point) Compare the portfolio frontiers given different values of n (With the increase of n, the portfolio frontier should move further toward left theoretically, i.e., given the same E(rp), you can generate a smaller portfolio standard deviation given more stocks) (1 point) Examine the special case for n = 2: (1 point) Check that the point of (E(r ), ) for each of the two stocks lies on i i the portfolio frontier Consider the case of 12 = 1 (simply setting 12 to be 1) and demonstrate that the portfolio frontier is a straight line in this case Consider the case of 12 = 1 (simply setting 12 to be 1) and demonstrate that the portfolio frontier is a saw-like, piecewise linear curve and there is a portfolio with zero standard deviation Compare with the portfolio frontier with the short sales constraints (i.e., w1, w2,, wn are nonnegative) (1 point) The basic requirement is 10 points, and the bonus is at most 3 additional points 9.97
Implement Homework 3 with VBA Basic requirement (with one CommandButton): Inputs: Time series of ri,t of the five firms Outputs: For each portfolio frontier, 1. Calculate (E(ri), i) and correlation ij for all i, j 2. Solve wi to minimize the portfolio variance and next obtain the pair (E(rp), p) 3. Based on the generated 41 points of (E(rp), p), plot the portfolio frontier Bonus (with another CommandButtons):
Inputs: Time series of ri,t Outputs: (E(ri), i), ij, (E(rp), p), and the diagram of the portfolio frontier VBA Solver SolverOk SolverOptions AssumeNonNeg:=True SolverSolve UserFinish:=True [ ] SolverSolve 9.98
What is happening with Business Education programs on LI?
Ellen Palazzo. Long Island Field Associate, CTE TAC of NY. Director of Long Island Region of VE. [email protected] What is happening with Business Education programs on LI?What does it mean to you? What is Virtual Enterprises? How does it prepare...STUDENT REGISTRATION Spring 2011 MyA&P Student Registration 2007
Title: PowerPoint Presentation Author: Pearson Education Last modified by: Valued Acer Customer Created Date: 11/26/2002 2:56:46 PM Document presentation format