|
|
| Author |
Message |
Massimiliano
science forum beginner
Joined: 28 Sep 2005
Posts: 2
|
 Posted: Wed Sep 28, 2005 4:36 am Post subject:
AUXILIARY PROBLEM OF THE SIMPLEX ALGORITHM
|
|
|
Hi
i didnt understand a thing in the simplex algorithm:
we create the auxiliary problem for finding an feasible basic solution.
But what if an artificial variable remains in base during second phase
of the algorithm?
What guarantees me that that artificial variable never exceeds zero?
I want a proof.
I am reading original book of Dantzig, but it is not clear in this.
Please, answer me  |
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sun Oct 02, 2005 2:48 am Post subject:
Re: AUXILIARY PROBLEM OF THE SIMPLEX ALGORITHM
|
|
|
Massimiliano wrote:
| Quote: | Hi
i didnt understand a thing in the simplex algorithm:
we create the auxiliary problem for finding an feasible basic solution.
But what if an artificial variable remains in base during second phase
of the algorithm?
|
I'm not sure what you mean, but after solving the auxiliary problem,
you take that particular solution and "graft" most of it into the
original LP. The artificial variable isn't copied over.
See http://math.asu.edu/~checkman/revsimplex.pdf , for instance.
| Quote: | What guarantees me that that artificial variable never exceeds zero?
|
It might. If it does, then the feasible region is empty, and you don't
bother with the next phase.
| Quote: | I want a proof.
I am reading original book of Dantzig, but it is not clear in this.
|
Chvatal's _Linear Programming_ might be worth checking out. (That was
the one I used in grad school.)
--- Christopher Heckman |
|
| Back to top |
|
|
Massimiliano
science forum beginner
Joined: 28 Sep 2005
Posts: 2
|
| Posted: Sat Oct 08, 2005 2:32 pm Post subject:
Re: AUXILIARY PROBLEM OF THE SIMPLEX ALGORITHM
|
|
|
Proginoskes ha scritto:
| Quote: | Massimiliano wrote:
Hi
i didnt understand a thing in the simplex algorithm:
we create the auxiliary problem for finding an feasible basic solution.
But what if an artificial variable remains in base during second phase
of the algorithm?
I'm not sure what you mean, but after solving the auxiliary problem,
you take that particular solution and "graft" most of it into the
original LP. The artificial variable isn't copied over.
See http://math.asu.edu/~checkman/revsimplex.pdf , for instance.
What guarantees me that that artificial variable never exceeds zero?
It might. If it does, then the feasible region is empty, and you don't
bother with the next phase.
I want a proof.
I am reading original book of Dantzig, but it is not clear in this.
Chvatal's _Linear Programming_ might be worth checking out. (That was
the one I used in grad school.)
--- Christopher Heckman
|
Now i understood all about the two phases method.
Anyway you are in error when you say that the artificial variables
arent copied over, because it is possible that artifical variable
appear as basic variables during the second phase of the algorithm
(anyway their value is zero).
Dantzig explains it in detail in the exercies at the end of the chapter
on the simplex. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 12:31 am | All times are GMT
|
|
Bad Credit Mortgages | Credit Report | Debt Consolidation | Guitar Books | Remortgages
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
