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

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?

• @nathan.j.mcdougall Can you prove it? Or suggest me a link from where I could read – cmi Jan 26 '19 at 11:43
• did any of the replies answer your question? – LinAlg Feb 25 '19 at 16:30

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.

• You seemed to have taken very exceptional case..I was talking about a general Linear Prigramming problem which consists of an objective function which is essentially not zero and some independent constraints..@Siong Thye Goh – cmi Jan 26 '19 at 11:46
• btw, the first sentence, convex combination of the same ... is something missing at the end? – Siong Thye Goh Jan 26 '19 at 11:52
• of the same lp.. – cmi Jan 26 '19 at 12:03

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.