Find the question you need
What optimal means · Solve the optimal segment · Secondary costs · Sensitivity · All chapters
Several decisions can share the same best score. This worked allocation model proves the entire optimal segment, compares slack and secondary outcomes, and shows how an explicit tie-breaking rule changes the selected plan.
Chapter index
Final audit: parameterise every optimal allocation
Advanced companion: sensitivity and solution selection
Chapters 1–4
1. One winning score does not identify one decision · 2. Write all constraints before selecting a solution · 3. Prove the upper bound on the primary score · 4. Construct the entire optimal segment
Chapters 5–8
5. Verify three candidates without guessing · 6. Examine resource and activity-capacity slack · 7. Compare an additional outcome that was not in the objective · 8. Choose a lexicographic secondary objective transparently
Chapters 9–12
9. Trade-offs can point to another optimum · 10. Distinguish multiple optima from degeneracy · 11. Sensitivity to small objective-coefficient changes · 12. What a resource shadow value describes
Chapters 13–16
13. Continuous decisions versus integer choices · 14. Audit the optimal solution before implementation · 15. Frequently asked questions and practice · 16. Read the connected methods and decision framework
An optimisation report may say that the maximum achievable score is thirty. That is a correct description of the best objective value, but it does not necessarily identify a unique plan. Multiple different allocations can achieve exactly the same score while giving different outcomes outside the stated objective.
We will construct an original two-variable linear programme representing two fictional categories of activity, x and y. Their combined use of a shared resource is limited, and each activity has its own capacity. The score rewards both activities at the same rate.
The feasible boundary contains not just one optimal point but an entire line segment of optimal points. We will verify the geometry, compare several allocations, examine slack and add a second decision criterion without silently changing the primary mathematical problem.
The quantities are invented units and do not describe a real procurement, school timetable or government budget. Their purpose is to expose the distinction between the maximum value of an objective function and the operational properties of a particular solution chosen from the optimum set.
Let x and y be nonnegative continuous decision variables. Each represents an amount of a different fictional activity. Assume the capacity limits x≤8 and y≤7, and a common resource limit x+y≤10.
The primary goal is to maximise P=3x+3y. Both activities contribute three score units per unit of activity. This is a stipulated decision value; it is not a measured monetary profit or social benefit.
The feasible set includes every point satisfying all five inequalities x≥0, y≥0, x≤8, y≤7 and x+y≤10. Some apparently attractive choices, such as x=8,y=7, are not feasible because they require fifteen units of a resource capped at ten.
Feasibility and optimality are different checks. A point cannot be called optimal merely because it has a high nominal score if it violates a constraint. Conversely a feasible point need not be best under the declared objective.
Contents · Previous chapter · Next chapter
The objective can be rearranged as P=3(x+y). Because x+y≤10, every feasible decision satisfies P≤3×10=30. This is a simple mathematical upper bound independent of any graph or software output.
To show that thirty is attainable, find a feasible point with x+y=10. The allocation (x,y)=(6,4) satisfies x≤8, y≤7 and both nonnegativity requirements, so it has P=3×6+3×4=30.
Therefore the global optimal value of the linear programme is exactly thirty. We have shown both an upper bound and a feasible point that reaches it, which is sufficient to prove optimality.
This proof tells us the maximum score, not whether (6,4) is the only maximiser. A mathematical certificate of objective value should not be mistaken for a uniqueness proof.
Contents · Previous chapter · Next chapter
To achieve P=30 the solution must satisfy x+y=10. Substituting y=10−x into y≤7 gives 10−x≤7, so x≥3. The separate capacity x≤8 gives x≤8.
Thus the complete set of optimal solutions is (x,10−x) for any real x between three and eight, inclusive. Every point on this segment is feasible and has the same objective P=30.
The endpoint allocations are A=(8,2) and B=(3,7). The midpoint-like option C=(6,4) lies between them. All three are optimal under the stated single-objective model despite being different operational allocations.
The Springer text on linear optimisation modelling explains that parallel objective and binding-constraint lines can produce multiple optimal points rather than one uniquely determined corner.
Contents · Previous chapter · Next chapter
Allocation A=(8,2) uses ten shared units, respects x≤8 and y≤7, and gives P=3×8+3×2=30. Allocation B=(3,7) also uses ten shared units and gives P=3×3+3×7=30.
Allocation C=(6,4) satisfies all capacities and yields P=18+12=30. The equality of objective values is exact; it is not a rounding effect, a near tie or a failure of a numerical solver.
Other allocations, such as (5,5) or (7.5,2.5), also achieve the optimum in this continuous model. The optimal set contains infinitely many points because every convex combination of A and B remains on the feasible optimal segment.
This geometric fact is different from a programme that merely has several almost-equal scores. We have a whole face of exact optimisers with an identical mathematical objective.
Contents · Previous chapter · Next chapter
Slack is the amount by which an upper-bound constraint is not fully used. For the shared resource x+y≤10, every optimal solution has zero slack because x+y=10 at the optimum.
At A=(8,2), the x-capacity is fully used and has zero slack, while y≤7 has slack 7−2=5. At B=(3,7), y-capacity is fully used and x-capacity has slack 8−3=5.
At C=(6,4), the x-capacity slack is two and the y-capacity slack is three. These slack patterns are different despite an identical maximum score and zero shared-resource slack.
A decision maker may care about unused specialised capacity, flexibility for later changes or resilience to disruption. The primary score says nothing about which slack profile should be preferred unless that consideration has been included explicitly.
Contents · Previous chapter · Next chapter
Imagine each unit of x has a secondary indicator E cost of four, and each unit of y has E cost of one. This is a fictional auxiliary measure, not measured environmental emissions or actual currency. Define E=4x+y.
For A, E=4×8+2=34. For B, E=4×3+7=19. For C, E=4×6+4=28. The secondary values differ substantially even though all three primary scores are thirty.
The primary linear programme did not try to minimise E; it only maximised P. Therefore it would be wrong to describe A and B as equally good across all possible operational criteria merely because they tie on P.
A multi-criteria decision requires another declared objective, constraint or preference rule. Introducing that rule after the result can be useful, but it should not be hidden as if it were already implied by the original maximum-score calculation.
Contents · Previous chapter · Next chapter
Suppose the decision policy is to maximise P first and, among exact primary optima, minimise E=4x+y. The lexicographic ordering protects the original maximum P=30 while selecting among the eligible optimal plans.
On the primary optimal boundary y=10−x, E=4x+10−x=10+3x. Because E increases with x, it is minimised at x=3, so the selected plan is B=(3,7) and the secondary minimum is nineteen.
Another policy could favour allocating at least six units to activity x. Adding x≥6 to the optimal-set comparison restricts x to [6,8]. Among those primary optima, E is minimised at C=(6,4), giving E=28.
The choice is not generated by the primary score alone. It comes from an explicitly stated secondary preference or constraint, and readers should be able to identify that additional decision information.
| Metric | A (8,2) | B (3,7) | C (6,4) |
|---|---|---|---|
| Primary P=3x+3y | 30 | 30 | 30 |
| Secondary E=4x+y | 34 | 19 | 28 |
| Secondary Q=2x+y | 18 | 13 | 16 |
| x-capacity slack | 0 | 5 | 2 |
| y-capacity slack | 5 | 0 | 3 |
| Shared resource slack | 0 | 0 | 0 |
Contents · Previous chapter · Next chapter
Define a different auxiliary measure Q=2x+y, interpreted purely as a second fictional benefit indicator. Along the primary optimal boundary y=10−x, Q=10+x. Thus Q increases with x.
Among all primary optima, the maximum Q occurs at A=(8,2), where Q=18. At B it is thirteen, and at C it is sixteen. This choice conflicts with the E-minimising preference, which favoured B.
Neither secondary criterion was in the original objective P. Their disagreement does not imply an optimisation error; it shows why a single mathematical score can omit considerations that the decision maker cares about.
An honest decision report presents alternative optimal allocations, relevant secondary metrics and the preference rule used for final selection. It should not label one solution uniquely best across all values when only one score was optimised.
Contents · Previous chapter · Next chapter
Multiple optimal solutions means more than one feasible decision vector attains the same global optimal objective value. Our example has infinitely many such points because the entire segment between A and B achieves P=30.
The technical term degeneracy in linear programming usually concerns a basic feasible solution with one or more zero basic variables or related basis structure, depending on formulation. That is not synonymous with having multiple optima.
A solver may return a corner point, such as A or B, even when interior points on the optimal segment exist. Its returned vector may depend on the algorithm and implementation details without making the other exact optima invalid.
See the Georgia Tech introduction to linear programming for feasible-region geometry, extreme points and multiple optimal solutions. A mathematical optimiser reports a solution to the stated model, not a complete statement of the organisation’s unstated preferences.
Contents · Previous chapter · Next chapter
The equal primary coefficients are responsible for the objective line being parallel to the shared-resource boundary. Suppose x now earns 3.1 score units while y still earns three, and all original constraints remain fixed.
The new objective becomes 3(x+y)+0.1x. Since the total resource remains capped at ten, the new optimum uses the full resource and favours the largest feasible x, which is eight. Allocation A=(8,2) becomes the unique optimum for this perturbed objective.
If instead y earns 3.1 while x earns three, the model favours maximum feasible y=7, selecting B=(3,7). Small changes in the coefficient ordering can select different endpoints when the original objective contains an exact tie.
This sensitivity is a mathematical property of the specified model. It shows why coefficients should be justified and, when uncertain, tested over credible ranges rather than reported as unquestionable facts.
Contents · Previous chapter · Next chapter
With both activities rewarded equally, define the shared resource limit as x+y≤b rather than ten. As long as b is positive and no larger than the combined individual capacities 8+7=15, feasible allocations can use the full b resource under this simple model.
The maximum primary score is then P*(b)=3b for 0≤b≤15. Increasing b from ten to 10.5 increases the optimal score from thirty to 31.5, a change of 1.5. The local marginal score from an extra shared-resource unit is three.
That marginal value is sometimes described as a shadow price in linear programming. It refers to the stated objective and the specified perturbation, not to an observed market price or a blanket value of all possible resources.
Once b exceeds fifteen, separate capacities prevent further growth of x+y. The optimum saturates at 3×15=45, so the marginal value of more shared resource falls to zero under this model. Shadow values can change across parameter regimes.
Contents · Previous chapter · Next chapter
Our model permits fractional activity units, so every real x∈[3,8] with y=10−x is an exact optimum. This is appropriate for divisible quantities but may be inappropriate when x and y count indivisible machines, whole classrooms or discrete appointments.
If x and y must instead be nonnegative integers, the feasible optimal options become exactly six allocations: (3,7), (4,6), (5,5), (6,4), (7,3) and (8,2). All six still have primary score thirty.
The integer restriction removes the continuum of intermediate optima but does not create a unique allocation. Additional constraints and an operational choice remain necessary if exactly one plan must be implemented.
Never assume an optimisation solution can be rounded freely. Naively rounding several variables may violate a binding resource or capacity constraint. Integer programming changes the feasible set and should be modelled explicitly.
Contents · Previous chapter · Next chapter
A useful optimisation audit begins with the actual objective, decision variables and units. Are coefficients measured or stipulated? Do they correspond to the real decisions the model claims to support?
Next check every constraint and its interpretation. A capacity might represent a maximum, a minimum service obligation or an equality. Confusing these changes the feasible region and invalidates the computed plan.
Then verify that the selected solution attains the stated objective and that no superior feasible objective is possible. In our case P≤30 is a simple upper-bound certificate and every listed optimal point reaches it.
Finally examine whether secondary consequences matter. The model’s objective cannot speak for fairness, delivery timing, reliability or environmental impact unless those have been included or explicitly evaluated after identifying the optimal set.
Contents · Previous chapter · Next chapter
Does a solver returning A prove A is uniquely optimal? No. Our original objective also permits B, C and every point on the segment between A and B. An extreme-point algorithm may output a corner without showing the full optimal face.
Does equal objective mean equal resource use? In this example all primary optima use shared resource ten, but their uses of the two individual activity capacities differ. A different optimisation model could exhibit other patterns.
Practice A: verify all five inequalities for (5,5). Practice B: show why (2,8) is infeasible despite having P=30, because y exceeds seven. Practice C: choose a lexicographic objective that maximises Q=2x+y among primary optima and derive A as the selected plan.
Practice D: change x-capacity from eight to six while keeping y≤7 and shared resource ten. Determine the new optimal segment and its endpoints. The maximum P remains thirty because x=3,y=7 or x=6,y=4 can still use ten resource units.
Contents · Previous chapter · Next chapter
The result is exact: with P=3(x+y), x≤8, y≤7 and x+y≤10, the maximum is thirty and all points (x,10−x), 3≤x≤8, attain it. Different decisions can share a mathematically optimal score while carrying different secondary consequences.
Use The Gold Standard of Operations Research for the subject foundation and The Gold Standard of Decision Theory for explicit preferences and competing objectives.
The Springer linear-optimisation chapter and Georgia Tech linear-programming introduction explain objective functions, feasible regions and multiple optima. Our three example allocations and secondary metrics are original hypothetical calculations.
Continue through the Gold Standard hub and How X Works. A trustworthy optimisation report identifies what is optimal, what remains undecided and what extra policy or evidence selects one plan from a set of equally scoring alternatives.
Advanced worked companion: sensitivity, selection rules and implementation
Prove which primary-optimal plans remain after a new service requirement
Return to the original optimum set: all allocations (x,10−x) with 3≤x≤8. Suppose the organisation adds a requirement that activity x receive at least six units. This is a new policy constraint, x≥6, not something implied by the original objective function P=3x+3y.
The primary-optimal segment is now restricted to 6≤x≤8, with y=10−x. All these points still achieve P=30. The earlier allocation B=(3,7) becomes unacceptable under the new policy, while C=(6,4) and A=(8,2) remain feasible. The changed feasible set is the reason B disappears; it has not suddenly become worse at the original primary objective.
If the secondary indicator E=4x+y must be minimised among the remaining primary optima, substitute y=10−x to obtain E=10+3x. This expression rises with x, so the selected plan is C=(6,4), with E=28. The decision path is clear: first satisfy the declared x-allocation rule, then preserve P=30, then minimise E.
A different added policy, such as y≥6, would restrict the original optimal segment to x≤4. Since the segment already required x≥3, the eligible points would be 3≤x≤4, and the E-minimising plan would again be B=(3,7). The precise additional constraint determines which tie-breaking result is defensible.
An epsilon-constraint example without hiding the hierarchy
Suppose the secondary cost indicator must not exceed E=25. Along the primary-optimal boundary, E=10+3x. The inequality 10+3x≤25 gives x≤5. Combining it with the original optimal segment yields 3≤x≤5, y=10−x. The primary maximum thirty remains achievable within this restricted set.
Among that subset, if a further objective seeks to maximise Q=2x+y=10+x, it selects x=5,y=5, giving Q=15 and E=25. If instead the secondary aim were solely to minimise E, the choice remains x=3,y=7 with E=19. The chosen plan changes because the preference rule changes, not because the numerical solver has produced inconsistent answers.
The epsilon-constraint method represents an important modelling principle: move a secondary performance threshold into the constraints while retaining a primary objective. This may be more transparent than adding arbitrary weighted scores when decision makers can specify a real upper limit on a meaningful secondary quantity.
Sensitivity when objective coefficients are uncertain
Originally both activities contribute three units of primary score, so every point with x+y=10 ties. Now suppose x’s coefficient is 3+δ and y’s stays three. Along the shared-resource boundary the objective becomes 30+δx. Any positive δ selects the largest x=8, while any negative δ selects the smallest x=3, provided the resource boundary remains optimal for the small perturbation being considered.
For an explicit small change δ=0.1, the objective at A becomes 3.1×8+3×2=30.8, at B 3.1×3+3×7=30.3, and at C 3.1×6+3×4=30.6. This makes A the unique optimal allocation. A small negative perturbation δ=−0.1 reverses that ordering, favouring B.
The example shows why an exact tie can make the selected decision sensitive to small coefficient differences. If real-world benefit coefficients are estimated from uncertain observations, a plan that depends entirely on an insignificant coefficient difference should be labelled accordingly. Sensitivity analysis is evidence about robustness, not an excuse to invent precision.
Trace the shared-resource shadow value
Write the shared capacity as x+y≤b instead of ten while keeping 0≤x≤8 and 0≤y≤7. For any b between zero and fifteen, there is a feasible allocation using the full amount b. The primary objective maximum is therefore P*(b)=3b in this range.
At b=10, increasing shared resource by half a unit makes the new optimum 31.5 instead of thirty. The additional half unit is worth 1.5 units of objective score, corresponding to a local marginal value of three score units per resource unit. One possible new allocation is x=8,y=2.5; another is x=3.5,y=7.
Once b reaches fifteen, the individual capacities x≤8 and y≤7 together cap total activity at fifteen. Further increases in b then cannot raise P, so the shadow value of additional shared capacity becomes zero in this simple model. A shadow price belongs to a particular objective and range of constraints, not to every possible scenario.
Distinguish continuous decisions and indivisible units
The original continuous model has infinitely many optimal points along its segment. If x and y represent whole objects that cannot be divided, constrain them to integers. Then the primary optimum has exactly six allocations: (3,7), (4,6), (5,5), (6,4), (7,3) and (8,2). Each reaches P=30.
Integer restrictions change the feasible set. A fractional optimal output should not simply be rounded independently when resources are binding, because rounding may create an infeasible plan. In other optimisation problems, integer restrictions can even change the best attainable objective value, not just the count of optimal plans.
The Georgia Tech linear-programming materials discuss basic feasible points and simplex methods, while the Springer linear optimisation chapter explains how a flat optimal face contains multiple solutions. Those principles frame our hypothetical two-variable example.
A decision-ready report after mathematical optimisation
A useful implementation report separates model facts from policy choices. It states the variables and units, the exact feasible constraints, the optimum value, whether that optimum is unique, and the secondary indicators that differ across exact primary optima.
The report then records how one plan was selected. In our example, choosing B because it minimises E is defensible if E is relevant and the choice has been approved. Choosing A because it maximises Q is also consistent with the primary optimum under a different declared secondary aim. Neither decision can be recovered from P=30 alone.
Finally, validate the model coefficients and constraints against actual operations before implementation. The mathematics can correctly optimise a flawed objective or an incomplete capacity description. Robust operational reasoning makes the missing assumptions visible rather than trusting an impressive maximum score to explain the entire decision.
Return to chapter index · Operations Research subject root
Final audit: parameterise every optimal allocation
The entire primary-optimal segment can be expressed with a single parameter θ between zero and one: x=3+5θ and y=7−5θ. At θ=0 the plan is B=(3,7); at θ=1 it is A=(8,2). Every intermediate θ is another exact continuous optimum. The shared resource remains x+y=10 and the primary score remains P=30.
Under this parameterisation, secondary cost E=4x+y becomes 19+15θ, while auxiliary benefit Q=2x+y becomes 13+5θ. Increasing θ improves Q but also increases E, assuming lower E and higher Q are desirable. Neither endpoint dominates the other on both secondary criteria; there is a genuine trade-off that the primary score does not resolve.
Capacity slacks can also be reconstructed from θ: the unused x capacity is 8−x=5−5θ, and unused y capacity is 7−y=5θ. These sum to five throughout the optimal segment, but their allocation between activities changes. Equal total unused specialised capacity does not mean equal operational flexibility.
This explicit one-parameter representation provides a useful audit when software returns only one corner. Analysts can enumerate the alternative optimal face, calculate secondary outcomes and invite decision makers to state a legitimate selection rule before one mathematical optimum is converted into an implemented operational plan.