Augmenting path in a matching Created 2026-10-06 Updated 2026-10-14
An augmenting path in a matching is a nonempty alternating path in a matching with distinct endpoints that are both unmatched vertices in a matching. Its first and last edges lie outside . Thus it has unselected edges and selected edges, for some . Taking the symmetric differenceremoves the selected edges on and inserts its unselected edges. Each internal vertex exchanges one selected edge for another; each endpoint gains its first selected edge. All choices away from stay in place, so is a matching in a graph with .[ref]
Graph Theory by Reinhard Diestel. Matching, Covering and Packing, §2.1, printed p. 2: alternating paths, augmenting paths and symmetric difference
For an explicit repair, let the path graph have vertices in that order and start withThe endpoints and are initially unmatched vertices in a matching. Along the edges are outside, inside, outside, inside, outside . Remove and , then add together:This raises the cardinality from two to three and gives a perfect matching. Six vertices allow at most three disjoint pairs, so it is also a maximum cardinality matching. The initial is already a maximal matching: every unused edge touches a matched vertex. Augmentation succeeds because it can replace earlier choices instead of only adding to them.
The augmenting path in a matching on P₆ replaces two selected edges by three using symmetric difference
. Details. One unused edge joining two unmatched vertices in a matching is the shortest possible augmenting path in a matching. Longer augmenting paths in a matching reassign several partners, explaining why a stalled greedy matching need not be optimal. For edge benefits , the change in total benefit iswhich need not be positive even though the cardinality increases. A maximum-weight matching therefore needs a different optimality test. In an assignment equality graph an augmenting path in a matching moves toward a perfect matching while preserving zero reduced costs on matched edges; this is the setting used by the Hungarian algorithm.
Dantzig pivot rule 2026-10-14
In maximization, select the entering nonbasic variable with greatest positive reduced cost, meaning objective increase per unit of that variable. Unlike geometric steepest-edge pricing, this rate depends on variable and constraint scaling. A rescaled Klee-Minty cube can give the same -pivot path as smallest-index improving-facet pivoting.
Dual feasibility 2026-10-14
For minimization with constraints , , a dual-feasible vector obeys , so is a lower bound on every primal-feasible objective value. For a simplex dictionary with basis matrix , the associated vector is . Its basic reduced costs are zero and its nonbasic reduced costs are . Thus nonnegative reduced costs are exactly dual feasibility in this minimization convention; basic primal values may still be negative, as in the dual simplex algorithm.
Greatest improvement pivot rule 2026-10-14
For a feasible simplex dictionary, let be a nonbasic variable's improving reduced cost and let be its largest feasible increase from the simplex ratio test. The greatest improvement pivot rule chooses an entering variable maximizing . It measures the improvement over the entire edge, whereas the Dantzig pivot rule maximizes only .
// Target: mathematical-optimization.bigb
Hungarian algorithm Created 2026-10-06 Updated 2026-10-14
The Hungarian algorithm maintains feasible assignment dual potentials and a matching of equality edges. If the alternating search cannot augment, adjust reachable job and agent potentials by the smallest reduced cost leaving the search set. This preserves feasibility and existing matching equalities while exposing a new equality edge. A resulting perfect matching attains the dual lower bound.
Linear programming sensitivity within a fixed optimal basis Created 2026-10-06 Updated 2026-10-14
For a linear program with unchanged cost and constraint matrix, an optimal simplex basis remains optimal while its basic solution remains feasible. Its reduced costs and dual certificate do not change. The new basic variables are , and the objective is the displayed affine function, with the basis's dual solution. This gives an exact piecewise-affine sensitivity region, determined by nonnegativity of the basic variables, rather than merely a formal first derivative.
Network simplex algorithm Created 2026-10-06 Updated 2026-10-14
The network simplex algorithm specializes the simplex algorithm to network flows. A basis is represented by a spanning tree with nonbasic flows at their bounds; potentials give reduced costs, and entering arcs produce cycle pivots. Degeneracy in linear programming is particularly common in assignment instances.
Past exam of the mathematics course of the University of Cambridge 2001 ib Paper 3 15D Solution Created 2026-09-24 Updated 2026-10-14
Use the original PDF constraints, whose right sides are and . Introduce nonnegative surplus variables , slack , and artificial variables :All seven variables are nonnegative. Phase I of the two-phase simplex method minimizes with initial basis . The initial simplex dictionary isEnter and leave : the ratio test gives . Substituting givesNow enter and leave . The bounds from are , so the ratio test selects . The new dictionary isThe associated basic solution has and , which is a global minimum because artificial variables are nonnegative. Delete their columns for Phase II. In the remaining basis the objective isFor , both reduced costs are nonnegative, so the simplex method has reached the optimum at :For , the coefficient of is negative. Enter ; the ratio test gives from and from , so leaves. Eliminating givesand henceThe two reduced costs are now positive, so is optimal andAt the whole feasible edge from to is optimal; both value formulas agree. These dictionaries explicitly carry out both phases rather than inferring the answer solely from a feasible-region sketch.
Past exam of the mathematics course of the University of Cambridge 2003 ib Paper 4 14H Solution Created 2026-09-24 Updated 2026-10-14
Introduce nonnegative slack variables , a nonnegative surplus variable , and an artificial variable . Phase I of the two-phase simplex method minimizes . The initial simplex dictionary isWith the nonbasic variables zero this is feasible for the artificial problem. Enter ; the minimum ratios are , so leaves. Solving its row for and substituting givesNow enter . The ratios from decreasing basic variables are and , so leaves. The resulting dictionary isSetting the nonbasic variables zero gives , so Phase I has reached its minimum and found feasibility. Remove and reinstate the true objective . Substitution of the basic variables givesEnter . The decreasing rows give ratios for and for , so leaves. Phase II then hasEvery nonbasic variable is nonnegative and every reduced cost is positive. Thus the simplex optimality criterion provesAll three original constraints are active. Positivity of all three reduced costs also proves uniqueness: equality in the objective lower bound forces , which fixes the displayed solution.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 33 1 Solution 2026-10-14
For the linear program in maximization form, a nonnegative multiplier of the resource inequalities giveswhenever . Equivalently, the Lagrangian is ; its supremum over is finite exactly when . Minimizing this bound gives the dual linear programThe displayed inequality proves weak duality directly.
For the final simplex tableau, the basic-variable order is . With interpreted as the ordinary unpriced slack variables, its constraint equations giveThe bottom row is read in the reduced-cost convention , with right side minus the basic objective value. It says the reduced costs of are . Thus optimality requires , while can increase without changing the objective until reaches zero. The complete primal optimum set is
Reconstructing a linear program from a final simplex tableau exposes a source inconsistency. The slack columns areBecause the first basic column is that of , the original constraint data areThe slack reduced costs give andConsequently the recovered homogeneous linear program isEvery point in the optimum segment has value . Since the segment contains a point with both variables positive, complementary slackness forces both dual column inequalities to be equalities. They give the unique dual optimum
The printed bottom-right entry is , but it must be for this linear objective and these constraint rows. Thus no original problem in the stated homogeneous standard form has exactly the entire printed tableau. Changing that one entry to gives the reconstructed problem above. Alternatively, if an affine objective is permitted, has the displayed optimum value and unchanged reduced costs; the corresponding affine dual objective is . Both interpretations have exactly the same primal and dual optimizer sets. The discrepancy is in the objective constant, not in the optimal segment.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 40 1 Solution Created 2026-10-03 Updated 2026-10-14
Introduce nonnegative slack variables and write for the objective value. The initial simplex dictionary, recovered from the original PDF rather than the corrupted converted table, isFor this minimization convention, nonnegative objective coefficients give dual feasibility. The dual simplex algorithm repairs a negative basic value while retaining those nonnegative reduced costs. If the leaving row is , , an entering variable must have ; choose the smallest ratio of its objective coefficient to .
Choose to leave. Eligible columns are , with ratios and . Thus enters. Solving its row and substituting givesNow only has a negative basic value. Its only eligible entering column is , so pivot there, with leaving. The resulting dictionary isSetting the nonbasic variables to zero gives a basic feasible solution. The final objective row also proves for every feasible point, because its nonbasic variables are nonnegative. Hence the unique relaxed optimum is
For the integer program, all four original slack variables are integers whenever the decision variables are integers. The fractional row can be writtenThe Gomory fractional cut keeps the fractional parts of these coefficients: and . It therefore gives , or . Its validity can also be seen directly: the displayed row makes an odd nonnegative integer. In original variables this cut is .
Introduce the new integer-valued slack , with initial row . It is primal infeasible but retains dual feasibility, so one more dual-simplex pivot has leave and enter. Substitute to obtainAll basic values at are nonnegative integers, including . The objective row proves a lower bound of on every point satisfying the valid cut, hence on every integer-feasible point. It is attained atThe strictly positive nonbasic objective coefficients also show uniqueness. One Gomory cut and its reoptimization are sufficient.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 38 1 Solution Created 2026-10-03 Updated 2026-10-14
Introduce slack variables . The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.
The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has , and . Although increasing improves the objective at rate four, reaches zero first at , giving pivot three. After pivot four, and ; the upper bound gives pivot five.
In the final objective row every reduced cost is nonpositive. Since , it also directly certifies the upper bound , attained only when all three vanish. Thus
A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements , and . It therefore brings into the simplex basis first, with leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.
This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, for constraints and original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.
Past exam of the mathematics course of the University of Cambridge 2008 iii Paper 38 2 Solution Created 2026-10-03 Updated 2026-10-14
Encode a vertex of a polytope by three bits: bit records whether the lower or upper bound of coordinate is tight. Every choice is possible because , and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing . It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string , switching bit 2 decreases , so the rule switches bit 1, leaving facet 2. At , neither of the earlier-coordinate switches improves , so the rule finally leaves facet 5. The upper face reverses the direction in which changes of improve , and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of .
Seven Bland pivots through all eight vertices of the Klee-Minty cube, with epsilon equal to one quarter
. Details. Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in dimensions has inequalities and vertices of a polytope. On its lower last-coordinate face, increasing means increasing , and the first coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing means decreasing , and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies , , andThe usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed , the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.
For a lower bound that applies to every pivot choice, use and maximize , starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is . Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least pivots, and every strictly improving route takes exactly .
For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates byThe transformed linear program still maximizes , now with boundsWhen the active facet for coordinate is freed, the other active equations give . The positive rates per unit are thereforefor , respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate changes its entering slack by . Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In dimensions set ; the rates give the same pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.
Past exam of the mathematics course of the University of Cambridge 2009 ib Paper 3 20H Solution Created 2026-09-24 Updated 2026-10-14
Let be shipments, with column sums eight and row sums at most the four capacities. Total demand is , below total capacity , so unused capacity is allowed. This is a transportation problem with capacity inequalities; equivalently add a dummy shop demanding four units with zero shipping cost.
Using the original PDF's cost , take the feasible solutionIts row totals are and all column totals are eight. Four units of capacity remain unused at the second factory. Its shipping cost is .
To prove that the cost is a global minimum, use the transportation dual certificate with capacity inequalities. If row potentials satisfy and , every feasible solution satisfieswhere . The second inequality uses the sign of : multiplying a capacity upper bound by a nonpositive number reverses it. Choose and . The reduced costs areso every entry is nonnegative. The lower bound is , equal to the displayed shipping cost. The minimum shipping cost is .
For the production costs in a transportation problem, add the production cost of each factory to every real shipment from that factory. Unused capacity incurs no production cost, so the dummy-shop costs remain zero. The resulting real-shop cost matrix isA feasible solution isIts row totals are and column totals remain eight, leaving four units unused at the fourth factory. Its combined cost is .
For a matching transportation dual certificate with capacity inequalities, take and . Their reduced costs areall nonnegative. The lower bound is . Thus the minimum combined production and shipping cost is , and the second allocation attains it.
Past exam of the mathematics course of the University of Cambridge 2010 iii Paper 35 3 c Solution Created 2026-10-03 Updated 2026-10-14
Use the transportation simplex algorithm, with transportation dual potentials and reduced costs . On a basic cell choose . The initial shipment matrix, read from the circled entries in the PDF, isIts six positive cells form a transportation spanning tree. Setting givesEnter cell , whose reduced cost is . The cycle pivot has signsThe maximum feasible increment is , so cell leaves the basis. The result isFor the new transportation spanning tree,Enter cell with reduced cost . Its cycle pivot isNow , and cell leaves. We obtainIts row sums are and its column sums , as required. The final transportation dual potentials areAll reduced costs are nonnegative, proving optimality. More explicitly, for any feasible shipment matrix ,Our shipments use only zero-reduced-cost cells and attain this lower bound. This supplies an independent weak duality certificate for the transportation optimum.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 212 3 Solution Created 2026-10-03 Updated 2026-10-06
Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply and agent vertices demand . An arc from job to agent has cost and nonnegative flow ; an upper bound may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its positive arcs form a perfect matching, hence give one job per agent.
A network simplex algorithm basis for this connected -vertex network has tree arcs, whereas an integral assignment has only positive flows. For , at least basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.
Suppose the assignment dual potentials satisfy . For every feasible assignment ,If the selected assignment uses only arcs with , its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by ; the TeX aid mistakenly replaces it with .
The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where . Search for an augmenting path in a matching in this equality graph. If there is none, let be the reachable jobs and the reachable agents in the alternating search from unmatched jobs. Every agent in is matched to a job in . SetReduced costs from to its complement decrease by , those from outside into increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.
For the example, start with the row minima and . The reduced cost matrix isMatch job to agent . Searching from both unmatched jobs gives and ; the minimum cost to an agent outside is . Update to and :The new equality edge augments the matching. From unmatched job , the next alternating search reaches agent and its matched job , giving and . Now . The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching uses job to agent , the reversed matched edge to job , then the new edge to agent . It gives the optimal assignmentThe dual linear program value is , an independent optimality certificate.
Past exam of the mathematics course of the University of Cambridge 2022 ib Paper 3 19H b Solution Created 2026-09-24 Updated 2026-09-25
The stated plan isIts six positive cells form a spanning tree of the supplier--consumer bipartite graph, so it is basic and feasible. Taking , the basic-cell equations giveThe complete matrix of reduced costs isThe negative entry proves that the plan is not optimal.
Enter cell . The alternating cycle isand the step is . The new plan iswhose cost is , down from . New potentials areand the reduced-cost matrix isEvery reduced cost is nonnegative, so the transportation optimality criterion shows thatThe zero reduced cost in cell also indicates an alternative optimum.
Past exam of the mathematics course of the University of Cambridge 2025 ib Paper 4 18H c Solution Created 2026-09-24 Updated 2026-09-25
The northwest-corner rule constructs an initial basic feasible solution: fill the current cell with the smaller remaining supply and demand, delete the exhausted row or column, and continue.
For a current spanning-tree basis, solve on its occupied cells, fixing one potential to zero. The reduced cost of an unoccupied cell isIf all reduced costs are nonnegative, part (a) proves optimality. Otherwise choose a cell with negative reduced cost. Adding its edge to the tree creates a unique even cycle. Mark its cells alternately and , starting with at the entering cell, and setAdd on the plus cells and subtract it on the minus cells. Row and column totals are unchanged, the entering cell becomes positive, and a minimizing minus cell leaves the basis. In the nondegenerate case the objective decreases strictly. There are finitely many bases, so no basis repeats and the algorithm terminates at a basis with no negative reduced cost, which is optimal.
Changing only the second profit coefficient leaves the dual prices at , because the basic products remain one and three. The nonbasic product has nonpositive reduced cost exactly when . ThereforeThere is no mathematical lower bound; if profit coefficients are additionally restricted to be nonnegative, intersect this range with . At , alternate optimal solutions are possible.
At the current dual prices , the new product has reduced cost , so it can increase profit. Its transformed resource column isIncreasing by changes the old basic variables to and . Thus leaves at , givingFor a certificate, take dual prices . They price the four products at , respectively, each at least its profit. Their resource total is , equal to the achieved profit. Weak duality proves optimality, and the profit has increased by two.

