Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 38 ยท Getting Started

What Is Linear Programming?

Learn what linear programming is: decision variables, a linear objective, linear constraints and the feasible region, with a small production example you can run.

Linear programming (LP) is a way to make the best possible decision when your choices are limited by resources. You describe the decision as numbers you can choose (the decision variables), say what "best" means with one formula (the objective), and list the limits as inequalities (the constraints). Everything is linear: no squares, no products of variables, just sums of variables times constants.

LP is the workhorse of operations research (OR), the discipline that uses mathematics to run factories, airlines, power grids and supply chains. This course builds the ideas from scratch in Python: we model problems, write our own solvers, and then compare with the professional-grade solver inside SciPy. Everything in the runnable examples uses real Python, NumPy and SciPy in your browser.

A first problem

A small bakery sells bread and cakes. Each batch of bread earns 40 dollars of profit and each batch of cakes earns 30. The bakery has these limits per day:

  • Oven time: a bread batch needs 2 oven hours, a cake batch needs 1, and 100 oven hours are available.
  • Labor: each batch needs 1 labor hour, and 80 labor hours are available.
  • The flour supplier delivers enough for at most 40 bread batches.

How many batches of each should the bakery make to earn the most?

Translate it into math

Let x be the number of bread batches and y the number of cake batches. These are the decision variables.

TEXT
maximize    40x + 30y          (profit)
subject to  2x +  y <= 100     (oven hours)
             x +  y <=  80     (labor hours)
             x      <=  40     (flour)
             x, y   >=   0     (no negative production)

That is a complete linear program. The objective 40x + 30y is a linear function; each constraint is a linear inequality; the last line, the non-negativity constraints, says you cannot bake a negative number of batches.

The four ingredients

Ingredient In the bakery General idea
Decision variables x, y Quantities you control
Objective function 40x + 30y One number to maximize or minimize
Constraints oven, labor, flour Linear limits (<=, >=, =)
Bounds x, y >= 0 Sign restrictions on variables

A choice of (x, y) that satisfies every constraint is feasible. The set of all feasible points is the feasible region. The best feasible point is the optimal solution, and its objective value is the optimal value.

Linear means the model assumes proportionality (twice the bread uses twice the oven time) and additivity (the total oven time is the sum of the parts). Real life is only approximately like this, and good modelers check that the approximation is reasonable.

Checking points by hand

Before solving anything, you can test any candidate plan. The code below defines the bakery model with NumPy and evaluates a few plans: whether each is feasible and what profit it earns.

Python Test candidate plans

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that (30, 50) breaks the oven limit (2*30 + 50 = 110) and (45, 0) breaks the flour limit. Among the feasible plans, (20, 60) earns the most so far. But is it the best of all plans? There are infinitely many feasible points, so we cannot try them all. LP theory gives a precise answer, which we build up over this course.

Letting a solver do it

SciPy ships scipy.optimize.linprog, which uses the HiGHS solver. It minimizes by convention, so to maximize we minimize the negative objective.

Python Solve the bakery LP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver reports 20 bread and 60 cake batches for a profit of 2600. The slack array shows unused capacity: oven and labor are exactly used up (slack 0) while the flour constraint has 20 spare units. Constraints with zero slack are called binding; they are the ones that actually limit the profit.

Why optimal solutions sit at corners

If you plot the feasible region, it is a polygon with straight edges. The objective 40x + 30y is a tilted plane, and the largest value over a polygon always occurs at a corner (a vertex). That single geometric fact is why the simplex method works, and we explore it next lesson.

flowchart LR
  A["Real situation"] --> B["Decision variables"]
  B --> C["Objective + constraints"]
  C --> D["Solve (graph, simplex, solver)"]
  D --> E["Interpret and act"]
  E --> A

The OR cycle: model, solve, interpret, and refine the model as you learn what it misses.

Possible outcomes

Every LP ends in exactly one of three ways:

  1. Optimal: a best solution exists (usually at a vertex).
  2. Infeasible: the constraints contradict each other, so no point qualifies.
  3. Unbounded: you can improve the objective forever (usually a sign of a missing constraint in the model).

The lesson Unbounded and infeasible problems shows how to detect each.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these is NOT allowed in a linear program?

    Products of variables make the model nonlinear. Sums of constants times variables, with <=, >= or =, are all fine.
  2. 2. What is a feasible solution?

    Feasible means every constraint (and bound) holds. Optimal is the best feasible point.
  3. 3. linprog minimizes by default. How do you maximize 40x + 30y with it?

    Maximizing f is the same as minimizing -f; the optimal value is then -res.fun.
  4. 4. A constraint has slack 0 at the optimum. It is called

    A binding constraint holds with equality at the optimum; it is using up its resource completely.

Summary

  • An LP has decision variables, a linear objective, linear constraints and bounds.
  • Feasible points satisfy all constraints; the optimum is the best feasible point.
  • linprog minimizes, so negate the objective to maximize.
  • Binding constraints have zero slack and limit the objective.
  • The outcome is optimal, infeasible or unbounded.

Next: The Graphical Method