Mathematical Formulation of the Problem

The Mathematical Formulation of a Linear Programming Problem

The core of any linear programming problem is translating a real-world situation into precise mathematical language. This process, called mathematical formulation, expresses the problem's key elements as equations and inequalities.

The Motivating Example: A Furniture Dealer's Problem

Let:

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

Step 1: The Non-Negativity Constraints

The dealer cannot buy a negative number of tables or chairs:

These are the non-negative constraints (or non-negative restrictions).

Step 2: Identifying the Constraints

1. Investment Constraint: each table costs ₹2500 and each chair ₹500, and the total investment $2500x + 500y$ cannot exceed the ₹50,000 budget:

2. Storage Constraint: at most 60 items in total:

Inequalities (1), (2), and (3) together form the constraints.

Step 3: Defining the Objective Function

The dealer makes ₹250 profit per table and ₹75 per chair. The total profit $Z$ is:

This objective function is to be made as large as possible while satisfying all constraints.

The Complete Mathematical Formulation

This is a classic example of a Linear Programming Problem (LPP).

Formal Definitions of Key Terms

• Objective Function: a linear function $Z = ax + by$ ($a, b$ constants) to be maximised or minimised. Here $Z = 250x + 75y$.
• Decision Variables: the variables $x$ and $y$ whose values we determine — the inputs to the objective function.
• Constraints: the linear inequalities (or equations) restricting the decision variables, e.g. $5x + y \leq 100$ and $x + y \leq 60$.
• Non-Negative Restrictions: the constraints $x \geq 0$ and $y \geq 0$, almost always part of an LPP.
• Optimisation Problem: any problem seeking to maximise or minimise a function subject to constraints. An LPP is the special case where the objective function and all constraints are linear.

The General Structure of an LPP …