15.053 Lecture Notes - Lecture 8: Miliana, Canadian English, Linear Programming
Document Summary
A basic solution for a linear program in standard form is feasible if it is greater than or equal to zero. Not the midpoint of two other feasible points. Recall: if a linear program with non-negativity constraints has an optimum solution, it has an extreme point optimum. Theorem: a solution for a linear program in standard form is a basic feasible solution if and only if it is an extreme point. All variables are greater than or equal to zero. To stay feasible, always pivot on a positive coef cient. A tableau in canonical form basic feasible solutions. Speci ed nonbasic variable a is the coef cient of x in constraint i of the tableau is the right hand side in constraint i of the tableau x is the basic variable for the jth constraint. We will express the edge or ray as a set of solutions, de ned for each in a speci c range.
