If the solution set of linear programming problem is unbounded, can you find that out in finite steps?
up vote
1
down vote
favorite
Let $(P) maxleft{c^T cdot x mid A cdot x leq b, x geq
0right}$ be an arbitrary linear programming problem and $M$ its
solution set. Is it possible to find out if $M$ is unbounded (in
finite steps)?
I think the answer is yes because we have linear program here and that's why it's possible to tell in polynomial time if it has feasible solution or infeasible. So there must be an algorithm to do this in polynomial time e.g. in finite steps.
But I don't know any algorithm to do this. So far I've read about the simplex method in a book and if I understood correctly, if you run simplex method on the LP above, you will see in the table that the problem is unbounded because there will appear one or more variables where you can pivot these to $infty$.
But this is only thought is it correct like that? Maybe it's possible with another way too?
optimization linear-programming
asked Nov 10 at 10:57
tenepolis
4011316
add a comment |
up vote
1
down vote
favorite
Let $(P) maxleft{c^T cdot x mid A cdot x leq b, x geq
0right}$ be an arbitrary linear programming problem and $M$ its
solution set. Is it possible to find out if $M$ is unbounded (in
finite steps)?
I think the answer is yes because we have linear program here and that's why it's possible to tell in polynomial time if it has feasible solution or infeasible. So there must be an algorithm to do this in polynomial time e.g. in finite steps.
But I don't know any algorithm to do this. So far I've read about the simplex method in a book and if I understood correctly, if you run simplex method on the LP above, you will see in the table that the problem is unbounded because there will appear one or more variables where you can pivot these to $infty$.
But this is only thought is it correct like that? Maybe it's possible with another way too?
optimization linear-programming
asked Nov 10 at 10:57
tenepolis
4011316
1
Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$.
– A.Γ.
Nov 10 at 11:14
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $(P) maxleft{c^T cdot x mid A cdot x leq b, x geq
0right}$ be an arbitrary linear programming problem and $M$ its
solution set. Is it possible to find out if $M$ is unbounded (in
finite steps)?
I think the answer is yes because we have linear program here and that's why it's possible to tell in polynomial time if it has feasible solution or infeasible. So there must be an algorithm to do this in polynomial time e.g. in finite steps.
But I don't know any algorithm to do this. So far I've read about the simplex method in a book and if I understood correctly, if you run simplex method on the LP above, you will see in the table that the problem is unbounded because there will appear one or more variables where you can pivot these to $infty$.
But this is only thought is it correct like that? Maybe it's possible with another way too?
optimization linear-programming
asked Nov 10 at 10:57
tenepolis
4011316
Let $(P) maxleft{c^T cdot x mid A cdot x leq b, x geq
0right}$ be an arbitrary linear programming problem and $M$ its
solution set. Is it possible to find out if $M$ is unbounded (in
finite steps)?
I think the answer is yes because we have linear program here and that's why it's possible to tell in polynomial time if it has feasible solution or infeasible. So there must be an algorithm to do this in polynomial time e.g. in finite steps.
But I don't know any algorithm to do this. So far I've read about the simplex method in a book and if I understood correctly, if you run simplex method on the LP above, you will see in the table that the problem is unbounded because there will appear one or more variables where you can pivot these to $infty$.
But this is only thought is it correct like that? Maybe it's possible with another way too?
optimization linear-programming
optimization linear-programming
asked Nov 10 at 10:57
tenepolis
4011316
asked Nov 10 at 10:57
tenepolis
4011316
asked Nov 10 at 10:57
tenepolis
4011316
asked Nov 10 at 10:57
tenepolis
4011316
asked Nov 10 at 10:57
tenepolis
4011316
4011316
1
Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$.
– A.Γ.
Nov 10 at 11:14
add a comment |
1
Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$.
– A.Γ.
Nov 10 at 11:14
1
1
Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$.
– A.Γ.
Nov 10 at 11:14
Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$.
– A.Γ.
Nov 10 at 11:14
add a comment |
1 Answer
1
active
oldest
votes
up vote
4
down vote
accepted
$$max c^Tx$$
subject to
$$Axle b$$
$$x ge 0$$
Using the simplex algorithm, we can determine if there is a solution, $x^*$.
Now consider
$$max e^Tx$$
subject to
$$Axle b$$
$$c^Tx=c^Tx^*$$
$$x ge 0$$
where $e$ is the all-one vector.
We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
1
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
$$max c^Tx$$
subject to
$$Axle b$$
$$x ge 0$$
Using the simplex algorithm, we can determine if there is a solution, $x^*$.
Now consider
$$max e^Tx$$
subject to
$$Axle b$$
$$c^Tx=c^Tx^*$$
$$x ge 0$$
where $e$ is the all-one vector.
We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
1
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
add a comment |
up vote
4
down vote
accepted
$$max c^Tx$$
subject to
$$Axle b$$
$$x ge 0$$
Using the simplex algorithm, we can determine if there is a solution, $x^*$.
Now consider
$$max e^Tx$$
subject to
$$Axle b$$
$$c^Tx=c^Tx^*$$
$$x ge 0$$
where $e$ is the all-one vector.
We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
1
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
add a comment |
up vote
4
down vote
accepted
up vote
4
down vote
accepted
$$max c^Tx$$
subject to
$$Axle b$$
$$x ge 0$$
Using the simplex algorithm, we can determine if there is a solution, $x^*$.
Now consider
$$max e^Tx$$
subject to
$$Axle b$$
$$c^Tx=c^Tx^*$$
$$x ge 0$$
where $e$ is the all-one vector.
We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
$$max c^Tx$$
subject to
$$Axle b$$
$$x ge 0$$
Using the simplex algorithm, we can determine if there is a solution, $x^*$.
Now consider
$$max e^Tx$$
subject to
$$Axle b$$
$$c^Tx=c^Tx^*$$
$$x ge 0$$
where $e$ is the all-one vector.
We check if the solution is unbounded, if it is unbounded, then $M$ is unbounded.
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
edited Nov 10 at 14:07
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
answered Nov 10 at 12:58
Siong Thye Goh
93.3k1462114
93.3k1462114
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
1
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
add a comment |
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
1
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
Oh hi you again :p That $e$ is the same as from my previous question, right (the "all ones vector")?
– tenepolis
Nov 10 at 14:01
1
1
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
ah yes, it's my habit to use that notation.
– Siong Thye Goh
Nov 10 at 14:06
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2992493%2fif-the-solution-set-of-linear-programming-problem-is-unbounded-can-you-find-tha%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Yes, it is possible. You may look here. NB(!): the standard form there is minimization and equality $Ax=b$.
– A.Γ.
Nov 10 at 11:14