Mixing
Solving a LP problem
$begingroup$
I am learning optimization and I came across this exercise to solve the following problem:
$$min 2x_1+3x_2$$
$$x_1+x_2geq 5$$
$$x_1geq 1$$
$$x_2geq 2$$
This exercise has been introduced just after the definition of the standard LP and the corresponding dual problem.
The question is to prove that $x^*=(3,2)$ is the optimal solution by showing that the objective value of any feasible solution is at least 12.
I have tried to convert the problem to the dual form.
First I convert my LP problem to a standard LP problem by introducing the surplus variables $x_3,x_4,x_5:$
$$min 2x_1+3x_2$$
$$x_1+x_2-x_3 = 5$$
$$x_1-x_4 = 1$$
$$x_2 - x_5 = 2$$
with all $x_i geq 0$.
Then I convert the problem to the corresponding standard dual:
$$max 5y_1+y_2+2y_3$$
$$y_1+y_2leq 2$$
$$y_3leq 3$$
$$y_i geq 0, i in {1,2,3}$$
But then I am stuck...
optimization linear-programming duality-theorems
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
$endgroup$
|
show 3 more comments
$begingroup$
I am learning optimization and I came across this exercise to solve the following problem:
$$min 2x_1+3x_2$$
$$x_1+x_2geq 5$$
$$x_1geq 1$$
$$x_2geq 2$$
This exercise has been introduced just after the definition of the standard LP and the corresponding dual problem.
The question is to prove that $x^*=(3,2)$ is the optimal solution by showing that the objective value of any feasible solution is at least 12.
I have tried to convert the problem to the dual form.
First I convert my LP problem to a standard LP problem by introducing the surplus variables $x_3,x_4,x_5:$
$$min 2x_1+3x_2$$
$$x_1+x_2-x_3 = 5$$
$$x_1-x_4 = 1$$
$$x_2 - x_5 = 2$$
with all $x_i geq 0$.
Then I convert the problem to the corresponding standard dual:
$$max 5y_1+y_2+2y_3$$
$$y_1+y_2leq 2$$
$$y_3leq 3$$
$$y_i geq 0, i in {1,2,3}$$
But then I am stuck...
optimization linear-programming duality-theorems
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
$endgroup$
1
$begingroup$
How can $x^*=(3,2)$ if $x_1geq5$? Did you mean to write $x_1geq3$?
$endgroup$
– Thoth
Jan 17 at 6:00
$begingroup$
You are right, sorry for the typo. I have corrected it. Thanks
$endgroup$
– JejeBelfort
Jan 17 at 6:12
$begingroup$
@JejeBelfort Note the constraints at the dual are $$y_1+y_2color{red}= 2$$ $$y_3color{red}= 3$$
$endgroup$
– callculus
Jan 17 at 6:40
$begingroup$
Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $ x_1 ge 0 ,$ and $ x_2ge 0 $ , then the second inequality in your dual, corresponding to the variable $ x_2 $ of the primal, should be $y_1 + y_3 le 3 $, because the coefficient of $ x_2 $ in the first inequality of the primal, corresponding to the variable $ y_1 $ of the dual, is $ 1 $.
$endgroup$
– lonza leggiera
Jan 17 at 6:52
$begingroup$
@JejeBelfort Your dual is still wrong. Didn´t you get my comment?
$endgroup$
– callculus
Jan 17 at 7:02
|
show 3 more comments
$begingroup$
I am learning optimization and I came across this exercise to solve the following problem:
$$min 2x_1+3x_2$$
$$x_1+x_2geq 5$$
$$x_1geq 1$$
$$x_2geq 2$$
This exercise has been introduced just after the definition of the standard LP and the corresponding dual problem.
The question is to prove that $x^*=(3,2)$ is the optimal solution by showing that the objective value of any feasible solution is at least 12.
I have tried to convert the problem to the dual form.
First I convert my LP problem to a standard LP problem by introducing the surplus variables $x_3,x_4,x_5:$
$$min 2x_1+3x_2$$
$$x_1+x_2-x_3 = 5$$
$$x_1-x_4 = 1$$
$$x_2 - x_5 = 2$$
with all $x_i geq 0$.
Then I convert the problem to the corresponding standard dual:
$$max 5y_1+y_2+2y_3$$
$$y_1+y_2leq 2$$
$$y_3leq 3$$
$$y_i geq 0, i in {1,2,3}$$
But then I am stuck...
optimization linear-programming duality-theorems
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
$endgroup$
I am learning optimization and I came across this exercise to solve the following problem:
$$min 2x_1+3x_2$$
$$x_1+x_2geq 5$$
$$x_1geq 1$$
$$x_2geq 2$$
This exercise has been introduced just after the definition of the standard LP and the corresponding dual problem.
The question is to prove that $x^*=(3,2)$ is the optimal solution by showing that the objective value of any feasible solution is at least 12.
I have tried to convert the problem to the dual form.
First I convert my LP problem to a standard LP problem by introducing the surplus variables $x_3,x_4,x_5:$
$$min 2x_1+3x_2$$
$$x_1+x_2-x_3 = 5$$
$$x_1-x_4 = 1$$
$$x_2 - x_5 = 2$$
with all $x_i geq 0$.
Then I convert the problem to the corresponding standard dual:
$$max 5y_1+y_2+2y_3$$
$$y_1+y_2leq 2$$
$$y_3leq 3$$
$$y_i geq 0, i in {1,2,3}$$
But then I am stuck...
optimization linear-programming duality-theorems
optimization linear-programming duality-theorems
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
edited Jan 17 at 6:53
JejeBelfort
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
asked Jan 17 at 5:53
JejeBelfortJejeBelfort
1159
1159
1
$begingroup$
How can $x^*=(3,2)$ if $x_1geq5$? Did you mean to write $x_1geq3$?
$endgroup$
– Thoth
Jan 17 at 6:00
$begingroup$
You are right, sorry for the typo. I have corrected it. Thanks
$endgroup$
– JejeBelfort
Jan 17 at 6:12
$begingroup$
@JejeBelfort Note the constraints at the dual are $$y_1+y_2color{red}= 2$$ $$y_3color{red}= 3$$
$endgroup$
– callculus
Jan 17 at 6:40
$begingroup$
Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $ x_1 ge 0 ,$ and $ x_2ge 0 $ , then the second inequality in your dual, corresponding to the variable $ x_2 $ of the primal, should be $y_1 + y_3 le 3 $, because the coefficient of $ x_2 $ in the first inequality of the primal, corresponding to the variable $ y_1 $ of the dual, is $ 1 $.
$endgroup$
– lonza leggiera
Jan 17 at 6:52
$begingroup$
@JejeBelfort Your dual is still wrong. Didn´t you get my comment?
$endgroup$
– callculus
Jan 17 at 7:02
|
show 3 more comments
1
$begingroup$
How can $x^*=(3,2)$ if $x_1geq5$? Did you mean to write $x_1geq3$?
$endgroup$
– Thoth
Jan 17 at 6:00
$begingroup$
You are right, sorry for the typo. I have corrected it. Thanks
$endgroup$
– JejeBelfort
Jan 17 at 6:12
$begingroup$
@JejeBelfort Note the constraints at the dual are $$y_1+y_2color{red}= 2$$ $$y_3color{red}= 3$$
$endgroup$
– callculus
Jan 17 at 6:40
$begingroup$
Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $ x_1 ge 0 ,$ and $ x_2ge 0 $ , then the second inequality in your dual, corresponding to the variable $ x_2 $ of the primal, should be $y_1 + y_3 le 3 $, because the coefficient of $ x_2 $ in the first inequality of the primal, corresponding to the variable $ y_1 $ of the dual, is $ 1 $.
$endgroup$
– lonza leggiera
Jan 17 at 6:52
$begingroup$
@JejeBelfort Your dual is still wrong. Didn´t you get my comment?
$endgroup$
– callculus
Jan 17 at 7:02
1
1
$begingroup$
How can $x^*=(3,2)$ if $x_1geq5$? Did you mean to write $x_1geq3$?
$endgroup$
– Thoth
Jan 17 at 6:00
$begingroup$
How can $x^*=(3,2)$ if $x_1geq5$? Did you mean to write $x_1geq3$?
$endgroup$
– Thoth
Jan 17 at 6:00
$begingroup$
You are right, sorry for the typo. I have corrected it. Thanks
$endgroup$
– JejeBelfort
Jan 17 at 6:12
$begingroup$
You are right, sorry for the typo. I have corrected it. Thanks
$endgroup$
– JejeBelfort
Jan 17 at 6:12
$begingroup$
@JejeBelfort Note the constraints at the dual are $$y_1+y_2color{red}= 2$$ $$y_3color{red}= 3$$
$endgroup$
– callculus
Jan 17 at 6:40
$begingroup$
@JejeBelfort Note the constraints at the dual are $$y_1+y_2color{red}= 2$$ $$y_3color{red}= 3$$
$endgroup$
– callculus
Jan 17 at 6:40
$begingroup$
Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $ x_1 ge 0 ,$ and $ x_2ge 0 $ , then the second inequality in your dual, corresponding to the variable $ x_2 $ of the primal, should be $y_1 + y_3 le 3 $, because the coefficient of $ x_2 $ in the first inequality of the primal, corresponding to the variable $ y_1 $ of the dual, is $ 1 $.
$endgroup$
– lonza leggiera
Jan 17 at 6:52
$begingroup$
Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $ x_1 ge 0 ,$ and $ x_2ge 0 $ , then the second inequality in your dual, corresponding to the variable $ x_2 $ of the primal, should be $y_1 + y_3 le 3 $, because the coefficient of $ x_2 $ in the first inequality of the primal, corresponding to the variable $ y_1 $ of the dual, is $ 1 $.
$endgroup$
– lonza leggiera
Jan 17 at 6:52
$begingroup$
@JejeBelfort Your dual is still wrong. Didn´t you get my comment?
$endgroup$
– callculus
Jan 17 at 7:02
$begingroup$
@JejeBelfort Your dual is still wrong. Didn´t you get my comment?
$endgroup$
– callculus
Jan 17 at 7:02
|
show 3 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Edited hint: Since a reformulation of the original problem into standard form has now been added, my original answer is no longer very comprehensible. The dual of the problem, as originally formulated is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:} & &\
y_1+y_2 &=& 2\
y_1 + y_3&=&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0
end{eqnarray}
$
As callculus has pointed out, in the absence of any explicit sign restrictions on the variabes $x_1, mbox{and } x_2 $, the constraints in the dual should be equations rather than inequalities. However, since the second and third constraints of the primal imply that $ x_1ge0, mbox{and } x_2ge0 $, these implied constraints could have been made explicit in the original formulation—as you have now so made them in your reformulation into standard form—, and then the dual constraints would have been $y_1+y_2 le 2 $ and $y_1 + y_3le3 $, as they are, in fact, for the standard form, whose dual is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:}& &\
y_1+y_2 &le& 2\
y_1 + y_3&le&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0 .
end{eqnarray}
$
Now if $ x^* = left(3, 2right) $ is an optimal solution for the primal, then because the non-negativity conditions, $ x_1 ge 0 mbox{ and } x_2 ge0$, of your primal (in standard form) are both slack for those values (i.e. $ 3, {color{red} >}, 0 mbox{ and } 2, {color{red} >}, 0 $), the complementary slackness conditions imply that the corresponding constraints, $ y_1+y_2le 2 mbox{ and } y_1 + y_3le3 $, must be tight for an optimal solution, $ left(y_1^*, y_2^*, y_3^*right) $, of the dual—that is, $ y_1^*+y_2^*= 2 mbox{ and } y_1^* + y_3^*=3 $. Similarly, because the non-negativity condition $x_4 ge 0$ is also slack (since $ x_4 = x_1^* - 1 = 2, {color{red} >}, 0 $), then the corresponding constraint, $ y_2 ge 0 $, should be tight for the optimal solution of the dual. That is, $ y_2^* = 0 $. These conditions are sufficient to determine uniquely what the optimal solution of the dual would have to be—namely, $ y_1^* = 2, y_2^* = 0, $ and $ y_3^* = 1 $. To verify that these purported optimal solutions really are optimal, all you have to do is check that the values of their respective objective functions are the same for both of them, which is, in fact, the case.
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
$endgroup$
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
1
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
add a comment |
$begingroup$
Let's use a graphical solution.
Taking $x_1$ on x axis and latter on y axis.
We get
$$x+y≥5$$
$$x≥1$$
$$y≥2$$
And we need to find the minimum value of c
In $$2x+3y= c$$image of graphical rendering by desmos
By slowly increasing c we can easily see that it first intersects the red area (possible values of X and y) first at (2,3) and is the unique solution to c= 12
I have used a graphing calculator for this but it can be easily drawn on paper.
answered Jan 17 at 7:02
KarthikKarthik
13212
$endgroup$
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
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%2f3076636%2fsolving-a-lp-problem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Edited hint: Since a reformulation of the original problem into standard form has now been added, my original answer is no longer very comprehensible. The dual of the problem, as originally formulated is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:} & &\
y_1+y_2 &=& 2\
y_1 + y_3&=&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0
end{eqnarray}
$
As callculus has pointed out, in the absence of any explicit sign restrictions on the variabes $x_1, mbox{and } x_2 $, the constraints in the dual should be equations rather than inequalities. However, since the second and third constraints of the primal imply that $ x_1ge0, mbox{and } x_2ge0 $, these implied constraints could have been made explicit in the original formulation—as you have now so made them in your reformulation into standard form—, and then the dual constraints would have been $y_1+y_2 le 2 $ and $y_1 + y_3le3 $, as they are, in fact, for the standard form, whose dual is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:}& &\
y_1+y_2 &le& 2\
y_1 + y_3&le&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0 .
end{eqnarray}
$
Now if $ x^* = left(3, 2right) $ is an optimal solution for the primal, then because the non-negativity conditions, $ x_1 ge 0 mbox{ and } x_2 ge0$, of your primal (in standard form) are both slack for those values (i.e. $ 3, {color{red} >}, 0 mbox{ and } 2, {color{red} >}, 0 $), the complementary slackness conditions imply that the corresponding constraints, $ y_1+y_2le 2 mbox{ and } y_1 + y_3le3 $, must be tight for an optimal solution, $ left(y_1^*, y_2^*, y_3^*right) $, of the dual—that is, $ y_1^*+y_2^*= 2 mbox{ and } y_1^* + y_3^*=3 $. Similarly, because the non-negativity condition $x_4 ge 0$ is also slack (since $ x_4 = x_1^* - 1 = 2, {color{red} >}, 0 $), then the corresponding constraint, $ y_2 ge 0 $, should be tight for the optimal solution of the dual. That is, $ y_2^* = 0 $. These conditions are sufficient to determine uniquely what the optimal solution of the dual would have to be—namely, $ y_1^* = 2, y_2^* = 0, $ and $ y_3^* = 1 $. To verify that these purported optimal solutions really are optimal, all you have to do is check that the values of their respective objective functions are the same for both of them, which is, in fact, the case.
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
$endgroup$
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
1
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
add a comment |
$begingroup$
Edited hint: Since a reformulation of the original problem into standard form has now been added, my original answer is no longer very comprehensible. The dual of the problem, as originally formulated is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:} & &\
y_1+y_2 &=& 2\
y_1 + y_3&=&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0
end{eqnarray}
$
As callculus has pointed out, in the absence of any explicit sign restrictions on the variabes $x_1, mbox{and } x_2 $, the constraints in the dual should be equations rather than inequalities. However, since the second and third constraints of the primal imply that $ x_1ge0, mbox{and } x_2ge0 $, these implied constraints could have been made explicit in the original formulation—as you have now so made them in your reformulation into standard form—, and then the dual constraints would have been $y_1+y_2 le 2 $ and $y_1 + y_3le3 $, as they are, in fact, for the standard form, whose dual is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:}& &\
y_1+y_2 &le& 2\
y_1 + y_3&le&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0 .
end{eqnarray}
$
Now if $ x^* = left(3, 2right) $ is an optimal solution for the primal, then because the non-negativity conditions, $ x_1 ge 0 mbox{ and } x_2 ge0$, of your primal (in standard form) are both slack for those values (i.e. $ 3, {color{red} >}, 0 mbox{ and } 2, {color{red} >}, 0 $), the complementary slackness conditions imply that the corresponding constraints, $ y_1+y_2le 2 mbox{ and } y_1 + y_3le3 $, must be tight for an optimal solution, $ left(y_1^*, y_2^*, y_3^*right) $, of the dual—that is, $ y_1^*+y_2^*= 2 mbox{ and } y_1^* + y_3^*=3 $. Similarly, because the non-negativity condition $x_4 ge 0$ is also slack (since $ x_4 = x_1^* - 1 = 2, {color{red} >}, 0 $), then the corresponding constraint, $ y_2 ge 0 $, should be tight for the optimal solution of the dual. That is, $ y_2^* = 0 $. These conditions are sufficient to determine uniquely what the optimal solution of the dual would have to be—namely, $ y_1^* = 2, y_2^* = 0, $ and $ y_3^* = 1 $. To verify that these purported optimal solutions really are optimal, all you have to do is check that the values of their respective objective functions are the same for both of them, which is, in fact, the case.
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
$endgroup$
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
1
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
add a comment |
$begingroup$
Edited hint: Since a reformulation of the original problem into standard form has now been added, my original answer is no longer very comprehensible. The dual of the problem, as originally formulated is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:} & &\
y_1+y_2 &=& 2\
y_1 + y_3&=&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0
end{eqnarray}
$
As callculus has pointed out, in the absence of any explicit sign restrictions on the variabes $x_1, mbox{and } x_2 $, the constraints in the dual should be equations rather than inequalities. However, since the second and third constraints of the primal imply that $ x_1ge0, mbox{and } x_2ge0 $, these implied constraints could have been made explicit in the original formulation—as you have now so made them in your reformulation into standard form—, and then the dual constraints would have been $y_1+y_2 le 2 $ and $y_1 + y_3le3 $, as they are, in fact, for the standard form, whose dual is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:}& &\
y_1+y_2 &le& 2\
y_1 + y_3&le&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0 .
end{eqnarray}
$
Now if $ x^* = left(3, 2right) $ is an optimal solution for the primal, then because the non-negativity conditions, $ x_1 ge 0 mbox{ and } x_2 ge0$, of your primal (in standard form) are both slack for those values (i.e. $ 3, {color{red} >}, 0 mbox{ and } 2, {color{red} >}, 0 $), the complementary slackness conditions imply that the corresponding constraints, $ y_1+y_2le 2 mbox{ and } y_1 + y_3le3 $, must be tight for an optimal solution, $ left(y_1^*, y_2^*, y_3^*right) $, of the dual—that is, $ y_1^*+y_2^*= 2 mbox{ and } y_1^* + y_3^*=3 $. Similarly, because the non-negativity condition $x_4 ge 0$ is also slack (since $ x_4 = x_1^* - 1 = 2, {color{red} >}, 0 $), then the corresponding constraint, $ y_2 ge 0 $, should be tight for the optimal solution of the dual. That is, $ y_2^* = 0 $. These conditions are sufficient to determine uniquely what the optimal solution of the dual would have to be—namely, $ y_1^* = 2, y_2^* = 0, $ and $ y_3^* = 1 $. To verify that these purported optimal solutions really are optimal, all you have to do is check that the values of their respective objective functions are the same for both of them, which is, in fact, the case.
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
$endgroup$
Edited hint: Since a reformulation of the original problem into standard form has now been added, my original answer is no longer very comprehensible. The dual of the problem, as originally formulated is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:} & &\
y_1+y_2 &=& 2\
y_1 + y_3&=&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0
end{eqnarray}
$
As callculus has pointed out, in the absence of any explicit sign restrictions on the variabes $x_1, mbox{and } x_2 $, the constraints in the dual should be equations rather than inequalities. However, since the second and third constraints of the primal imply that $ x_1ge0, mbox{and } x_2ge0 $, these implied constraints could have been made explicit in the original formulation—as you have now so made them in your reformulation into standard form—, and then the dual constraints would have been $y_1+y_2 le 2 $ and $y_1 + y_3le3 $, as they are, in fact, for the standard form, whose dual is:
$
begin{eqnarray}
max 5y_1 + &y_2&+ 2y_3\
mbox{ subject to:}& &\
y_1+y_2 &le& 2\
y_1 + y_3&le&3 mbox{, and}\
y_1ge0, y_2&ge0,& y_3ge 0 .
end{eqnarray}
$
Now if $ x^* = left(3, 2right) $ is an optimal solution for the primal, then because the non-negativity conditions, $ x_1 ge 0 mbox{ and } x_2 ge0$, of your primal (in standard form) are both slack for those values (i.e. $ 3, {color{red} >}, 0 mbox{ and } 2, {color{red} >}, 0 $), the complementary slackness conditions imply that the corresponding constraints, $ y_1+y_2le 2 mbox{ and } y_1 + y_3le3 $, must be tight for an optimal solution, $ left(y_1^*, y_2^*, y_3^*right) $, of the dual—that is, $ y_1^*+y_2^*= 2 mbox{ and } y_1^* + y_3^*=3 $. Similarly, because the non-negativity condition $x_4 ge 0$ is also slack (since $ x_4 = x_1^* - 1 = 2, {color{red} >}, 0 $), then the corresponding constraint, $ y_2 ge 0 $, should be tight for the optimal solution of the dual. That is, $ y_2^* = 0 $. These conditions are sufficient to determine uniquely what the optimal solution of the dual would have to be—namely, $ y_1^* = 2, y_2^* = 0, $ and $ y_3^* = 1 $. To verify that these purported optimal solutions really are optimal, all you have to do is check that the values of their respective objective functions are the same for both of them, which is, in fact, the case.
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
edited Jan 19 at 1:18
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
answered Jan 17 at 7:15
lonza leggieralonza leggiera
82117
82117
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
1
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
add a comment |
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
1
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
You haven´t mentioned that the dual is still wrong.
$endgroup$
– callculus
Jan 17 at 7:19
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
$begingroup$
I was assuming that the primal constraints implicitly included the redundant inequalities $x_1ge 0 $ and $ x_2ge 0 $, in which case the dual constraints can be inequalites rather than equations.
$endgroup$
– lonza leggiera
Jan 17 at 7:51
1
1
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
I´ve change my downvote into an upvote.
$endgroup$
– callculus
Jan 18 at 20:57
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
$begingroup$
--------Thank you.
$endgroup$
– lonza leggiera
Jan 18 at 22:19
add a comment |
$begingroup$
Let's use a graphical solution.
Taking $x_1$ on x axis and latter on y axis.
We get
$$x+y≥5$$
$$x≥1$$
$$y≥2$$
And we need to find the minimum value of c
In $$2x+3y= c$$image of graphical rendering by desmos
By slowly increasing c we can easily see that it first intersects the red area (possible values of X and y) first at (2,3) and is the unique solution to c= 12
I have used a graphing calculator for this but it can be easily drawn on paper.
answered Jan 17 at 7:02
KarthikKarthik
13212
$endgroup$
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
add a comment |
$begingroup$
Let's use a graphical solution.
Taking $x_1$ on x axis and latter on y axis.
We get
$$x+y≥5$$
$$x≥1$$
$$y≥2$$
And we need to find the minimum value of c
In $$2x+3y= c$$image of graphical rendering by desmos
By slowly increasing c we can easily see that it first intersects the red area (possible values of X and y) first at (2,3) and is the unique solution to c= 12
I have used a graphing calculator for this but it can be easily drawn on paper.
answered Jan 17 at 7:02
KarthikKarthik
13212
$endgroup$
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
add a comment |
$begingroup$
Let's use a graphical solution.
Taking $x_1$ on x axis and latter on y axis.
We get
$$x+y≥5$$
$$x≥1$$
$$y≥2$$
And we need to find the minimum value of c
In $$2x+3y= c$$image of graphical rendering by desmos
By slowly increasing c we can easily see that it first intersects the red area (possible values of X and y) first at (2,3) and is the unique solution to c= 12
I have used a graphing calculator for this but it can be easily drawn on paper.
answered Jan 17 at 7:02
KarthikKarthik
13212
$endgroup$
Let's use a graphical solution.
Taking $x_1$ on x axis and latter on y axis.
We get
$$x+y≥5$$
$$x≥1$$
$$y≥2$$
And we need to find the minimum value of c
In $$2x+3y= c$$image of graphical rendering by desmos
By slowly increasing c we can easily see that it first intersects the red area (possible values of X and y) first at (2,3) and is the unique solution to c= 12
I have used a graphing calculator for this but it can be easily drawn on paper.
answered Jan 17 at 7:02
KarthikKarthik
13212
answered Jan 17 at 7:02
KarthikKarthik
13212
answered Jan 17 at 7:02
KarthikKarthik
13212
answered Jan 17 at 7:02
KarthikKarthik
13212
13212
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
add a comment |
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Agreed for the graphical solution, thanks! However, I don't think this is the philosophy of the exercise, which is to play around with the dual problem.
$endgroup$
– JejeBelfort
Jan 17 at 7:11
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
Welcome to MSE: It should be clear from the question that the person who asked it is not after a solution that uses computers.
$endgroup$
– José Carlos Santos
Jan 17 at 7:12
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer wasn't necessary.
$endgroup$
– Karthik
Jan 17 at 7:13
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
$begingroup$
As I mentioned a computer isn't necessary. It can be easily hand drawn and the solution could be obtained just using a rough graph. I used the computer just so that it looks good.
$endgroup$
– Karthik
Jan 17 at 7:15
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.
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%2f3076636%2fsolving-a-lp-problem%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
$begingroup$
How can $x^*=(3,2)$ if $x_1geq5$? Did you mean to write $x_1geq3$?
$endgroup$
– Thoth
Jan 17 at 6:00
$begingroup$
You are right, sorry for the typo. I have corrected it. Thanks
$endgroup$
– JejeBelfort
Jan 17 at 6:12
$begingroup$
@JejeBelfort Note the constraints at the dual are $$y_1+y_2color{red}= 2$$ $$y_3color{red}= 3$$
$endgroup$
– callculus
Jan 17 at 6:40
$begingroup$
Assuming that you're thinking of your primal as including the implicit (but redundant) constraints $ x_1 ge 0 ,$ and $ x_2ge 0 $ , then the second inequality in your dual, corresponding to the variable $ x_2 $ of the primal, should be $y_1 + y_3 le 3 $, because the coefficient of $ x_2 $ in the first inequality of the primal, corresponding to the variable $ y_1 $ of the dual, is $ 1 $.
$endgroup$
– lonza leggiera
Jan 17 at 6:52
$begingroup$
@JejeBelfort Your dual is still wrong. Didn´t you get my comment?
$endgroup$
– callculus
Jan 17 at 7:02