linear programmingpolyhedra
Problem: Prove the solution set of a Linear programming problem is a polyhedron.
I have proved the feasible set of an LPP is a polyhedron (as the constraints are inequations). Now I want to show the solution set is also a polyhedron but I don't know where to start. I'd like to have some hints for the problem.
Thank you.
In two dimensional case the linear optimization (linear programming) is specified as follows: Find the values $(x, y)$ such that the goal function $$g(x, y) = a x + b y \;\;\; (Eq. 1)$$ is maximized (or minimized) subject to the linear inequalities $$a_1 x + b_1 y + c_1 \ge 0 \;\; (or \le 0) $$ $$a_2 x + b_2 y + c_2 \ge 0 \;\; (or \le 0) $$ $$ ... $$
Each of these linear inequalities defines a half plane bounded by the line obtained by replacing the inequality by equality. The solution $(x, y)$ that maximizes the goal function must lie in the intersection of all these halfplanes which is obviously a convex polygon. This polygon is called the feasible region. Let the value of the goal function at a point $(x, y)$ of the feasible region be $m$ $$g(x, y) = a x + b y = m \;\;\; (Eq. 2)$$ The value $m$ of the goal function will obviously not change when we move $(x, y$) on the line defined by (Eq. 2). But the value of $g()$ will be increased when we increase $m$. This leads to a new line which is parallel to (E.q. 2). We can do this as long as the line contains at least one point of the feasible region. We conclude that the maximum of the goal function is achieved at an extreme point of the feasible region which - for a convex polygon - is a vertex (or an edge when the goal line is parallel to the restriction line going through the extreme vertex).
What I remember is that if the objective function is parallel to any part of the boundary that contains an extreme point, then any number on that boundary is also an extreme point.
Admittedly it has been a long time since I looked a linear programming though.
Best Answer
Hint: If $x^*$ minimizes $c^T x$ subject to $Ax \le b$, then every optimal solution satisfies $c^T x \ge c^T x^*$ (in fact, $c^T x = c^T x^*$).