CO227 Lecture Notes - Lecture 10: Identity Matrix
30 May 2017
School
Department
Course
Professor
Document Summary
In general, there are several nice properties in this example we are taking advantage of: we can easily find a feasible solution because columns 5,3,6 of a forms the identity matrix. In the objective function , the coefficient of the non-zero variables (x 3,x5,x6) were zero. We can change those variables and not affect the objective value: we are changing one variable that has value zero at a time. Not how doing so made a non-zero variable go to zero. It is reasonable to assume for a feasible lp max {ctx| ax=b,x>=0} that the rows of a are linearly independent. If not, then either we have redundant equality constraints we do not need or the lp is infeasible. The rows of a are linearly dependent but that is because adding the 1 st two constraints gives the third constraint. Consider the system x1 + 3x2 = 5. The rows of a are linearly dependent, however the system has no solution.
