Why does a solution to a linear programming problem always end up at a vertex?
The constraints form planes which intersect to form lines. The lines intersect and form a polygon in space. If there is a minimum/maximum it will lie on the polygon, IF the constraints come into play. The classic LP method of Danzig operates by finding a vertex and then going around the polygon to find the next vertex until the maximum is found. Because of this mode of operation you will always end up at a vertex. Note, however that if one or more constraints do not come into play in the solution, the solution could also be found anywhere on a particular line segment.
