Limits...
A streamlined artificial variable free version of simplex method.

Inayatullah S, Touheed N, Imtiaz M - PLoS ONE (2015)

Bottom Line: This paper proposes a streamlined form of simplex method which provides some great benefits over traditional simplex method.For instance, it does not need any kind of artificial variables or artificial constraints; it could start with any feasible or infeasible basis of an LP.Last but not the least, it provides a teaching aid for the teachers who want to teach feasibility achievement as a separate topic before teaching optimality achievement.

View Article: PubMed Central - PubMed

Affiliation: Department of Mathematical Sciences, University of Karachi, Karachi, Pakistan.

ABSTRACT
This paper proposes a streamlined form of simplex method which provides some great benefits over traditional simplex method. For instance, it does not need any kind of artificial variables or artificial constraints; it could start with any feasible or infeasible basis of an LP. This method follows the same pivoting sequence as of simplex phase 1 without showing any explicit description of artificial variables which also makes it space efficient. Later in this paper, a dual version of the new method has also been presented which provides a way to easily implement the phase 1 of traditional dual simplex method. For a problem having an initial basis which is both primal and dual infeasible, our methods provide full freedom to the user, that whether to start with primal artificial free version or dual artificial free version without making any reformulation to the LP structure. Last but not the least, it provides a teaching aid for the teachers who want to teach feasibility achievement as a separate topic before teaching optimality achievement.

No MeSH data available.


Reduced primal short table for system (10) along with the dual infeasibility objective w’.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4358952&req=5

pone.0116156.g007: Reduced primal short table for system (10) along with the dual infeasibility objective w’.

Mentions: As demonstrated earlier in this manuscript to achieve optimality one may either have to achieve primal feasibility and then go for optimality through primal simplex method, or on the other hand one may have to achieve dual feasibility and then go for optimality through dual simplex method. If we measure the degree of infeasibility through the number of infeasible variables, one can see that the above problem is more primal infeasible than dual infeasible. So, from a general perspective the primal feasibility achievement problem might be a difficult task in comparing to dual feasibility achievement problem. For system (10), to attain dual feasibility we may either consider solving it by using art-free simplex method on its reduced dual short table see Fig. 6 or using dual art-free simplex on its reduced primal short table see Fig. 7.


A streamlined artificial variable free version of simplex method.

Inayatullah S, Touheed N, Imtiaz M - PLoS ONE (2015)

Reduced primal short table for system (10) along with the dual infeasibility objective w’.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4358952&req=5

pone.0116156.g007: Reduced primal short table for system (10) along with the dual infeasibility objective w’.
Mentions: As demonstrated earlier in this manuscript to achieve optimality one may either have to achieve primal feasibility and then go for optimality through primal simplex method, or on the other hand one may have to achieve dual feasibility and then go for optimality through dual simplex method. If we measure the degree of infeasibility through the number of infeasible variables, one can see that the above problem is more primal infeasible than dual infeasible. So, from a general perspective the primal feasibility achievement problem might be a difficult task in comparing to dual feasibility achievement problem. For system (10), to attain dual feasibility we may either consider solving it by using art-free simplex method on its reduced dual short table see Fig. 6 or using dual art-free simplex on its reduced primal short table see Fig. 7.

Bottom Line: This paper proposes a streamlined form of simplex method which provides some great benefits over traditional simplex method.For instance, it does not need any kind of artificial variables or artificial constraints; it could start with any feasible or infeasible basis of an LP.Last but not the least, it provides a teaching aid for the teachers who want to teach feasibility achievement as a separate topic before teaching optimality achievement.

View Article: PubMed Central - PubMed

Affiliation: Department of Mathematical Sciences, University of Karachi, Karachi, Pakistan.

ABSTRACT
This paper proposes a streamlined form of simplex method which provides some great benefits over traditional simplex method. For instance, it does not need any kind of artificial variables or artificial constraints; it could start with any feasible or infeasible basis of an LP. This method follows the same pivoting sequence as of simplex phase 1 without showing any explicit description of artificial variables which also makes it space efficient. Later in this paper, a dual version of the new method has also been presented which provides a way to easily implement the phase 1 of traditional dual simplex method. For a problem having an initial basis which is both primal and dual infeasible, our methods provide full freedom to the user, that whether to start with primal artificial free version or dual artificial free version without making any reformulation to the LP structure. Last but not the least, it provides a teaching aid for the teachers who want to teach feasibility achievement as a separate topic before teaching optimality achievement.

No MeSH data available.