0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ @nathan.j.mcdougall Can you prove it? Or suggest me a link from where I could read $\endgroup$ – cmi Jan 26 at 11:43
  • $\begingroup$ did any of the replies answer your question? $\endgroup$ – LinAlg Feb 25 at 16:30
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – cmi Jan 26 at 11:46
  • $\begingroup$ btw, the first sentence, convex combination of the same ... is something missing at the end? $\endgroup$ – Siong Thye Goh Jan 26 at 11:52
  • $\begingroup$ of the same lp.. $\endgroup$ – cmi Jan 26 at 12:03
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.