Lesson 1: Decision Variables, Objectives, and Constraints

1 Modelling context

A decision problem asks: among the available courses of action, which one is best? The word "best" implies an objective — a quantity to maximize or minimize. The word "available" implies constraints — the limitations within which the choice must be made. A linear program is a formal representation of such a problem when the objective and constraints are linear in the decision quantities.

The hardest part of linear programming is not solving the problem. The solver does that in milliseconds. The hardest part is stating the problem correctly: identifying the actual decision variables, choosing the right objective, and translating each constraint from prose into a linear inequality. A model that is solved correctly but stated incorrectly produces a confident recommendation to solve the wrong problem.

Formulation is the modelling step

In this module, the modelling content is in the formulation. The spreadsheet setup and the solver call are mechanical. The value of the analyst is in getting the decision variables, objective, and constraints right.

2 Learning objectives

By the end of this lesson you will be able to

Identify the decision variables in a decision problem.
State the objective as a linear function of the decision variables.
Translate each constraint into a linear inequality or equality.
Recognise when a problem cannot be represented as a linear program.
Justify the units and the nonnegativity restrictions of the decision variables.

3 Prerequisite review

Linear function: A function of the form f(x₁, …, xₙ) = c₁ x₁ + … + cₙ xₙ. No products of decision variables, no powers, no transcendental functions.
Inequality: A statement of the form a₁ x₁ + … + aₙ xₙ ≤ b or ≥ b. The left-hand side is linear in the decision variables.
Feasible region: The set of points satisfying all constraints. For a linear program, this is always a convex polyhedron.
Nonnegativity: The restriction x_j ≥ 0 on a decision variable. Common in LP because many decision quantities (quantities to produce, amounts to allocate) cannot be negative.

4 Mathematical formulation

The three ingredients

Every linear program has the same three ingredients:

Decision variables. The quantities to choose. Usually denoted x₁, …, xₙ, with clear units.
Objective function. A linear function c₁ x₁ + … + cₙ xₙ to be maximized or minimized.
Constraints. Linear inequalities or equalities the variables must satisfy. Often accompanied by nonnegativity restrictions.

Standard form

maximize    c₁ x₁ + c₂ x₂ + … + cₙ xₙ
subject to  a₁₁ x₁ + a₁₂ x₂ + … + a₁ₙ xₙ ≤ b₁
            a₂₁ x₁ + a₂₂ x₂ + … + a₂ₙ xₙ ≤ b₂
            …
            a_{m1} x₁ + a_{m2} x₂ + … + a_{mn} xₙ ≤ b_m
            x₁, x₂, …, xₙ ≥ 0

Recognising linearity

The objective and constraints must be linear in the decision variables. This rules out:

Products of decision variables. x₁ x₂ is not linear.
Powers. x₁² is not linear.
Nonlinear transformations. log(x₁), sin(x₁), e^{x₁} are not linear.
Min, max, or absolute values of decision variables. max(x₁, x₂) is not linear, though it can sometimes be reformulated with additional variables and constraints.
If-then logic. "Produce x₁ if demand exceeds some threshold" is not linear, though binary variables can represent such logic in integer programming.

Choosing decision variables

The single most important step in formulation is choosing the decision variables. They must capture what the decision-maker actually controls. Common choices:

Quantities to produce or purchase. x_j = number of units of product j.
Amounts to allocate. x_j = amount of resource assigned to activity j.
Binary choices. x_j = 1 if a project is selected, 0 otherwise. (Technically integer programming; discussed further in Lesson 3.)
Proportions. x_j = fraction of a total to assign to activity j, with Σ x_j = 1.

Figure 6.2. The three ingredients of a linear program. The decision variables appear in both the objective and the constraints. Getting the variables right is the most important step.

5 Worked example

A production planning problem

A workshop produces two products, A and B. Each unit of A requires 2 hours of labour and 1 kg of raw material. Each unit of B requires 1 hour of labour and 3 kg of raw material. The workshop has 100 hours of labour and 90 kg of raw material available each week. Product A sells for a profit of $40 per unit; product B sells for $30 per unit. At most 40 units of A can be sold per week, and at most 30 units of B. The workshop wants to maximize weekly profit.

Step 1 — Identify the decision variables.

The decision is how much of each product to make. Define:

x_A = number of units of product A produced per week
x_B = number of units of product B produced per week

Units: units per week. Nonnegativity: x_A, x_B ≥ 0.

Step 2 — State the objective.

Profit is $40 per unit of A and $30 per unit of B:

maximize   40 x_A + 30 x_B

Units of the objective: dollars per week.

Step 3 — Translate the constraints.

Labour: 2 x_A + 1 x_B ≤ 100 (hours per week).
Raw material: 1 x_A + 3 x_B ≤ 90 (kg per week).
Demand for A: x_A ≤ 40.
Demand for B: x_B ≤ 30.
Nonnegativity: x_A ≥ 0, x_B ≥ 0.

Step 4 — Verify linearity.

The objective is linear in x_A, x_B. Each constraint is linear. The problem is a linear program.

Step 5 — Verify the units.

The coefficients of each constraint must produce the same units on both sides. For the labour constraint:

2 (hours/unit) · x_A (units) + 1 (hours/unit) · x_B (units) = hours
≤ 100 hours ✓

Step 6 — State the complete LP.

maximize   40 x_A + 30 x_B
subject to 2 x_A + x_B ≤ 100
           x_A + 3 x_B ≤ 90
           x_A ≤ 40
           x_B ≤ 30
           x_A, x_B ≥ 0

This LP can be solved in a spreadsheet (Lesson 2). The solution should be interpreted in terms of production quantities, and the dual values should be interpreted in terms of the marginal value of additional labour or materials (Unit 6.2).

6 Verification check

Checks to perform

Units check. Every term in the objective must have the same units. Every term in each constraint must have the same units, and the two sides must match.
Linearity check. No products of decision variables, no powers, no nonlinear transformations.
Completeness check. Every constraint mentioned in the problem statement appears in the formulation, and no constraints have been invented.
Bound check. Each variable has an appropriate nonnegativity restriction (or an explicit statement that it may be negative).
Interpretation check. The optimal solution, when found, corresponds to a decision that makes sense in the original context.

7 Interpretation

A linear program is a formal statement of a decision problem. The solution to the LP is a recommendation: it tells the decision-maker the best course of action according to the stated objective and constraints.

Three interpretive points:

The recommendation is conditional on the model. If the objective coefficients or the constraint bounds are wrong, the recommendation may be wrong even though the LP was solved correctly.
The optimal solution often lies at a corner. In practice, a corner solution may correspond to an extreme policy (produce only one product, allocate all resources to a single activity) that the decision-maker would not choose in practice. This is a legitimate critique of LP models but not a defect of the method.
Sensitivity analysis is essential. The optimal solution assumes that the coefficients are exactly as stated. The sensitivity analysis in Unit 6.2 shows how the solution changes when the coefficients change — which is what the decision-maker actually needs to know.

Garbage in, garbage out — but confidently

An LP solver returns the optimal solution to the LP you specified. It does not check whether that LP corresponds to the problem you meant to solve. The formulation is the modelling step, and it is the analyst's responsibility.

8 Uncertainty and limitations

The coefficients of a linear program are rarely known exactly. They are estimated from data, taken from accounting records, or assumed from domain knowledge. Each coefficient carries uncertainty, and the LP solution inherits that uncertainty.

Sources of uncertainty in an LP formulation
Source	Effect
Objective coefficients	Profit margins, costs, or prices may change or be uncertain
Constraint bounds	Available labour, materials, or capacity may vary
Constraint coefficients	Resource consumption per unit may not be constant
Model form	Real problems often involve nonlinearities or discrete choices

The sensitivity analysis of Unit 6.2 quantifies the first two sources: how much can each coefficient change before the optimal solution changes? The third and fourth sources are structural and may require a different model form.

Linearity is an approximation

Real production processes often exhibit economies of scale (a nonlinearity), resource constraints that depend on other decisions (a coupling), and discrete choices (integer variables). Linear programming is used because the approximation is often adequate and because the resulting problem is efficiently solvable. The limitations should be documented alongside the model.

9 Common implementation errors

Watch for these

Choosing the wrong decision variables. The decision variables must capture what the decision-maker actually controls. A common error is to make the decision variables outputs (profit, cost) rather than inputs (quantities).
Units mismatches. A term like 2 x_A + x_B ≤ 100 is only valid if all terms have the same units. Mixing hours and kilograms produces a nonsensical constraint.
Missing constraints. If the problem statement mentions a limitation, it must appear as a constraint. A model that omits the demand limit may recommend producing more than can be sold.
Inventing constraints. Adding constraints not implied by the problem restricts the feasible region and can change the optimum.
Violating linearity. A constraint like x_A · x_B ≤ 40 is not linear. If products of variables are required, the problem is nonlinear.
Forgetting nonnegativity. Unless stated otherwise, decision variables representing physical quantities should be nonnegative.
Not documenting the units of coefficients. A coefficient of 2 in a labour constraint means "2 hours per unit" — a fact that must be recorded.

10 Independent modelling task

Your turn

Choose a decision problem you know. It can be from a business, a household, a public service, or a personal context.
Write down the decision. State clearly what is being chosen.
Identify the decision variables. Give each a symbol and a unit.
State the objective. What is being maximized or minimized? Give the units of the objective.
List every limitation mentioned in the problem statement. Translate each into a linear inequality.
Verify linearity and units. If the problem is not linear, identify which part is nonlinear and discuss what would be lost by approximating it linearly.
Write the complete LP in standard form.

This exercise forms part of Laboratory 11 and the formulation component of Assignment 5.

11 Reflection prompt

Reflect before continuing

Real decision problems are rarely linear. Why is linear programming still useful?

Two or three sentences. Consider the tradeoff between model accuracy and tractability, and the value of a first approximation.

12 Lesson summary

Key takeaways

A linear program has three ingredients: decision variables, an objective, and constraints. All three must be linear in the decision variables.
Formulation is the modelling step. The solver only optimizes the problem you specify.
The decision variables must capture what the decision-maker controls. A common error is to make them outputs rather than inputs.
Units must match in every term. A units mismatch is a formulation error, not a numerical one.
Linearity is an approximation. Problems with nonlinearities or discrete choices require different models.

Coming next

Lesson 2 turns to the spreadsheet implementation: how to lay out an LP, how to call the solver, and how to read the output.

§ Self-quiz, practice, and homework

Practice exercises

For the production planning example, add a constraint that the total number of units produced (A plus B) cannot exceed 60. Write the new constraint and update the LP.
For the same example, suppose product A's profit increases to $50 per unit. Rewrite the objective function. Does the LP remain linear?
Identify whether each of these is linear: (a) 2x₁ + 3x₂ ≤ 10, (b) x₁² + x₂ ≤ 10, (c) x₁ / x₂ ≤ 3, (d) max(x₁, x₂) ≤ 5.
Write an LP with two decision variables and three constraints. State the units of each coefficient.

Homework problems

Formulation from prose. A company produces three products (P, Q, R) using two resources (labour and material). P requires 3 labour-hours and 1 kg of material per unit; Q requires 2 labour-hours and 2 kg; R requires 1 labour-hour and 3 kg. Available resources are 200 labour-hours and 150 kg per week. Profits are $20, $25, and $30 per unit respectively. Demand limits are 40, 50, and 30 units per week. Formulate the LP. Verify units for every coefficient.
Recognising non-linearity. For each of the following, state whether the problem is a linear program. If not, identify the source of nonlinearity: (a) a production problem where cost per unit decreases with volume; (b) a scheduling problem where a task starts only after another finishes; (c) a portfolio problem with a fixed budget and per-asset returns; (d) a distribution problem where shipping costs depend on distance squared.
Variable definition exercise. Take a problem you have encountered (from your own experience, a business, or a public service) and write down two different formulations of the same decision using different choices of decision variables. Discuss which is easier to solve and which better captures the decision.

Mini project

Choose a real decision problem. Formulate it as a linear program: state the decision variables with units, the objective, and every constraint. Include a units-check table and a linearity assessment. Submit a two-page formulation document. This is the basis for Laboratory 11 and Assignment 5.