Optimisation and game theory · Maths EE idea · Ambitious

Why the simplex method finds the optimum

A research question to start from

Why does the optimum of a linear programme occur at a vertex of the feasible region, and how does the simplex method move between vertices to find it?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

Geometry and algebra combine in a method you can justify and run by hand.

Mathematics you would need

Linear inequalities
Convex regions
Vertices and basic solutions
Pivoting

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Prove the vertex property for two variables, then generally.
Solve small problems graphically and by simplex.
Discuss degeneracy and cycling.

Scope and difficulty

Ambitious. Ambitious.

Pitfalls

Software solutions.
No justification of pivoting.

Where to start reading

Search a library catalogue or a university's open lecture notes for: linear programming optimal vertex proof; simplex method degeneracy cycling. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.