Optimal value range in interval linear programming. (English) Zbl 1173.90469
Summary: We deal with the linear programming problem in which input data can vary in some given real compact intervals. The aim is to compute the exact range of the optimal value function. We present a general approach to the situation the feasible set is described by an arbitrary linear interval system. Moreover, certain dependencies between the constraint matrix coefficients can be involved. As long as we are able to characterize the primal and dual solution set (the set of all possible primal and dual feasible solutions, respectively), the bounds of the objective function result from two nonlinear programming problems. We demonstrate our approach on various cases of the interval linear programming problem (with and without dependencies).
MSC:
| 90C05 | Linear programming |
Keywords:
linear interval systems; linear programming; optimal value range; interval matrix; dependenceReferences:
| [1] | Alefeld G., Herzberger J. (1983) Introduction to interval computations. Academic Press, London · Zbl 0552.65041 |
| [2] | Alefeld G., Kreinovich V., Mayer G. (1998) The shape of the solution set for systems of interval linear equations with dependent coefficients. Mathematische Nachrichten 192: 23–36 · Zbl 0907.15003 · doi:10.1002/mana.19981920103 |
| [3] | Alefeld, G., Kreinovich, V., & Mayer, G. (2003a). On symmetric solution sets. In J. Herzberger(ed.), Inclusion methods for nonlinear problems. With applications in engineering, economics and physics. Proceedings of the international GAMM-workshop, Munich and Oberschleissheim, December 15–18, 2000. Wien, Springer, Comput. Suppl., 16, 1–22. |
| [4] | Alefeld G., Kreinovich V., Mayer G. (2003b) On the solution sets of particular classes of linear interval systems. Journal of Computational and Applied Mathematics 152(1–2): 1–15 · doi:10.1016/S0377-0427(02)00693-3 |
| [5] | Chanas S., Kuchta D. (1996) Multiobjective programming in optimization of interval objective functions – a generalized approach. European Journal of Operational Research 94(3): 594–598 · Zbl 1006.90506 · doi:10.1016/0377-2217(95)00055-0 |
| [6] | Chinneck J.W., Ramadan K. (2000) Linear programming with interval coefficients. Journal of the Operational Research Society 51(2): 209–220 · Zbl 1107.90420 |
| [7] | Fiedler M., Nedoma J., Ramik J., Rohn J., Zimmermann K. (2006) Linear optimization problems with inexact data. Springer–Verlag, New York · Zbl 1106.90051 |
| [8] | Gerlach W. (1981) Zur Lösung linearer Ungleichungssysteme bei Störung der rechten Seite und der Koeffizientenmatrix. Mathematische Operationsforschung und Statistik, Series Optimization 12: 41–43 · Zbl 0454.90078 |
| [9] | Hladík M. (2007) Solution set characterization of linear interval systems with a specific dependence structure. Reliable Computing 13(4): 361–374 · Zbl 1127.65024 · doi:10.1007/s11155-007-9033-x |
| [10] | Inuiguchi M., Ramik J., Tanino T., Vlach M. (2003) Satisficing solutions and duality in interval and fuzzy linear programming. Fuzzy Sets and Systems 135(1): 151–177 · Zbl 1026.90105 · doi:10.1016/S0165-0114(02)00253-1 |
| [11] | Jansson C., Rump S.M. (1991) Rigorous solution of linear programming problems with uncertain data. Zeitschrift für Operations Research 35(2): 87–111 · Zbl 0735.90043 |
| [12] | Kolev L.V. (2004) Solving linear systems whose elements are nonlinear functions of interval parameters. Numerical Algorithms 37: 199–212 · Zbl 1076.65028 · doi:10.1023/B:NUMA.0000049467.43979.94 |
| [13] | Machost, B. (1970). Numerische Behandlung des Simplexverfahrens mit intervallanalytischen Methoden, Berichte der Gesellschaft für Mathematik und Datenverarbeitung, Nr. 30, Bonn. · Zbl 0204.49404 |
| [14] | Mráz F. (1998) Calculating the exact bounds of optimal values in LP with interval coefficients. Annals of Operations Research 81: 51–62 · Zbl 0908.90188 · doi:10.1023/A:1018985914065 |
| [15] | Oettli W., Prager W. (1964) Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numerische Mathematik 6: 405–409 · Zbl 0133.08603 · doi:10.1007/BF01386090 |
| [16] | Popova E. (2001) On the solution of parameterised linear systems. In: Kraemer W., Gudenberg J. (eds) Scientific computing, validated numerics, interval methods. Kluwer Academic, Boston, pp 127–138 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
