CO227 Lecture Notes - Lecture 6: Linear Combination, Slack Variable

• School: University of Waterloo
• Department: Combinatorics and Optimization
• Course: CO227
• Professor: Patrick Roh

Document Summary

There are many ways an lp can be formulated: we can maximize or minimize the objective function, the constraints can be formulated as equalities or inequalities. Should we use x = y or x y = 0: variables can be non-negative (x>=0) or we may allow negative values. Any algorithm we use to solve lps must we use to solve lps must deal with all these cases. In order to do so, we will convert any lp into a standard structure called standard equality form (sef) This form has 3 requirements: we always maximize the objective function, constraints must be equalities (no inequalities) where the left hand side is just a linear combination, the variables must be non-negative. For our example we can represent the variables with a single vector. Since the objective function is linear, if we let a vector c represent the coefficient of the objective function: The equality constraints are just a system of linear equations.