Linear Programming Problem and Mathematical Formulation

From a Business Decision to Mathematics

A furniture dealer has ₹50,000 to invest and storage space for at most $60$ pieces. A table costs ₹2,500 and yields a profit of ₹250; a chair costs ₹500 and yields ₹75. How many of each should the dealer buy to maximise profit?

Try a few strategies: all tables — $20$ tables (₹50,000 spent), profit ₹5,000. All chairs — money allows $100$ but storage caps at $60$, profit ₹4,500. A mix of $10$ tables and $50$ chairs — profit ₹6,250. Clearly, strategies differ; the question is which is best. That question, made precise, is a linear programming problem.

The formulation

Let $x$ = number of tables, $y$ = number of chairs. Then:

$$\text{Maximise } Z = 250x + 75y$$

subject to the constraints

$$5x + y \leq 100 \ \text{(investment, after dividing } 2500x + 500y \leq 50000 \text{ by } 500\text{)}$$

$$x + y \leq 60 \ \text{(storage)}, \qquad x \geq 0, \ y \geq 0$$

The vocabulary

1. Objective function: the linear function $Z = ax + by$ (with constants $a, b$) to be maximised or minimised. Here $Z = 250x + 75y$.
2. Decision variables: the quantities $x$ and $y$ being chosen.
3. Constraints: the linear inequalities (or equations) restricting the variables. The conditions $x \geq 0, y \geq 0$ are the non-negative restrictions.
4. Optimisation problem: any problem seeking to maximise or minimise a linear function subject to such constraints; a Linear Programming Problem (LPP) is exactly this, with everything linear.

Key Point: "linear" means every relation in the problem is linear (no $x^2$, $xy$, $\sqrt{x}$ anywhere); "programming" is an older word for planning — choosing the best programme of action, nothing to do with computers.

The Formulation Recipe

Every word problem becomes an LPP through the same four moves:

1. Name the decision variables. "Let $x$ = number of (first item), $y$ = number of (second item)." State their units. This sentence carries a mark of its own on board papers.
2. Write the objective function. Identify what is being maximised (profit, revenue) or minimised (cost) and express it as $Z = ax + by$ using per-unit values.
3. Translate each resource or requirement into one inequality. A limited resource (money, hours, space) gives a $\leq$ constraint; a minimum requirement (nutrients, orders to fulfil) gives a $\geq$ constraint. Keep coefficients as per-unit consumptions.
4. Add the non-negative restrictions $x \geq 0, y \geq 0$ — quantities cannot be negative, and forgetting to write this loses a mark even when everything else is right.

Simplify constraints by dividing out common factors ($2500x + 500y \leq 50000$ becomes $5x + y \leq 100$) — smaller numbers mean fewer graphing errors later.

Reading a formulation back

Given a stated LPP, be able to identify each piece instantly: the objective function is the line starting "Maximise/Minimise"; everything after "subject to" is a constraint; the direction of each inequality tells you whether it models a ceiling ($\leq$: budget, capacity, hours) or a floor ($\geq$: minimum demand, nutritional requirement).

Key Point (this chapter's scope): with two decision variables everything can be drawn in the plane — which is why the chapter solves LPPs graphically. Problems with more variables exist (and matter in industry), but they need algebraic methods beyond this course.

Solved Examples

Example 1: The dealer, formally

Formulate the furniture dealer's problem (₹50,000 to invest, at most $60$ pieces stored; tables ₹2,500 each with profit ₹250, chairs ₹500 each with profit ₹75) as an LPP.

Solution:

1. Variables: let $x$ = number of tables, $y$ = number of chairs.
2. Objective: maximise profit $Z = 250x + 75y$.
3. Constraints: investment $2500x + 500y \leq 50000$, i.e. $5x + y \leq 100$; storage $x + y \leq 60$.
4. Non-negativity: $x \geq 0, \ y \geq 0$.

Answer: Maximise $Z = 250x + 75y$ subject to $5x + y \leq 100$, $x + y \leq 60$, $x, y \geq 0$.

Example 2: A diet problem, formulated

Two foods $F_1$ and $F_2$ cost ₹4 and ₹6 per unit. Each unit of $F_1$ contains $3$ units of vitamin A and $4$ units of minerals; each unit of $F_2$ contains $6$ units of vitamin A and $3$ units of minerals. The diet requires at least $80$ units of vitamin A and at least $100$ units of minerals. Formulate the least-cost diet as an LPP.

Solution:

1. Variables: $x$ units of $F_1$, $y$ units of $F_2$.
2. Objective: minimise cost $Z = 4x + 6y$.
3. Requirement constraints (floors, so $\geq$): vitamin A: $3x + 6y \geq 80$; minerals: $4x + 3y \geq 100$.
4. Non-negativity: $x, y \geq 0$.

Answer: Minimise $Z = 4x + 6y$ subject to $3x + 6y \geq 80$, $4x + 3y \geq 100$, $x, y \geq 0$ — minimum requirements point the inequalities up.

Example 3: A manufacturing problem, formulated

A factory makes products A and B. Each unit of A needs $1$ hour of cutting and $3$ hours of assembly; each unit of B needs $2$ hours of cutting and $1$ hour of assembly. At most $12$ cutting hours and $15$ assembly hours are available daily. Profits are ₹5 per unit of A and ₹3 per unit of B. Formulate for maximum profit.

Solution:

1. Variables: $x$ units of A, $y$ units of B per day.
2. Objective: maximise $Z = 5x + 3y$.
3. Resource constraints (ceilings, so $\leq$): cutting: $x + 2y \leq 12$; assembly: $3x + y \leq 15$.
4. Non-negativity: $x, y \geq 0$.

Answer: Maximise $Z = 5x + 3y$ subject to $x + 2y \leq 12$, $3x + y \leq 15$, $x, y \geq 0$.

Example 4: Reading a formulation

For the LPP "Minimise $Z = 200x + 500y$ subject to $x + 2y \geq 10$, $3x + 4y \leq 24$, $x \geq 0, y \geq 0$", identify the objective function, the decision variables, each constraint's type, and what the problem is asking.

Solution:

1. Objective function: $Z = 200x + 500y$, to be minimised — a cost-type problem.
2. Decision variables: $x$ and $y$.
3. Constraints: $x + 2y \geq 10$ is a floor (a minimum requirement); $3x + 4y \leq 24$ is a ceiling (a limited resource); $x, y \geq 0$ are the non-negative restrictions.

Answer: the problem asks for the cheapest $(x, y)$ meeting a requirement floor while staying under a resource ceiling — mixed-direction constraints are perfectly normal.

Example 5: Spotting a non-LPP

Why is "maximise $Z = xy$ subject to $x + y \leq 10$, $x, y \geq 0$" NOT a linear programming problem?

Solution:

1. Test every relation for linearity: the constraint $x + y \leq 10$ is linear; the non-negative restrictions are linear.
2. The objective fails: $Z = xy$ is a product of variables — not of the form $ax + by$.

Answer: the objective function is nonlinear, so this is an optimisation problem but not an LPP — every relation, objective included, must be linear.