15.053 Lecture Notes - Lecture 7: Linear Programming
Document Summary
Row operations that do not change the set of solutions. A solution is feasible if it satis ed the equations. Gaussian elimination modi es the equations in a way that: it does not alter the set of feasible solutions, the equivalent equations are easy to solve. Examples of elementary row operations: multiply a constraint by a constant, add a multiple of a constraint to another constraint, swap constraints. In this case, there will either be one unqiue solution or none. Step 1: make the coef cients for x in the three equations 1, 0, and 0 respectively by adding multiples of the rst equation (called a pivot) Have a column for the right hand side. If there is at least one solution, there is an in nite number of solutions. Basic variables: m variables with m linearly independent columns. In this case, let x , x , x be basic variables and so x and x are the nonbasic variables.