Formulating a Linear Programming Problem

Linear programming is a method for finding the best possible value — the maximum or minimum — of a linear quantity, subject to a collection of linear restrictions. It is the mathematics behind almost every resource-allocation decision: how a factory splits limited machine time between products to make the most profit, how a hospital meets nutrition targets at the least cost, how a transporter ships goods from warehouses to outlets as cheaply as possible. A problem that can be cast in this form is called a linear programming problem (LPP).

The word linear is doing real work. Every expression that appears — both the quantity being optimised and every restriction — must be of the first degree in the variables. There can be no $x^2$, no $xy$, no $\sqrt{x}$, no $\frac{1}{x}$. The moment a squared term or a product of variables appears, the problem leaves the world of linear programming.

The four ingredients of every LPP

• Decision variables (usually $x$ and $y$): the quantities you are free to choose — the number of chairs to make, units of a food to buy, trucks to dispatch. Naming these clearly, with units, is the first and most important step.
• Objective function $Z = ax + by$: the linear quantity you wish to optimise. State plainly whether you are maximising (profit, output) or minimising (cost, time, distance).
• Constraints: the linear inequalities (occasionally equations) that capture every limited resource or requirement — available labour hours, machine capacity, minimum nutrient levels, demand to be met.
• Non-negativity restrictions: $x \ge 0,\ y \ge 0$. You cannot make a negative number of tables or buy a negative quantity of food, so the decision variables are never negative. These are easy to forget but must always be written down.

Translating words into a model

Formulation is a disciplined reading exercise. Work through three questions in order:

1. What are you deciding? → the decision variables. Define them precisely, e.g. "let $x$ = number of tables produced per day, $y$ = number of chairs produced per day".
2. What are you trying to optimise? → the objective function. Multiply each variable by its per-unit profit or cost and add.
3. What limits you? → the constraints. Take each resource one at a time and write the inequality.

The language of the problem fixes the direction of each inequality. Learn these signal phrases:

A line such as "each table needs $2$ hours of carpentry, each chair needs $1$ hour, and at most $40$ hours are available" becomes the single inequality $2x + y \le 40$.

Worked formulation — a manufacturing problem

A carpenter makes tables and chairs. A table needs $2$ h on the saw and $1$ h on the lathe; a chair needs $1$ h on the saw and $3$ h on the lathe. The saw is available for $40$ h and the lathe for $60$ h per week. Profit is ₹$70$ per table and ₹$30$ per chair. Set up the LPP.

Let $x$ = tables and $y$ = chairs made per week. Profit to be maximised is $Z = 70x + 30y$. Saw time: $2x + y \le 40$. Lathe time: $x + 3y \le 60$. Adding non-negativity:

The standard problem types

Manufacturing (product-mix) problems maximise profit from products that compete for shared resources (machine hours, raw material, labour). These almost always give "$\le$" constraints, because resources are capped.

Diet problems minimise the cost of a meal plan that must supply at least stated amounts of nutrients (protein, calcium, vitamins). These give "$\ge$" constraints, because the requirements are floors that must be cleared.

Transportation and allocation problems minimise total cost or distance of moving goods from sources (factories, warehouses) to destinations (shops, depots), where supply is limited and demand must be satisfied — a mix of "$\le$" (supply) and "$\ge$" (demand) constraints.

Feasible and infeasible

A point $(x, y)$ that satisfies all the constraints, including non-negativity, is a feasible solution. The collection of every such point is the feasible region. A point that violates even one constraint is infeasible and is no candidate at all — it lies outside the feasible region. If the constraints contradict one another so that no point can satisfy them together, the feasible region is empty and the LPP has no solution.

Deeper Insight — formulation is the whole battle. Once a word problem is correctly translated, the graphical solution that follows is almost mechanical. Nearly every mark lost in this chapter is lost at the formulation stage: forgetting the non-negativity restrictions, mixing up which variable carries which profit, or choosing $\le$ where the problem demands $\ge$. A reliable habit fixes most of this — write a one-line definition of each variable with its unit before anything else, then build a small table with one row per resource and one column per product. The numbers in that table become the coefficients of your constraints directly, and the structure leaves nothing to guesswork.