Prove that optimal solution is an extreme point in LPP.
While proving this I have proved that Optimal solution cannot lie inside the feasible set and that each supporting hyperplane to a set bounded from below (which is the case as in LPP we can always set x>0) has at least one extreme point.
I have also been give a hint to use Hahn Banach Theorem which states that Every boundary point of a convex set has a supporting hyperplane.
So using these two I now have to prove that any boundary point which is not an extreme point will have an extreme point as the solution (which I assume will be the extreme point lying on the optimal plane (which will also be the Supporting hyperplane or in general every point on this hyperplane will be an optimal solution).
optimization linear-programming
asked Feb 2 '15 at 13:36
user3109578
62
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
While proving this I have proved that Optimal solution cannot lie inside the feasible set and that each supporting hyperplane to a set bounded from below (which is the case as in LPP we can always set x>0) has at least one extreme point.
I have also been give a hint to use Hahn Banach Theorem which states that Every boundary point of a convex set has a supporting hyperplane.
So using these two I now have to prove that any boundary point which is not an extreme point will have an extreme point as the solution (which I assume will be the extreme point lying on the optimal plane (which will also be the Supporting hyperplane or in general every point on this hyperplane will be an optimal solution).
optimization linear-programming
asked Feb 2 '15 at 13:36
user3109578
62
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
While proving this I have proved that Optimal solution cannot lie inside the feasible set and that each supporting hyperplane to a set bounded from below (which is the case as in LPP we can always set x>0) has at least one extreme point.
I have also been give a hint to use Hahn Banach Theorem which states that Every boundary point of a convex set has a supporting hyperplane.
So using these two I now have to prove that any boundary point which is not an extreme point will have an extreme point as the solution (which I assume will be the extreme point lying on the optimal plane (which will also be the Supporting hyperplane or in general every point on this hyperplane will be an optimal solution).
optimization linear-programming
asked Feb 2 '15 at 13:36
user3109578
62
While proving this I have proved that Optimal solution cannot lie inside the feasible set and that each supporting hyperplane to a set bounded from below (which is the case as in LPP we can always set x>0) has at least one extreme point.
I have also been give a hint to use Hahn Banach Theorem which states that Every boundary point of a convex set has a supporting hyperplane.
So using these two I now have to prove that any boundary point which is not an extreme point will have an extreme point as the solution (which I assume will be the extreme point lying on the optimal plane (which will also be the Supporting hyperplane or in general every point on this hyperplane will be an optimal solution).
optimization linear-programming
optimization linear-programming
asked Feb 2 '15 at 13:36
user3109578
62
asked Feb 2 '15 at 13:36
user3109578
62
asked Feb 2 '15 at 13:36
user3109578
62
asked Feb 2 '15 at 13:36
user3109578
62
asked Feb 2 '15 at 13:36
user3109578
62
62
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
bumped to the homepage by Community♦ 2 days ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
To prove this let x be a boundary point which is not an extreme point but is an optimal solution and P be its optimal hyperplane.
First observe that any optimal hyperplane will be a supporting hyperplane. For this let there be a point y on optimal hyperplane which lies inside the feasible set. Then by definition (c=cost coefficients) cy=cx=optimal value. But this means the optimal value of the Lpp lies inside the Feasible set. Hence contradiction.
Thus Optimal Hyperplane=>supporting Hyperplane.
And since each supporting hyperplane has at least one extreme point, P contains an extreme point. Let it be z. since z lies on the plane it is the optimal solution. But this means each point on the line segment x and z is an optimal solution (for this take any general point w between x and z and show cw=cx(=cz=optimal solution)).
Hence proved.
Source: My college teacher.
answered Feb 2 '15 at 16:09
user3109578
62
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f1130281%2fprove-that-optimal-solution-is-an-extreme-point-in-lpp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
To prove this let x be a boundary point which is not an extreme point but is an optimal solution and P be its optimal hyperplane.
First observe that any optimal hyperplane will be a supporting hyperplane. For this let there be a point y on optimal hyperplane which lies inside the feasible set. Then by definition (c=cost coefficients) cy=cx=optimal value. But this means the optimal value of the Lpp lies inside the Feasible set. Hence contradiction.
Thus Optimal Hyperplane=>supporting Hyperplane.
And since each supporting hyperplane has at least one extreme point, P contains an extreme point. Let it be z. since z lies on the plane it is the optimal solution. But this means each point on the line segment x and z is an optimal solution (for this take any general point w between x and z and show cw=cx(=cz=optimal solution)).
Hence proved.
Source: My college teacher.
answered Feb 2 '15 at 16:09
user3109578
62
add a comment |
To prove this let x be a boundary point which is not an extreme point but is an optimal solution and P be its optimal hyperplane.
First observe that any optimal hyperplane will be a supporting hyperplane. For this let there be a point y on optimal hyperplane which lies inside the feasible set. Then by definition (c=cost coefficients) cy=cx=optimal value. But this means the optimal value of the Lpp lies inside the Feasible set. Hence contradiction.
Thus Optimal Hyperplane=>supporting Hyperplane.
And since each supporting hyperplane has at least one extreme point, P contains an extreme point. Let it be z. since z lies on the plane it is the optimal solution. But this means each point on the line segment x and z is an optimal solution (for this take any general point w between x and z and show cw=cx(=cz=optimal solution)).
Hence proved.
Source: My college teacher.
answered Feb 2 '15 at 16:09
user3109578
62
add a comment |
To prove this let x be a boundary point which is not an extreme point but is an optimal solution and P be its optimal hyperplane.
First observe that any optimal hyperplane will be a supporting hyperplane. For this let there be a point y on optimal hyperplane which lies inside the feasible set. Then by definition (c=cost coefficients) cy=cx=optimal value. But this means the optimal value of the Lpp lies inside the Feasible set. Hence contradiction.
Thus Optimal Hyperplane=>supporting Hyperplane.
And since each supporting hyperplane has at least one extreme point, P contains an extreme point. Let it be z. since z lies on the plane it is the optimal solution. But this means each point on the line segment x and z is an optimal solution (for this take any general point w between x and z and show cw=cx(=cz=optimal solution)).
Hence proved.
Source: My college teacher.
answered Feb 2 '15 at 16:09
user3109578
62
To prove this let x be a boundary point which is not an extreme point but is an optimal solution and P be its optimal hyperplane.
First observe that any optimal hyperplane will be a supporting hyperplane. For this let there be a point y on optimal hyperplane which lies inside the feasible set. Then by definition (c=cost coefficients) cy=cx=optimal value. But this means the optimal value of the Lpp lies inside the Feasible set. Hence contradiction.
Thus Optimal Hyperplane=>supporting Hyperplane.
And since each supporting hyperplane has at least one extreme point, P contains an extreme point. Let it be z. since z lies on the plane it is the optimal solution. But this means each point on the line segment x and z is an optimal solution (for this take any general point w between x and z and show cw=cx(=cz=optimal solution)).
Hence proved.
Source: My college teacher.
answered Feb 2 '15 at 16:09
user3109578
62
answered Feb 2 '15 at 16:09
user3109578
62
answered Feb 2 '15 at 16:09
user3109578
62
answered Feb 2 '15 at 16:09
user3109578
62
62
add a comment |
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%2f1130281%2fprove-that-optimal-solution-is-an-extreme-point-in-lpp%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
