Linear Programming — Simplex Method & Graphical Solution

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

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

Linear Programming Definition

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

subject to constraints such as

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

plus similar linear inequalities, together with conditions like $x_i \ge 0$ when negative values do not make sense.

The set of all points that satisfy every constraint is called the feasible region. Linear programming asks: among those feasible points, which one gives the best objective value?

How the Graphical Method Works

If there are only two decision variables, you can draw each constraint on the $xy$-plane. The overlap of all allowed regions is the feasible region.

Each point in that region is a valid solution. The objective function assigns a value to each one.

For linear programs, one key fact is this: if an optimal solution exists, then at least one optimal solution occurs at a corner point of the feasible region. That is why the graphical method focuses on vertices instead of checking every point in the shaded region.

Worked Example: Solve a Linear Programming Problem Graphically

Suppose a shop makes two products, $A$ and $B$.

• Profit per unit of $A$: $3$
• Profit per unit of $B$: $5$
• Machine time limit: each unit of $A$ uses $1$ hour, each unit of $B$ uses $2$ hours, and at most $8$ hours are available
• Assembly limit: each unit of $A$ uses $1$ hour, each unit of $B$ uses $1$ hour, and at most $5$ hours are available

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

Maximize

$$P = 3x + 5y$$

subject to

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Find the corner points

From the axes and the constraint lines, the feasible corner points are

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

The point $(2,3)$ comes from solving the boundary equations

$$x + 2y = 8,\quad x + y = 5$$

Subtracting gives $y = 3$, and then $x = 2$.

Test the objective at each corner

Compute the profit at each corner point:

• 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 graphical method in one sentence: graph the feasible region, find the corner points, and evaluate the objective there.

Simplex Method Intuition

The graphical method is practical only when there are two variables, and sometimes three if you are willing to picture a 3D region. Real optimization problems often have many variables, so drawing the feasible region is no longer 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 another that improves the objective, and it stops when no adjacent move gives a better value.

So a good mental model is:

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

This description is the intuition, not the full algorithm. The actual simplex procedure uses a tableau or an equivalent algebraic form to decide which variable enters and leaves at each step.

Why Corner Points Matter

Linear objective functions create level lines such as

$$3x + 5y = k$$

for different values of $k$. As you slide that line in the direction of larger profit, the last point where it still touches the feasible region is where the maximum occurs.

In many pictures, that last touch happens at a single vertex. If the objective line is parallel to a boundary edge, multiple points on that edge can all be optimal. In that case, there is still at least one optimal corner point.

Common Mistakes

Confusing feasible with optimal

A point can satisfy every constraint and still fail to maximize or minimize the objective. Feasible only means allowed.

Forgetting nonnegativity conditions

If $x$ and $y$ represent quantities you produce or ship, negative values usually do not make sense. Leaving out $x \ge 0$ or $y \ge 0$ can change the problem.

Assuming every answer must be a whole number

Plain linear programming allows fractional values. If the variables must be whole numbers, such as number of trucks or number of workers, you need an integer-programming model or an extra integrality condition.

Assuming every problem has a best answer

Some linear programs are infeasible, which means no point satisfies all constraints. Others are unbounded, which means the objective can improve without limit. You only get a finite optimum when the constraints actually contain the problem enough.

Using the graphical method when there are too many variables

Once there are many variables, graphing is no longer the right tool. That is where simplex or other optimization methods become necessary.

When Linear Programming Is Used

Linear programming is used when decisions compete for limited resources and both the goal and the limits can be modeled linearly. Typical examples include production planning, transportation, staffing, blending, scheduling, and budget allocation.

The model is only as good as its assumptions. If the real relationship is not close to linear, or if the variables must be integers, a plain linear program may be only a starting point.

Try a Similar Problem

Take a small word problem with two products, two resource limits, and a profit function. Write the variables, graph the constraints, and test the corner points yourself. Once that idea clicks, the simplex method becomes much easier to understand because it is extending the same logic to higher dimensions.