D1 5.1 - Formulating linear programs
Turn choices about production, costs and limited resources into a linear program. Define variables with meaningful units, choose an objective to maximise or minimise, and write constraints that express the context accurately.
Decision variables and units
A workshop earns more from a large kit than a small one. Should it make only large kits? Not necessarily: a large kit may use much more of a scarce resource. We need a model that compares whole production plans, not just individual selling prices.
A decision variable represents a quantity we are free to choose. Write what it counts, its unit and the time period. If means small kits made per day and means large kits made per day, then describes one day's plan. It does not mean six pounds of profit or six hours of work.
Linear program
A linear program chooses values of decision variables to maximise or minimise a linear objective, subject to linear constraints. Each variable appears to the first power with a constant coefficient; expressions such as are linear, whereas and are not.
A model can have more than two variables. Graphical solutions use two because we can draw their feasible plans on ordinary coordinate axes. Whole objects require integer values; divisible quantities such as kilograms may be continuous. Record that condition explicitly where it applies.
Worked example 1: counting individual products
A workshop chooses how many small kits and large kits to make each day. Define suitable variables and express a plan of small kits and large kits.
Plan. Let each variable count one product type over the same period.
Answer. The plan is , with and integer because kits are whole objects.
Check. There are kits in the day's plan. Both variables use counts per day, so this addition makes sense.
Change only the counting unit: the workshop now plans in batches of four kits. Numerical coefficients in the later model must change with the unit.
Worked example 2: counting batches
Let and count batches of four small and four large kits made per day. Express the same physical plan of small and large kits.
Plan. Divide each product count by the four kits per batch.
Answer. The batch plan is . If only complete batches are allowed, are nonnegative integers.
Check. Multiplying back gives small and large kits. The same numbers would describe a different plan in batch variables.
Watch out
Do not define as “small kits” alone. “Number of small kits made per day” identifies the quantity and period. If a problem defines variables for you, keep that definition throughout.
The coefficient of a variable must match its unit: a cost per individual kit cannot multiply a batch count without conversion.
Objective functions
The objective function measures what makes one feasible plan better than another.
If a small kit contributes profit and a large kit contributes , then a daily plan contributes pounds. To seek the greatest profit, state maximise, not just the expression. For a purchasing problem the objective may instead be to minimise total cost.
“Linear” assumes each additional item has the same contribution within the model. If the selling price changes with the amount sold, or a discount changes unit cost after a threshold, a single constant-coefficient expression may no longer describe the situation.
Objective function
An objective function is the quantity to be optimised. A complete objective specifies both the expression and the direction, such as “maximise ” or “minimise ”. Its units follow from the coefficients and variable definitions.
Worked example 3: maximising profit
A small kit sells for and costs to make. A large kit sells for and costs to make. With individual kits made and sold per day, write the profit objective.
Plan. Subtract each unit's cost from its selling price, then multiply by the number sold.
Answer. Maximise , measured in pounds per day.
Check. A plan has revenue and variable cost , so profit . The objective gives .
Change only the objective being requested, from profit to revenue. The products and their prices and costs are unchanged.
Worked example 4: maximising revenue
For the same workshop, write the daily revenue objective.
Plan. Revenue counts money received, so use selling prices without subtracting production costs.
Answer. Maximise , pounds per day.
Check. At , , matching the actual sales receipts. Maximising revenue and maximising profit are different modelling aims and need not choose the same plan.
A fixed daily overhead, say , changes profit to . It changes the reported profit but not which feasible plan maximises it, because every plan loses the same . A cost incurred only when a particular decision is made is not automatically a fixed constant.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account