4.10.21 · D5Advanced Topics (Elite Level)
Question bank — Linear programming — simplex method (intro)
Before we begin, the words and standing assumptions we lean on constantly, in plain language:
The two pictures below anchor everything: what a corner is, and what goes wrong when the easy starting corner isn't even inside the field.
The red dot is the corner the objective picks; the black dots are the other corners simplex may hop through. Look how the optimum sits at a sharp corner, never in the flat interior.
True or false — justify
The non-negativity rule is just a convenience we could drop.
False — it is a load-bearing assumption. The whole starting corner , the ratio test, and "set non-basic variables to " all rely on variables never going below zero; drop it and the corner-hopping logic collapses.
Every feasible LP has a maximum attained at a vertex.
False in general — if the region is unbounded in the improving direction the maximum is (no maximizer). True whenever a finite maximum exists: a linear objective always achieves any finite optimum at a vertex.
The simplex method examines every vertex of the polytope.
False — it hops corner-to-corner along improving edges and stops early. Most vertices are never visited; that skipping is exactly why it beats brute force.
If all objective-row coefficients are , the current corner is optimal.
True for a maximization tableau — no non-basic variable can be raised to increase , so no neighbouring corner is better, and by convexity that means globally optimal.
A slack variable being zero means the LP has no solution.
False — a zero slack just means that one constraint is tight (we sit on its boundary). It is a normal, feasible situation and in fact happens at every vertex for the constraints that define it.
Multiplying a constraint by changes which points are feasible.
False — an inequality and its multiple describe the exact same set of points; only the "" vs "" symbol flips. This is why standard form loses no generality.
The most-negative entering rule guarantees the fewest pivots.
False — it maximizes improvement per unit of the entering variable (best slope), not total gain. It is a solid heuristic for hand-work but not step-optimal.
Every basic feasible solution is a vertex, and every vertex is a basic feasible solution.
True (for a polytope in standard form) — setting the non-basic variables to and solving for the basic ones is algebraically the same as intersecting enough boundary constraints, which is what defines a corner.
Adding slack variables changes the optimal value of the LP.
False — slacks only rewrite as by naming leftover room; they are forced to in the objective's coefficient and add no cost. The feasible original variables and the optimum are untouched.
A tableau column full of non-positive entries in the pivot column signals optimality.
False — it signals unboundedness: the entering variable can grow forever without any constraint bounding it, so . Optimality is about the -row, not the pivot column.
If some , we can still start at and run simplex normally.
False — setting originals to would give slack , which violates . The starting "corner" is infeasible, so we must first run Phase I to find any feasible corner.
Spot the error
"Increasing is worthless here because its -row entry is , a negative — negatives shrink ."
Backwards. The -row stores , so a means ; raising increases by per unit. A negative -row entry is precisely the invitation to enter.
"For the ratio test I'll divide RHS by every column entry and take the minimum: , ."
You must skip non-positive entries. Dividing by gives , which would wrongly win as "smallest", yet a negative entry never bounds the increase — the variable there only gets more feasible as grows.
"At the constraint is violated, since is fine but we ignored it."
No violation — holds with slack . The constraint is simply not tight; feasibility only requires , not equality.
"To minimize , run simplex normally and read off the last -value as the minimum."
Simplex only maximizes. To minimize you maximize ; the answer is . Reading the raw maximized value gives the wrong sign.
"The pivot only needs to zero-out the entering column in the constraint rows."
It must also update the -row (and RHS). Skipping the -row leaves stale objective coefficients, so the next optimality/entering decision is made on wrong numbers.
"Since pivoting is Gaussian elimination, any pivot element works."
Only the ratio-test winner is a legal pivot. Plain Gaussian Elimination ignores feasibility; simplex adds the minimum-ratio rule so no basic variable turns negative.
"The problem has a constraint with , so it's automatically infeasible."
Wrong — a negative only means the easy starting corner is unavailable, not that the region is empty. Phase I decides feasibility; the region may be perfectly non-empty.
Why questions
Why is the feasible region always convex?
Each inequality carves out a half-space (a convex set), and the intersection of convex sets is convex — so no matter how many constraints, the region can't have dents (see Convex Sets and Polytopes).
Why must a linear objective's optimum sit on the boundary, not the interior?
Its level sets are parallel flat sheets and the gradient never vanishes; you can always slide further in the improving direction until a wall stops you, so an interior point is never optimal.
Why do we start simplex at the corner (all originals zero)?
Only when (every resource limit non-negative): then "set originals to , let each slack equal its " gives non-negative slacks, an instantly-feasible basic solution — a free starting vertex needing no work. If some this shortcut fails and Phase I is required.
Why does the process terminate?
There are finitely many vertices and each pivot strictly improves (ignoring degeneracy), so no corner repeats and we run out of corners to improve to.
Why do we pick the smallest ratio, not the largest, when choosing who leaves?
The smallest ratio is the first constraint that binds as the entering variable grows; stopping there keeps all variables . Going to a larger ratio would drive an earlier-binding variable negative — infeasible.
Why is duality relevant to knowing we've truly finished?
At optimality the primal and dual objective values coincide; matching them certifies the answer independently of the pivoting path (see Duality in Linear Programming).
Why do we need a Phase I (auxiliary) problem at all?
Because simplex can only walk between feasible corners — it needs a feasible starting corner to begin. When isn't feasible, Phase I's job is to find one (or prove none exists) before ordinary optimization starts.
Edge cases
What happens if two ratios tie in the ratio test?
You have a degenerate vertex; either choice is legal but you may pivot without improving , risking cycling. Anti-cycling rules (e.g. Bland's rule) restore guaranteed termination.
What if a basic variable is already at the current corner?
That is degeneracy again — more than the minimal number of constraints pass through this corner, so a pivot can move the basis without moving the point or the objective.
What if the pivot column has a positive entry but RHS there is ?
The ratio is , the smallest possible, so that row wins the ratio test and the entering variable enters at value — a degenerate, zero-improvement pivot.
What if every -row entry is negative but the region is unbounded upward?
Simplex tries to enter a variable whose pivot column has no positive entry; the ratio test finds no bound, so it correctly reports unbounded () rather than a corner.
What if the objective is constant along an entire edge (a -row zero on a non-basic variable at optimum)?
Multiple optimal solutions exist — that variable can enter with zero change in , sweeping a whole edge (or face) of equally-optimal points, not a unique corner.
What if the initial basic solution is infeasible because some ?
The start gives a negative slack, so we run Phase I: introduce artificial variables to build an obviously-feasible corner, then minimize their total. If that minimum drives all artificials to , we've reached a genuine feasible corner and switch to Phase II (the real objective). Look at the right panel of the figure below — the "start" sits outside the shaded region until Phase I nudges it in.
How does simplex certify that an LP has no feasible solution at all?
If Phase I ends with the artificial variables' minimum total strictly greater than — no valid pivot can push them to zero — then no point satisfies all constraints. That leftover positive total is the infeasibility certificate: the feasible region is empty (in the picture, the constraint half-planes share no common point).
What changes if variables are forced to be whole numbers?
The vertex-optimum guarantee breaks: the integer optimum may sit strictly inside the polytope, so simplex alone is insufficient and you need Integer Programming methods (branch-and-bound, cutting planes).
What if a constraint is an equality from the start, not ?
You can't add an ordinary slack (it would have to be ); instead split it into two constraints or introduce an artificial variable driven to zero in Phase I — the smooth-constraint analogue is handled by Optimization (Lagrange Multipliers).
Recall One-line self-test
Say aloud the three-part rule that resolves half the traps above, plus the two-phase caveat. Enter the most negative -row entry; leave by the smallest positive-only ratio; stop when the whole -row is — and if isn't feasible (some ), run Phase I first, declaring "infeasible" if the artificials can't reach .
Connections
- Parent: Simplex method (intro)
- Convex Sets and Polytopes — the convexity that forces optima to corners.
- Gaussian Elimination — pivoting is row reduction plus a feasibility rule.
- Duality in Linear Programming — the certificate that you've stopped correctly.
- Gradient and Level Sets — why flat objectives slide to the boundary.
- Integer Programming — when the vertex guarantee fails.
- Optimization (Lagrange Multipliers) — the equality-constraint cousin.