CO227 Lecture 14: co 227 lec14
30 May 2017
School
Department
Course
Professor
Document Summary
Input: a linear program in standard equality form and a feasible basis b. Output: an optimal solution or show unboundedness (with certificate) Note: we still have to deal with some issues: how do we deal with infeasibility, how do we find a feasible basis, can we simplify finding canonical forms? (takes a lot of work) There is a potential issues if t = 0. Although we may want to increase the value of a variable, it is possible we cannot to maintain feasibility. (this could occur if a basic variable equals zero). In rare cases, the basis could continue to change but non improvement is made in the solution until the algorithm returns to an old basis it has worked on before. To prevent this, one can always choose the smallest element to leave the basis. The lexicographic simplex method uses this extra step.
