Mathematics · Ch 12 — Linear Programming

Linear Programming Problem and Its Mathematical Formulation

12.2

Linear Programming Problem and Its Mathematical Formulation

The Furniture Dealer Problem: A Concrete Starting Point

A dealer can invest in two products: tables and chairs. Each table costs ₹2500 and yields ₹250 profit; each chair costs ₹500 and yields ₹75 profit. He has at most ₹50,000 to invest and storage for at most 60 pieces. A few possibilities:

Only tables: with ₹50,000 he buys $\frac{50000}{2500} = 20$ tables. Profit $= 20 \times 250 = ₹5000$ .
Only chairs: he could buy 100 chairs but storage limits him to 60. Profit $= 60 \times 75 = ₹4500$ .
Mixed: 10 tables and 50 chairs (60 pieces). Cost $= 25000 + 25000 = ₹50000$ . Profit $= 2500 + 3750 = ₹6250$ .

The mixed option beats both extremes. Among all combinations satisfying both constraints, which one yields the maximum profit?

Mathematical Formulation: Translating the Problem into Equations

To answer this systematically, we convert the word problem into a mathematical model — its mathematical formulation.

Step 1: Identify the Decision Variables

Let $x$ = number of tables and $y$ = number of chairs the dealer buys.

Note

Decision variables are the quantities we can control. Here $x$ and $y$ are non-negative integers, but for mathematical convenience we often treat them as real numbers first.

Step 2: Express the Objective Function

The profit to be maximised is the objective function, denoted $Z$ :

Z = 250x + 75y

Step 3: Identify the Constraints

Investment constraint: the total cost cannot exceed ₹50,000.

2500x + 500y \leq 50000 \;\Rightarrow\; 5x + y \leq 100

Storage constraint: the total number of pieces cannot exceed 60.

x + y \leq 60

Non-negativity constraints:

x \geq 0, \quad y \geq 0

Step 4: Assemble the Complete Mathematical Model

Z = 250x + 75y

General Form of a Linear Programming Problem

A linear programming problem in two variables has:

Decision variables: $x$ and $y$ .
Objective function: a linear function $Z = ax + by$ to maximize or minimize.
Constraints: linear inequalities (or equations) that restrict $x$ and $y$ .
Non-negativity restrictions: $x \geq 0$ , $y \geq 0$ .

Important

"Linear" means every term in the objective function and constraints is of the first degree — no $x^2$ , $xy$ , $\sin x$ , etc. "Programming" here means planning, not computer programming.

Key Terminology

Term	Meaning	Example
Decision variables	Quantities to be determined	$x$ (tables), $y$ (chairs)
Objective function	Linear function to optimize	$Z = 250x + 75y$
Constraints	Linear inequalities limiting variables	$5x + y \leq 100$ , $x + y \leq 60$
Non-negativity constraints	Variables cannot be negative	$x \geq 0$ , $y \geq 0$
Feasible solution	Any $(x, y)$ satisfying all constraints	$(10, 50)$ is feasible
Optimal solution	Feasible solution that optimizes $Z$	To be found

The Optimization Problem

In general, an LPP is either a maximization (e.g. profit, revenue) or a minimization (e.g. cost, time). The solution process finds all feasible solutions, then selects the one giving the best (maximum or minimum) value of $Z$ . …

Start your 14-day free trial to unlock the full solution →

← Previous · 12.1Introduction Next · 12.2.1 →Mathematical Formulation of the Problem