Linear Program Formulation¶

Definition¶

Linear program formulation converts a practical description into an LP by organizing the data, stating the objective in words, defining decision variables, writing the objective function, and writing all constraints including variable restrictions.

Interpretation¶

Formulation translates a description in words into a model that can be solved. A good formulation can be read without guessing: every symbol has a stated meaning and unit, and every requirement in the description appears as a constraint.

A vertical sequence of five steps for formulating a linear program: organize the data, state the goal, define the decision variables, write the objective, and write the constraints.

The five boxes carry out the steps of the Definition for the Giapetto model: collect the data (profits $3$ and $2$ , hours per toy, limits $100$ , $80$ and $40$ ), state the goal of maximizing weekly profit in words, define $x_s$ and $x_t$ as soldiers and trains per week, and only then write the objective and the constraints. The variables are defined before any formula uses them.

The steps separate what can be chosen from what is given. A model parameter, such as a unit profit or a number of available hours, is fixed data; only the decision variables are left to the optimizer. Each constraint compares quantities in one unit, hours with hours or pounds with pounds.

Two slips are common. One is a vague variable definition such as " $x_s$ = soldiers", which leaves open whether $x_s$ counts soldiers per week or in total. The other is leaving out a restriction that is obvious in the description, such as nonnegativity: the optimizer only knows what is written in the model.

Key Results¶

State variable meanings before using them in formulas.
Use consistent measurement units in each constraint.
A percentage requirement can often be rearranged into a linear inequality.
Do not add integrality to a requested LP unless the intended model requires an integer program.

Examples¶

After solving, translate the variable values and objective back into the practical decisions they represent.

A maximum one-third share of feed A in the diet problem becomes $x_A\le(x_A+x_B)/3$ $x_{B}) /3$ .
Tow-bar production uses $3.5x_t+2.5x_s\le18$ for machine 1.

Prerequisites¶

Sources¶

OR Modelling · Week 1

Aliases: LP formulation, linear programming formulation

Last updated: 20 October 2026 03:02