Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Sensitivity analysis of linear programming in the presence of correlation among right-hand side parameters or objective function coefficients

  • Original Paper
  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

Abstract

In the literature, sensitivity analysis of linear programming (LP) has been widely studied. However, only some very simple and special cases were considered when right-hand side (RHS) parameters or objective function coefficients (OFC) correlate to each other. In the presence of correlation when one parameter changes, other parameters vary, too. Here principal component analysis is used to convert the correlation of the LP homogenous parameters into functional relations. Then, using the derivatives of the functional relations, it is possible to perform classical sensitivity analysis for the LP with correlation among RHS parameters or OFC. The validity of the devised method is corroborated by open literature examples having correlation among homogenous parameters.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Arsham H (2007) Construction of the largest sensitivity region for general linear programs. Appl Math Comput 189(2):1435–1447

    Google Scholar 

  • Arsham H, Oblak M (1990) Perturbation analysis of general LP models: a unified approach to sensitivity, parametric, tolerance, and more-for-less analysis. Math Comput Model 13(8):79–102

    Article  Google Scholar 

  • Bazaraa MS, Jarvis JJ, Sherali HD (2009) Linear Programming and Network Flows, 4th edn. Wiley, New York

  • Berkelaar AB, Roos K, Terlaky T (1997) The optimal set and optimal partition approach to linear and quadratic programming. In: Gal T, Greenberg HJ (eds) Advances in sensitivity analysis and parametric programming. International series in operations research and management science, vol 6. Kluwer Academic Publishers, London, pp 159–202

  • Bradley SP, Hax AC, Magnanti TL (1977) Applied mathematical programming. Addison-Wesley Publishing Company, Boston

    Google Scholar 

  • Cai P, Cai J (1997) On the 100 % rule of sensitivity analysis in linear programming. In: Jiang T, Lee DT (eds) Computing and combinatorics: third annual international conference, COCOON ’97, Shanghai, China, 20–22 August, 1997. Proceedings vol 1276 of lecture notes in computer science. Springer, New York, pp 460–469

  • Dantzig GB (1963) Linear programming and extensions. Princeton University Press, Princeton

    Google Scholar 

  • Dehghan M, Ghaffari Hadigheh A, Mirnia K (2007) Support set invariancy sensitivity analysis in bi-parametric linear optimization. Adv Model Optim 9(1):81–89

  • Doustdargholi S, Derakhshan Asl A (2009) Sensitivity analysis of righthand-side parameter in transportation problem. Appl Math Sci 3(30):1501–1511

    Google Scholar 

  • Gal T (1995) Postoptimal analyses, parametric programming, and related topics, 2nd edn. Walter de Gruyter, Berlin

    Google Scholar 

  • Gass SI, Saaty TL (1955) Parametric objective function (part 2)-generalization. Oper Res 3(4):395–401

    Google Scholar 

  • Ghaffari Hadigheh A, Ghaffari Hadigheh H (2008) Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization. Cent Eur J Oper Res 16(2):215–238

  • Ghaffari Hadigheh A, Mirnia K, Terlaky T (2007) Active constraint set invariancy sensitivity analysis in linear optimization. J Optim Theor App 133(3):303–315

    Article  Google Scholar 

  • Ghaffari Hadigheh A, Terlaky T (2006a) Generalized support set invariancy sensitivity analysis in linear optimization. J Ind Manag Optim 2(1):1–18

    Article  Google Scholar 

  • Ghaffari Hadigheh A, Terlaky T (2006b) Sensitivity analysis in linear optimization: invariant support set intervals. Eur J Oper Res 169(3):1158–1175

    Article  Google Scholar 

  • Greenberg HJ (1994) The use of the optimal partition in a linear programming solution for postoptimal analysis. Oper Res Lett 15(4):179–185

    Article  Google Scholar 

  • Greenberg HJ (2000) Simultaneous primal-dual right-hand-side sensitivity analysis from a strictly complementary solution of a linear program. SIAM J Optim 10(2):427–442

    Article  Google Scholar 

  • Hanafizadeh P, Ghaemi A, Tavana M (2011) Local perturbation sensitivity analysis of linear programming with functional relation among parameters. Int J Oper Res Inf Syst 2(1):42–65

    Article  Google Scholar 

  • Hladík M (2010) Multiparametric linear programming: support set and optimal partition invariancy. Eur J Oper Res 202(1):25–31

    Article  Google Scholar 

  • Hladík M (2011) Tolerance analysis in linear systems and linear programming. Optim Method Softw 26(3):381–396

    Article  Google Scholar 

  • Hladík M (2012) Complexity of necessary efficiency in interval linear programming and multiobjective linear programming. Optim Lett 6(5):893–899

    Article  Google Scholar 

  • Hladík M, Sitarz S (2013) Maximal and supremal tolerances in multiobjective linear programming. Eur J Oper Res 228(1):93–101

    Article  Google Scholar 

  • Illés T, Peng J, Roos C, Terlaky T (2000) A strongly polynomial rounding procedure yielding a maximally complementary solution for \(P^*(\kappa )\) linear complementarity problems. SIAM J Optim 11(2):320–340

  • Jansen B, Jong J, Roos C, Terlaky T (1997) Sensitivity analysis in linear programming: just be careful! Eur J Oper Res 101(1):15–28

  • Johnson RA, Wichern DW (2007) Applied multivariate statistical analysis, 6th edn. Pearson Prentice Hall, New Jersey

    Google Scholar 

  • Koltai T, Terlaky T (2000) The difference between managerial and mathematical interpretation of sensitivity analysis results in linear programming. Int J Prod Econ 65(3):257–274

    Article  Google Scholar 

  • Labbé M, Thisse JF, Wendell RE (1991) Sensitivity analysis in minimum facility location problems. Oper Res 39(6):961–969

    Article  Google Scholar 

  • Murty KG (1983) Linear programming. Wiley, New York

    Google Scholar 

  • Roos C, Terlaky T, Vial J (1997) Interior point approach to linear optimization: theory and algorithms. Wiley, New York

    Google Scholar 

  • Saaty TL, Gass SI (1954) Parametric objective function (part 1). Oper Res 2(3):316–319

    Google Scholar 

  • Singh S (2010) Multiparametric sensitivity analysis of the additive model in data envelopment analysis. Int Trans Oper Res 17(3):365–380

    Article  Google Scholar 

  • Sitarz S (2010) Standard sensitivity analysis and additive tolerance approach in MOLP. Ann Oper Res 181(1):219–232

    Article  Google Scholar 

  • Ward JE, Wendell RE (1990) Approaches to sensitivity analysis in linear programming. Ann Oper Res 27(1):3–38

    Article  Google Scholar 

  • Wendell RE (1982) A preview of a tolerance approach to sensitivity analysis in linear programming. Discrete Math 38(1):121–124

    Article  Google Scholar 

  • Wendell RE (1984) Using bounds on the data in linear programming: the tolerance approach to sensitivity analysis. Math Program 29(3):304–322

    Article  Google Scholar 

  • Wendell RE (1985) The tolerance approach to sensitivity analysis in linear programming. Manag Sci 31(5):564–578

    Article  Google Scholar 

  • Wendell RE (1992) Sensitivity analysis revisited and extended. Decis Sci 23(5):1127–1142

    Article  Google Scholar 

  • Wendell RE (1997) Linear programming III: the tolerance approach. In: Gal T, Greenberg HJ (eds) Advances in sensitivity analysis and parametric programming. International series in operations research and management science, vol. 6. Kluwer Academic Publishers, London, pp 1–21

  • Wondolowski FR (1991) A generalization of Wendell’s tolerance approach to sensitivity analysis in linear programming. Decis Sci 22(4):792–811

    Article  Google Scholar 

  • Wright SJ (1997) Primal-dual interior-point methods. SIAM, Philadelphia

    Book  Google Scholar 

Download references

Acknowledgments

M. Hladík was supported by the project CE-ITI (GAP202/12/G061) of the Czech Science Foundation.

Author information

Authors and Affiliations

  1. Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran

    Amir Shahin

  2. Department of Industrial Management, Allameh Tabataba’i University, 14155-6476,  Tehran, Iran

    Payam Hanafizadeh

  3. Department of Applied Mathematics, Charles University in Prague, Malostranske nam. 25, 118 00,  Prague, Czech Republic

    Milan Hladík

Authors
  1. Amir Shahin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Payam Hanafizadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Milan Hladík
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Payam Hanafizadeh.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shahin, A., Hanafizadeh, P. & Hladík, M. Sensitivity analysis of linear programming in the presence of correlation among right-hand side parameters or objective function coefficients. Cent Eur J Oper Res 24, 563–593 (2016). https://doi.org/10.1007/s10100-014-0353-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-014-0353-8

Keywords

Search

Navigation