Linear Programming and the Simplex Procedure

By the end you should be able to: Formulate a real-world problem as a linear programme, solve a two-variable problem graphically, and state the principle behind the simplex method.

A linear programme is a constrained optimisation where the objective and every constraint are linear.

\text{maximise } Z = c_1x_1 + c_2x_2 \quad\text{subject to linear inequalities and } x_i \ge 0

Linearity is a strong restriction, and it buys a great deal: the solution always sits at a corner, and there is a systematic procedure to find it.

Formulating

Three questions, in order:

Decision variables — what am I choosing? ( $x$ chairs, $y$ tables)
Objective — what am I maximising or minimising? (profit)
Constraints — what limits me? (machine hours, material, demand)

Formulation is where marks are won and lost. A neat solution to the wrong model scores nothing.

The vocabulary

Term	Meaning
Feasible solution	Any point satisfying all constraints
Feasible region	The set of all such points
Optimal solution	The feasible point giving the best objective value
Corner (vertex)	A point where constraint boundaries intersect

Because the constraints are linear inequalities, the feasible region is a convex polygon — in three variables, a polyhedron.

The theorem that makes it work

If an optimum exists, it occurs at a corner of the feasible region.

Why: the objective $Z = c_1x+c_2y$ has straight, parallel level lines. Slide such a line across a convex polygon and the last point it touches on the way out is a vertex. Only if the line is exactly parallel to an edge does a whole edge tie — and then its endpoints, both corners, tie too.

The consequence is enormous. The feasible region contains infinitely many points, but only finitely many corners. Optimisation becomes a search over a finite list.

Graphical method, two variables

Draw each constraint boundary as a line
Shade the side satisfying the inequality
Identify the feasible region — the common overlap
Find the coordinates of every corner
Evaluate $Z$ at each and take the best

Reliable, and limited to two variables because you cannot draw more.

The simplex procedure

For more variables, the simplex method does what the graphical method does, without the picture:

Start at a feasible corner (often the origin, when it is feasible)
Examine the edges leaving that corner
Move along whichever most improves $Z$
Repeat until no leaving edge improves $Z$
That corner is optimal

It is hill-climbing along the edges of the polygon. Crucially, because the region is convex, a corner with no improving edge is not merely locally best — it is globally optimal.

That is a genuine contrast with steepest descent on a general function, where no such guarantee exists. The reward for linearity is a certificate of global optimality.

Possible outcomes

Outcome	Meaning
Unique optimum	One corner is best
Multiple optima	Objective parallel to an edge; every point on it is optimal
Unbounded	Feasible region open in the improving direction; $Z$ grows without limit
Infeasible	Constraints contradict; the region is empty

An unbounded result in a real problem usually means a constraint was left out of the model, not that infinite profit is available.