AL17, AL18 - Solving linear programs with software | OCR A-Level Further Mathematics B (MEI)

Specify an LP or ILP for a solver, read its decision values and objective in context, and distinguish an optimal result from a feasible candidate or a failed model. Software provides computing power; the formulation determines what its answer means.

Supplying the correct mathematical model

A solver reports a minimum of $7$ worker-minutes for two tasks, yet the workers can finish them in $4$ minutes. Can both statements be correct?

Yes: total worker-time and elapsed completion time are different objectives. First check what the model asked the computer to optimise.

You already know

An LP needs defined numerical decisions, an objective and constraints. Ordinary simplex solves a continuous problem; whole-count decisions need an integer requirement. Graphs and hand calculations help check a small instance before scaling up.

A spreadsheet solver typically needs decision cells, an objective cell with a maximise/minimise setting, resource or balance constraints, and variable domains. Other optimisation software needs the same mathematical information in another format. Some routines accept only standard-form LPs; others also accept non-standard or integer formulations.

Worked example 1: a continuous solver model

Question. Specify a solver model for maximising $P=3x+2y$ , subject to $2x+y\le8$ , $x+2y\le8$ , $x,y\ge0$ . The quantities are divisible.

Plan. Identify the decision entries, calculated expressions, optimisation direction and continuous domains.

Solver component	Required content
Decision entries	Numerical values of $x,y$
Objective expression	$3x+2y$ , maximise
First calculated resource	$2x+y\le8$
Second calculated resource	$x+2y\le8$
Domains	Non-negative continuous $x,y$

An optimal output is:

Variable	Value
$x$	$2.666667$
$y$	$2.666667$
Objective	$13.333333$

2\left(\frac83\right)+\frac83=8,\qquad 3\left(\frac83\right)+2\left(\frac83\right)=\frac{40}3

Why this step? The solver's variable cells must be the actual decisions; calculated resource totals are constraints, not extra independent choices.

Answer. The settings in the first table define the continuous model. Its exact optimal solution is $x=y=8/3$ , $P=40/3$ .

Check. Both resources are fully used. The displayed decimals are rounded versions of the exact values, so tiny rounding discrepancies are expected.

Change only the decision domains.

Worked example 2: an integer requirement

Question. The same objective and resource limits now concern complete items. Specify the required solver change and interpret this optimal output.

Variable	Value
$x$	$3.000000$
$y$	$2.000000$
Objective	$13.000000$

Plan. Retain the expressions and bounds, but require both decision variables to be integers.

\begin{aligned} x,y&\in\mathbb Z_{\ge0}&&\text{whole non-negative items}\\ 2(3)+2&=8&&\text{first resource use}\\ 3+2(2)&=7&&\text{second resource use}\\ P&=3(3)+2(2)=13&&\text{objective in its original units} \end{aligned}

Why this step? Formatting a spreadsheet cell to show no decimal places does not impose an integer constraint on the mathematical solution.

Answer. Add the integer domains to the solver. The output recommends $3$ first items and $2$ second items, with objective $13$ .

Check. The slacks are $0$ and $1$ ; both are non-negative.

For practical data, keep the constraint coefficient table, bounds and units explicit. A correct solver answer to the wrong table remains the wrong answer to the practical question.

Watch out

Wrong: round a continuous report and call it an integer optimisation. Right: solve with the required integer or binary domains included.

Read a new domain choice before accepting a report.

Interpreting allocation output and units

A solver's output often lists values for many arc or allocation variables. Return to their definitions before adding anything.

Here $A1=1$ means worker $A$ performs task $1$ , not that the task takes one minute. Each worker may do at most one task, and both tasks are required.

Worker	Task $1$ , minutes	Task $2$ , minutes
$A$	$4$	$7$
$B$	$5$	$3$
$C$	$6$	$4$

Worked example 3: selected pairings and total time

Question. Interpret this optimal allocation output and calculate its total worker-time.

Variable	Value
$A1$	$1.000000$
$A2$	$0.000000$
$B1$	$0.000000$
$B2$	$1.000000$
$C1$	$0.000000$
$C2$	$0.000000$

Plan. Translate the binary selections, then multiply each selected variable by its task time.

\begin{aligned} A1=B2&=1&&\text{selected assignments}\\ W&=4(1)+3(1)=7&&\text{worker-minutes}\\ \text{elapsed time}&=\max(4,3)=4&&\text{if both start together} \end{aligned}

Why this step? The objective sums worker-times. Independent simultaneous tasks finish when the slower selected task finishes, not when their durations have been added.

Answer. $A$ does task $1$ , $B$ does task $2$ , and $C$ is unused. Total worker-time is $7$ minutes; with simultaneous starts and no further restrictions, elapsed time is $4$ minutes.

Check. Each task appears once, each selected worker has one task, and all other selection variables are zero.

Change only worker availability.

Worked example 4: interpreting a changed optimum

Question. Worker $B$ is unavailable. An optimal solver output has $A1=C2=1$ , with every other variable zero. Interpret the result and calculate the relevant times.

Plan. Decode the new selection and use the unchanged cost table.

\begin{aligned} A1=C2&=1&&\text{new assignments}\\ W&=4+4=8&&\text{total worker-minutes}\\ \text{elapsed time}&=\max(4,4)=4&&\text{independent simultaneous starts} \end{aligned}

Why this step? A higher total workload need not mean a longer elapsed completion time; the chosen objective and the parallel schedule measure different quantities.

Answer. $A$ performs task $1$ , $C$ performs task $2$ . Total worker-time is $8$ minutes and possible elapsed time remains $4$ minutes.

Check. No variable belonging to unavailable $B$ is selected, and both task equalities still hold.

For flow output, add flows across the source boundary or sink boundary, rather than summing every arc value. Internal flow would otherwise be counted several times. For path output, read selected arcs in connectivity order rather than treating the variable listing as a route order.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AL17, AL18 - Solving linear programs with software

Supplying the correct mathematical model

Interpreting allocation output and units

Continue this lesson.

Learn faster with Nova