Linear Programming Formula

The Formula

max/min;c^Tx; ext{subject to};Axle b

When to use: You search the corners of an allowed region for the best score.

Quick Example

\max z = 3x+2y subject to x+y \le 4,\; x \ge 0,\; y \ge 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.

You search the corners of an allowed region for the best score.

Formal View

Find xinmathbb{R}^n that optimizes c^Tx over a polyhedral feasible set {xmid Axle b}.

Worked Examples

Example 1

medium
Maximize z = 3x + 2y subject to x + y \leq 4, x \geq 0, y \geq 0.

Solution

  1. 1
    Step 1: Identify the feasible region: the triangle with vertices (0,0), (4,0), (0,4).
  2. 2
    Step 2: Evaluate z at each vertex: z(0,0) = 0, z(4,0) = 12, z(0,4) = 8.
  3. 3
    Step 3: Maximum is z = 12 at (4, 0).
  4. 4
    Check: The coefficient of x is larger, so the maximum favors x ✓

Answer

z = 12 at (4, 0)
Linear programming optimizes a linear objective over a feasible region defined by linear inequalities. The optimal value always occurs at a vertex (corner point) of the feasible region.

Example 2

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

Common Mistakes

  • Testing random interior points instead of vertices
  • Reversing inequality directions when graphing constraints

Why This Formula Matters

Linear programming is used in scheduling, logistics, budgeting, and resource allocation worldwide.

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?

You search the corners of an allowed region for the best score.

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?

Linear programming is used in scheduling, logistics, budgeting, and resource allocation worldwide.

What do students get wrong about Linear Programming?

Students optimize outside the feasible region or forget to include all constraints when finding corner points.

What should I learn before the Linear Programming formula?

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

← Back to Linear Programming See All Examples Practice Problems