"user manual"
Contents
1. Sec 2 11 Row Operations and Gaussian Elimination Consider a system of linear equations 21 2 9 2X3 0 229 823 8 4 92 3 9 1 2 1 The coefficient matrix of the system is 0 2 8 5 9 1 2 1 0 The augmented matrix of the system is 0 2 8 8 5 9 9 Note that the number of columns of the coefficient matrix of a given system equals the number of in that system Remark Given a matrix A we can construct a linear system having A as the augmented ma 2 1 trix For example the linear system we can recover from a matrix 1 7 is We are mainly interested in solving a given system i e finding the solution set of the system We will develop several methods to do so Ex 1 Consider systems T 2 73 0 T 2 T3 7 I 2 9 8r 8 and Il tq 2z3 l 4 d z 9r 9 r 4 System l is easier to solve indeed we can solve using backward substitution One idea to solve a general more complicated system such as I is to change it to a triangular system like I When we change the original system we should be careful not to change the solution set of the system But How Fact 1 scaling operation If we replace an equation in a linear system by a nonzero multiple of the equation the solution set remains unchanged Ex 2 Let 221 dz 2273 0 1 2 9 23 0 r 2 2 8r3 8 and T Zo 4r 4 421 5292. z y 2 22 2y 2z 2 From the example above we see that the following is generally true Theorem Two planes are either identical or parallel if and only if the x y z coefficients of one plane are common multiples respectively of the x y z coefficients of the other plane The interaction of three planes is much more complicated There are a number of possible con figurations and several not all possible configurations are shown in the following Ex 7 Show that the three planes have no points of intersection Ex 8 Show that the three planes 2x z have no points of intersection What is the difference between Ex 7 and Ex 8 y mz 2y 2z y z 2y z y z 5y 82 w The interaction of three planes can be summarized as follows Case 1 the system is inconsistent a Case 2 the system has a unique solution e Case 3 the system has infinitely many solution with 1 free variable Case 4 the system has infinitely many solution with 2 free variables h Two points in the xy plane determine a unique line Similarly if there are three points that do not all lie on a line then there is a unique plane containing the three points How do we find an equation of the plane Ex 9 Find an equation of the plane that contains the points 1 4 6 2 7 9 and 2 8 11 Sec 2 61 Linear Programming The Simplex Algorithm
3. 2 3 1203 0 0 2 2 7 1 1 6 2415 0 2 6 Ex 3 Given a linear system the row rank of the coefficient matrix is always the row rank of the augmented matrix Remark If A is an m x n matrix then the row rank of A is less than or equal to the minimum of m and n Theorem 1 A linear system is consistent if and only if the row rank of the coefficient matrix is equal to the row rank of the augmented matrix Ex 4 Find the value of k that makes the following linear system consistent 273 8 421 2529 1023 6 221 13x2 6x3 Ex 5 Find the relationship between a b and c for which the following system will be consistent z 9 3z a 2y z b r Idy z c We now turn to systems that have infinitely man solutions We start with an example Ex 6 Solve the following linear system 21 5X 2 3 3 721 432 3023 19 221 1275 823 4 In general how to represent the solution set when there are infinitely many solutions One way to do this is parametric representation The procedure can be described as follows Step 1 Step 2 Step 3 Step 4 Ex 7 Solve the following linear system 3X2 423 274 3 221 625 923 4 8 Ex 8 A dairy company makes breakfast lunch and dinner meals from a mixture of curds and whey The breakfast uses 10 ounces of curds and 40 ounces of whey per batch The lunch uses 20 ounces of curds and 90 ounces of whey
4. 810 minutes on the sewing machines and 180 square feet of leather Set up and solve the linear program to obtain the maximum profit from the available resources Ex 9 Pauls Pipe and Tobacco Shop blends Virginia Turkish and Mexican tobaccos into three aromatic house mixtures A packet of Wild has 6 ounces Virginia 4 ounces Turkish and 14 ounces Mexican Heather has 3 ounces Virginia 1 ounce Turkish and 2 ounces Mexican and Silk has 4 ounces Virginia 2 ounces Turkish and 8 ounces Mexican If Wild sells for 8 Heather for 10 and Silk for 16 per packet and if there are 32 ounces of Virginia 10 ounces of Turkish and 72 ounces of Mexican on hand set up and solve the linear program to find the amounts of Wild Heather and Silk that should be blended to maximize profit from the tobacco on hand Sec 2 71 Simplex Algorithm Additional Considerations Sometimes the simplex algorithm can fail Ex 1 Consider the following linear program maximize z 62 4 T3 subject to 221 23 lt 3 z 2 3 2 3 lt 3 1 222 423 4 6 z gt 0 z gt 0 z3 gt 0 The Simplex Algorithm for Minimum Programs Same requirements needed except that now we are looking for a minimum value Step 1 Select the most positive entry in the first row of the table The column that contains this entry is called the pivot column Step 2 Look at the quotients obtained by dividing each positive entry of the p
5. 923 9 421 529 923 9 then both I and I are equivalent to I In other words systems I I and T are essentially the same Notation Fact 2 interchange operation If we interchange two equations in a system the solution set remains unchanged Ex 3 Consider 2292 23 0 A 421 529 923 9 5 222 823 6 then is equivalent to I Notation Fact 3 replacement operation If we replace one equation in a system by the sum of itself and a multiple of another equation the solution set remains unchanged Ex 4 The system 21 2275 23 0 199 27 823 8 3x2 1323 9 is obtained by replacing of system I by of I Notation Definition Three operations described above are called elementary row operations Thus elemen tary row operations do NOT alter the solution set of the original system So how to change a general system to a triangular one Let s take system I as an example T 2 273 0 22o 23 0 222 623 5 222 823 8 421 529 923 9 312 1323 9 27 23 0 T 2 23 0 o tq 444 4 424 4 z 1373 9 T3 3 It is easy to find the solution to the last system x3 ny Now let s describe the process above in terms of the augmented matrices 1 2 12 0 1 2 1 0 0 2 8 1 0 2 8 8 4 5 9 9 0 3 13 9 From the last
6. per batch The dinner uses 30 ounces of curds and 30 ounces of whey per batch There are 300 ounces of curds and 500 ounces of whey on hand Find the number must be an integer of batches that will use the entire supply Definition A linear system is called homogeneous if all of the constant terms are 0 z T r 4r3 221 X9 9x3 221 T2 23 0 is a homogeneous system Is this consistent Definition The trivial solution to a homogeneous system is the zero solution all variables equal Zero Theorem 2 Every homogeneous system is consistent Theorem 3 For any homogeneous system a If the row rank equals the number of variables then the trivial solution is the only solution b If the row rank is less than the number of of variables then there are infinitely many solutions Ex 10 Without doing any computation explain why the following homogeneous system must have an infinite number of solutions then solve the system 311 629 T3 24 7X5 27o 223 3X4 ls 221 dz 523 824 4z Sec 2 41 Euclidean 3 Space In chapter 1 we considered linear programs involving only two variables It is not too hard to solve these linear programs because when we have two variables we can graph the feasibility region in the xy plane If we have 3 or more variables the problem gets complicated because it is now hard if not impossible to vis
7. rows 2 001 and 3 then it will be in echelon form 1234 0 111l Ex 9 0001 is in echelon form 00 0 0 Roughly speaking matrices in echelon form look like x indicates that any number can be present TE 1 x x x l x x OT 0 00 15 0001 x 00 0 0 As mentioned before the significance of row echelon form is that when the augmented matrix of a system is reduced to this form via row operations the solution of the system is easily obtained by backward substitution Remark There is one flaw in row echelon forms a row echelon form of a matrix is not unique In other words if two people start with a given matrix and perform different sequences of row oper ations until a row echelon form is obtained their final matrices may not be identical To resolve this problem we consider reduced row echelon form Sec 2 21 Reduced Echelon Form Let s go back to system I in Ex 1 in the previous section The augmented matrix associated with system I is 1 2 1 0 1 4 4 0 0 1 1 2 1 0 1 0 7 8 100 2 Ry R 2R2 Bi R 7 Rz 0 1 4 4 So v zn 0 1 4 4 eee 0 10 16 Ro R2 4R3 0 0 23 00 1 3 001 3 The system we get from the last matrix is and we immediately get a unique solution z 29 2 16 and x3 3 The reason we do not need backward substitution is that the matrix 100 010 001 is even nicer than echelon matrices To be more precise vve need a definition Definition Recall that a ma
8. In this section we consider linear programs involving two or more variables Requirements Needed to Use the Simplex Algorithm 1 The linear program must be looking for a maximum value 2 The constraint inequalities are all of the form less then or equal to a positive number 3 All variables are non negative One of the key ideas in the simplex algorithm is to convert inequalities into equations Ex 1 If we have an inequality such as 27 y lt 7 then a nonnegative value can be added to the left hand side to bring it up to the value 7 If we introduce a nonnegative variable z then we can write the inequality as the equation 2r y z 7 where z gt 0 In other words the new variable z takes up the slack For this reason z is called a slack variable Ex 2 Use slack variables to convert the constraints 4z lt 20 2 T lt 35 120 2220 into a system of linear equations with nonnegative variables Ex 3 Consider the following linear program maximize z 18x 20 32 3 subject to z 2 2x 3 lt 22 321 T 2X9 423 lt 40 3x1 T2 223 x 14 z gt 0 z gt 0 x3 gt 0 First we write the objective function as the equation z 18x 2025 3224 Then we introduce the nonnegative slack variables za x5 e to convert the inequalities into the system of linear equations 21 2X9 223 X 22 321 22 423 2X5 40 321 273 z 14 Putting th
9. apply as stated in the theorem above Calculator commands We can use a calculator to find the reduced echelon form of a given matrix Look up the function rref in your User s Manual Ex 9 Solve the following system using rref Use your calculator to find the rref of the augmented matrix 1 229 23 4 321 92 2 3 1 221 22 323 l Ex 10 Solve the following system using calc 221 521 How should we interpret the result Ex 11 Solve the two systems 229 T3 4 321 729 2273 1 221 312 323 1 ulator 22 4T3 s 37 223 824 723 1 229 T3 2 and 3x 72 2 3 5 221 329 323 3 Sec 2 31 Consistency and Row Rank Recall that a system of linear equations is said to be consistent if it has one or infinitely many solutions A linear system is said to be inconsistent if it has no solutions Ex 1 Show that the following system is inconsistent 1 3 1 1 1 14 2 228 27 1 1 6 The reason the above system is inconsistent is that the bottom row of the rref is of the form 0000 1 which would mean that the corresponding equation is 0 1 This observation gives a simple but nice criterion for consistency of systems Definition The row rank of a matrix is the number of nonzero rows in a reduced row echelon form of the matrix Ex 2 Determine the row rank of each of the following matrices 1 3 1 1 1 123 2 4 2 7 14 2
10. e equations together we get the combined system 2 l8z 2022 93223 21 279 2273 2X4 22 321 279 473 25 40 321 X 2273 FE 14 From this system we have the following matrix 18 20 32 0 0 01 0 0 1 2 2 1 0 0J22 0 3 2 410 1 0140 0 3 1 2 0 0 1114 This matrix is called the initial simplex table Ex 4 Find the initial simplex table for the following linear program maximize z 821 629 subject to 221 42 lt 6 i T lt 4 z120 t220 Remark For a given linear program the initial simplex table should look like 1 x kx 0 0 0 x 11 0 lx x k 1 How the Simplex Algorithm Works Step 1 Select the most negative entry in the first row of the table The column that contains this entry is called the pivot column Step 2 Look at the quotients obtained by dividing each positive entry of the pivot column into the corresponding entry of the last column Select the entry that produces the smallest quotient In case of a tie choose either this number is called the pivot The row that contains the pivot is called the pivot row Step 3 pivoting step Using scaling operation make the pivot 1 Use replacement operations to get Os above and below the pivot Stopping Rule Repeat steps 1 3 until there are no more negative entries in the first row This last matrix is called the final simplex table Maximum Value The maximum value of z subject to the con
11. ivot column into the corresponding entry of the last column Select the entry that produces the smallest quotient In case of a tie choose either this number is called the pivot The row that contains the pivot is called the pivot row Step 3 pivoting step Using scaling operation make the pivot 1 Use replacement operations to get 0s above and below the pivot Stopping Rule Repeat steps 1 3 until there are no more positive entries in the first row This last matrix is called the final simplex table Minimum Value The minimum value of z subject to the constraints will be the last entry in the first row of the final simplex table Ex 2 Use the simplex algorithm to solve the linear program minimize z 42 1022 6273 subject to l z 422 8x3 lt 20 221 209 423 lt 6 421 209 223 lt 4 z gt 0 4220 z320 Finally we compare the simplex method to the geometric method we learned in Chapter 1 Ex 3 Solve the following linear program in two ways the geometric method and the simplex al gorithm maximize 2 4z subject to x 2y lt 6 5x 4y lt 20 xr gt 0 y20
12. matrix we recover a system 21 2279 23 T2 Axr3 4 03 3 and the solution of this new system is exactly the same as what we met before Remark This method is called the Gauss Jordan elimination Definition Two matrices are row equivalent if there is a sequence of elementary row operations that transforms one matrix into the other Ex 5 Solve the system 473 8 HI 221 3129 2273 521 8272 723 l 0 1 4 8 From the last matrix we recover a system Therefore system III is From the experience above we know that triangular or steplike matrices are good because the systems associated with such matrices are then easy to solve We want to define these nice matrices rigorously Definition A matrix is said to be in echelon form or row echelon form if it has the following four properties 1 The leftmost nonzero entry in each row is a 1 called leading 1 2 The entries below any leading 1 are all 0 3 The leading 1 for each row is to the left of the leading 1 for any row below it 4 Any row of all zeros is located below the rows that have leading 1s 1 4 0 1 Ex 6 0 1 1 3 is NOT in echelon form It violates condition 2 0 1 3 0 0120 Ex 7 1 2 3 0 is NOT in echelon form It violates condition If we switch rows 1 00 0 and 2 then it will be in echelon form 1200 Ex 8 0 0 0 is NOT in echelon form It violates condition If we switch
13. straints will be the last entry in the first row of the final simplex table Ex 5 Solve the linear program in Ex 3 above Ex 6 Solve the linear program in Ex 4 above In the previous examples we learned how to get the maximum value However when is the maximum obtained Recall the final simplex table of Ex 5 1 22 0 0 4 0 12 256 0 2 1 O 1 0 1 8 0 3 0 0 0 1 2 12 0 20 1 0 1 3 From this table we recover a system The variable z is maximized when z 24 z 0 which forces us to have z 5 and Therefore z z 2 3 L4 5 Z6 256 0 8 3 0 12 0 is a solution to the yeter which has maximum z value 0 8 3 0 12 0 is called the basic feasible solution Finally dropping the slack variables we conclude that z has the maximum of 256 at 0 8 3 Ex 7 When is the maximum of the objective function in the linear program in Ex 6 obtained Ex 8 Use PIVOT program Leather Products Ltd has cutting machines sewing machines and a supply of leather with which they make shoes purses and coats Suppose that the articles use the machines and leather as given in the table below Shoes Purse Coat Cutting machines min 10 20 50 Sewing machines min 40 10 50 Leather square ft 2 4 10 Further let there be a profit of 22 on shoes 15 on purses and 50 on a coat and suppose that there are 600 minutes available on the cutting machines
14. trix is said to be in echelon form if it has the folloving four prop erties 1 The leftmost nonzero entry in each row is a 1 called leading 1 2 The entries below any leading 1 are all 0 3 The leading 1 for each row is to the left of the leading 1 for any row below it 4 Any row of all zeros is located below the rows that have leading 1s If a matrix in echelon form satisfies the following additional condition then it is said to be in reduced echelon form or reduced row echelon form 5 All entries above any leading 1 are zero In other words each leading 1 is the only nonzero number in its column 123 4 0 11i1il Ex 1 000115 echelon form but NOT in reduced echelon form because it violates 00 condition 1000 0110 Ex 2 0001 8 reduced echelon form 0000 1030 0110 Ex 3 Hov about 000117 0000 Roughly speaking matrices in echelon form look like x indicates that any number can be present OHO x x ooo x xox 4 Put the following matrix in reduced echelon form 1 24 5 O 13 1 7 0 00 1 2 Why do people like reduced echelon forms more than echelon forms Theorem The reduced row echelon form rref associated with a matrix is uniquely determined mh 0 2 4 6 2 EN Method 1 1 0 3 1 1 3 0 2 4 6 2 Method 2 1 0 3 1 Z277 1 1 3 0 Thus we get the same result no matter what sequence of row operations we
15. ualize the problem However if there are only three variables then the situation is not too bad Recall that a typical line in the zy plane is of the form az by In the xyz space the role of lines is now replaced by planes A typical plane in the ryz plane is of the form az by cz d Of course some of the coefficients can be zero For example if a b d 0 and c 1 then we have z 0 which means the Ex 1 Graph the first quadrant portion ie gt 0 y gt 0 of the line 2x 3y 12 How do we find the intercepts of a plane Ex 2 Find the intercepts of the plane 4z 8y 22 16 and graph the first octant portion i e x gt 0 y gt 0 z gt 0 of the plane Definition The equation of a plane written in the form is called the intercept form Ex 3 Find the intercept form of planes 3x 4y 24z 12 and z 5y 8z 6 Sketch the first octant portion of these planes Not every plane has the intercept form Ex 4 Sketch the first octant portion of the plane z 3y 32 0 Going back to the two dimensional case let s consider the interaction of two lines in the xy plane Ex 5 Solve each of the following systems by graphing them z 2y 4 x 2y 6 x 2y 6 4 22 y 18 nd 2 4y 5 M 2x 4y 12 Now we consider the interaction of two planes Ex 6 Solve each of the following systems IV z y z 1 vit ty mz y z 3 z Ty 2 3
Download Pdf Manuals
Related Search