Mathematics and Statistics · Ch 14 — Linear Programming

Formulation of a Linear Programming Problem (LPP)

This Maharashtra Std XII (Commerce) Mathematics and Statistics chapter studies Linear Programming — a technique for getting the best possible outcome (largest profit, smallest cost) when limited resources must be shared between competing activities. It builds directly on the linear inequations and feasible-region work of Std XI, and draws on the same standard, well-established treatment of optimisation used in mathematics curricula nationally.

What a Linear Programming Problem is

Linear Programming Problem (LPP)

A Linear Programming Problem is the problem of maximising or minimising a linear function (called the objective function) of two or more variables, subject to a set of linear inequations or equations (called the constraints), where the variables are also required to be non-negative.

The word linear is essential: both the objective function and every constraint involve the variables only to the first power — no $x^{2}$ , no $xy$ , no $\sqrt{x}$ . This is what lets us solve the problem with straight lines and half-planes.

The four ingredients of every LPP

Note

Every LPP has exactly these parts

Decision variables — the unknown quantities we control, usually written $x$ and $y$ (e.g. numbers of two products to make).
Objective function $Z$ — the linear quantity to be optimised, e.g. $Z=5x+4y$ (a profit to maximise or a cost to minimise).
Constraints — the linear inequations expressing the limits on resources (labour hours, material, budget, demand).
Non-negativity restrictions — $x\ge 0,\ y\ge 0$ , because the variables count real quantities that cannot be negative.

How to formulate an LPP from a word problem

Formulation means translating a business situation into these four parts. A reliable recipe:

Tip

Five steps to formulate

Identify the decision variables and state clearly what each one counts.
Tabulate the data (resource used per unit of each activity, and the resource available) — a small table prevents mistakes.
Write the objective function $Z$ from the per-unit profit or cost, and say whether to maximise or minimise.
Write one constraint per limited resource using $\le$ for a ceiling ("at most", "available") or $\ge$ for a floor ("at least", "minimum requirement").
Add the non-negativity restrictions $x\ge 0,\ y\ge 0$ .

Watch out

"at most" vs. "at least" decides the sign

A resource that is available or usable at most to a certain limit gives $\le$ . A requirement that must be met at least to a certain minimum gives $\ge$ . Choosing the wrong direction reverses the whole feasible region, so read each phrase carefully before writing its inequation.

Definition 1Objective function

The linear function $Z=ax+by$ that an LPP seeks to maximise (profit) or minimise (cost). $a,b$ are known per-unit contributions and $x,y$ are the decision variables.

Definition 2Constraints

The linear inequations (occasionally equations) that express the limits on resources. A ceiling ("at most", "available") gives $\le$ ; a floor ("at least", "minimum") gives $\ge$ .

Definition 3Decision variables

The unknown quantities under our control (usually $x,y$ ) whose best values the LPP determines — e.g. the numbers of two goods to produce.

Definition 4Non-negativity restrictions

The conditions $x\ge 0,\ y\ge 0$ that every LPP carries, since the variables count real physical quantities that cannot be negative.

← Previous chapterCh 13 — Index Numbers Next · 2 →Feasible Region — Bounded and Unbounded