1. What Is Linear Programming?

Linear Programming (LP) is a mathematical optimization framework for maximizing or minimizing a linear objective function subject to linear constraints.

A standard LP can be written as:

max⁡  cTx\max \; c^T xmaxcTx

subject to

Ax≤b,x≥0Ax \le b,\quad x \ge 0Ax≤b,x≥0

where:

  • x∈Rnx \in \mathbb{R}^nx∈Rn: decision variables

  • c∈Rnc \in \mathbb{R}^nc∈Rn: objective coefficients

  • A∈Rm×nA \in \mathbb{R}^{m\times n}A∈Rm×n, b∈Rmb \in \mathbb{R}^mb∈Rm: constraint matrix and vector

Key properties:

  • The feasible region is a convex polytope.

  • If an optimal solution exists, it occurs at a vertex (corner point) of the feasible region.

2. LP Modeling Workflow

Most LP problems can be formulated using the following fixed procedure:

Step 1. Define decision variables

Example:

  • x1x_1x1​: quantity of product A

  • x2x_2x2​: quantity of product B

Step 2. Write the objective function

Profit → maximize
Cost → minimize

max⁡40x1+30x2\max 40x_1 + 30x_2max40x1​+30x2​

Step 3. Write constraints

Derived from resources, budgets, capacities, or requirements.

Step 4. Add non-negativity constraints

x1≥0,x2≥0x_1 \ge 0,\quad x_2 \ge 0x1​≥0,x2​≥0

Rule of thumb:

Variables → Objective → Constraints → Non-negativity

3. Converting to Standard Form

The Simplex algorithm requires the LP to be in the form:

max⁡cTx,Ax≤b,x≥0\max c^T x,\quad Ax \le b,\quad x \ge 0maxcTx,Ax≤b,x≥0

Any LP can be converted using three rules.

Rule 1: Minimization → Maximization

Multiply the objective by −1.

Rule 2: “≥” constraints → “≤”

Multiply the entire constraint by −1.

Rule 3: Free variables

If a variable is unrestricted in sign:

x=x+−x−,x+,x−≥0x = x^+ - x^-,\quad x^+,x^- \ge 0x=x+−x−,x+,x−≥0

4. Slack, Surplus, and Artificial Variables

Slack variables (for ≤ constraints)

Ax≤b⇒Ax+s=b,s≥0Ax \le b \Rightarrow Ax + s = b,\quad s \ge 0Ax≤b⇒Ax+s=b,s≥0

They represent unused resources and provide initial basic variables.

Surplus variables (for ≥ constraints)

Ax≥b⇒Ax−e=b,e≥0Ax \ge b \Rightarrow Ax - e = b,\quad e \ge 0Ax≥b⇒Ax−e=b,e≥0

Artificial variables

Used when:

  • Constraints are equalities

  • Constraints are “≥”

In these cases, no obvious initial basic feasible solution (BFS) exists.

Artificial variables are temporarily introduced to start Simplex.

5. Big-M Method (M Method)

To eliminate artificial variables, we penalize them in the objective.

For maximization:

max⁡cTx−Ma\max c^T x - M amaxcTx−Ma

For minimization:

min⁡cTx+Ma\min c^T x + M amincTx+Ma

where:

  • aaa is an artificial variable

  • MMM is a very large positive constant

This forces artificial variables to zero in the optimal solution.

If any artificial variable remains positive at optimum, the original LP is infeasible.

6. Geometry of LP

Each linear constraint defines a half-space.
Their intersection forms a polytope.

Important consequences:

  • The feasible region is convex.

  • Linear objectives attain optima at vertices.

  • Possible outcomes:

    • Unique optimum

    • Multiple optima (objective parallel to an edge)

    • Infeasible problem

    • Unbounded objective

7. Basic Feasible Solutions (BFS)

Given:

Ax=b,x≥0,A∈Rm×nAx = b,\quad x \ge 0,\quad A \in \mathbb{R}^{m\times n}Ax=b,x≥0,A∈Rm×n

Choose mmm linearly independent columns of AAA as basic variables.
Set remaining n−mn-mn−m variables to zero and solve.

If all variables are non-negative, the result is a basic feasible solution.

Key theorem:

Every vertex of the feasible region corresponds to a BFS, and vice versa.

The Simplex algorithm moves from one BFS to another.

8. The Simplex Algorithm (Conceptual View)

Simplex performs a directed walk along vertices of the feasible polytope.

At each iteration:

  1. Choose an entering variable (improves objective)

  2. Choose a leaving variable (ratio test)

  3. Pivot to obtain a new BFS

  4. Repeat until no improvement is possible

Termination condition:

  • All reduced costs satisfy optimality → current BFS is optimal.

9. Worked Example 1 (LP Formulation)

Problem

A factory produces two products.

  • Profit: A = 40, B = 30

  • Machine hours: A uses 2, B uses 1 (total ≤ 100)

  • Labor hours: A uses 1, B uses 2 (total ≤ 80)

Formulate the LP.

Solution

Let:

  • x1x_1x1​: units of A

  • x2x_2x2​: units of B

Objective:

max⁡40x1+30x2\max 40x_1 + 30x_2max40x1​+30x2​

Constraints:

{2x1+x2≤100x1+2x2≤80x1≥0,  x2≥0\begin{cases} 2x_1 + x_2 \le 100 \\ x_1 + 2x_2 \le 80 \\ x_1 \ge 0,\; x_2 \ge 0 \end{cases}⎩⎨⎧​2x1​+x2​≤100x1​+2x2​≤80x1​≥0,x2​≥0​

10. Worked Example 2 (Standard Form + Big-M)

Problem

min⁡3x1−2x2\min 3x_1 - 2x_2min3x1​−2x2​

subject to:

x1−x2≥1,x2 freex_1 - x_2 \ge 1,\quad x_2 \text{ free}x1​−x2​≥1,x2​ free

Step 1. Convert min to max

max⁡−3x1+2x2\max -3x_1 + 2x_2max−3x1​+2x2​

Step 2. Convert ≥ to ≤

−x1+x2≤−1-x_1 + x_2 \le -1−x1​+x2​≤−1

Step 3. Split free variable

x2=x2+−x2−,x2+,x2−≥0x_2 = x_2^+ - x_2^-,\quad x_2^+,x_2^- \ge 0x2​=x2+​−x2−​,x2+​,x2−​≥0

Substitute:

Objective:

max⁡−3x1+2x2+−2x2−\max -3x_1 + 2x_2^+ - 2x_2^-max−3x1​+2x2+​−2x2−​

Constraint:

−x1+x2+−x2−≤−1-x_1 + x_2^+ - x_2^- \le -1−x1​+x2+​−x2−​≤−1

Now the problem is in standard form.

11. Summary

Linear Programming optimizes linear objectives over linear constraints.
Its geometry guarantees that optima lie at vertices.

The Simplex algorithm exploits this by moving between basic feasible solutions.