Get reduced costs from simplex tableau
up vote
2
down vote
favorite
This is probably a dumb question... but I'm trying to find how to calculate the reduced cost for a particular variable based on the information in a simplex tableau after I've minimized a linear programming problem. I've been googling like crazy and, while I can find a million sites that explain how to interpret reduced costs and how they are useful, I can't find a single resource that tells me how to calculate them.
How can this be done?
linear-programming
asked Mar 21 '14 at 19:56
John Chrysostom
1111
add a comment |
up vote
2
down vote
favorite
This is probably a dumb question... but I'm trying to find how to calculate the reduced cost for a particular variable based on the information in a simplex tableau after I've minimized a linear programming problem. I've been googling like crazy and, while I can find a million sites that explain how to interpret reduced costs and how they are useful, I can't find a single resource that tells me how to calculate them.
How can this be done?
linear-programming
asked Mar 21 '14 at 19:56
John Chrysostom
1111
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
This is probably a dumb question... but I'm trying to find how to calculate the reduced cost for a particular variable based on the information in a simplex tableau after I've minimized a linear programming problem. I've been googling like crazy and, while I can find a million sites that explain how to interpret reduced costs and how they are useful, I can't find a single resource that tells me how to calculate them.
How can this be done?
linear-programming
asked Mar 21 '14 at 19:56
John Chrysostom
1111
This is probably a dumb question... but I'm trying to find how to calculate the reduced cost for a particular variable based on the information in a simplex tableau after I've minimized a linear programming problem. I've been googling like crazy and, while I can find a million sites that explain how to interpret reduced costs and how they are useful, I can't find a single resource that tells me how to calculate them.
How can this be done?
linear-programming
linear-programming
asked Mar 21 '14 at 19:56
John Chrysostom
1111
asked Mar 21 '14 at 19:56
John Chrysostom
1111
asked Mar 21 '14 at 19:56
John Chrysostom
1111
asked Mar 21 '14 at 19:56
John Chrysostom
1111
asked Mar 21 '14 at 19:56
John Chrysostom
1111
1111
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
After you have minimized the LP, there are no more reduced costs, e.g. they are all zero. All that you have are the dual variables. You only do have nonzero reduced costs at a local minimum (=basis = edge of the feasible polyhedron).
Generally, the reduced cost is:
begin{equation}
d_j = c_j - mu^top A_j
end{equation}
Cost of increasing a nonbasic variable $x_j$. Nonbasic row of the coefficientmatrix $A$: $A_j$.
With dual variable $mu$:
begin{equation}
mu = c_B^top B^{-1}
end{equation}
$B$ is the Basis of coefficient matrix $A$, sometimes $B$ is called $A_B$.
There is an example in Bertsimas - Introduction to Linear Optimization on p.84.
answered May 14 '14 at 13:54
JaBe
1707
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
After you have minimized the LP, there are no more reduced costs, e.g. they are all zero. All that you have are the dual variables. You only do have nonzero reduced costs at a local minimum (=basis = edge of the feasible polyhedron).
Generally, the reduced cost is:
begin{equation}
d_j = c_j - mu^top A_j
end{equation}
Cost of increasing a nonbasic variable $x_j$. Nonbasic row of the coefficientmatrix $A$: $A_j$.
With dual variable $mu$:
begin{equation}
mu = c_B^top B^{-1}
end{equation}
$B$ is the Basis of coefficient matrix $A$, sometimes $B$ is called $A_B$.
There is an example in Bertsimas - Introduction to Linear Optimization on p.84.
answered May 14 '14 at 13:54
JaBe
1707
add a comment |
up vote
0
down vote
After you have minimized the LP, there are no more reduced costs, e.g. they are all zero. All that you have are the dual variables. You only do have nonzero reduced costs at a local minimum (=basis = edge of the feasible polyhedron).
Generally, the reduced cost is:
begin{equation}
d_j = c_j - mu^top A_j
end{equation}
Cost of increasing a nonbasic variable $x_j$. Nonbasic row of the coefficientmatrix $A$: $A_j$.
With dual variable $mu$:
begin{equation}
mu = c_B^top B^{-1}
end{equation}
$B$ is the Basis of coefficient matrix $A$, sometimes $B$ is called $A_B$.
There is an example in Bertsimas - Introduction to Linear Optimization on p.84.
answered May 14 '14 at 13:54
JaBe
1707
add a comment |
up vote
0
down vote
up vote
0
down vote
After you have minimized the LP, there are no more reduced costs, e.g. they are all zero. All that you have are the dual variables. You only do have nonzero reduced costs at a local minimum (=basis = edge of the feasible polyhedron).
Generally, the reduced cost is:
begin{equation}
d_j = c_j - mu^top A_j
end{equation}
Cost of increasing a nonbasic variable $x_j$. Nonbasic row of the coefficientmatrix $A$: $A_j$.
With dual variable $mu$:
begin{equation}
mu = c_B^top B^{-1}
end{equation}
$B$ is the Basis of coefficient matrix $A$, sometimes $B$ is called $A_B$.
There is an example in Bertsimas - Introduction to Linear Optimization on p.84.
answered May 14 '14 at 13:54
JaBe
1707
After you have minimized the LP, there are no more reduced costs, e.g. they are all zero. All that you have are the dual variables. You only do have nonzero reduced costs at a local minimum (=basis = edge of the feasible polyhedron).
Generally, the reduced cost is:
begin{equation}
d_j = c_j - mu^top A_j
end{equation}
Cost of increasing a nonbasic variable $x_j$. Nonbasic row of the coefficientmatrix $A$: $A_j$.
With dual variable $mu$:
begin{equation}
mu = c_B^top B^{-1}
end{equation}
$B$ is the Basis of coefficient matrix $A$, sometimes $B$ is called $A_B$.
There is an example in Bertsimas - Introduction to Linear Optimization on p.84.
answered May 14 '14 at 13:54
JaBe
1707
edited May 14 '14 at 14:06
answered May 14 '14 at 13:54
JaBe
1707
answered May 14 '14 at 13:54
JaBe
1707
answered May 14 '14 at 13:54
JaBe
1707
1707
add a comment |
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%2f721480%2fget-reduced-costs-from-simplex-tableau%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
