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
4081316
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
4081316
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
4081316
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
4081316
asked Nov 10 at 10:57
tenepolis
4081316
asked Nov 10 at 10:57
tenepolis
4081316
asked Nov 10 at 10:57
tenepolis
4081316
asked Nov 10 at 10:57
tenepolis
4081316
4081316
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
95.8k1462116
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
95.8k1462116
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
95.8k1462116
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
95.8k1462116
$$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
95.8k1462116
edited Nov 10 at 14:07
answered Nov 10 at 12:58
Siong Thye Goh
95.8k1462116
answered Nov 10 at 12:58
Siong Thye Goh
95.8k1462116
answered Nov 10 at 12:58
Siong Thye Goh
95.8k1462116
95.8k1462116
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 |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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