Optimum Allocation of Resources - LPP: formula sheet

Key formulas

General form of an LPP

Maximise or Minimise Z = c₁x₁ + c₂x₂ + … + cₙxₙ

cⱼ is the profit or cost per unit of variable xⱼ. Z is the objective function.

Constraints

a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ (≤, =, ≥) b₁, and so on for each resource

aᵢⱼ is the amount of resource i used by one unit of xⱼ. bᵢ is the availability or requirement.

Non-negativity

x₁, x₂, …, xₙ ≥ 0

Always write this line. It is a required part of the model.

Typical constraint signs

Resource limit: ≤ | Minimum requirement: ≥ | Exact requirement: =

Maximisation problems usually have ≤ constraints. Minimisation problems usually have ≥ constraints.

Profit per unit

Selling price per unit − Variable cost per unit

Use contribution per unit as the objective coefficient when fixed costs are not affected by the decision.

General LPP form

Max or Min Z = ax + by, subject to constraints px + qy ≤, =, ≥ r, and x, y ≥ 0

Z is the objective function. x and y are decision variables.

Boundary line of a constraint

px + qy = r

Intercepts: x = r ÷ p (put y = 0) and y = r ÷ q (put x = 0).

Test point rule

Put (0, 0) in the constraint; if it holds, shade the side containing the origin

Use only when the line does not pass through the origin. Otherwise test another point such as (1, 0).

Corner point theorem

Optimal value of Z, if it exists, occurs at a corner point of the feasible region

Evaluate Z at every corner and compare.

Iso-profit line

ax + by = c; slope = −a ÷ b

Lines for different c are parallel. Maximise: move away from the origin. Minimise: move towards the origin.

Intersection of two lines

Solve the two boundary equations simultaneously

Use elimination to get the coordinates of a corner that is not on an axis.

Multiple optima test

Slope of Z line = slope of a binding constraint edge, and both end corners give equal Z

General solution on the edge between corners A and B: λA + (1 − λ)B, for 0 ≤ λ ≤ 1. Z is the same everywhere on it.

Unbounded test

Feasible region open in the direction of improving Z

Maximisation is unbounded only if Z can rise without limit. An open region alone is not enough. A minimisation problem on an open region may still have a finite optimum. Minimisation can be unbounded only if Z can fall without limit, which needs some negative cost coefficient.

Infeasible test

Feasible region = ∅ (no common point)

Typical sign: conflicting constraints such as x + y ≤ 4 and x + y ≥ 6.

Redundant constraint test

Every corner point of the region satisfies the constraint without it being binding

Deleting it leaves the feasible region and the optimum unchanged.

Slack variable (≤ constraint)

a1x1 + a2x2 ≤ b becomes a1x1 + a2x2 + s = b, s ≥ 0

Slack has coefficient 0 in Z and can start in the basis.

Surplus and artificial (≥ constraint)

a1x1 + a2x2 ≥ b becomes a1x1 + a2x2 − s + A = b, s, A ≥ 0

Surplus alone has a coefficient of −1, so it cannot start in the basis. Add A.

Equality constraint

a1x1 + a2x2 = b becomes a1x1 + a2x2 + A = b

Only an artificial variable is added.

Big M objective

Max Z = Σ cjxj − M·A (Min Z = Σ cjxj + M·A)

M is larger than any other number in the problem.

Net evaluation row

Cj − Zj, where Zj = Σ (CB × column entry)

Maximisation: optimal when all Cj − Zj ≤ 0. Minimisation: optimal when all Cj − Zj ≥ 0.

Entering variable

Largest positive Cj − Zj (max) or most negative Cj − Zj (min)

This fixes the key column.

Minimum ratio test

θ = solution value ÷ key column entry, for entries > 0

The smallest θ gives the leaving variable and the key row.

Pivot operations

New key row = old key row ÷ pivot element; other row = old row − (its key column entry × new key row)

Do this for every row, including the solution column.

Dual of a maximisation primal (all ≤ constraints)

Primal: Max Z = Σ cj xj, subject to Σ aij xj ≤ bi, xj ≥ 0. Dual: Min W = Σ bi yi, subject to Σ aij yi ≥ cj, yi ≥ 0.

Each primal constraint gives one dual variable. Each primal variable gives one dual constraint. Objective coefficients and right-hand sides swap roles, and the coefficient matrix is transposed.

Dual of a minimisation primal (all ≥ constraints)

Primal: Min Z = Σ cj xj, subject to Σ aij xj ≥ bi, xj ≥ 0. Dual: Max W = Σ bi yi, subject to Σ aij yi ≤ cj, yi ≥ 0.

Max becomes Min or the reverse, and the inequality direction flips for the constraints.

Handling other constraint types

Equality constraint in primal ↔ unrestricted (free) dual variable. Unrestricted primal variable ↔ equality dual constraint.

For a max primal, convert a ≥ constraint to ≤ by multiplying by -1 before dualising. For a min primal, convert a ≤ constraint to ≥ the same way.

Duality theorem

Optimal Z (primal) = Optimal W (dual)

Holds when either problem has a finite optimal solution. If one is unbounded, the other is infeasible.

Shadow price

Shadow price of resource i = yi* = change in optimal Z per unit increase in bi

Valid only while the optimal basis stays the same, i.e. within the range of bi. It is zero for a resource with positive slack.

Complementary slackness

xj × (dual slack of constraint j) = 0 and yi × (primal slack of constraint i) = 0

If a resource is not fully used, its shadow price is 0. If a variable is positive, its dual constraint is binding.

Reading the final simplex table

Shadow price of a ≤ resource = Zj value under its slack variable column (maximisation)

A slack column has cj = 0, so Cj - Zj = 0 - Zj = -Zj under that column. The shadow price is therefore the Zj value, which is the negative of the Cj - Zj entry. In a Max problem the Cj - Zj entries under slack columns are ≤ 0 at the optimum, so the shadow prices are ≥ 0.

Quick revision

• An LPP has decision variables, a linear objective function, linear constraints and non-negativity restrictions.
• Define variables clearly with units before writing any equation.
• Limited resources give ≤ constraints; minimum requirements give ≥ constraints.
• The feasible region is the area satisfying all constraints together.
• If an optimal solution exists for a bounded feasible region, it lies at a corner point.
• Test every corner point in the objective function and pick the best for max or min as asked.
• Multiple optimal solutions occur when the objective function line is parallel to a binding constraint that forms an edge of the feasible region at the optimum, so two adjacent corner points give the same optimal value.
• Infeasible means no common feasible region; unbounded means the objective can improve without limit.
• In simplex, add a slack variable for each ≤ constraint to turn it into an equation.
• Pick the entering variable by the optimality rule and the leaving variable by the minimum ratio.
• Every LPP has a dual; the dual of a maximisation problem is a minimisation problem.
• A shadow price shows how much the objective changes for one extra unit of a binding resource, within a valid range.

Common mistakes

• Using selling price instead of profit or contribution in the objective function. Fix: Check what the question asks to maximise. If costs are given, subtract variable cost from selling price per unit.
• Mixing units, such as machine time in minutes against availability in hours. Fix: Convert everything to one unit before writing the constraint.
• Shading the wrong side of a constraint. Fix: Always test (0, 0) in the inequality. If the line passes through the origin, test another point.
• Taking an intersection point that is not in the feasible region as a corner. Fix: Substitute every candidate corner in all constraints before using it.
• Calling a problem unbounded when it is infeasible, or the reverse. Fix: Unbounded has a feasible region that never ends. Infeasible has no feasible region at all. Always draw first and check whether any shaded area is common.
• Giving only two points as the answer when there are multiple optima. Fix: State that infinitely many solutions exist on the line segment joining the two corners. Give the general form λA + (1 − λ)B with 0 ≤ λ ≤ 1.
• Adding a slack variable to a ≥ constraint Fix: ≤ takes +s. ≥ takes −s and +A. = takes +A only.
• Choosing the leaving variable using a zero or negative key column entry Fix: Take the ratio only for strictly positive entries in the key column. Pick the smallest.
• Dualising a Max problem that still has a ≥ constraint without converting it first. Fix: Convert to standard form first. For a Max primal, multiply a ≥ constraint by -1 so it becomes ≤. Then dualise.
• Not flipping the inequality or the objective type, or flipping only one of them. Fix: Remember that Max ↔ Min and the constraint direction flips together. Max primal with ≤ gives Min dual with ≥.

Exam tips

• In MCQs, check the sign of each constraint and the objective coefficients before looking at the options. Wrong options usually swap a sign or a coefficient.
• In written answers, always start with 'Let x₁ = …'. A complete answer defines the variables, the objective function, each constraint and non-negativity.
• Draw the usage table in your rough work. It prevents missed constraints and unit errors.
• Know the assumptions by name. Theory questions ask for them, often with a short explanation of each.
• Do not solve unless asked. If the question says 'formulate', stop after the model and use the saved time on other questions.
• Show the formulation, the plotted constraint lines, a shaded feasible region and a corner point table. Each earns marks even if the final arithmetic slips.
• Label every line with its equation and mark the corner coordinates on the graph.
• In MCQs, you often need only the corner points. Find the intersection and compare Z values rather than drawing a full graph.