Basic feasible solution Created 2026-09-24 Updated 2026-11-05
For a full-row-rank system with rows and variables , choose linearly independent columns as a simplex basis. Set all nonbasic variables to zero and solve . If , the resulting vector is a basic feasible solution. Redundant equality rows can first be removed.
Equivalently, a feasible vector is basic when the columns indexed by its strictly positive coordinates are linearly independent. Those columns can be extended to a basis of the full column space because has row rank . The extension may have zero-valued basic variables; this is degeneracy in linear programming.
For and , the two basic feasible solutions are and . The feasible midpoint is not basic: its two positive columns are dependent. In this standard form, basic feasible solutions are exactly the extreme points of the feasible polyhedron, connecting basis algebra to the Fundamental theorem of linear programming.
Integrality of the transportation problem Created 2026-09-24 Updated 2026-11-05
For nonnegative integer supplies and demands with equal totals, the complete transportation problem has an integral optimal shipment matrix for every finite real cost array. A feasible matrix exists, and its nonnegative entries are bounded by their row supplies, so the transportation polytope is compact and a linear objective attains its minimum.
Its constraints are the vertex-edge incidence equations of a bipartite graph. Negating the demand rows gives a directed incidence matrix, which is a totally unimodular matrix. After deleting one redundant equality, any independent square basis has determinant or . An integer right side therefore gives integer basic coordinates by Cramer's rule. The Fundamental theorem of linear programming supplies an optimal basic feasible solution, proving integrality.
There is also an algorithmic view. The northwest corner method starts with integer shipments; a cycle pivot adds and subtracts an integer minimum along its alternating cycle, preserving integrality. Zero allocations may be needed to complete a degenerate basis. With forbidden routes, equality of total supply and demand is no longer enough for feasibility, though an existing transportation feasible polytope retains the same incidence-matrix integrality property.
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 4 18H b Solution Created 2026-09-24 Updated 2026-10-03
Choose an optimal feasible vector having as few positive coordinates as possible, and letIf the columns were linearly dependent, there would be a nonzero vector , supported on , such that . For all sufficiently small positive , bothwould remain feasible.
If , one of these two perturbations would increase the objective, contradicting optimality. Hence . We may then increase in one of the two directions until at least one positive coordinate first becomes zero. The resulting vector is still feasible and optimal but has smaller positive support, contradicting the choice of .
Thus the active columns are linearly independent, so is basic. This proves the Fundamental theorem of linear programming: whenever the finite maximum is attained, an optimal basic feasible solution exists.
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 4 18H c iii Solution Created 2026-09-24 Updated 2026-09-25
Let be a basic feasible solution of . Part (ii) gives , and put . We already know that is feasible for .
Suppose the columns with were linearly dependent. Then some nonzero , supported on those indices, would satisfy . PutSince and ,The vector is nonzero and is supported only on positive variables of . It is therefore a linear dependence among the active constraint columns of , contradicting that is basic. Hence the active columns are linearly independent, and
By the Fundamental theorem of linear programming, has an optimal basic feasible solution. Its image has the same objective ratio, by part (ii). Conversely, every is feasible for and maps to a feasible point of . Since solves ,