A self-validating method for solving linear programming problems with interval input data

Publikationstyp
Book part
Date Issued
1988
Sprache
English
Author(s)
Jansson, Christian  
Institut
Zuverlässiges Rechnen E-19  
TORE-URI
http://hdl.handle.net/11420/9505
First published in
Computing / Supplementum  
Number in series
6
Start Page
33
End Page
45
Citation
Scientific computation with automatic result verification. - Wien: 33-45 (1988)
Publisher DOI
10.1007/978-3-7091-6957-5_4
Publisher
Springer
ISBN
978-3-211-82063-6
978-3-7091-6957-5
A Self-Validating Method for Solving Linear Programming Problems with Interval input Data. Linear programming problems are very important in many practical applications. They are usually solved by the simplex method. The computational results are, in general, good approximations to the solution of the problem. However, in some cases the computed approximation may be wrong due to round-off and cancellation errors. In practice it occurs frequently that the input data of a linear programming problem are not known exactly but are afflicted with tolerances. In this case it has to be precisely defined what a “solution” to such a problem is. A sensitivity or postoptimality analysis is necessary.

In the following a method for linear programming problems with interval input data is described which computes guaranteed lower and upper bounds for all optimal vertices and the optimal value. The method controls rigorously all round-off errors and gives an automatic sensitivity analysis. As an example a diet problem is treated to demonstrate how the method in principle works. © Springer-Verlag/Wien 1988
Subjects
Linear Programming Problem
Basic Feasible Solution
Interval Vector
Interval Matrix
Optimal Vertex
DDC Class
004: Informatik
510: Mathematik