![]() 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). Typically, the entering variable xs does increase in value, and the objective value z improves. ![]() 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$. What is degeneracy As you know, the simplex algorithm starts at a corner point and moves to an adjacent corner point by increasing the value of a non-basic variable xs with a positive cost coefficient. 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). 2)If either the primal or dual problem has unbounded soln the other problem (dual or primal) has no feasible soln. Now consider any number $t > 0$ and the vector obtained by considering the sum $x^* + ty$. 1)The dual of dual linear programming problem is again the primal problem. 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. ![]() You can think of certain vectors $y$ as directions leading to "unboundedness" if they satisfy the following two conditions: 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. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |