Formulating a linear programming problem

Most marks in an LP question come from formulating the problem correctly. The graphing and evaluation that follow are mechanical; the translation from words to math is where students stumble.

The three ingredients

Every LPP has three components.

Decision variables: the unknowns the problem is asking you to determine. Typically $x$ and $y$ represent quantities of something , units produced, kilograms of a food eaten, hours spent at an activity.

Objective function: the quantity to maximise or minimise. Always linear in the decision variables: $Z = ax + by$.

Constraints: linear inequalities (or sometimes equalities) describing limits on the decision variables. Include the non-negativity constraints $x, y \ge 0$ explicitly , quantities of things can't be negative.

The formulation algorithm

1. Read carefully. Identify what is being chosen (decision variables) and what is being optimised (objective).
2. Define each variable in plain words. Write "Let $x$ = number of units of A produced per day" , not just "$x$".
3. Write the objective. Express the quantity to be optimised as a linear function. State "maximise" or "minimise."
4. Write each constraint as a linear inequality (or equality). One constraint per limit in the problem.
5. Include $x, y \ge 0$.

Common patterns

Diet problem. A person needs at least so many units of nutrient A, so many of nutrient B, etc. Foods cost different amounts and contain different amounts of each nutrient. Minimise total cost. Variables: quantities of each food. Objective: cost. Constraints: nutrient requirements.

Manufacturing problem. A factory makes two products. Each unit of product I uses certain hours on machine A and machine B; same for product II. Available machine hours are limited. Profit per unit is given. Maximise total profit. Variables: units of each product. Objective: profit. Constraints: machine-hour limits.

Transportation problem. Goods sent from $m$ sources to $n$ destinations. Supplies, demands, and per-unit costs are given. Minimise total cost. Variables: amount sent from each source to each destination.

Resource allocation. Limited budget, multiple investment options with different returns and risks. Maximise total return (or minimise risk).

Reading practice

Problem A. "A confectioner makes two kinds of biscuits, Crunch and Munch. One packet of Crunch requires $300\,\text{g}$ of flour and $50\,\text{g}$ of sugar; one of Munch requires $150\,\text{g}$ of flour and $50\,\text{g}$ of sugar. He has $7.5\,\text{kg}$ of flour and $3\,\text{kg}$ of sugar. Profit on Crunch is ₹$5$ per packet, on Munch ₹$4$ per packet. How many packets of each should he make to maximise profit?"

Decision variables: let $x$ = packets of Crunch, $y$ = packets of Munch.

Objective: maximise $Z = 5x + 4y$.

Constraints (in grams):

• Flour: $300x + 150y \le 7500$, i.e. $2x + y \le 50$.
• Sugar: $50x + 50y \le 3000$, i.e. $x + y \le 60$.
• Non-negativity: $x, y \ge 0$.

Problem B. "A diet needs at least $8$ units of vitamin A and $10$ units of vitamin B daily. Food $F_1$ contains $2$ units of A and $1$ unit of B per gram; food $F_2$ contains $1$ unit of A and $2$ units of B per gram. $F_1$ costs ₹$4$/gram, $F_2$ costs ₹$3$/gram. Minimise the cost."

Decision variables: $x$ grams of $F_1$, $y$ grams of $F_2$.

Objective: minimise $Z = 4x + 3y$.

Constraints:

• Vitamin A: $2x + y \ge 8$.
• Vitamin B: $x + 2y \ge 10$.
• Non-negativity: $x, y \ge 0$.

Worked examples

Example 1. A factory produces two products P and Q. P needs $3$ hours on machine $M_1$ and $2$ hours on machine $M_2$ per unit; Q needs $4$ hours on $M_1$ and $1$ hour on $M_2$. $M_1$ is available for $12$ hours, $M_2$ for $5$ hours daily. Profit per unit: ₹$5$ for P, ₹$4$ for Q. Maximise daily profit.

$x$ = units of P, $y$ = units of Q. $Z = 5x + 4y$. Constraints: $3x + 4y \le 12$, $2x + y \le 5$, $x, y \ge 0$.

Example 2. A farmer has $50$ acres of land for wheat and barley. Wheat earns ₹$200$/acre with $40$ hours of labour; barley earns ₹$150$/acre with $30$ hours. Total labour available: $1500$ hours. Maximise revenue.

$x$ = acres of wheat, $y$ = acres of barley. $Z = 200x + 150y$. Constraints: $x + y \le 50$ (land), $40x + 30y \le 1500$ i.e. $4x + 3y \le 150$ (labour), $x, y \ge 0$.

Example 3. A medical clinic wants to plan its supply of vitamin tablets. Tablet A costs ₹$2$ and provides $4$ units of vit-C and $1$ unit of vit-E. Tablet B costs ₹$1$ and provides $1$ unit of vit-C and $1$ unit of vit-E. Daily intake at least $8$ vit-C and $5$ vit-E. Minimise cost.

$x$ tablets of A, $y$ of B. $Z = 2x + y$. Constraints: $4x + y \ge 8$, $x + y \ge 5$, $x, y \ge 0$.

Example 4. A toy company makes dolls and trains. Each doll uses $4$ units of plastic and $6$ minutes of machine time. Each train uses $5$ units of plastic and $5$ minutes of machine time. Daily plastic: $200$ units; daily machine: $300$ minutes. Profit ₹$10$ per doll, ₹$12$ per train. Maximise profit.

$x$ dolls, $y$ trains. $Z = 10x + 12y$. Constraints: $4x + 5y \le 200$, $6x + 5y \le 300$, $x, y \ge 0$.

Example 5. Two transporters charge ₹$10$/km and ₹$12$/km, respectively. They can carry $50$ and $80$ kg in one trip. A merchant has $200$ kg to send a distance of $20$ km. Transporter 1 has $4$ trucks; Transporter 2 has $5$ trucks. Minimise cost.

This is more complex , but formulate cleanly. $x$ = trips by Transporter 1, $y$ = trips by Transporter 2. Cost per trip: ₹$200$ and ₹$240$. Objective: minimise $Z = 200x + 240y$. Constraints: $50x + 80y \ge 200$ (capacity), $x \le 4$, $y \le 5$, $x, y \ge 0$.

Example 6. A student studies for two subjects, Maths and Physics, scoring marks proportional to study time. Each hour of Maths gives $5$ marks, each hour of Physics gives $4$. Constraint: total time $\le 10$ hours, Maths time at least $3$ hours, Physics time at least $2$ hours. Maximise score.

$x$ = Maths hours, $y$ = Physics hours. $Z = 5x + 4y$. Constraints: $x + y \le 10$, $x \ge 3$, $y \ge 2$.

Try it yourself

For each problem, identify decision variables, objective, and constraints.

1. A baker makes two cakes A and B. A uses $1$ kg flour, $2$ kg sugar, profit ₹$30$. B uses $2$ kg flour, $1$ kg sugar, profit ₹$25$. Available: $10$ kg flour, $12$ kg sugar.
2. A pharmacy sells two pills. Pill X has $5$ vit-A, $3$ vit-B, cost ₹$5$. Pill Y has $2$ vit-A, $4$ vit-B, cost ₹$4$. Need at least $20$ vit-A and $30$ vit-B daily.
3. A factory makes chairs and tables. Chair needs $2$ hours of work, $1$ kg wood. Table needs $4$ hours, $3$ kg wood. Available: $30$ hours, $24$ kg. Profit ₹$10$/chair, ₹$25$/table.
4. A car rental company has $20$ cars, each rented for ₹$200$/day or sold for ₹$10000$. At least $5$ cars must be rented. Maximise weekly revenue (assume rentals run all week).
5. A student needs at least $16$ units of vitamin A and $20$ of B daily. Cereal P has $2$ A, $3$ B per scoop, ₹$1$/scoop. Cereal Q has $4$ A, $1$ B, ₹$2$/scoop. Minimise cost.
6. A clothing manufacturer makes shirts and trousers. Shirt: $1$m fabric, $0.5$h labour, ₹$25$ profit. Trouser: $1.5$m fabric, $1$h labour, ₹$30$ profit. Available: $60$m fabric, $40$h labour.
7. A confectioner has $50$kg sugar, $30$kg butter. Cake type A uses $1$kg sugar, $0.5$kg butter, profit ₹$80$. Type B uses $2$kg sugar, $1$kg butter, profit ₹$120$.
8. A truck operator transports oranges and apples. Truck capacity: $5$ tonnes. Oranges: $1$ tonne, profit ₹$1500$. Apples: $0.5$ tonne, profit ₹$1000$. Demand: at least $2$ tonnes of each.
9. A farmer has $40$ acres for sugarcane ($x$) and wheat ($y$). Profit: ₹$1200$/acre sugarcane, ₹$800$/acre wheat. Sugarcane needs $20$ hours/acre water, wheat needs $10$ hours/acre. Water available: $600$ hours.
10. A diet plan: $2$ types of foods. Food 1 has $200$ calories, $30$ proteins per unit. Food 2: $100$ calories, $20$ proteins. Need at least $400$ calories and $50$ proteins. Cost: ₹$20$/unit, ₹$15$/unit. Minimise.
11. A library buys two types of books. Type A: ₹$500$/book, $1$kg, profit ₹$80$. Type B: ₹$300$/book, $0.5$kg, profit ₹$50$. Budget ₹$15000$, shelf $25$kg.
12. An investor allocates ₹$2$ lakh to two schemes. Scheme 1: $8\%$ return, low risk. Scheme 2: $12\%$ return, high risk. At most ₹$80000$ in scheme 2. Maximise return.
13. A baker has $5$kg flour, $1$kg sugar. Bread: $0.5$kg flour, $0.05$kg sugar, profit ₹$5$. Cake: $0.25$kg flour, $0.1$kg sugar, profit ₹$10$.
14. A factory packages two products in boxes. Type X: $1$kg/box, $0.5$m³/box, profit ₹$10$. Type Y: $2$kg, $1$m³, profit ₹$25$. Limits: $100$kg, $50$m³.

Pitfalls and tricks

• Define variables in words. Just "$x$" isn't enough , say "$x$ = number of …".
• Match units. Don't mix kg and g; convert everything to a single unit.
• Include $x, y \ge 0$ explicitly , easy to forget.
• One constraint per resource. Don't combine two constraints into one inequality; keep them separate.
• Re-read the problem after formulation to ensure each constraint corresponds to a real-world limit and the objective matches what's asked.