Formulating a Linear Program

Most of the difficulty in linear programming is not solving. It is deciding what the variables are, which sentences in a description are constraints, and which are just background.

This is the step everything else rests on. The simplex method, standard-form conversion, and every optimality test operate on a program that someone has already written. If the formulation misrepresents the situation, those methods will faithfully solve the wrong problem and report a confident answer.

The difficulty is rarely algebraic. It lies in deciding what is actually being chosen, in what units, and which sentences in the description are genuine restrictions rather than background.

This unit assumes you can read and write a linear inequality.

A problem description is prose, and prose mixes several kinds of statement together. Sorting them is most of the work.

What you choose. "The plant can make chairs and tables." This becomes a decision variable, one per thing genuinely under your control.

What you are trying to achieve. "Profit is £30 per chair and £20 per table, and the plant wants as much profit as possible." This becomes the objective, and its direction.

What limits you. "There are 100 machine hours available this week." This becomes a constraint.

Everything else. "The plant has been running since 1974 and employs forty people." This becomes nothing.

The common error is treating a computed quantity as a decision. Profit is not something you choose; it is what follows from what you choose. If a quantity is determined once the variables are fixed, it belongs in the objective or a constraint, not in the variable list.

A linear program consists of:

• decision variables $x_1,\dots ,x_n$, the quantities under the decision maker's control;
• a linear objective $c^{\mathsf{T}}x=c_1{x}_1+\cdots +c_n{x}_n$, to be maximized or minimized;
• finitely many linear constraints, each of the form $a_i^{\mathsf{T}}x\le b_i$, $a_i^{\mathsf{T}}x\ge b_i$, or $a_i^{\mathsf{T}}x=b_i$;
• sign restrictions on the variables, commonly $x_j\ge 0$.

Written together:

Linear means each term is a constant times a single variable. These are not linear, and none of them can appear:

A feasible solution is any $x$ satisfying every constraint and sign restriction. An optimal solution is a feasible $x$ whose objective value is best among all feasible points. The optimal value is that objective value; a program may have several optimal solutions but only one optimal value.

Identify what is being chosen. Ask what the decision maker can actually set. Write one variable per such quantity, and state its units explicitly: not "let $x$ be chairs" but "let $x$ be the number of chairs produced this week". A variable without units cannot be checked.

Write the objective. Express the stated goal as a single linear combination of the variables, and note whether it is maximized or minimized. If the goal mentions a quantity that is not a variable, such as profit, write it in terms of the variables rather than introducing a new symbol.

Write one constraint per restriction. For each limit in the description, write the expression that consumes the limited resource on the left and the available amount on the right, with the inequality pointing the way the restriction runs. Check that both sides are in the same units.

State sign restrictions. Most physical quantities are nonnegative. Say so explicitly. If a variable represents a net change or an adjustment that can go either way, it is free, and that must be stated too.

Check the model against the description. Read each sentence of the problem and point to where it appears in the program, or say why it appears nowhere. A restriction with no constraint is an omission; a constraint with no restriction is an invention.

Check that linearity and divisibility hold. If the description contains a bulk discount, a fixed set-up cost, a product of two decisions, or an indivisible unit, say so. A linear program is then the wrong model, and forcing it is a modeling error rather than a simplification.

Problem. A workshop makes two products, A and B. Each unit of A needs 2 machine hours and 1 labour hour; each unit of B needs 1 machine hour and 1 labour hour. This week there are 100 machine hours and 80 labour hours available. At most 40 units of A can be sold. Profit is £30 per unit of A and £20 per unit of B. The workshop has operated for thirty years and employs forty people. Plan production to maximize profit.

Goal. Write the linear program.

Relevant principle. One variable per decision, one constraint per genuine restriction, and nothing at all for background.

Step 1: what is being chosen.
The workshop chooses how much of each product to make.

Let $a$ be the number of units of A produced this week, and $b$ the number of units of B produced this week.

Reason: profit is not a choice; it follows from $a$ and $b$. Machine hours are not a choice either; they are consumed by the choice.

Step 2: the objective.

Reason: the stated goal is maximum profit, and profit in pounds is £30 per unit of A plus £20 per unit of B.

Step 3: one constraint per restriction.

Machine hours: each A takes 2, each B takes 1, and 100 are available.

Labour hours: each takes 1, and 80 are available.

Market limit on A: at most 40 units can be sold.

Reason: each left-hand side is the amount of that resource consumed, in the same units as the right-hand side. The sentence about thirty years and forty employees limits nothing and becomes no constraint.

Step 4: sign restrictions.

The program.

Check. Every sentence of the description is accounted for: two decisions, one goal, three limits, one irrelevant remark. Units are consistent in each row, hours against hours and units against units.

Interpretation. Solving this program gives $a=20$, $b=60$, with profit £1800. Both the machine-hour and labour-hour constraints are tight at this point: $2(20)+60=100$ and $20+60=80$. The market limit is not tight, since $a=20$ is well below 40.

A restriction that appears in the description need not bind at the optimum, and a formulation is not wrong for including it. Leaving it out, however, would be wrong: the program would then permit plans the workshop cannot sell.

The most common formulation error is introducing a variable for something the description merely mentions. It produces a program that looks richer and is in fact broken.

Use the workshop problem again.

Incorrect. "Let $a$ be units of A, $b$ be units of B, $p$ be the profit, and $h$ be the machine hours used."

This is not wrong in the sense of having the wrong solutions. The defining equations pin $p$ and $h$ down exactly, so the feasible set projects correctly onto $(a,b)$. But two of its four variables are not decisions, and each one costs a constraint to define. The model has grown without saying anything new.

Correct.

Where it becomes genuinely wrong. The same habit produces real errors when the introduced quantity is given a sign restriction it should not have, or when it is constrained twice. Writing $p\ge 0$ above would silently forbid loss-making plans that the description permits. And if a learner writes both $p=30a+20b$ and $p\le 2000$ from a stray sentence about a profit target, the program now caps profit rather than maximizing it.

The test to apply. For each proposed variable, ask: can the decision maker set this directly, without first setting something else? If the answer is no, it is determined by the real decisions, and it belongs in the objective or a constraint expression rather than in the variable list.

Formulating well is half the skill. The other half is knowing when not to formulate at all.

A linear program requires three things of a situation. The decision variables must be divisible, so that a fractional value means something. The objective and every constraint must be linear in those variables: a sum of variables each multiplied by a constant. And the data must be fixed and known, not depending on the choices being made.

When one of these fails, the failure is usually specific and nameable.

Indivisible decisions. A lorry is assigned to a route or it is not; 0.4 of a lorry is not a partial answer, it is a meaningless one. Rounding a fractional solution is not a repair, because the rounded point may be infeasible or far from optimal. The situation needs integer or binary variables, giving an integer program.

A product of decision variables. Revenue is price times quantity. If both are decision variables, the objective contains $p\cdot q$, a product of two decisions. That is not linear and no rearrangement makes it so. This calls for nonlinear programming.

A cost that changes with the decision. A price break, £2 per kilogram for the first 500 kg, £1.60 beyond, makes cost a piecewise function of the amount bought. A single linear expression cannot represent a bend. Binary indicators can encode which segment applies, giving a mixed-integer program, or the curve may be approximated linearly when the approximation is defensible.

Uncertain data. When a coefficient is a random quantity rather than a number, optimizing against one guess of it answers a different question than the one being asked. Stochastic or robust formulations exist for this.

The counter-case matters as much. Not everything that looks nonlinear is. An octane limit expressed as a volume-weighted average,

contains a ratio of decision variables and looks disqualifying. Multiply through by the denominator, which is positive whenever anything is blended:

That is linear. Rejecting this situation would cost a correct and useful model.

So the question is never "does this look linear?" but "which specific requirement does this violate, and does it survive rearrangement?" Naming the violated requirement is what identifies the model class that does fit.