Linear Programming Formula

Linear programming optimizes a linear objective subject to linear inequality or equality constraints.

The Formula

max⁡/min⁡  cTx  subject to  Ax≤b

Ask yourself: Am I optimizing a linear objective over a region bounded by linear inequalities, with the answer expected at a corner?

Quick example

max⁡z=3x+2y subject to x+y≤4,  x≥0,  y≥0 — optimal at a corner.

Notation

max⁡z or min⁡z with linear constraints.

What this formula means

Linear programming optimizes a linear objective subject to linear inequality or equality constraints.

Finding the optimum is like pushing a ruler across a polygon cut from paper, keeping it parallel to the profit line. The last bit of paper the ruler touches before it leaves is a corner, because the ruler and the polygon's edges are all straight. If the profit rule were curved, the last point touched could be in the middle of a side.

Formal view

Find x∈Rn that optimizes cTx over a polyhedral feasible set {x∣Ax≤b}.

Worked examples

Example 1

medium
Maximize z=3x+2y subject to x+y≤4, x≥0, y≥0.
Show solution

Answer

z=12 at (4,0)

First step

1.
Step 1: Identify the feasible region: the triangle with vertices (0,0), (4,0), (0,4).

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

hard
Minimize z=2x+5y subject to x+2y≥6, x+y≥4, x≥0, y≥0.

Example 3

medium
Maximize P=5x+6y subject to x+y≤8, 2x+y≤12, x,y≥0.

Common mistakes

  • Searching the interior for the best value - the optimum of a linear objective lies at a vertex of the feasible region; evaluate the objective at each corner
  • Forgetting hidden constraints like x≥0 - real quantities are often nonnegative, which changes the corners
  • Mixing up maximize and minimize - read whether you want the largest or smallest objective value before comparing corners

Why this formula matters

Airlines, factories and farms use linear programming to decide how many of each product to make, which planes fly which routes, and how to mix animal feed at the lowest cost. The corner principle turns infinitely many choices into a short list to check. Without it, people guess at a good mix, or pick the point where the main constraints cross, and can miss a corner that earns more.

Frequently asked questions

What is the Linear Programming formula?

Linear programming optimizes a linear objective subject to linear inequality or equality constraints.

How do you use the Linear Programming formula?

Use it when a problem asks you to maximize or minimize one quantity, such as profit, cost or time, subject to several limits written as linear inequalities. Look for two or more decision variables and phrases like at most 40 hours or at least 30 g of protein. If there is no quantity to optimize, you only need to graph the inequalities. If the objective contains squares or products of the variables, the corner rule no longer applies.

What do the symbols mean in the Linear Programming formula?

max⁡z or min⁡z with linear constraints.

Why is the Linear Programming formula important in Math?

Airlines, factories and farms use linear programming to decide how many of each product to make, which planes fly which routes, and how to mix animal feed at the lowest cost. The corner principle turns infinitely many choices into a short list to check. Without it, people guess at a good mix, or pick the point where the main constraints cross, and can miss a corner that earns more.

What do students get wrong about Linear Programming?

The procedure for linear programming is the easy part; the trap is searching the interior for the best value. Asking "Am I optimizing a linear objective over a region bounded by linear inequalities, with the answer expected at a corner?" first is what keeps a correct-looking calculation from being attached to the wrong concept.

What should I learn before the Linear Programming formula?

Before studying the Linear Programming formula, you should understand: inequalities, systems of equations, constraint system.