Linear Programming: formula sheet

Key formulas

Objective function (maximisation)

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

cⱼ is the contribution or profit per unit of xⱼ. Use contribution per unit, not profit after fixed costs, when fixed costs do not change with the decision.

Objective function (minimisation)

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

cⱼ is the cost per unit or per use of xⱼ.

Resource constraint

a₁₁x₁ + a₁₂x₂ + … + a₁ₙxₙ ≤ b₁

aᵢⱼ is the use of resource i per unit of xⱼ; bᵢ is the availability. Use ≤ for limited resources.

Requirement constraint

a₂₁x₁ + a₂₂x₂ + … + a₂ₙxₙ ≥ b₂

Use ≥ for minimum requirements such as minimum nutrients, minimum output or contracted supply.

Non-negativity

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

Always state it. Leaving it out loses marks.

General two-variable LPP

Maximise or minimise Z = ax + by, subject to a₁x + b₁y (≤ or ≥) c₁, a₂x + b₂y (≤ or ≥) c₂, x ≥ 0, y ≥ 0

Z is the objective function. Write it clearly before you draw anything.

Axis intercepts of a constraint line

Put y = 0 to get the x-intercept: x = c ÷ a. Put x = 0 to get the y-intercept: y = c ÷ b.

Two intercepts are enough to draw each line.

Corner point theorem

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

Evaluate Z at every corner. Pick the largest for maximisation and the smallest for minimisation.

Slope of the objective (iso-line)

Slope of ax + by = Z is −a ÷ b

Useful to cross-check which corner is optimal. Lines of equal profit or cost are parallel.

Corner at intersection of two lines

Solve the two constraint equations simultaneously

Then check the point satisfies all other constraints.

Test for the side to shade

Substitute (0, 0) into the constraint. If true, shade the side containing the origin.

Do not use this test if the line passes through the origin.

Slack variable (≤ constraint)

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

S has coefficient 0 in the objective. It can serve as a starting basic variable.

Surplus and artificial variables (≥ constraint)

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

S is surplus and A is artificial. The artificial variable is the starting basic variable. An = constraint gets only A.

Big M objective coefficients

Maximisation: −M for each A. Minimisation: +M for each A.

M is a very large positive number. Slack and surplus variables carry 0.

Zj and Cj − Zj rows

Zj = Σ (Cb × column coefficient); Cj − Zj = Cj − Zj

Cb is the objective coefficient of each basic variable. The value of Z is Σ (Cb × solution value).

Entering variable rule

Maximisation: largest positive Cj − Zj. Minimisation: most negative Cj − Zj.

This column is the key column.

Minimum ratio (leaving variable)

Ratio = solution value ÷ key column coefficient, only where the coefficient > 0

The smallest ratio gives the key row. The element where key row and key column meet is the pivot.

Optimality condition

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

Stop when this holds. Check that no artificial variable remains in the basis at a positive value.

Row operations

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

After this, the key column becomes a unit column.

Primal to dual: objective

Max Z = c1x1 + ... + cnxn ↔ Min W = b1y1 + ... + bmym

Maximisation primal gives a minimisation dual, and the reverse. Dual objective coefficients are the primal right-hand sides (b values).

Primal to dual: constraints

Number of dual constraints = number of primal variables; number of dual variables = number of primal constraints

Each primal constraint gives one dual variable. Each primal variable gives one dual constraint. The dual's right-hand sides are the primal's objective coefficients (c values).

Transpose rule

Dual coefficient matrix = transpose of primal coefficient matrix (rows become columns)

The coefficient of xj in constraint i of the primal becomes the coefficient of yi in constraint j of the dual.

Standard pair (max, ≤)

Primal: Max Z = cx, Ax ≤ b, x ≥ 0 ↔ Dual: Min W = by, Aᵀy ≥ c, y ≥ 0

Put the primal in this form first. For a min primal with ≥ constraints, the dual is a max with ≤ constraints.

Handling = and ≥ in a max primal

A ≥ constraint: multiply by -1 to get ≤ form. An = constraint: gives a dual variable unrestricted in sign (or write it as two inequalities, ≤ and ≥).

Convert ≥ constraints before forming the dual. An unrestricted primal variable gives an = constraint in the dual.

Strong duality

Optimal Z (primal) = Optimal W (dual)

Holds when both problems have optimal solutions. Use it as a check on your answer.

Shadow price

Shadow price of resource i = yi* = ΔZ ÷ Δbi

Change in optimal objective per unit change in resource i, valid only within the range where the optimal basis stays the same.

Complementary slackness

If slack in constraint i > 0, then yi* = 0. If yi* > 0, then constraint i is binding.

Likewise, if xj* > 0 then the j-th dual constraint holds as an equality.

Shadow price

Shadow price = ΔZ ÷ Δb (change in optimal Z per unit change in a resource), valid only within the range of feasibility

In a maximisation final table, read it from the Zj − Cj value under that constraint's slack variable.

Range of optimality (two variables, graphical)

Optimum stays unchanged while the slope of the objective line lies between the slopes of the two binding constraints

For constraints a1x + b1y and a2x + b2y at the optimal corner, c_x ÷ c_y must lie between a1 ÷ b1 and a2 ÷ b2.

Range of feasibility

Vary one RHS b, recompute the basic variables, and keep b within the limits where all basic variables stay ≥ 0

Outside this range the shadow price changes or the basis changes.

Complementary slackness

Slack > 0 ⇒ shadow price = 0; shadow price > 0 ⇒ slack = 0

Use it to check which resources are worth buying more of.

Optimality test (maximisation)

Optimal when all Zj − Cj ≥ 0 (equivalently Cj − Zj ≤ 0)

A zero value for a non-basic variable signals alternative optima.

Special-case signals in the simplex table

Unbounded: entering column has no positive entry. Infeasible: an artificial variable remains in the basis at a positive value at the end. Degenerate: tie for the minimum ratio, giving a basic variable at zero.

Check these before you declare an answer.

Quick revision

• Formulation order: define decision variables, write the objective function, list constraints, add non-negativity.
• The objective coefficient is usually contribution per unit, not selling price.
• The optimal solution of a feasible, bounded LP lies at a corner point of the feasible region.
• Graphical method handles two decision variables.
• Simplex adds a slack variable to each ≤ constraint to make it an equation.
• Entering variable in maximisation is the column with the most positive value in the Cj − Zj row.
• Leaving variable comes from the minimum non-negative ratio of the right-hand side to the pivot column value.
• Stop when no Cj − Zj value in a maximisation problem is positive.
• Shadow price is the change in the optimal objective value for one extra unit of a scarce resource.
• A resource with spare capacity (positive slack) has a shadow price of zero.
• The dual of a maximisation problem is a minimisation problem, and dual variables correspond to primal constraints.
• Infeasible means no feasible region exists, and unbounded means the objective can grow without limit.

Common mistakes

• Using selling price instead of contribution per unit in the objective function. Fix: Compute selling price minus variable cost per unit. Use it unless the question states profit per unit.
• Choosing the wrong inequality sign. Fix: Resource limits and maximum demand take ≤. Minimum requirements and minimum supply take ≥.
• Shading the wrong side of a constraint line Fix: Substitute (0, 0) into the inequality. If it holds, shade the origin side. Otherwise shade the other side.
• Taking an intercept as a corner point when it is outside another constraint Fix: Test every candidate corner in all constraints. Only points satisfying all of them belong to the feasible region.
• Adding a slack variable to a ≥ constraint. Fix: For ≥, subtract a surplus variable and add an artificial variable. A slack variable belongs only to ≤.
• Dividing by zero or negative key-column entries in the ratio test. Fix: Take ratios only where the key-column coefficient is positive. Ignore zero and negative entries.
• Not converting the primal to standard form before writing the dual. Fix: For a max problem, make every constraint ≤ first (multiply a ≥ constraint by -1). For a min problem, make every constraint ≥. Then dualise.
• Using the wrong inequality direction in the dual. Fix: Max primal with ≤ gives a min dual with ≥. Min primal with ≥ gives a max dual with ≤. Say it aloud once before writing.
• Applying a shadow price beyond its range of feasibility Fix: Always compute the range. State the premium is worth paying only up to the upper limit of that range.
• Giving a positive shadow price to a resource with unused slack Fix: If slack > 0 the shadow price is zero. Only fully used resources carry a positive shadow price.

Exam tips

• In Section A, expect MCQs on LP assumptions, the meaning of terms like objective function and feasible region, and which sign suits a given condition. Learn the assumptions as a short list.
• In descriptive questions, always define variables first. Marks are usually given for variables, objective, each constraint and non-negativity separately.
• Check whether the question gives contribution, profit or only price and cost. Compute contribution if needed and show the working.
• If the question asks to formulate and solve, formulate cleanly first, because an error in formulation carries through every later step.
• For 'state limitations of LP' questions, link each limitation to an assumption: linearity, certainty, divisibility and single objective.
• Write the formulation first: define variables, objective and constraints. Marks are usually given for correct formulation even if arithmetic slips later.
• Label each line with its equation and mark the feasible region clearly. A clean graph earns presentation marks and helps you find corners.
• Show a corner point table with Z values. It makes the examiner's job easy and shows you compared all corners.