Skip to content
Sem 5 Prep
← BI & Data ScienceLinear programming: turning a business problem into a model

Formulas for this chapter

The LP model template

Maximise (or Minimise) Z = c1 x1 + c2 x2 + ... + cn xn subject to a11 x1 + a12 x2 + ... <= b1 a21 x1 + a22 x2 + ... <= b2 x1, x2, ..., xn >= 0

Every formulation question. Write the four blocks in this order: variables in words, objective with direction, one line per constraint, non-negativity.

xj
Decision variable j, defined in words with units
cj
Objective coefficient: profit or cost per unit of xj
aij
Amount of resource i used by one unit of xj
bi
Amount of resource i available, the right-hand side

Corner point of two constraints

Solve the two boundary equations simultaneously: a11 x + a12 y = b1 a21 x + a22 y = b2 Subtract when a term matches; else substitute.

Listing the corners of a two-variable feasible region. Discard any intersection that violates another constraint or non-negativity.

b1, b2
Right-hand sides of the two constraints
(x, y)
The candidate corner point

Slack and surplus

slack = RHS - LHS (for a <= constraint) surplus = LHS - RHS (for a >= constraint) Binding <=> slack = 0

After solving, to say which resource limits the business. Solver's Answer Report prints this column for you.

LHS
Left-hand side evaluated at the optimal solution
RHS
The stated limit
Step 2 of 25
The real wordsTheory

Linear programming, defined

Linear programmingA mathematical optimisation technique used to determine the best possible decision, such as maximising profit or minimising cost, while satisfying a set of business constraints such as limited labour, materials, budget or machine hours, with a set of linear rules.

"Programming" here means planning, not coding. The technique dates from the 1940s and predates the computer it now runs on.

← BackContinue →