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

DOI10.1504/IJMOR.2013.057489MaRDI QIDQ1635378zbMATH OpenOpenAlexFDO

Authors H. Arsham, Angappa Gunasekaran

Publication date 6 June 2018

Published in International Journal of Mathematics in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijmor.2013.057489

zbMATH Keywords

artificial-freebig-M freefeasible direction methodfull gradient simplex algorithmlargest sensitivity regionlinear programmingpivoting algorithmsimplex standard-form free

Mathematics Subject Classification ID

Linear programming (90C05) Sensitivity, stability, parametric optimization (90C31) Optimality conditions and duality in mathematical programming (90C46)

Review text

Summary: 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.

Recommendations

• A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs
• The sensitivity analysis of linear programming based on the improved basic line algorithm
• Construction of the largest sensitivity region for general linear programs
• Matrix Sensitivity Analysis from an Interior Solution of a Linear Program
• An \(\varepsilon\)-sensitivity analysis in the primal-dual interior point method

Cited in

(1)

• A hybrid gradient and feasible direction pivotal solution algorithm for general linear programs

This page was built for publication: An interior boundary pivotal solution algorithm for linear programmes with the optimal solution-based sensitivity region

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1635378)