A streamlined artificial variable free version of simplex method.

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

Related In: Results  -  Collection

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

pone.0116156.g009: Comparison of SM and ASM in terms of Addition Operations.
Mentions: Figs. 8 and 9 depict the comparison of SM and ASM by the average number of multiplication and addition operations needed to solve LP problems of different sizes. The tables illustrate that (either we consider multiplications or additions) ASM always need less number of operation computations as compared to SM. This difference becomes quite noticeable especially for the problems that have greater number of constraints as compared to the number of variables. So, it is empirically observed that ASM is much advantageous when “number of constraints minus number of variables” is a large number. This observation could be verified by the graph as depicted in Fig. 10, as the value of m − n increases the percentage of saved computations in ASM also increases. For example for a 200 × 300 order problem the average saving in computations is just about 5% but in contrast to a 300 × 200 order problem it reaches a remarkable level of 40%. This fact can also be seen in the problems of order 5 × 10, 10 × 5, 50 × 100 and 100 × 70. For the problems having m ≈ n, the savings in number of computations is not much high. Basic theory of duality asserts that in contrast to ASM, the dual art-free simplex method (DASM) would be more efficient computationally when n − m is large.

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.