Article: An interior boundary pivotal solution algorithm for linear programmes with the optimal solution-based sensitivity region Journal: International Journal of Mathematics in Operational Research (IJMOR) 2013 Vol.5 No.6 pp.663 - 692 Abstract: We have developed a full gradient method that consists of three phases. The initialisation phase provides the initial tableau that may not have a full set of basis. The push phase uses a full gradient vector of the objective function to obtain a feasible vertex. This is then followed by a series of pivotal steps using the sub-gradient, which leads to an optimal solution (if exists) in the final iteration phase. At each of these iterations, the sub-gradient provides the desired direction of motion within the feasible region. The algorithm hits and/or moves on the constraint hyper-planes and their intersections to reach an optimal vertex (if exists). The algorithm works in the original decision variables and slack/surplus space, therefore, there is no need to introduce any new extra variables such as artificial variables. The simplex solution algorithm can be considered as a sub-more efficient. Given a linear programme has a known unique non-degenerate primal/dual solution; we develop the largest sensitivity region for linear programming models-based only the optimal solution rather than the final tableau. It allows for simultaneous, dependent/independent changes on the cost coefficients and the right-hand side of constraint. Numerical illustrative examples are given. Inderscience Publishers - linking academia, business and industry through research

Title: An interior boundary pivotal solution algorithm for linear programmes with the optimal solution-based sensitivity region

Authors: Hossein Arsham; Angappa Gunasekaran

Addresses: Merrick School of Business, University of Baltimore, Baltimore, MD 21201, USA ' Department of Decision and Information Sciences, Charlton College of Business, University of Massachusetts, Dartmouth, 285 Old Westport Road, North Dartmouth, MA 02747-2300, USA

Abstract: We have developed a full gradient method that consists of three phases. The initialisation phase provides the initial tableau that may not have a full set of basis. The push phase uses a full gradient vector of the objective function to obtain a feasible vertex. This is then followed by a series of pivotal steps using the sub-gradient, which leads to an optimal solution (if exists) in the final iteration phase. At each of these iterations, the sub-gradient provides the desired direction of motion within the feasible region. The algorithm hits and/or moves on the constraint hyper-planes and their intersections to reach an optimal vertex (if exists). The algorithm works in the original decision variables and slack/surplus space, therefore, there is no need to introduce any new extra variables such as artificial variables. The simplex solution algorithm can be considered as a sub-more efficient. Given a linear programme has a known unique non-degenerate primal/dual solution; we develop the largest sensitivity region for linear programming models-based only the optimal solution rather than the final tableau. It allows for simultaneous, dependent/independent changes on the cost coefficients and the right-hand side of constraint. Numerical illustrative examples are given.

Keywords: linear programming; full gradient simplex algorithm; artificial-free; pivoting algorithm; feasible direction method; simplex standard-form free; big-M free; largest sensitivity region.

DOI: 10.1504/IJMOR.2013.057489

International Journal of Mathematics in Operational Research, 2013 Vol.5 No.6, pp.663 - 692

Published online: 31 Mar 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: An interior boundary pivotal solution algorithm for linear programmes with the optimal solution-based sensitivity region

Keep up-to-date