Maximise a weighted sum of two objectives and sweep the weight from one end to the other. The optimal basis changes at only finitely many weights — objective coefficient ranging, chained — and the corners visited along the way are exactly the efficient points of the two-objective problem. The weights are the decision and they are made outside the model; what the mathematics delivers is the set of corners nothing beats in both objectives together.
Core ideas
Nothing new is computed here. What is new is that a two-objective problem has a set of answers rather than an answer, and that the set is finite and computable.
(1 − λ)f₁ + λf₂ is a single linear objective whose coefficients are affine in λ. For a fixed basis, every reduced cost is therefore affine in λ too, so the set of weights keeping that basis optimal is an intersection of intervals — one line of arithmetic, not a search. The breakpoint is where some reduced cost reaches exactly zero, which is an objective coefficient range endpoint under a different name.
There are only so many bases, so the sweep from λ = 0 to λ = 1 visits finitely many corners and changes at finitely many weights. Those weights are exact fractions. Sampling λ on a grid would find the same corners on a good day and could never establish that there are no others between two samples.
A corner is efficient, or Pareto optimal, when no feasible point scores at least as much on both objectives and strictly more on one. That is a weaker demand than being best, and it is the right one: a two-objective problem has no single best point unless the objectives happen to agree, and what the mathematics can deliver is the set that survives this test.
The material
Why the breakpoints are finite and exact, what the corners in between are, and which part of the problem the mathematics does not decide.
For a feasible region and two objectives f₁, f₂ to be maximised, a feasible point p is efficient when no feasible point q has f₁(q) ≥ f₁(p) and f₂(q) ≥ f₂(p) with at least one inequality strict. The set of efficient points is the Pareto front.
The corners found by maximising (1 − λ)f₁ + λf₂ over λ in [0, 1] are the supported efficient corners — those a weighted sum can reach.
The lab's slider is the weight on the second objective, so λ = 0 maximises f₁ alone and λ = 1 maximises f₂ alone. Everything between is a trade, and the useful fact is that the trade is not continuous in the answer: the corner chosen is constant over an interval of weights and then jumps.
Fix a basis. Under the objective (1 − λ)f₁ + λf₂, every reduced cost is of the form a + λ(b − a), where a and b are that column's reduced costs under f₁ and f₂ alone. The basis is optimal exactly while all of them are non-negative, which is an intersection of at most one interval per nonbasic column.
At the upper end of that interval some reduced cost is exactly zero, and one pivot on that column reaches the next basis, whose interval begins there. Since there are finitely many bases, the sweep terminates, and the breakpoints are the finitely many weights at which two corners score the same weighted total.
At λ = 0 the answer is (7, 0), which is the most f₁ the region allows. Nudge the weight towards the second objective and nothing happens until λ = 1/12, where (7, 0) and (6, 3) score the same 105/4 and the answer changes. It then holds until 1/3, and so on.
So λ = 0.08 chooses (7, 0) and λ = 0.09 chooses (6, 3), and no slider position in hundredths ever lands on 1/12 itself — the breakpoint falls strictly between two hundredths. That is the difference between computing the breakpoints and looking for them.
This is the misconception the lesson exists for. A two-objective problem does not have an optimum, and the weights are not a technical detail on the way to one: they are the decision, and they are made outside the model by whoever is entitled to make it. What the mathematics delivers is smaller and more honest — the set of corners that no feasible point beats on both objectives at once, with the exact weight at which each one takes over.
Which is genuinely useful, because it rules things out. A point that is not efficient is one nobody should choose under any weights at all, since something else is at least as good on both counts. Presenting four corners and their scores is a complete answer to what the model can say, and it leaves the part it cannot say visible rather than buried in a weight somebody picked.
x1 ≤ 8, x2 ≤ 6, x1 + x2 ≤ 10, 2x1 + x2 ≤ 16, with f₁ = 3x1 + x2 and f₂ = x1 + 3x2. The front is (8, 0) scoring (24, 8) for λ up to 1/6, then (6, 4) scoring (22, 18) up to 1/2, then (4, 6) scoring (18, 22).
Note that (0, 6), which scores (6, 18), is a corner of the region and is not on the front: (4, 6) beats it on both objectives at once. A corner being reachable is not the same as a corner being worth considering, and the front is the smaller list.
There is a second route to the same set. Instead of weighting the two objectives, maximise f₁ subject to a constraint f₂ ≥ t and sweep t — the ε-constraint method. That is right-hand-side ranging rather than objective ranging, and its breakpoints are the values of t at which the basis changes, exactly as in the shadow-price lesson. The two sweeps trace the same front, and the ε-constraint route additionally reaches efficient points that no weighted sum does, which is a distinction that costs nothing here — a linear programme has none — and matters elsewhere.
One structural fact, and the place it stops being true. Every efficient point of a linear programme is a convex combination of efficient corners, so the four corners above describe the whole front and not merely samples of it. That is false for integer problems: an integer programme's efficient set has points that lie between corners and are not combinations of them, because the combinations are not feasible. Integer Programming is where that is felt, and it is worth knowing in advance that this lesson's tidiness is a property of linearity rather than of two-objective problems.
Interactive
every corner a weighted sum can reach, and the exact weights where it changes
Method
Solve at one end, range the weight, pivot at the breakpoint, repeat. The Pareto test comes last and is a comparison, not a solve.
At λ = 0 the objective is f₁ alone. That gives the first corner and the basis the sweep starts from. Solving at the other end as well is a useful check on where the sweep must finish.
For each nonbasic column, its reduced cost is affine in λ; require all of them to be non-negative and intersect the intervals. The upper end of the result is the next breakpoint, and the column whose reduced cost reached zero there is the one that enters.
One pivot on that column reaches the next basis, whose interval starts where the last one ended. Record the corner and its two scores (f₁, f₂), not just the weighted total, because the weighted total is the thing that depends on a choice.
Compare every recorded corner against every other: drop any that another beats on both objectives. Then present the survivors with their scores and their weight intervals, and state plainly that choosing among them is not a mathematical question.
The weight below is the weight on the second objective, so the sweep starts at the corner that maximises the first one. Each breakpoint is found by setting two weighted totals equal, which is why they come out as exact fractions.
The Pareto test at the end is three comparisons and no arithmetic: the corners come out of the sweep sorted by f₁ descending, and if f₂ is ascending at the same time then none can dominate another. When f₂ is not monotone the sweep has produced a corner that something else beats on both counts, and it is dropped — as (0, 6) is on the smaller region.
The last two lines are the reason the breakpoints are computed. The slider moves in hundredths, 1/12 is 0.0833…, and no position on the slider is ever exactly at the breakpoint. A reader sweeping by hand would see the answer change between two positions and would have no way to say where.
For a faded rehearsal, run the smaller region: x1 ≤ 8, x2 ≤ 6, x1 + x2 ≤ 10, 2x1 + x2 ≤ 16, with f₁ = 3x1 + x2 and f₂ = x1 + 3x2. The supplied move is that λ = 0 gives (8, 0). Find the two breakpoints by setting corner totals equal, list the front, and then explain why the region's corner (0, 6) does not appear on it.
You should be able to write the weighted objective, range the weight for a basis, find each breakpoint by setting two corner totals equal, list the corners with both their scores and their weight intervals, drop the ones another dominates, and say which part of the problem the mathematics did not decide.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.