3. Linear Programming

3. Linear Programming 3.1 Linear Algebra Square n-by-n Matrix Solution of Simultaneous Linear Equations a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2 n xn b2 an1 x1 an 2 x2 ann xn bn Two ways of solving them directly: (1) determinants (Cramer's rule), which gives the solution as a ratio of two n n determinants; (2) elimination. Cramers CramersTheorem Theorem (Solution (Solutionof ofLinear

LinearSystems Systemsby byDeterminants) Determinants) IfIfaalinear linearsystem systemof ofnnequations equationsin inthe thesame samenumber number of ,,xxn ofunknowns unknownsax11x1x1,1, a12x2 n a1nxn b1 a21x1 a22x2 a2nxn b2

an1x1 an2x2 annxn bn has coefficient determinant DD= Dn D1 D2 hasaanonzero nonzero coefficient determinant =det detA, A,the the x , x

, , x ( Cramer's rule ) system has precisely one solution. This solution is 1 2 n systemDhas precisely one solution.

This solution is D D given givenby bythe theformulas formulas where whereDDkkisisthe thedeterminant determinantobtained obtainedfrom fromDDby by Gaussian Elimination Forward Elimination pivot 2u+ v+ w= 1 4u+ v

= -2 -2 u + 2 v + w = 7 Backward Substitution (1) (2) (3) Step 1: equation (2) +( 2) x equation (1) Step 2: equation (3) + (+1) x equation (1) 2u+ v+ w = 1 (4) (5) pivot (-1) v - 2 w = - 4 3v+2w = 8 (6) Step 3: equation (6) + (+3) x equation (5) 2u+ v+ w = 1 (7) - v - 2 w = -4 (8) - 4 w = -4

(9) w=1 v=2 u = -1 Elementary Transformation of Matrices (i) An elementary matrix of the first kind it an n n diagonal matrix formed by replacing the ith diagonal element of identity matrix I with a nonzero constant q. For example, if n 4, i 3 1 0 0 1 Q 0 0 0 0 det Q q 0 0 0 0

q 0 0 1 1 0 1 Q 0 0 0 0 0 1 0 0 0 1/ q 0 0 0 1

Elementary Transformation of Matrices (ii) An elementary matrix of the second kind is an n n matrix R formed by interchanging anytwo rows i and j of the identity matrix I. For example, if n 4, i 1 and j 3 0 0 R 1 0 0 1 0 1 0 0 0 0 0 0 0 1 det R 1 0

0 R 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 Elementary Transformation of Matrices (iii) An elementary matrix of the third kind it an n n matrix S formed by inserting the a nonzero constant s into the off-diagonal position (i, j ) of the identity matrix I. For example, if n 4, i 3 and j 1 1 0 S

s 0 det S 1 0 1 0 0 0 0 1 0 0 0 0 1 1

0 S 1 s 0 0 1 0 0 0 0 1 0 0 0 0 1

Elementary Row Operation Any row manipulation can be accomplished by pre-multiplication of elementary matrices! QA np : multiplication of all elements of the ith row in A by a constant q; RA np : interchange of the ith and jth row in A; SA np : addition of a scalar multiple s of the jth row to the ith row. 1 0 S1S 2 s1 0 1 0 S 21S1 1 0 0

0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 s2 0 0 0 1 1 0 0 0 0 1 0 s1 s2 0 1 0 0 0 1 0 0 0 0 1 1 0 s1 0 0 1 0 s2 0 0 0 1 1 0 0 0 0 1 0 s1

0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 s2 0 0 1 0 0 0 0

1 Elementary Column Operation Any column manipulation can be accomplished by post-multiplication of elementary matrices! A pn Q : multiplication of all elements of the ith column in A by a constant q; A pn R : interchange of the ith and jth column in A; A pnS : addition of a scalar multiple s of the jth column to the ith column. Gaussian Elimination = Triangular Factorization 2 1 1 u 1 Ax 4 1 0 v 2 b -2 2 1 w 7 3 elimination steps 2 1 1 u 1 Ux 0 1 2 v 4 c

0 0 4 w 4 upper triangular!!! Step 1: 2nd equation + ( 2) 1st equation S 21A 1 0 0 where, S 21 2 1 0 0 0 1 Step 2: 3rd equation + (+1) 1st equation S31S 21A 1 0 0 where, S31 0 1 0 1 0 1 Step 3: 3rd equation + (+3) 2nd equation S32S31S 21A where,

1 0 0 S32 0 1 0 0 3 1 U S 32S31S 21A S32S31S 21Ax S32S31S 21b Upper triangular Lower triangular c S32S 31S 21b 1 0 0 Let S S32S 31S 21 2 1 0 1 3 1 A S 1U S 1S 1S 1U LU 21 31

32 1 0 0 1 1 where L S 211S31 S32 2 1 0 1 3 1 Note that 2, -1 and -3 are the negative values of the multipliers used in the 3 elimination steps. Conclusions If no pivots are zero, the matrix A can be written as a product LU,i.e., Gaussian Elimination Triangular Factorization L is a lower triangular matrix with 1's on the main diagonal, i.e., see next page. U is an upper triangular matrix. The nonzero entries of U are the coefficients of the equations which appear after elimination and bef ore back-substitution. The diagonal entries of U are the pivots. 0

1 L e21 1 e31 e32 0 0 1 Thus, eij is the quantity that multiply row j when it is subtracted from row i to produce zero in the (i, j ) entry. Implications Solve: Ax n b n n 1, 2,3, (1) Obtain A LU

(2) Solve Lc n b n with forward substitution for c n (3) Solve Ux n c n with backward substitution for x n Row Exchange Ax b 1 0 A 0 0 2 3 4 0 5 6 0 d 6 c 7 8 1 0 R 24 A 0

0 2 3 4 c 7 8 0 d 6 0 5 6 If c 0, the problem is incurable and the matrix is called singular. Elimination with Row Exchange Assume A is nonsingular, then there exists a permutation matrix R that reorders the rows of A so that RA LU Round Off Error Consider 1.0 1.0

A ; 1.0 1.0001 0.0001 1.0 A 1.0 1.0 First Point : Some matrices are extremely sensitive to small changes, and others are not. The matrix A is ill-conditioned (i.e. sensitive); A is well-conditioned. A is "nearly" singular Singular matrix 1

1 1 1 1 1 A 1 1.0001 x1 2 2 (1) Ax b x2 0 2 2 x1 1 (2) Ax b x2 1 2.0001 No numerical methods can provide this sensitivity to small perturbations!!!

Second Point: Even a well-conditioned matrix can be ruined by a poor algorithm. 0.0001 1.0 x1 1.0 Ax 1.0 x2 2.0 1.0 Correct solution: 10000 x1 1.00010001 (round off after 9th digit) 9999 9998 x2 0.99989998 (round off after 9th digit) 9999 If a calculator is capable of keeping only 3 digits, then Gaussian elimination gives the

wrong answer!!! (0.0001) x1 x2 1 (A) x1 x2 2 (B) Eq. (B) - 10000 Eq.(A): (1.0 0.000110000.0) x1 (1.0 1.0 10000.0) x2 0 =2.0 1.0 10000.0 1.0 1.0 10000.0 9999.0 1.00 1.00E4 1.00E4 2.0 1.0 10000.0 9998.0 2.00 1.00E4 1.00E4 x2 1.00 (not too bad) Substituting into Eq.(A) x1 0.00 (This is wrong)

Third Point A computer program should compare each pivot with all the other possible pivots in the same column. Choosing the largest of these candidates, and exchanging the corresponding rows so as to make this largest value pivot, is called partial pivoting. Solution of m Equations with n Unknowns (m

0 0 6 2 elementary row operation S32 1 3 3 2 U 0 0 3 1 Echelon Form! 0 0 0 0 Echelon Form Solution of m Equations with n Unknowns (m

3 0 elementary row operation S31S 21 1 3 3 2 0 0 3 1 0 1 6 2 elementary row operation R 23 1 3 3 2 U 0 1 6 2 0 0 3 1 CONCLUSION To any m-by-n matrix A there corresponds 1.a square (i.e., m-by-m) permutation matrix R, 2.a square (i.e., m-by-m) lower triangular matrix L with unit diagonal, and 3.an m-by-n echelon matrix U, such that

RA = LU Homogeneous Solution for Example 1 b 0 Ax 0 pivot Ux 0 u 1 3 3 2 0 v Ux 0 0 3 1

0 w 0 0 0 0 0 y u, w : basic variables (correspond to the pivots) v, y : free variables Express basic variables in terms of free variables! 1 3w+y=0 w y 3 u 3v 3w 2 y 0 u 3v y 3v y 3 1 v 1 0 v y x

y/3 0 1 / 3 y 0 1 All solutions are linear combinations of -3 -1 1 0 and 0 -1/3

0 1 Within the 4-D space of all possible x, the solution of Ax = 0 form a 2-D subspace. the nullspace of A Subspace A subspace of a vector space is a subset that satisfies two requirements: 1. If we add any two vectors x and y in the subspace, the sum x+y is still in the subspace. 2. If we multiply any vector x in the subspace by any scalar c, the multiple cx is still in the subspace. Note that the zero vector belongs to every subspace. Conclusions Every homogeneous system Ax=0, if it has more unknowns than equations (n>m), has infinitely many nontrivial solutions. The dimension of nullspace is the number of

free variables (which is larger than than or equal to n-m>0). The nullspace is a subspace of R. Inhomogeneous Solution of Example 1 b 0 Ax LUx b Ux L 1b c u b1 1 3 3 2 v Ux 0 0 3 1 b2 2b1 c w 0 0 0 0 b3 2b2 5b1 y Note that the equations are inconsistent unless 5 b1 b3 2b2 5b1 2 b2 0 1 b3 In other words, the set of attainable vectors b

is not the whole of the 3-D space - it lies on a plane that is perpendicular to the vector [5 -2 1]T . Ax a1 a 2 a3 a 4 x b u 1 3 3 2 b1 2 6 9 5 v b w 2 1 3 3 0 b3 y ua1 va 2 wa3 ya 4 b 1 3 3 2 b1

u 2 v 6 w 9 y 5 b2 1 3 3 0 b3 Conclusion The system Ax=b is solvable if and only if the vector b can be expressed as a linear combination of the columns of A, i.e. n Ax x j a j b j 1

Note also that a 2 3a1 1 a 4 a1 a3 3 b ua1 va 2 wa3 ya 4 1 ua1 v 3a1 wa3 y a1 a3 3 1 u 3v y a1 w y a3 3 u

w 1 3 u 2 w 9 1 3 Conclusions Ax b can be solved iff b lies in the plane that is spanned by a1 and a3. The plane is a subspace of R m called column space of the matix A. The equation Ax = b can be solved iff b lies in the column space. u 1 3 3 2 1 v

Ax 2 6 9 5 5 b w 1 3 3 0 5 y u 1 3 3 2 1 v Ux 0 0 3 1 3 c w 0 0 0 0 0 y 1 3w y 3 w 1 y 3 u 3v 3w 2 y 1 u 2 y 3v u 2 3

1 v 0 1 0 x v y w 1 0 1/ 3 y 0 0 1 particular soln

homogeneous solution Ax=0 CONCLUSIONS Suppose the m-by-n matrix A is reduced by elementary operations and row exchanges to a matrix U in echelon form. Let there be r nonzero pivots; the last m-r rows of U are zero. Then there will be r basic variables and n-r free variables, corresponding to the columns of U with and without pivots respectively. Note that r m n CONCLUSIONS The nullspace, formed of solutions to Ax=0, has the n-r free variables as the independent parameters, i.e., its dimension is also n-r. If r=n ( i.e., m ), there are no free variables and

the null space contains only x=0. Solution always exists for every right side b iff r=m

Recently Viewed Presentations

• The boy's first outcry was a rueful laugh, As he swung toward them holding up the hand. Half in appeal, but half as if to keep. The life from spilling. Then the boy saw all— Since he was old enough...
• Students will start in the suburb of Upperby and follow a transect into the city centre. Along the way they will investigate changes in services, housing, environmental quality and quality of life. Once in the city centre students will investigate...
• Cysylltwch â Lesley er mwyn trefnu trafodaeth gyda thiwtoriaid y brifysgol. Darllenwch am y rhaglenni yn y dogfennau canlynol; ... Cyfleoedd Datblygu Arweinyddiaeth yn PCYDDS. You may know whether there are already official Welsh names for these publications, and if...
• Chapter 17 - from gene to protein. The information content of genes is in the form of specific sequences of nucleotides along the DNA strands. The DNA of an organism leads to specific traits by dictating the synthesis of proteins...
• In the case of ordinarily resident taxpayers, overseas assets are required to be reported in tax returns for the financial year 2015/16 and onwards, even if acquired from income not chargeable to tax in India. Failing this, a penalty of...
• Examples Mercury manometer is connected to an air duct to measure its insice pressure. The manometer deflection is 15mm. Atmospheric pressure is 100kPa. Find the duct's absolute pressure. Hg = 13,600kg/m3. Examples Refer figure. Find the manometer deflection.
• Grammar Daily Review: week six. Sentence: Copy the sentence below for week six. who likes to lie under the stars on clear nights. Monday Focus: Verb - action or linking AND is it present, past or future? Interrogative pronoun. Verbal...
• An object traveling in a circular motion is always changing its direction. Therefore, its velocity is always changing, so it is accelerating. The acceleration that occurs in circular motion is known as . centripetal acceleration.