共查询到20条相似文献,搜索用时 15 毫秒
1.
We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions. 相似文献
2.
In this paper, we first extend the dual simplex method to a type of fuzzy linear programming problem involving symmetric trapezoidal fuzzy numbers. The results obtained lead to a solution for fuzzy linear programming problems that does not require their conversion into crisp linear programming problems. We then study the ranges of values we can achieve so that when changes to the data of the problem are introduced, the fuzzy optimal solution remains invariant. Finally, we obtain the optimal value function with fuzzy coefficients in each case, and the results are described by means of numerical examples. 相似文献
3.
Richard E. Wendell 《Mathematical Programming》1984,29(3):304-322
In contrast to traditional sensitivity analysis in linear programming, the tolerance approach considers simultaneous and independent
variations in a number of parameters. A primary focus of this approach is to determine a maximum tolerance percentage for
selected right-hand-side terms in which the same basis is optimal as long as each term is accurate to within that percentage
of its estimated value. Similarly, the approach yields a maximum tolerance percentage for selected objective function coefficients.
This paper shows how the tolerance approach can exploit information on the range of possible values over which terms and coefficients
can vary to yield larger maximum tolerance percentages. 相似文献
4.
Shizuhiko Nishisato 《Annals of Operations Research》1995,55(2):345-359
Dual scaling can be looked at as several different optimization problems, which suggests a number of optimal properties inherent in this scaling method. This study identifies some of its old and new aspects, providing a brief, but comprehensive, characterization of dual scaling. It is important to be aware of its limitations as well as possibilities, particularly because the method is deterministic or mathematical rather than probabilistic or statistical, hence rendering it a greater risk of misapplication. Seven key characteristics of dual scaling are identified and discussed. 相似文献
5.
É. Komáromi 《Journal of Optimization Theory and Applications》1992,75(3):587-602
We present two pairs of dually related probabilistic constrained problems as extensions of the linear programming duality concept. In the first pair, a bilinear function appears in the objectives and each objective directly depends on the feasibility set of the other problem, as in the game theoretical formulation of dual linear programs. In the second pair, we reformulate the objectives and eliminate their direct dependence on the feasibility set of the other problem. We develop conditions under which the dually related problems have no duality gap and conditions under which the two pairs of problems are equivalent as far as their optimality sets are concerned. 相似文献
6.
In exploratory data analysis, handling of missing responses requires special considerations because of the absence of a model for them. This study investigates effects of missing responses on dual scaling results, in particular a practical decision rule when to and not to impute for missing responses. More specifically, three questions are asked: when to discard a subject, when to exclude a variable, and when to stop data analysis entirely. The decision rule is based on the concept of substantial discrepancy in the scaling outcome between the best and worst imputations for missing responses. This problem is discussed in the context of the current knowledge on missing responses in data analysis. 相似文献
7.
Dr. H. Isermann 《Mathematical Methods of Operations Research》1978,22(1):33-41
Summary This paper is a contribution to the theory of multiple objective linear programming. Existence and duality properties for multiple objective linear programs are developed which contain the fundamental existence and duality results of linear programming as special cases. Several implications of the duality results will be indicated.
Zusammenfassung In diesem Beitrag werden einige Existenz- und Dualitätsaussagen für lineare Programme mit mehreren Zielfunktionen (Vektoroptimierungsprobleme) vorgestellt. Es wird gezeigt, daß diese Aussagen die Existenz- und Dualitätsaussagen der linearen Programmierung als Spezialfälle enthalten.相似文献
8.
Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints
This note presents an efficient method for the routine solution of the subproblem associated with the Lagrangian dual of discrete programming problems having separable non-linear objective function and linear constraints. An additional advantage for subgradient methods is described. 相似文献
9.
A continuing priority in sensitivity and parametric analysis is to develop approaches that provide useful information, that are easy for a decision-maker to use, and that are computationally practical. Herein we review approaches to sensitivity analysis in linear programming and discuss how they meet the above needs. Special emphasis is given to sensitivity analysis of the objective function coefficients.The second author gratefully acknowledges financial support from the National Science Foundation under grant ECS-8615302. 相似文献
10.
ABSTRACTLocal sensitivity information is obtained for KKT points of parametric NLPs that may exhibit active set changes under parametric perturbations; under appropriate regularity conditions, computationally relevant generalized derivatives of primal and dual variable solutions of parametric NLPs are calculated. Ralph and Dempe obtained directional derivatives of solutions of parametric NLPs exhibiting active set changes from the unique solution of an auxiliary quadratic program. This article uses lexicographic directional derivatives, a newly developed tool in nonsmooth analysis, to generalize the classical NLP sensitivity analysis theory of Ralph and Dempe. By viewing said auxiliary quadratic program as a parametric NLP, the results of Ralph and Dempe are applied to furnish a sequence of coupled QPs, whose unique solutions yield generalized derivative information for the NLP. A practically implementable algorithm is provided. The theory developed here is motivated by widespread applications of nonlinear programming sensitivity analysis, such as in dynamic control and optimization problems. 相似文献
11.
Finite-dimensional linear programs satisfy strong duality (SD) and have the “dual pricing” (DP) property. The DP property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correctly “prices” the perturbation by computing the exact change in the optimal objective function value. These properties may fail in semi-infinite linear programming where the constraint vector space is infinite dimensional. Unlike the finite-dimensional case, in semi-infinite linear programs the constraint vector space is a modeling choice. We show that, for a sufficiently restricted vector space, both SD and DP always hold, at the cost of restricting the perturbations to that space. The main goal of the paper is to extend this restricted space to the largest possible constraint space where SD and DP hold. Once SD or DP fail for a given constraint space, then these conditions fail for all larger constraint spaces. We give sufficient conditions for when SD and DP hold in an extended constraint space. Our results require the use of linear functionals that are singular or purely finitely additive and thus not representable as finite support vectors. We use the extension of the Fourier–Motzkin elimination procedure to semi-infinite linear systems to understand these linear functionals. 相似文献
12.
W. Oettli 《Mathematical Programming》1972,3(1):302-311
An iterative method for dual linear programming problems is described, and its rate of convergence is established.On leave of absence from IBM Research Laboratory, Ruschlikon, Switzerland. 相似文献
13.
14.
Charles Blair 《Annals of Operations Research》1992,34(1):13-19
We show that (L+1)-level linear programs are as difficult as levelL of the polynomial-time hierarchy, even if one only considers problems with unique optimal solutions.Dedicated to Robert Jeroslow (1942–1988) 相似文献
15.
A linear fractional program is shown, under certain restrictions, to have a fractional linear program as its dual. 相似文献
16.
Lakshman S Thakur 《Journal of Mathematical Analysis and Applications》1980,75(2):486-494
Computable lower and upper bounds on the optimal and dual optimal solutions of a nonlinear, convex separable program are obtained from its piecewise linear approximation. They provide traditional error and sensitivity measures and are shown to be attainable for some problems. In addition, the bounds on the solution can be used to develop an efficient solution approach for such programs, and the dual bounds enable us to determine a subdivision interval which insures the objective function accuracy of a prespecified level. A generalization of the bounds to certain separable, but nonconvex, programs is given and some numerical examples are included. 相似文献
17.
Alexander Shapiro 《Mathematical Programming》1985,33(3):280-299
In this paper we study second-order differential properties of an optimal-value function(x). It is shown that under certain conditions(x) possesses second-order directional derivatives, which can be calculated by solving corresponding quadratic programs. Also upper and lower bounds on these derivatives are introduced under weaker assumptions. In particular we show that the second-order directional derivative is infinite if the corresponding quadratic program is unbounded. Finally sensitivity results are applied to investigate asymptotics of estimators in parametrized nonlinear programs. 相似文献
18.
In this paper, we apply the tolerance approach proposed by Wendell for sensitivity analysis in linear programs to study sensitivity analysis in linear complementarity problems. In the tolerance approach, we find the range or the maximum tolerance within which the coefficients of the right-hand side of the problem can vary simultaneously and independently such that the solution of the original and the perturbed problems have the same index set of nonzero elements.The work of the first author was completed while he was at Virginia Commonwealth University, Richmond, Virginia. 相似文献
19.
Michael B. Freimer Jeffrey T. Linderoth Douglas J. Thomas 《Computational Optimization and Applications》2012,51(1):51-75
Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the
problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function
at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator
is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for
minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative
sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus
the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and
variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally
investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at
reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and
the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1–19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely
to reduce bias. 相似文献
20.
Alireza Ghaffari-Hadigheh Habib Ghaffari-Hadigheh Tamás Terlaky 《Central European Journal of Operations Research》2008,16(2):215-238
In bi-parametric linear optimization (LO), perturbation occurs in both the right-hand-side and the objective function data
with different parameters. In this paper, the bi-parametric LO problem is considered and we are interested in identifying
the regions where the optimal partitions are invariant. These regions are referred to as invariancy regions. It is proved
that invariancy regions are separated by vertical and horizontal lines and generate a mesh-like area. It is proved that the
boundaries of these regions can be identified in polynomial time. The behavior of the optimal value function on these regions
is investigated too. 相似文献