Optimization Methods in Management Science Tutorial 3 - Solving Systems of Equations

Solving Systems of Equations: A brief tutorial • This is a very brief introduction to solving systems of equations. You probably learned these techniques in high school, and you certainly learned them if you had 18.06 or any other type of linear algebra course. It doesn’t hurt to review. And perhaps you’ll learn something new. 1 Elementary Row Operations • The following is a 3 x 4 matrix on which we will perform three types of elementary row operations. [1] [2] [3] [4] Row 1 1 2 3 4 Row 2 1 3 5 6 Row 3 0 1 2 3 The first elementary row operation consists of multiplying one row by a constant. We illustrate this by multiplying Row 2 by 3. [1] [2] [3] [4] Row 1 1 2 3 4 Row 2 3 9 15 18 Row 3 0 1 2 3 2 The Second Elementary Row Operation The second elementary row operation consists of adding a multiple of one row of a matrix to another row of the matrix. [1] [2] [3] [4] Row 1 1 2 3 4 Row 2 3 9 15 18 Row 3 0 1 2 3 We illustrate this by adding four times Row 1 to Row 3. [1] [2] [3] [4] Row 1 1 2 3 4 Row 2 3 9 15 18 Row 3 4 9 14 19 3 The Third Elementary Row Operation The third elementary row operation consists of interchanging two rows of a matrix. [1] [2] [3] [4] Row 1 1 2 3 4 Row 2 3 9 15 18 Row 3 4 9 14 19 We illustrate this by interchanging Row 1 and Row 3. [1] [2] [3] [4] Row 1 4 9 14 19 Row 2 3 9 15 18 Row 3 1 2 3 4 4 Summary of Elementary Row Operations (EROs) • • • ERO 1: Multiply a Row by a constant ERO 2: Add a multiple of one Row to another ERO 3: Interchange two rows. These operations may be simple, but they are very powerful for solving equations. Cleaver 5 A Website for Using Elementary Row Operations • You can carry out elementary row operations by hand, or using Excel. There is also a site developed by IFORS Tutor for carrying out elementary row operations. Here is the URL And then click on Row Operations and then go to the ROWOPS Operations Center. 6 Using the ROWOPS Machine: ERO 1 To Multiply a Row by a constant, put the constant in the operator input box, select the left button for the row, and click on the operator box for row multiplication. Here we multiply Row 2 by 3. 7 Using the ROWOPS Machine: ERO 2. To add a multiple of one row to another, select the right radio button of the first row, the left radio button of the second row, put the multiplier in the operator input box, and then select the operator for adding a multiple of one row to another. Here we add 4 times Row 1 to Row 3. 8 Using the ROWOPS Machine: ERO 3. To interchange two rows, select the left radio button for one row, the right radio button for the other row, and then select the operator box for exchanging rows. Here we exchange rows 1 and 3. 9 Using ERO’s to Solve a System of Equations • We now use ERO’s to solve a system of linear equations. This technique is widely known as Guassian elimination, after the famous mathematician Gauss. It’s also widely known as Gauss-Jordan elimination after the famous mathematician Wilhelm Jordan Carl Friedrich Gauss (1777-1855) Gauss is way more famous than I am. And I’m honored to share credit with him for this technique. Wilhelm Jordan (1842 to 1899) 10 Solving a System of Linear Equations The system of equations that we solve is the following: 2x1 + 2x2 + x3 = 9 2x1 - x2 + 2x3 = 6 x1 - x2 + 2x3 = 5 Rather than keeping the x’s, we will write it in a matrix type form, and keep the x’s on the top, just to keep track of what each column represents. x1 x2 x3 RHS Equation 1 2 2 1 = 9 Equation 2 2 -1 2 = 6 Equation 3 1 -1 2 = 5 When we perform elementary row operations on this system of equations, we do not change the set of solutions to the equations. Our goal is to perform a series of EROs until a solution can be read off in an obvious manner. 11 Converting the first column into the correct form. x1 x2 x3 RHS Equation 1 2 2 1 = 9 Equation 2 2 -1 2 = 6 Equation 3 1 -1 2 = 5 1 We want the first column of the matrix to have the form of 1, 0, 0. 0 0 To accomplish this we first multiply Equation 1 by 1/2. We then subtract 2 times ( the resulting) Equation 1 from Equation 2. We then subtract Equation 1 from Equation 3. x1 x2 x3 Equation 2 2 1 2 0 2 1 -1 -3 1 1/2 2 1 = = = 9 9/2 6 -3 Equation 3 1 0 -1 -2 2 3/2 = = 5 1/2 Equation 1 RHS 12 Converting the second column into the correct form. x1 x2 x3 RHS Equation 1 1 1 1/2 = 9/2 Equation 2 0 -3 1 = -3 Equation 3 0 -2 3/2 = 1/2 0 We want the 2nd column of the matrix to have the form of 0, 1, 0. 1 0 To accomplish this we first multiply Equation 2 by -1/3. We then subtract (the resulting) Equation 2 from Equation 1 We then add two times Equation 2 to Equation 3. x1 x2 x3 Equation 1 1 01 1/2 5/6 = 9/2 7/2 Equation 2 0 00 -3 1 -2 0 1 -1/3 3/2 5/6 == -3 1 1/2 5/2 Equation 3 RHS = = 13 Converting the third column into the correct form. x1 x2 x3 RHS Equation 1 1 0 5/6 = 7/2 Equation 2 0 1 -1/3 = 1 Equation 3 0 0 5/6 = 5/2 0 We want the 3rd column of the matrix to have the form of 0, 0, 1. 0 1 To accomplish this we first multiply Equation 3 by 6/5. We then subtract 6/5 times (the resulting) Equation 3 from Equation 1 We then add 1/3 times Equation 3 to Equation 2. x1 x2 x3 RHS Equation 1 1 0 0 5/6 = 1 7/2 Equation 2 0 1 -1/3 0 = 21 Equation 3 0 0 5/6 1 = 5/2 3 14 Summary x1 x2 x3 Equation 1 1 0 0 5/6 = 1 7/2 Equation 2 0 1 -1/3 0 = 21 Equation 3 0 0 5/6 1 = 5/2 3 I told you it was simple. All one needs to do is to perform elementary row operations until you get it into the correct form. Cleaver At this point, all one needs to do is read off the solution. Equation 1 means “x1 = 1.” Equations 2 and 3 mean x2 = 2 and x3 = 3. Ollie, the computationally wise owl. RHS Personally, I find all of the ERO’s pretty confusing. Tim, the turkey 15 Pivoting It’s a lot simpler to describe if one combines the ERO’s into a smaller number of basic operations called “pivots.” I’ll show you how to solve the same system of equations with three pivots. Nooz, the most trusted name in fox. 16 A Pivot To pivot on entry (i, j) of a matrix is to carry out ERO’s so that 1. Row i is multiplied by a constant 2. Every other row has a multiple of Row i added to it. 3. After the operations, Column j has a 1 in row i and a 0 elsewhere. [1] [2] [3] RHS Equation 1 2 2 -1 = 9 Equation 2 2 -1 2 = 6 Equation 3 1 -1 2 = 5 [1] [2] [3] Equation 1 1 1 1/2 = 9 Equation 2 0 -3 1 = 6 Equation 3 0 -2 3/2 = 5 For example, if we pivot on entry (1,1) of the matrix, we end up with the matrix below. RHS The pivot combines three EROs into a single operation. 17 More on Pivots Solving the system of equations is simple if we think in terms of pivots. First we pivoted on element 1,1. Next, we pivot on element 2,2. And finally we pivot on 3,3. And we are done. You can think of a pivot as a computer macro. Each pivot carries out a specified set of ERO’s. [1] [2] [3] RHS Equation 1 1 1 1/2 = 9 Equation 2 0 -3 1 = 6 Equation 3 0 -2 3/2 = 5 [1] [2] [3] Equation 1 1 0 5/6 Equation 2 0 1 -1/3 = Equation 3 0 0 5/6 [1] [2] [3] Equation 1 1 0 0 = 1 Equation 2 0 1 0 = 2 Equation 3 0 0 1 = 183 RHS = = 7/2 1 5/2 RHS Pivoting in General A pivot can be carried out on any element of a matrix, and we don’t have to be solving a system of equations. Look what happens if we pivot on the element in position 2,4. 2 2 -1 2 2 2 -1 2 -1 1 1 -1 2 1 0 2 6 02 -1 3 02 42 2 -2 -1 1 2 -2 -1 1 1 -1 1 3 -1 -2 24 01 01 Now, column 4 has the correct form, a 1 in position 2 and 0s elsewhere. 19 Solving a Systems of Equations Using Matrix Notation Consider the n x n system If you think that pivoting is a fast way of describing a system of equations, then wait till you see this. Ax=b and assume that A has full row rank. The solution is given by x = A-1b, where A-1 is the inverse of matrix A. 15.053 does not assume a knowledge of matrix algebra, but it does assume a knowledge of solving systems of linear equations and pivoting. Roadrunner 20 On Systems of Equations Usually, if we solve an system of n equations with n unknowns, we will obtain a unique solution. But this is not always true. This system has no feasible solution. Pivot first on entry (1, 1) x1 x2 x3 RHS Equation 1 1 1 0 = 1 Equation 2 0 1 1 = 2 Equation 3 1 2 1 = 5 x1 x2 x3 Equation 1 1 1 0 = 1 Equation 2 0 1 1 = 2 Equation 3 0 1 1 = 4 RHS x1 x2 x3 Equation 1 1 0 -1 = -1 Equation 2 0 1 1 = 2 Equation 3 0 0 0 = 2 Pivot next on entry (2, 2) RHS 21 There is no feasible solution The third Equation reads: 0 x1 + 0 x2 + 0 x3 = 2. There is no feasible solution for this, nor for the original system. x1 x2 x3 RHS Equation 1 1 0 -1 = -1 Equation 2 0 1 1 = 2 Equation 3 0 0 0 = 2 22 On Systems with an Infinite Number of Solutions This system has an infinite number of solutions. x1 x2 x3 RHS Equation 1 1 1 0 = 1 Equation 2 0 1 1 = 3 Equation 3 1 2 1 = 4 x1 x2 x3 Equation 1 1 1 0 = 1 Equation 2 0 1 1 = 3 Equation 3 0 1 1 = 3 Pivot first on entry (1, 1) Pivot next on entry (2, 2) RHS x1 x2 x3 Equation 1 1 0 -1 = -2 Equation 2 0 1 1 = 3 Equation 3 0 0 0 = 0 RHS 23 This system has an infinite number of solutions The third equation reads: 0 x1 + 0 x2 + 0 x3 = 0, which is always true. And there are an infinite number of solutions to the first two equations. x1 x2 x3 RHS Equation 1 1 0 -1 = -2 Equation 2 0 1 1 = 3 Equation 3 0 0 0 = 0 If you give me a value for x3, I can give you values for x1 and x2 that solve this system of equations. For example, if x3 = 0, then x1 = -2 and x2 = 3. If x3 = 1, then x1 = -1 and x2 = 2. You can try for yourself. Where did those solutions come from? Ollie, the computationally wise owl. Tim, the turkey 24 On finding the set of optimal solutions. Tim, it may help you if we rewrite the equations, with x3 on the right hand side. x1 x2 x3 Equation 1 1 0 -1 = -2 Equation 2 0 1 1 = 3 Equation 3 0 0 0 = 0 You can also solve systems of equations at the same IFORS website given earlier Equation 1. x1 = -2 + x3 Equation 2. x2 = 3 - x3 RHS If we substitute in x3 = 1, we get x1 = -1 x2 = 2 Ollie 25 Last Slide Well, that concludes this tutorial on solving systems of equations. I hope that it was helpful. I want to give special thanks to my friends Ollie, Tim, Nooz, and Professor Orlin for their help in this presentation. Finally, let us all thank Gauss and Jordan, without whom there would have been nothing to present. 26