Characterizing Trade-Offs Between Sensitivity and Optimality: The Tolerance Approach

表征灵敏度和最优性之间的权衡：容忍方法

基本信息

批准号：
8615302
负责人：
Richard Wendell
金额：
$ 2.9万
依托单位：
University of Pittsburgh
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
1987
资助国家：
美国
起止时间：
1987-05-15 至 1988-10-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=8615302&HistoricalAwards=false
关键词：
Characterizing Trade Offs Between Sensitivity

项目摘要

The primary focus of this research is on linear programming sensitivity analysis. The approach being proposed is called the "tolerance approach" and the basic idea is to be able to tell the decision maker that a given solution will be optimal as long as each objective function coefficient is within a certain maximum tolerance percentage of its nominal value. The approach can exploit a priori information on ranges of variability of the coefficients to yield larger maximum tolerance percentages. This research will generalize the tolerance approach to characterize trade-offs between optimality and sensitivity of a solution. More specifically, the project will address the following points: to characterize trade-offs between optimality and sensitivity of a solution and to develop efficient algorithms to calculate such trade-offs for general linear programming problems; to streamline these results to network problems; and to investigate possible extensions of the results to nonlinear, integer, and multiple objective programming problems. This research concerns the trade-offs between sensitivity and optimality of a solution in linear programming. Both theoretical justification and efficient algorithms will be derived to characterize and compute the trade-offs. The results will be specialized for network problems and possible extensions to multiple objective programming problems will be investigated. It is expected that the research will yield valuable information which can be used by decision-makers in implementing solutions of large optimization problems.

这项研究的主要重点是线性编程灵敏度分析。提出的方法称为“公差方法”，基本思想是能够告诉决策者，只要每个目标函数系数在其名义值的一定最大公差百分比之内，则给定解决方案将是最佳的。该方法可以利用有关系数可变性范围的先验信息，以产生更大的最大公差百分比。这项研究将概括耐受性方法，以表征解决方案的最优性和灵敏度之间的权衡。更具体地说，该项目将解决以下几点：要表征解决方案的最优性和灵敏度之间的权衡，并开发有效的算法来计算一般线性编程问题的此类权衡；简化这些结果为网络问题；并研究结果可能扩展到非线性，整数和多个客观编程问题。这项研究涉及线性编程中解决方案的敏感性和最佳性之间的权衡。理论上的理由和有效算法都将得出以表征和计算权衡。结果将专门用于网络问题，并将研究对多个客观编程问题的可能扩展。预计该研究将产生有价值的信息，决策者可以使用这些信息来实施大型优化问题的解决方案。