# Prove the solution set of a Linear programming problem is a polyhedron

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.

• Which definition of polyhedron are you using? By "solution set" do you mean the set of optimal solutions? Commented Mar 16, 2021 at 17:36
• @RobPratt I use the definition: "A polyhedron is a set that can be described in the form $\{x \in \mathbb{R}^n | Ax \geq b\}$, where A is an m x n matrix and b is a vector in $\mathbb{R}^m$. And yes, the solution set is the set of optimal solutions Commented Mar 17, 2021 at 14:16

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^*$$).

• What if there are infinite $x^*$ minimizes $c^Tx$? If there are infinite $x^*$ like that, we cannot interpret the constraints as the matrix form. Commented Mar 17, 2021 at 14:43
• Even if there are an infinite number of optimal solutions (which will happen if there are even two), you need only one additional constraint. The RHS depends only on the common value of $c^T x^*$. Commented Mar 17, 2021 at 15:09