Linear Programming (LP) β€” Beginner Guide

Last updated: β€’ Sources β€’ Methodology

Linear Programming (LP) β€” Beginner Guide: Objective, Constraints, Feasible Region, and How LP Solvers Find the Optimum

Linear programming (LP) is the core β€œmaximize/minimize subject to linear constraints” model behind planning, scheduling, blending, and allocation. This guide explains the pieces you’ll see in any LP, what the solver output means, and how to spot infeasible, unbounded, or multiple-optimum cases.

To practice as you read, solve the same models in our Linear Programming calculator. If your constraints include = or β‰₯ and you want a hand method, see Two Phase Simplex Method (Worked Example).

On this page

Quick takeaway: A linear program (LP) chooses decision variables x to maximize or minimize a linear objective (like profit or cost) subject to linear constraints (like capacity, demand, budgets). If the constraints admit at least one solution, the LP is feasible. If the objective can increase forever while staying feasible, the LP is unbounded. If there’s no feasible solution at all, it’s infeasible. For the practical β€œwhat to fix first” list, use Unbounded vs Infeasible LP (Fix Checklist).

The LP model: objective, constraints, variables

Beginner

Canonical LP template (what you’ll see everywhere)

maximize or minimize   cα΅€x
subject to             Ax ≀ b   (or =, β‰₯)
                       x β‰₯ 0    (or variable bounds l ≀ x ≀ u)

Think of it as: choose x (your decisions) to make cα΅€x (your goal) as large/small as possible, while satisfying Ax ≀ b (your limitations).

When LP is not enough: if some decisions must be integers (like β€œopen/close” or β€œchoose exactly k projects”), you need Integer Linear Programming (ILP/MILP) and typically branch-and-bound.

Beginner β†’ intermediate

Variable bounds matter more than beginners expect

Many β€œmysterious” solver results come from missing bounds. If a variable can grow without limit and it helps the objective, your model can become unbounded. See Upper Bounds in Linear Programming for the practical ways bounds prevent unrealistic solutions.

Feasible region and why corner points matter

Core idea

LP optimum occurs at an extreme point (corner) when an optimum exists

In two variables, constraints define a polygonal region. The LP optimum (if it exists and the feasible set is nonempty) happens at a corner point (also called an extreme point).

That’s why the Graphical Method for LP (2 Variables) works: it checks a small set of corners rather than infinitely many points.

Simplex intuition: the simplex method β€œwalks” along corners of the feasible region, improving the objective at each step, until no improving move exists.

Standard form + slack/surplus/artificial variables

Setup

Converting constraints for simplex-type methods

Constraint type Equality form Extra variables Typical method next
aα΅€x ≀ b aα΅€x + s = b Slack s β‰₯ 0 Standard simplex start often works
aα΅€x β‰₯ b aα΅€x βˆ’ s + a = b Surplus s β‰₯ 0, Artificial a β‰₯ 0 Two-phase simplex or Big‑M method
aα΅€x = b aα΅€x + a = b Artificial a β‰₯ 0 Two-phase simplex or Big‑M method

The β€œwhat to add and why” is covered in Slack / Surplus / Artificial Variables.

Possible solver outcomes (what they mean)

Interpretation

Optimal vs infeasible vs unbounded vs multiple optima

Status What it means Common cause What to do next
Optimal Feasible solution found and objective is best possible Model is well-posed Validate constraints and units; run scenario checks
Infeasible No solution satisfies all constraints simultaneously Contradictory requirements, sign errors, missing flexibility Use Infeasible vs Unbounded checklist
Unbounded Objective can improve forever while staying feasible Missing upper bounds; missing β€œcost” constraints Add realistic bounds (upper bounds guide)
Multiple optimal solutions More than one solution gives the same best objective value Objective parallel to a binding constraint edge/face See Multiple Optimal Solutions in LP

Questions people ask about linear programming (LP basics)

People ask

What is linear programming (LP) in simple words?

Linear programming is a method to choose decision variables (like production amounts) that maximize profit or minimize cost, while satisfying linear constraints (like capacity, labor, or budget limits). β€œLinear” means both the objective and constraints are linear expressions in the variables.

People ask

What are decision variables, constraints, and the objective function in an LP?

Decision variables are what you control (the x values). Constraints are limits that must hold (the inequalities/equalities). The objective function is what you optimize (maximize/minimize), like profit = 5x1 + 3x2.

People ask

How do you solve a linear programming problem?

For two variables, you can solve by the graphical method (compute corner points). For larger problems, solvers use simplex or interior-point methods. To compute solutions instantly, use the Linear Programming calculator.

People ask

Why does an LP optimum occur at a corner point?

With linear constraints, the feasible set is a polyhedron (a polygon in 2D). A linear objective increases in a fixed direction, so if an optimum exists it will be achieved at an extreme point (corner) of that shape.

People ask

What does β€œunbounded” mean in linear programming?

Unbounded means there is no finite best objective value: you can increase (or decrease) the objective without limit while still satisfying all constraints. Missing realistic variable bounds is one of the most common causesβ€”see Upper Bounds in Linear Programming.

People ask

What does β€œinfeasible” mean in linear programming?

Infeasible means the constraints contradict each other so no solution exists. A quick way to debug is to check signs (≀ vs β‰₯), units, and whether you accidentally forced two requirements to be simultaneously true. Use Unbounded vs Infeasible LP (Fix Checklist).

People ask

What’s the difference between linear programming and integer linear programming?

In LP, variables can be fractional (e.g., x = 2.7). In integer linear programming (ILP/MILP), some variables must be integers or binaries. That changes the solve method: ILPs typically require branch-and-bound instead of pure simplex.

People ask

How do you solve linear programming in Excel Solver or Python?

If you need a spreadsheet workflow, see Linear Programming in Excel Solver. For code-based modeling, see Linear Programming in Python (PuLP/OR Tools).

People ask

What is the primal–dual relationship in linear programming?

Every LP has a dual LP that provides bounds and shadow-price interpretation. If you want the intuition (and why it matters for sensitivity), see Primal–Dual Relationship in LP.

Worked examples (fully solved)

Worked examples

Expand only the example you need

Each example below is collapsible (collapsed by default) to keep the page scannable while remaining fully indexable. All examples can be verified in the LP calculator.

Example 1 β€” Graphical method linear programming example (maximize profit; 2 variables)

Problem:

maximize   z = 3x1 + 2x2
subject to x1 +  x2 ≀ 4
           x1 + 2x2 ≀ 6
           x1, x2 β‰₯ 0

Step 1: Find corner points (extreme points)

In 2D, corner points come from intersections of constraint boundaries and axes. Consider these candidates:

  • Axis corners: where x1 = 0 or x2 = 0
  • Intersection of the two lines: x1 + x2 = 4 and x1 + 2x2 = 6

Step 2: Compute the candidates

A) (0,0) is feasible.

B) On x2 = 0:

x1 + 0 ≀ 4  β‡’ x1 ≀ 4
x1 + 0 ≀ 6  β‡’ x1 ≀ 6
So the farthest feasible point on the x1-axis is (4,0).

C) On x1 = 0:

0 + x2 ≀ 4   β‡’ x2 ≀ 4
0 + 2x2 ≀ 6  β‡’ x2 ≀ 3
So the farthest feasible point on the x2-axis is (0,3).

D) Intersection of the two binding constraints:

x1 +  x2 = 4
x1 + 2x2 = 6
Subtract first from second: x2 = 2
Then x1 = 4 βˆ’ 2 = 2
Intersection point: (2,2)

Step 3: Evaluate the objective at each corner

Corner point (x1, x2) Feasible? z = 3×1 + 2×2
(0,0) Yes 0
(4,0) Yes 12
(0,3) Yes 6
(2,2) Yes 10

The maximum objective value is z = 12 at (x1, x2) = (4,0).

Optimal solution (Example 1): x1 = 4, x2 = 0, and z* = 12.

If you want the same logic with a picture (and more corner-point practice), use Graphical Method for LP (2 Variables).
Example 2 β€” Unbounded linear programming example (feasible but objective has no maximum)

Problem:

maximize   z = x1 + x2
subject to x1 βˆ’ x2 β‰₯ 1
           x1, x2 β‰₯ 0

Step 1: Show feasibility (at least one feasible point exists)

Try (x1, x2) = (1,0): 

x1 βˆ’ x2 = 1 βˆ’ 0 = 1  β‰₯ 1  βœ“
x1, x2 β‰₯ 0 βœ“

So the LP is feasible.

Step 2: Show the objective can increase without limit

Consider the family of points: 

x2 = t
x1 = t + 1
for any t β‰₯ 0

Check feasibility:

x1 βˆ’ x2 = (t+1) βˆ’ t = 1 β‰₯ 1 βœ“
x1, x2 β‰₯ 0 βœ“

Compute objective:

z = x1 + x2 = (t+1) + t = 2t + 1

As t β†’ ∞, z β†’ ∞. Therefore there is no finite maximum.

Conclusion (Example 2): The LP is unbounded (feasible, but no finite optimal solution). A common fix is adding realistic variable boundsβ€”see Upper Bounds in Linear Programming.

Example 3 β€” Infeasible linear programming example (constraints contradict)

Problem:

minimize   z = x1 + x2
subject to x1 + x2 ≀ 1
           x1 + x2 β‰₯ 3
           x1, x2 β‰₯ 0

Step 1: Combine constraints to expose the contradiction

The two constraints require the same quantity x1 + x2 to satisfy: 

x1 + x2 ≀ 1
x1 + x2 β‰₯ 3

No real number can be simultaneously ≀ 1 and β‰₯ 3. Therefore, no point (x1,x2) can satisfy both constraints.

Conclusion (Example 3): The LP is infeasible (feasible region is empty). Use Unbounded vs Infeasible LP (Fix Checklist) to debug real models.

How to check your answer (calculator + next steps)

Tooling

Verify quickly, then choose the right method for your constraint types

Enter any of the worked examples into the Linear Programming calculator to confirm the optimum (or the infeasible/unbounded status).

Picking the right β€œnext” page: If you have β‰₯ or = constraints and want to understand simplex startup, read Two Phase Simplex Method or the Big‑M Method. If your model needs integers, switch to ILP/MILP.

Troubleshooting checklist (common modeling mistakes)

Troubleshooting

Symptom β†’ likely cause β†’ fix

What you observe Likely cause What to do next
Solver says unbounded Missing variable upper bounds; objective improves by increasing a variable forever Add realistic bounds and review upper bounds in LP
Solver says infeasible Contradictory constraints or sign errors (≀ vs β‰₯) Use infeasible/unbounded checklist and validate units
Solution contains β€œunexpected” fractions LP variables are continuous; fractional decisions are allowed If you need integers, use ILP/MILP (branch-and-bound)
More than one solution gives the same objective Objective parallel to a binding edge/face See multiple optimal solutions in LP
Hard to start simplex by hand (no obvious basis) = or β‰₯ constraints require artificials Use two-phase simplex and slack/surplus/artificial

Glossary

Glossary

  • Decision variables: quantities you choose (the x values).
  • Objective function: what you maximize/minimize (e.g., profit or cost).
  • Constraint: a linear rule the solution must satisfy (capacity, demand, budget).
  • Feasible region: the set of points that satisfy all constraints.
  • Extreme point (corner): a vertex of the feasible region; LP optima occur at corners when an optimum exists.
  • Slack variable: converts a ≀ constraint to equality.
  • Surplus variable: converts a β‰₯ constraint to equality (with a negative sign).
  • Artificial variable: temporary variable used to start simplex when no natural basis exists.
  • Unbounded: objective can improve without limit while remaining feasible.
  • Infeasible: no solution satisfies all constraints.

Disclaimer

This article and the associated calculators are provided for educational and informational purposes only. Optimization outcomes depend on modeling assumptions and input data and may not reflect real-world constraints unless you encode them correctly. This is not legal, financial, operational, or safety advice. For high-stakes decisions, validate results against domain requirements and consult a qualified professional. For details, read our full disclaimer.

Sources
  1. Wikipedia β€” Linear programming (overview, terminology)
  2. Google OR-Tools β€” Linear Programming documentation
  3. COIN-OR CLP β€” Open-source LP solver documentation (simplex implementations)
  4. SCIP Documentation β€” Linear optimization foundations and solver components
  5. GNU GLPK β€” LP/MIP solver project documentation