Linear Programming — Simplex Method & Graphical Solution

Linear programming finds the best value of a linear objective — maximum profit or minimum cost — subject to linear constraints. In a two-variable problem, the graphical method finds the feasible region and checks its corner points. In larger problems, the simplex method applies the same corner-point idea algebraically.

When this method applies

Use linear programming only when both the objective and the constraints are linear. If a relationship bends, curves, or depends on products like $xy$, it is not a linear program. The general shape is

subject to linear inequalities such as

together with conditions like $x_i \ge 0$ when negative values make no sense. The set of all points satisfying every constraint is the feasible region, and the question is: among those feasible points, which gives the best objective value? Typical settings are production planning, transportation, staffing, blending, scheduling, and budget allocation — anywhere decisions compete for limited resources under linear limits.

The procedure, step by step

1. Define the variables. Choose what each variable counts, e.g. units of product $A$ and product $B$.
2. Write the objective. Express the quantity to maximize or minimize as a linear function.
3. List the constraints. Translate each limit into a linear inequality, and add nonnegativity conditions where they apply.
4. Graph the feasible region. Draw each constraint on the $xy$-plane; the overlap of all allowed regions is the feasible region.
5. Find the corner points. Locate the vertices where boundary lines intersect.
6. Evaluate the objective at each corner and pick the best value.

Why corner points are enough

For linear programs, one fact drives the whole method: if an optimal solution exists, at least one optimal solution sits at a corner point of the feasible region. Linear objectives create parallel level lines such as $3x + 5y = k$; as you slide that line toward larger profit, the last point still touching the feasible region is where the maximum occurs. Usually that last touch is a single vertex. If the objective line is parallel to a boundary edge, every point on that edge can be optimal — but there is still at least one optimal corner. That is why you check vertices instead of every point in the shaded region.

Full worked example: solve graphically

A shop makes products $A$ and $B$. Profit per unit is $3$ for $A$ and $5$ for $B$. Machine time allows at most $8$ hours, with $A$ using $1$ hour and $B$ using $2$ hours each. Assembly allows at most $5$ hours, with each unit of either using $1$ hour.

Let $x$ be units of $A$ and $y$ units of $B$. Maximize

subject to

The feasible corner points are $(0,0)$, $(5,0)$, $(0,4)$, and $(2,3)$. The point $(2,3)$ comes from solving the boundary equations $x + 2y = 8$ and $x + y = 5$; subtracting gives $y = 3$, then $x = 2$.

Evaluate the objective at each corner:

• At $(0,0)$, $P = 0$
• At $(5,0)$, $P = 15$
• At $(0,4)$, $P = 20$
• At $(2,3)$, $P = 21$

So the maximum profit is $P = 21$ at $(x,y) = (2,3)$. That is the whole graphical method in one sentence: graph the region, find the corners, evaluate the objective.

Simplex method intuition

The graphical method is practical only with two variables, or sometimes three if you can picture a 3D region. Real optimization problems often carry many variables, so drawing the feasible region stops being realistic. The simplex method keeps the same corner-point logic but does it algebraically: in broad terms it moves from one feasible corner point to an adjacent one that improves the objective, and it halts when no adjacent move gives a better value. A clean mental model:

• Graphical method: see the corner points
• Simplex method: navigate the corner points without drawing them

That is the intuition, not the full algorithm — the actual procedure uses a tableau or equivalent algebraic form to decide which variable enters and which leaves at each step. The model is only as good as its assumptions, too: if the real relationship is far from linear, or the variables must be integers, a plain linear program may be just a starting point.

Where each step traps people, plus a self-check

A frequent trap is confusing feasible with optimal: a point can satisfy every constraint and still not optimize the objective — feasible only means allowed. Another is forgetting nonnegativity; leaving out $x \ge 0$ or $y \ge 0$ can change the problem when the variables are quantities. A third is assuming answers must be whole numbers — plain linear programming permits fractions, so counts like trucks or workers need an integer-programming model. A fourth is assuming every problem has a finite best: some programs are infeasible (no point satisfies all constraints) and others are unbounded (the objective improves without limit). And graphing stops being the right tool once there are many variables.

For your own pass, take a small word problem with two products, two resource limits, and a profit function. Define the variables, graph the constraints, and test the corner points. Once that clicks, the simplex method reads as the same logic extended to higher dimensions.