Formulating models

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:

maximize   70x + 50y

Constraints.

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

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.

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.