Math
Simplex on the plane
The feasible region lies on the table and a plate hangs over it at the height of the objective. The objective is linear, so the plate is flat and tilted, and the best point is literally its highest corner. The simplex climbs the edges to it.
What happens
Two variables and a few constraints: each one is a wall on the table, and what is left inside is the feasible region. Over it hangs a plate whose height at every point is the objective p·x + q·y. Because that is linear, the plate is a flat tilted plane - it has no hill in the middle - and the best point is its highest corner. That is the whole reason the answer is always at a vertex, and 60 000 probes inside the region never beat one. The simplex walks that staircase: from the origin to a neighbouring corner that stands higher, one pivot at a time, stopping where no neighbour is higher. Its answer is compared with an enumeration of every vertex, which knows nothing of the tableau. Push a wall out by one and the optimum grows by exactly that wall's shadow price - unless three walls meet at the top corner, and then the growth has no single rate at all.
Equations used in the module
Equations maximise p·x + q·y subject to a·x + b·y ≤ c for every row, and x ≥ 0, y ≥ 0 the feasible region is the intersection of half-planes; the objective is linear, so its plate over the region is a flat tilted plane therefore the maximum is at a VERTEX - a point where two of the lines (the axes count) cross and every constraint still holds simplex: start at the origin (every c ≥ 0, so it is feasible), walk to a neighbouring vertex that raises the objective, stop when none does Bland's rule - enter on the smallest eligible index, leave on the smallest basic index among tied ratios - makes cycling impossible the shadow price of a row is the dual variable: push its c out by h and the optimum grows by h·y, unless the top vertex is DEGENERATE degenerate vertex: more than two lines through the same point - there the derivative does not exist, so the shadow price is not defined
