Computing bounds for the optimal value in linear programming

Markku Kallio

Naval Research Logistics Quarterly, 1977, vol. 24, issue 2, 301-308

Abstract: Consider a standard linear programming problem and suppose that there are bounds available for the decision variables such that those bounds are not violated at an optimal solution of the problem (but they may be violated at some other feasible solutions of the problem). Thus, these bounds may not appear explicitly in the problem, but rather they may have been derived from some prior knowledge about an optimal solution or from the explicit constraints of the problem. In this paper, the bounds on variables are used to compute bounds on the optimal value when the problem is being solved by the simplex method. The latter bounds may then be used as a termination criteria for the simples iterations for the purpose of finding a “sufficiently good” near optimal solution. The bounds proposed are such that the computational effort in evaluating them is insignificant compared to that involved in the simplex iterations. A numerical example is given to demonstrate their performance.

Date: 1977
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/nav.3800240209

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:24:y:1977:i:2:p:301-308

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().