imengus

Contents:

• Converting linear programs to simplex tableaus
• Steps for the simplex algorithm

Converting linear programs to simplex tableaus

The constraints of a linear program define an n-dimensional feasible region, where n = number of variables. Any point within this region will satisfy the constraints, but we are interested in the coordinates of a point at which an objective function P is maximised (or minimised.)

The simplex algorithm starts at the basic solution x1 = x2 = ... = 0, then checks each vertex of the feasible region in the direction that would increase (or decrease if minimise) P the fastest. When objective value P cannot be improved any further, i.e. the optimum vertex is found, the algorithm terminates.