This provides a systematic way to show that a linear program is unbounded. So a linear program is unbounded if it has a feasible solution (our $x^*$ above) and a vector $y$ that satisfies conditions (1) and (2). If you look more closely at the steps above you will see that $c^Ty$ keeps increasing proportionally as we increase $t$ which means that $c^Ty \to \infty$ as $t \to \infty$. Suppose that $c^Ty = v$ condition (2) tells us that $v > 0$. Now let's consider condition (2) which tells you what happens when you scale $y$. Think of this ray as a "half-line" of infinite length in one direction starting at the point $x^*$. If you trace out all the values of $(x^* + ty)$ for all $t > 0$ you end up with a ray with base point $x^*$ and direction $y$. So it turns out that $x^* + ty$ is a feasible solution for your linear program. Since $x^* \geq 0$, $t > 0$ and $y \geq 0$ it follow that $x^* + ty \geq 0$ (the sum of non-negative quantities is non-negative). Now consider any number $t > 0$ and the vector obtained by considering the sum $x^* + ty$. More concretely, consider any feasible point $x^*$ (which means that $x^* \geq 0$ and $Ax^*=b$). The intuition is that any vector $y$ that satisfies condition (1) does not affect feasibility. The unbounded solution generally constitutes a problem which has been wrongly formulated since theres no actual applied problem with limitless return. You can think of certain vectors $y$ as directions leading to "unboundedness" if they satisfy the following two conditions: If one linear programming problems solution may be made arbitrarily big without breaking any of situations restrictions, it can be said to have an unbounded solution. Let's work with a linear program in the form you have used for your example, that is, a problem of the form
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |