A Solution Approach for a Class of Parametric Linear Programming Problems

Abstract

Depending on the nature, objectives, and constraints of the decision variables; linear programming, nonlinear programming, integer programming, mixed integer programming etc. can be classified. Extensive research has been conducted to solve all types of these problems in a parametric context. In this paper, to solve optimization problems having uncertainties represented by a single parameter on the objective function, a systematic linearization approach is developed considering the parametric expression as nonlinear. In the proposed approach, the objective function is considered as nonlinear which is converted into linear by using first order Taylor series expansion at the points making the parametric costs zero. Thus, the optimal solution is obtained from the constructed linear programming problem. In this way, by determining the intervals in which the optimal solution changes, the solution of the parametric linear programming problem is obtained. A numerical experiment is illustrated to present the effectiveness of the proposed approach.

Keywords

• Parametric linear programming
• linearization technique
• Taylor series expansion

References

1. Adler, I. & Monteiro, R. D. (1992). A geometric view of parametric linear programming. Algorithmica, 8(1-6), 161-176.
2. Barnett, S. (1968). A simple class of parametric linear programming problems. Operations Research, 16(6), 1160-1165.
3. Cambini, A., Schaible, S. & Sodini, C. (1993). Parametric linear fractional programming for an unbounded feasible region. Journal of global optimization, 3(2), 157-169.
4. Chong, E. K. & Zak, S. H. (2013). An Introduction to Optimization (Vol. 76). John Wiley&Sons.
5. Courtillot, M. (1962). On varying all the parameters in a linear-programming problem and sequential solution of a linear-programming problem. Operations Research, 10(4).
6. Dantzig, G.B. (1963). Linear Programming and Extensions, Princeton University Press, Princeton, NJ.
7. Gass, S. & Saaty, T. (1955a). The computational algorithm for the parametric objective function. Naval research logistics quarterly, 2(1‐2), 39-45.
8. Gass, S. I. & Saaty, T. L. (1955b). Parametric objective function (part 2)-generalization. Journal of the Operations Research Society of America, 3(4), 395-401.

9. Huang, R. & Lou, X. (2012). A Simplex Based Parametric Programming Method for the Large Linear Programming Problem. In Proceeding of the International Multiconference of Engineers and computer scientists (Vol. 2, pp. 14-16).
10. Remani, C. (2013). Numerical methods for solving systems of nonlinear equations. Lakehead University Thunder Bay, Ontario, Canada.
11. Saaty, T. L. (1959). Coefficient perturbation of a constrained extremum. Operations Research, 7(3), 294-302.
12. Taha, H. A. (2007). Operational Research: An Introduction. Pearson/Prentice Hall, 8th edition.
13. Willner, L. B. “On Parametric Linear Programming,” SIAM J. Appl. Math., Vol. 15, No. 5 (Sept.,1967), pp. 1253-1257.