Any feasible solution of a linear programming problem can be expressed as the convex combination of Basic Feasible Solutions.

Question

Any feasible solution of a linear programming problem can be expressed as the convex combination of Basic Feasible Solutions of the same.

Is the statement true?

I think the statement is true. Can anyone please help me to understand why this statement is true if it is true?

Answer 1

Consider the following problem.

$\min 0$ subject to $x \in \mathbb{R}$.

It has no basic feasible solution. The statement is false.

Edit:

Consider $\max y$ subject to $ x \ge 0, y \ge 0$.

The only basic feasible solution is the zero vector.

Note that a feasible region can be unbounded but the convex combination of BFS must be bounded. The statement is false unless the linear program has a bounded feasible region.

Answer 2

The statement is true if and only if the feasible region is bounded. Consider the inventory optimization problem $$\min_{x,y,z} \left\{\sum_t z_t : z_t \geq h y_t, z_t \geq -by_t, y_t = y_{t-1}+x_t-d_t, 0 \leq x_t \leq x_{\max} \right\},$$ with starting inventory $y_0$, inventory level $y_t$, production size $x_t$ (bounded above by some machine limitation $x_{\max}$, expected demand $d_t$, holding costs $h$ and backlogging costs $b$. This problem is feasible and has an optimal solution. The feasible region of this problem is unbounded ($z_t$ can grow infinitely large), so the statement is not true.

When the feasible region is bounded, it is a convex polyhedron whose extreme points are basic feasible solutions.