Lp formulation
LP Formulation
LP formulation is the process of translating a real-world decision problem into a linear programming model.
The model must clearly say:
- what we choose
- what we optimize
- what limits us
The Three Questions
| Question | LP Object |
|---|---|
| What do we choose? | decision variables |
| What do we want? | objective function |
| What limits us? | constraints |
Step 1: Define Decision Variables
Decision variables must be precise.
Bad:
\[x_1=\text{lettuce}\]Good:
\[x_1=\text{hectares allocated to lettuce}\]Bad:
\[x_2=\text{fund B}\]Good:
\[x_2=\text{number of units purchased of fund B}\]The units matter.
A variable can represent:
- units produced
- hours operated
- kilograms purchased
- euros invested
- hectares cultivated
- goods shipped
- workers hired
Step 2: Write the Objective Function
The objective function measures the goal.
Use maximization for benefits:
\[\max c^Tx\]Examples:
- maximize profit
- maximize revenue
- maximize expected return
- maximize number of hired workers
- maximize production output
Use minimization for costs:
\[\min c^Tx\]Examples:
- minimize cost
- minimize transportation expense
- minimize diet cost
- minimize operating time
- minimize resource usage
Step 3: Write the Constraints
Constraints translate the limitations and requirements.
Common phrases:
| Phrase | Mathematical Sign |
|---|---|
| at most | $\le$ |
| no more than | $\le$ |
| maximum | $\le$ |
| cannot exceed | $\le$ |
| at least | $\ge$ |
| no less than | $\ge$ |
| minimum | $\ge$ |
| must satisfy | usually $\ge$ or $=$ |
| exactly | $=$ |
Step 4: Add Sign Restrictions
Most LP variables represent quantities, so they are nonnegative:
\[x_j\ge 0\]For all variables:
\[x\ge 0\]This means:
\[x_1\ge 0,\quad x_2\ge 0,\quad \ldots,\quad x_n\ge 0\]Do not forget these constraints.
Example: Simple Production Model
A factory produces two products.
Let:
\[x_1=\text{units of product A}\] \[x_2=\text{units of product B}\]Suppose:
- product A gives profit $5$
- product B gives profit $12$
- product A uses $20$ resistors, $10$ transistors, $10$ capacitors
- product B uses $10$ resistors, $20$ transistors, $30$ capacitors
- available resources are $200$, $120$, and $150$
The LP is:
\[\max 5x_1+12x_2\]subject to:
\[20x_1+10x_2\le 200\] \[10x_1+20x_2\le 120\] \[10x_1+30x_2\le 150\] \[x_1,x_2\ge 0\]Example: Minimum Requirement Model
Suppose two machines produce standard and special yarn.
Let:
\[x_1=\text{hours of machine A}\] \[x_2=\text{hours of machine B}\] \[x_3=\text{hours of machine C}\]The daily cost is:
\[90x_1+80x_2+60x_3\]If the market requires at least $60$ standard and $40$ special hanks, and the machine outputs are:
| Machine | Standard | Special |
|---|---|---|
| A | 3 | 1 |
| B | 2 | 2 |
| C | 2 | 1 |
then the LP is:
\[\min 90x_1+80x_2+60x_3\]subject to:
\[3x_1+2x_2+2x_3\ge 60\] \[x_1+2x_2+x_3\ge 40\] \[x_1,x_2,x_3\ge 0\]Unit Check
Every term in a constraint must have the same unit.
Example:
\[2x_1+3x_2\le 120\]If $x_1,x_2$ are product quantities and the coefficients are hours per product, then the left side is total hours.
The right side must also be hours.
Ratio Constraints
Ratio statements must be converted into linear inequalities.
Example:
second-level salary expenditure cannot exceed $80\%$ of first-level salary expenditure
If:
\[x_1=\text{first-level researchers}\] \[x_2=\text{second-level researchers}\]and salaries are $40000$ and $30000$, then:
\[30000x_2 \le 0.8(40000x_1)\]This is linear.
Final Model Checklist
A complete LP formulation should include:
- variable definitions
- objective function with max or min
- all constraints
- sign restrictions
- units if needed
- any integer or binary restrictions if the problem asks for them
Common Mistakes
Avoid these mistakes:
- defining variables vaguely
- mixing units
- forgetting nonnegativity
- using $\le$ when the phrase says “at least”
- writing nonlinear expressions such as $x_1x_2$
- optimizing revenue when the problem asks for profit
- using euros invested when the variable is number of units, or the reverse
Key Takeaway
Formulation is not calculation.
The hard part is translating the story into variables, objective, and constraints without changing the meaning of the problem.
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.