Model real decisions with linear and integer programming, networks, queues, simulation and decision trees, then present the results so managers act on them.

Optimization & Operations Research

Write one sentence describing the decision, who makes it and for what time period (for example, one week).

Define each decision variable with a symbol, a plain-English meaning and a unit, such as "x = loaves baked per day".

Write the objective: what you maximize or minimize, as a sum of numbers times variables. Note the unit (dollars, hours).

List every limit or requirement in words, then write each one as an inequality or equation. Add the non-negativity constraints.

Check units on both sides of every constraint, and check the direction (<= for limits, >= for requirements).

Rewrite the model in matrix form: the vector c, the matrix A and the vector b, turning any >= row into <= by multiplying by -1.

Test one sensible guess (for example, x = 10, y = 5): does it satisfy every constraint, and what is the objective value?

List which of the four LP assumptions (proportionality, additivity, divisibility, certainty) your model might break, and how much that matters.

## Why it matters

Operations research (OR) is the craft of turning a messy decision into a precise model, solving the model, and turning the answer back into advice. How many trucks to send where, which projects to fund, how many nurses to schedule on each shift: these are all choices made under limits of money, time, people and capacity.

The hardest and most valuable step is not the solving. Solvers are fast and free. The hard part is **formulation**: deciding what you control, what you want, and what stops you. A wrong formulation solved perfectly still gives a wrong answer. This lesson teaches the three-part recipe that every linear program (LP) follows.

## The three parts of a model

1. **Decision variables**: the quantities you choose. Give each a symbol, a plain-English meaning and a unit. "x1 = number of tables built this week" is good. "x1 = tables" is not, because it hides the time period.
2. **Objective function**: the single number you want to maximize (profit, throughput) or minimize (cost, distance, delay), written in terms of the variables.
3. **Constraints**: the limits, written as equations or inequalities in the variables. Resource limits (`<=`), requirements (`>=`), balances (`=`), and the **non-negativity** constraints (`x >= 0`) that are easy to forget.

A model is **linear** when the objective and every constraint are sums of constants times variables: no `x * y`, no `x^2`, no `if`.

## Worked example 1: a furniture workshop

A small workshop builds tables and chairs. Each table earns 70 in profit and each chair earns 50. A table needs 4 hours of carpentry and 2 hours of painting. A chair needs 3 hours of carpentry and 1 hour of painting. This week there are 240 carpentry hours and 100 painting hours.

**Variables.** `x` = tables built this week, `y` = chairs built this week.

**Objective.** Maximize profit:

```text
maximize   70x + 50y
```

**Constraints.**

```text
4x + 3y <= 240     (carpentry hours)
2x +  y <= 100     (painting hours)
x >= 0, y >= 0
```

Read each line aloud with units: "4 hours per table times x tables, plus 3 hours per chair times y chairs, is at most 240 hours." If the units on both sides do not match, the constraint is wrong.

In matrix form the same model is `maximize c @ x subject to A @ x <= b, x >= 0` with

```text
c = [70, 50]
A = [[4, 3],
     [2, 1]]
b = [240, 100]
```

This `c, A, b` layout is exactly what solvers expect, and you will use it in the next two lessons.

## Worked example 2: a minimum-cost feed blend

A farm mixes two feeds. Feed P costs 0.30 per kg and has 8 g of protein and 2 g of fibre per kg. Feed Q costs 0.20 per kg with 4 g of protein and 3 g of fibre per kg. The daily mix must supply at least 640 g of protein and 300 g of fibre.

**Variables.** `p` = kg of feed P per day, `q` = kg of feed Q per day.

```text
minimize   0.30p + 0.20q
subject to 8p + 4q >= 640    (protein, g)
           2p + 3q >= 300    (fibre, g)
           p >= 0, q >= 0
```

Notice the direction flipped: requirements are `>=`. Many solvers accept only `<=`, so you multiply both sides by -1: `-8p - 4q <= -640`.

## The assumptions behind "linear"

An LP quietly assumes four things. Check them before you trust the answer.

- **Proportionality**: twice the tables use twice the hours and earn twice the profit. Volume discounts break this.
- **Additivity**: the hours for tables and chairs simply add. Shared set-up time breaks this.
- **Divisibility**: 12.5 chairs is allowed. When it is not, you need integer programming (module 2).
- **Certainty**: every number is known. When demand or times are random, you need the tools of module 3, or sensitivity analysis (module 4).

## Common mistakes

- **Variables that are outcomes, not choices.** "Profit" is not a decision variable; it is computed from the decisions.
- **Missing time periods or units.** "Hours" per week or per day? Kilograms or tonnes?
- **Forgetting non-negativity.** Without `x >= 0`, a solver may happily "build" minus 20 chairs.
- **Writing the wrong inequality direction** for requirements versus limits.
- **Sneaking in non-linear terms**, such as price that depends on quantity, without noticing.
- **Modelling everything.** A good first model is small. Add detail only when the decision changes because of it.

## Quick recap

- Every LP has decision variables (with units), one objective, and constraints including `x >= 0`.
- Write each constraint in words first, then in symbols, and check that the units match.
- The matrix form `c, A, b` is what solvers read.
- Linear models assume proportionality, additivity, divisibility and certainty.

## Try it

Open the **Do** tab and formulate a small model of your own on paper, then write it in `c, A, b` form.


Turn a business decision into decision variables, an objective and constraints.

Formulating models

Intro to Linear Programming

Operational Research 'ORigin Story'

## Why it matters

With two decision variables you can draw an LP and see its answer. That picture explains the single most important fact about linear programming: **if an LP has an optimal solution, one of them sits at a corner of the feasible region.** The simplex method, which solvers have used since the 1940s, is a clever way to walk from corner to corner in many dimensions. Understanding it lets you read solver output, spot unbounded or infeasible models, and explain results with confidence.

## The graphical method

Take the workshop from the last lesson:

```text
maximize   70x + 50y
subject to 4x + 3y <= 240   (carpentry)
           2x +  y <= 100   (painting)
           x >= 0, y >= 0
```

1. **Draw each constraint as a line.** Replace `<=` with `=`. The carpentry line crosses the axes at `(60, 0)` and `(0, 80)`. The painting line crosses at `(50, 0)` and `(0, 100)`.
2. **Shade the side that satisfies the inequality.** Test the origin: `0 <= 240` is true, so the feasible side contains `(0, 0)`.
3. **The feasible region** is where all the shaded parts overlap, including `x >= 0` and `y >= 0`. Here it is a four-sided shape.
4. **Find the corners** by intersecting pairs of lines and keeping only the points that satisfy every constraint.
5. **Evaluate the objective at each corner** and pick the best.

Where do the two resource lines cross? Solve `4x + 3y = 240` and `2x + y = 100`. From the second, `y = 100 - 2x`. Substitute: `4x + 300 - 6x = 240`, so `x = 30` and `y = 40`.

| corner | profit `70x + 50y` |
|---|---|
| (0, 0) | 0 |
| (50, 0) | 3,500 |
| (0, 80) | 4,000 |
| (30, 40) | **4,100** |

Build 30 tables and 40 chairs for a profit of 4,100. The point `(60, 0)` is a crossing of the carpentry line with the x-axis, but it breaks the painting limit, so it is not a corner of the region.

Why corners? Draw the **iso-profit line** `70x + 50y = k`. Increasing `k` slides the line outward, parallel to itself. The last point of the region it touches is a corner (or a whole edge, when the objective is parallel to a constraint: then there are many optimal solutions).

## Special cases to recognise

- **Infeasible**: the constraints have no point in common. For example `x + y <= 2` and `x + y >= 5`.
- **Unbounded**: the region is open in the direction of improvement, so the objective can grow forever. In practice this almost always means a missing constraint.
- **Multiple optima**: the objective is parallel to a binding edge. Any point on that edge is optimal.

## The simplex method in one page

Enumerating every corner works for two variables but explodes with more: `m` constraints in `n` variables can have up to "m + n choose n" corners. Simplex is smarter.

1. Turn each `<=` into an equation with a **slack variable**: `4x + 3y + s1 = 240`. Slack is unused capacity.
2. Start at the origin, where the slacks are the **basic** variables (`s1 = 240`, `s2 = 100`) and `x = y = 0`.
3. **Choose an entering variable**: one whose increase improves the objective. A common rule picks the most negative entry in the objective row of the tableau.
4. **Ratio test**: increase it until the first constraint becomes tight. For each row with a positive entry in that column, compute `right-hand side / entry`; the smallest ratio wins, and that row's basic variable **leaves**.
5. **Pivot**: rewrite the equations so the entering variable is basic. Geometrically, you have moved along an edge to a neighbouring corner.
6. Repeat until no variable improves the objective. That corner is optimal.

For the workshop, `x` enters first (70 is the larger profit). Ratios: carpentry `240 / 4 = 60`, painting `100 / 2 = 50`. Painting is tighter, so we move to `(50, 0)`. In the next step `y` enters and we arrive at `(30, 40)`. Two pivots, done.

The tableau for the start looks like this (bottom row holds the negated objective):

```text
        x    y   s1   s2 | rhs
s1      4    3    1    0 | 240
s2      2    1    0    1 | 100
obj   -70  -50    0    0 |   0
```

You will write the full tableau method in numpy in the next lesson.

## Common mistakes

- **Keeping intersection points that are not feasible.** Every candidate corner must satisfy every constraint.
- **Forgetting the axes.** `x = 0` and `y = 0` are constraints too, and they create corners.
- **Using negative entries in the ratio test.** Only positive column entries limit how far a variable can increase.
- **Reading "unbounded" as good news.** It means the model is missing a real-world limit.

## Quick recap

- An LP's optimum (if one exists) is at a corner of the feasible region.
- Graphical method: draw lines, find feasible corners, evaluate the objective.
- Simplex moves from corner to better corner using slack variables, an entering variable, the ratio test and a pivot.
- Watch for infeasible, unbounded and multiple-optimum models.

## Try it

In the **Do** tab, write Python that finds every feasible corner of a two-variable LP and picks the best one.


Solve a two-variable linear program by checking its corner points and see how the simplex method moves between them.

Graphical method and simplex

Linear Programming 1: Maximization -Extreme/Corner Points (LP)

Intro to Simplex Method | Solve LP | Simplex Tableau

## Why it matters

Real models have hundreds or millions of variables. Nobody solves those by hand. An OR analyst's day-to-day work is writing a model in code, handing it to a **solver**, checking the solver's status, and reading the answer. Python has two popular, free routes: `scipy.optimize.linprog` for models already in matrix form, and **PuLP** for writing models with named variables and constraints. This lesson shows both, then has you build a small simplex solver in numpy so the solver is no longer a black box.

## The running example: a furniture shop

A shop makes desks, tables and chairs, with profits of 60, 30 and 20.

| resource | desk | table | chair | available |
|---|---|---|---|---|
| lumber (board-feet) | 8 | 6 | 1 | 48 |
| finishing (hours) | 4 | 2 | 1.5 | 20 |
| carpentry (hours) | 2 | 1.5 | 0.5 | 8 |

```text
maximize   60d + 30t + 20c
subject to 8d +   6t +    c <= 48
           4d +   2t + 1.5c <= 20
           2d + 1.5t + 0.5c <= 8
           d, t, c >= 0
```

## Route 1: scipy's linprog

`linprog` always **minimizes**, and it takes constraints as `A_ub @ x <= b_ub` (plus optional `A_eq @ x == b_eq`). To maximize profit, minimize its negative.

```python
import numpy as np
from scipy.optimize import linprog

c = np.array([-60, -30, -20])          # negate: linprog minimizes
A_ub = np.array([[8, 6, 1],
                 [4, 2, 1.5],
                 [2, 1.5, 0.5]])
b_ub = np.array([48, 20, 8])

res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=[(0, None)] * 3, method="highs")
print(res.status, res.message)
print(res.x)          # [2. 0. 8.]
print(-res.fun)       # 280.0  (undo the negation)
```

Always check `res.status` (0 means an optimal solution was found; other codes mean infeasible, unbounded or a stopped run) before you use `res.x`. With the HiGHS methods, `res.ineqlin.marginals` holds the **dual values** of the `<=` constraints, which module 4 explains as shadow prices. For a minimization they are zero or negative; because you negated the objective, flip their sign to read them as "extra profit per extra unit of resource".

## Route 2: PuLP

PuLP lets you write the model the way you would on paper. It ships with the open-source CBC solver.

```python
import pulp

prob = pulp.LpProblem("furniture", pulp.LpMaximize)
d = pulp.LpVariable("desks", lowBound=0)
t = pulp.LpVariable("tables", lowBound=0)
c = pulp.LpVariable("chairs", lowBound=0)

prob += 60 * d + 30 * t + 20 * c, "profit"
prob += 8 * d + 6 * t + c <= 48, "lumber"
prob += 4 * d + 2 * t + 1.5 * c <= 20, "finishing"
prob += 2 * d + 1.5 * t + 0.5 * c <= 8, "carpentry"

prob.solve(pulp.PULP_CBC_CMD(msg=False))
print(pulp.LpStatus[prob.status])                     # Optimal
print(d.value(), t.value(), c.value())                # 2.0 0.0 8.0
print(pulp.value(prob.objective))                     # 280.0
print(prob.constraints["finishing"].pi)               # shadow price
```

Named constraints make reports readable, and changing `lowBound=0` to `cat="Integer"` or `cat="Binary"` turns the model into an integer program (next module). Both scipy and PuLP are installed with `pip install scipy pulp`. In this course's browser exercises only numpy is available, so you will write the solver yourself.

## Under the hood: the tableau simplex

The numpy version follows the steps from the last lesson.

1. Build the tableau `[A | I | b]` with the objective row `[-c | 0 | 0]`.
2. Pick the entering column with the most negative objective-row entry. If none is negative, stop: the current corner is optimal.
3. **Ratio test**: for rows where the column entry is positive, divide the right-hand side by it; the smallest ratio picks the pivot row. If no entry is positive, the LP is unbounded.
4. Pivot: divide the pivot row by the pivot element, then subtract multiples of it from every other row so the column becomes a unit vector.
5. Read the answer: each basic variable equals its row's right-hand side; the rest are zero. The bottom-right cell is the optimal objective.

This simple version assumes every constraint is `<=` with a non-negative right-hand side, so the slack variables give a starting corner. Real solvers handle `>=` and `=` constraints (with a "phase 1"), degeneracy, numerical tolerances and sparse matrices, which is why you use them in practice.

## Common mistakes

- **Forgetting that linprog minimizes.** You get the worst plan, or a sign error on the objective.
- **Using linprog's default bounds by accident.** They are `(0, None)`, which is right for most models, but free variables need `(None, None)`.
- **Ignoring the status.** An "answer" from an infeasible or unbounded run is meaningless.
- **Mixing units across rows.** The solver will not notice that one row is in hours and another in minutes.
- **Hard-coding numbers inside the model.** Keep data (costs, capacities) in tables or files so the model can be rerun.

## Quick recap

- `linprog(c, A_ub, b_ub, ...)` minimizes; negate `c` to maximize and negate `res.fun` back.
- PuLP writes models with named variables and constraints and solves with CBC.
- Check solver status before reading results.
- The tableau simplex is pivots chosen by the most negative cost and the minimum ratio test.

## Try it

In the **Do** tab, put the furniture model in linprog's form and finish the ratio test of a numpy simplex solver.


Solve linear programs in Python with scipy's linprog and PuLP, and build a small simplex solver in numpy.

Solving with Python

SciPy Beginner's Guide for Optimization

Python Tutorial : Basics of PuLP modeling

Formulate decisions as linear programs, solve two-variable models by the graphical and simplex methods, and solve larger ones in Python.