A brief review of Linear Algebra and Linear Programming ModelsReview of Linear AlgebraElementary Facts about VectorsMatrix MultiplicationMultiplying MatricesSlide 6Elementary Facts about Solving EquationsSolving a System of EquationsTo solve the system of equations:The fundamental operation: pivotingPivot on a23Jordan Canonical Form for an m x n matrixSlide 13There is an easily determined solution for every choice of non-basic variables.Another Jordan Canonical Form for the same system of equationsApplicationsA Financial ProblemReturn on investments (undiscounted dollars)Formulate Sarah’s problem as an LPFormulating the modelThe modelFAQ. Do the units matter? How does one choose the units?Addressing Problems in PracticeUnderstanding the modelScaling up: dealing with large problemsSlide 26Enrichments of the modelSummaryMIT and James Orlin © 20031A brief review of Linear Algebra and Linear Programming ModelsDeveloped by James OrlinMIT and James Orlin © 20032Review of Linear AlgebraSome elementary facts about vectors and matrices.The Gauss-Jordan method for solving systems of equations.Bases and basic solutions and pivoting.MIT and James Orlin © 20033Elementary Facts about Vectors[ ]1 2 3 4v v v v v=is called a row vector.1234� �� �� �=� �� �� �tvvvvvThe transpose of v is a column vector.[ ]1 2 3 4w w w w w=is another row vector.The inner product of vectors w and v is given by:1 1 2 2 3 3 4 4v w v w v w v w v w= + + +oMIT and James Orlin © 20034Matrix Multiplication( )=ijA a ( )=ijB b( )= = �ijC c A B1=�=kkjnikjia bcSuppose that A has n columns and B has n rows.MIT and James Orlin © 20035Multiplying MatricesLet C = (cij) = AB. Then cij is the inner product of row i of A and column j of B. 21 22 2311 12 1331 32 33a a aAa a aa a a� �� �=� �� �� �132311 1221 2231 3332bbbb bB b bb b� �� �=� �� �� �For example, what is c23?23 21 13 22 23 23 33c a b a b a b= + +MIT and James Orlin © 20036Multiplying MatricesLet C = (cij) = A  B. Then each column of C is obtained by adding multiples of columns of A. 1 2 3 100 1234 5 6 10 4567 8 9 1 789� �� � � �� �� � � �� =� �� � � �� �� � � �� �� � � �1 2 3100 4 10 5 67 8 9�� �� ���� �� ��= + +�� �� ���� �� ���� �� ��Similarly, each row of C is obtained by adding multiples of rows of B.Elementary Facts about Solving Equations1 2 31 2 4 02 1 1 6x x x�� �� � � ��+ + =�� �� � � ��-�� �� � � ��Find a linear combination of the columns of A that equals b.Solve for Ax = b, where211 2 42 1 1A� �=� �-� �123xxxx� �� �� �� �� �=06b��=����23311 2 31 2 32 4 02 6x x xx x x+ + =+ - =MIT and James Orlin © 20038Solving a System of EquationsTo solve a system of equations, use Gauss-Jordan elimination.x1 x2 x3 x41 2 4 1 = 02 1 -1 -1 = 6-1 1 2 2 = -3MIT and James Orlin © 20039To solve the system of equations:12-12114-121-12===06-3x1x2x3x4Go to the animationMIT and James Orlin © 200310b1b2b3===a12a22a32a14a24a34a11a21a31a13a23a33The fundamental operation: pivotingPivot on a23x1x2x3x4===MIT and James Orlin © 200311b1b2b3===a12a22a32a14a24a34a11a21a31a13a23a33Pivot on a23What will be the next coefficient of b1? a32? of aij for i 2? x1x2x3x4===a22/a23a24/a23a21/a231b2/a23a11a11 =a11 –a13(a21/a23)00MIT and James Orlin © 200312-112100010-110===100Jordan Canonical Form for an m x n matrixThe remaining variable(s) are called non-basic.01-1x2x1x3x4There are m columns that have been transformed into unit vectors, one for each row. The variables in these columns are called “basic.”MIT and James Orlin © 200313-112100010-110===100Jordan Canonical Form for an m x n matrixIn the “basic solution”, the non-basic variables are set to 0. 01-1x2x1x3x4The basic solution is: x1 = 2, x2 = 1, x3 = -1 x4 = 0MIT and James Orlin © 200314-1104-23===There is an easily determined solution for every choice of non-basic variables.If we set x4 = 2, what solution do we get?0 -11 1-1 2x2x1x3x4If we set x4 = , what solution do we get?100010100We get a feasible solution to the system of equations for every choice of values for non-basic variables.MIT and James Orlin © 200315110-1104-23===00-23-3Another Jordan Canonical Form for the same system of equationsWhat are the “basic”variables? 1 0 -10 0 30 1 1x2x1x3x41What is the basic solution?MIT and James Orlin © 200316ApplicationsA Financial Model–an investment model over multiple time periods–goal: optimize the total revenues at the end of the time horizonMIT and James Orlin © 200317A Financial ProblemSarah has $1.1 million to invest in five different projects for her firm. Goal: maximize the amount of money that is available at the beginning of 2006. –(Returns on investments are on the next slide). At most $500,000 in any investment, except for CDs.Can invest in CDs, at 5% per year.MIT and James Orlin © 200318Return on investments (undiscounted dollars)A B C D EJan. 2003-1 - -1 -1 -Jan. 2004.4 -1 1.2 - -Jan. 2005.8 .4 - - -1Jan. 2006- .8 - 1.5 1.2MIT and James Orlin © 200319Formulate Sarah’s problem as an LPPayback for A: for every dollar invested in January of 2003, Sarah receives $.40 in January of 2004 and $.80 in January of 2005.FORMULATION. –STEP 1. Choose the decision variables –Let xA denote the amount in millions of dollars invested in A. Define xB, xC, xD, and xE similarly.–Let x3 denote the amount put in a CD in 2003. (Define x4 and x5 similarly)MIT and James Orlin © 200320Formulating the modelWith your partner formulate the LP model.Step 2. Formulate the objective function–put the objective function in words first. E.G. we are “minimizing cost” or “maximizing utility”Step 3. Formulate the constraints–Put the constraints in words firstMIT and James Orlin © 200321The modelMax z= .8 xB + 1.5 xD + 1.2 xE + 1.05 x5Subject to xA + xC + xD + x3 = 1.1 (Year 2003) .4 xA - xB + 1.2 xC + 1.05 x3 - x4 = 0 (Year 2004) .8 xA + .4 xB - xE + 1.05 x4 - x5 = 0 (Year 2005) 0  xj  .5 for j = A, B, C, D, E, 3, 4, 5 Excel SolutionMIT and James Orlin © 200322FAQ. Do the units matter? How does one choose the units?The units do not matter so long as one is careful to use units correctly. It