Practice: Extreme Points and Basic Feasible Solutions

Feasibility: row 1 gives $0+2(2)+2=6$; row 2 gives $0-2+3=1$; all components are nonnegative. So the point is feasible. The strictly positive components are $x_2,x_3,x_4$, so the test applies to $A_2=(2,-1{)}^{\mathsf{T}}$, $A_3=(1,0{)}^{\mathsf{T}}$, $A_4=(0,1{)}^{\mathsf{T}}$. These are three vectors in ${\mathbb{R}}^2$, so they cannot be linearly independent (indeed $A_2=2A_3-A_4$). The point is therefore feasible but not a basic feasible solution, and not an extreme point.

The second point. $x=(0,3,0,4)$ satisfies both equations and is nonnegative, so it is feasible. Its positive components are $x_2$ and $x_4$, giving columns $A_2=(2,-1{)}^{\mathsf{T}}$ and $A_4=(0,1{)}^{\mathsf{T}}$. Two independent vectors in ${\mathbb{R}}^2$, so this is a basic feasible solution with basis $\{2,4\}$.

When fewer components are positive. Had only one component been positive, the support would give one column where $m=2$ are needed. That does not disqualify the point: the basis is completed by adding any column keeping the set independent, and the extra basic variable takes value zero. Such a point is degenerate, and its basis is not unique, several bases describe the same corner.

Basis $\{A_1,A_2\}$: solve $x_1+x_2=2$ and $x_1=2$, giving $x_1=2$, $x_2=0$, so $x=(2,0,0,0)$. Basis $\{A_1,A_4\}$: solve $x_1=2$ and $x_1+x_4=2$, giving $x_1=2$, $x_4=0$, so $x=(2,0,0,0)$ again. Both bases produce the same point. The inference is unsound because a basis change does not guarantee a change of point: the correspondence between extreme points and bases is not one-to-one. This point has only one strictly positive component while $m=2$, so it is degenerate, and a degenerate basic feasible solution corresponds to more than one basis. The practical consequence is that a simplex iteration can change basis while staying at the same vertex, which is stalling rather than progress, and is why anti-cycling rules exist.

Every extreme point is a basic feasible solution, and every basic feasible solution arises from choosing m columns out of n to form a basis. So the number of extreme points is at most C(n, m), the number of such choices. The bound is not tight for two reasons: many column choices are not linearly independent and so define no basis at all, and many bases give solutions that violate x >= 0 and so are basic but not feasible. Degeneracy pushes in the other direction, with several bases mapping to a single point, which also means the count of bases overstates the count of distinct corners. Finiteness does not imply practicality: C(n, m) grows combinatorially. For a modest instance with n = 60 and m = 30, C(60, 30) is approximately 1.18 x 10^17, so enumeration is infeasible even though the list is finite. This is precisely why the simplex method moves between adjacent bases guided by the objective rather than enumerating all of them.

(a) At most $(\genfrac{}{}{0ex}{}{40}{20})\approx 1.38\times {10}^{11}$. Every extreme point is a basic feasible solution, and every basic feasible solution is determined by a choice of $m=20$ columns of $A$ to form the basis, so the corners cannot outnumber the ways of making that choice.

(b) Two reasons. First, a chosen set of 20 columns may be linearly dependent, in which case $A_B$ is singular and no basic solution exists for it at all. Second, a basis that does exist may give a point with a negative component, which is basic but infeasible and therefore not a corner. (A third: degeneracy lets several distinct bases describe the same point, so even counting valid feasible bases overstates the number of distinct corners.)

(c) Not usable. At ${10}^6$ bases per second, $1.38\times {10}^{11}$ bases take about $1.38\times {10}^5$ seconds, roughly 38 hours, for a problem with only 40 variables, and the count grows combinatorially, so a modest increase in size makes it hopeless. Finiteness guarantees termination and says nothing about whether the wait is affordable. This is why the simplex method traverses a path of adjacent corners instead of enumerating them.

Student A's error is the word exactly. $(\genfrac{}{}{0ex}{}{50}{25})$ is an upper bound, not a count. Some choices of 25 columns are linearly dependent and define no basis at all; some bases give a point with a negative component, which is basic but infeasible and so not a corner; and degeneracy lets several distinct bases describe the same point. The true number of extreme points is generally smaller, often far smaller.

Student B's error is conflating correctness with usability. Termination establishes that the method stops, and says nothing about when. $(\genfrac{}{}{0ex}{}{50}{25})\approx 1.26\times {10}^{14}$; at a million bases per second that is about $1.26\times {10}^8$ seconds, roughly four years, for a problem most solvers handle in milliseconds. A finite method can be entirely correct and completely unusable.

What is true: enumeration is correct and impractical. The simplex method is preferable not because it examines fewer corners in principle but because it walks a path of adjacent improving corners rather than the whole set.