共查询到20条相似文献,搜索用时 31 毫秒
1.
We consider the problem of finding maximal flows with respect to capacities which are linear functions of a parametert [0,T]. Since this problem is a special case of a parametric linear program the classichorizontal approach can be applied in which optimal solutions are computed for successive subintervals of [0,T]. We discuss an alternative algorithm which approximates in each iteration the optimal solution for allt [0,T]. Thisvertical algorithm is a labeling type algorithm where the flow variables are piecewise linear functions. Flow augmentations are done alongconditional flow augmenting paths which can be found by modified path algorithms. The vertical algorithm can be used to solve the parametric flow problem optimally as well as to compute a good approximation for allt if the computation of the optimal solution turns out to be too time consuming.Partially supported by NSF Grants ECS-8412926 and INT-8521433, and NATO Grant RG 85/0240. 相似文献
2.
There is a classical technique for determining the equilibrium probabilities ofM/G/1 type Markov chains. After transforming the equilibrium balance equations of the chain, one obtains an equivalent system of equations in analytic functions to be solved. This method requires finding all singularities of a given matrix function in the unit disk and then using them to obtain a set of linear equations in the finite number of unknown boundary probabilities. The remaining probabilities and other measures of interest are then computed from the boundary probabilities. Under certain technical assumptions, the linear independence of the resulting equations is established by a direct argument involving only elementary results from matrix theory and complex analysis. Simple conditions for the ergodicity and nonergodicity of the chain are also given. 相似文献
3.
Richard F. Deckro James G. Morris 《The Journal of the Operational Research Society》1980,31(12):1085-1093
The objective is to compute equilibrium interregional trade flows in relation to approximately linear supply and demand curves for a single commodity. There are n regions on a network characterized by approximately linear interregional transportation costs. Quadratic programming approaches can be greatly simplified by exploiting the special structure of the problem. This paper shows how the reduced quadratic program can then be partitioned using Benders decomposition. The computation then involves solving relatively small transportation problems and quadratic programming problems. Numerical experiments show the method to be effective in reducing computational requirements. 相似文献
4.
A spatial price equilibrium problem is modeled which allows piecewise linear convex flow costs, and a capacity limit on the trade flow between each supply/demand pair of regions. Alternatively, the model determines the locations of intermediate distribution centers in a market economy composed of separate regions, each with approximately linear supply and demand functions. Equilibrium prices, regional supply and demand quantities, and commodity flows are determined endogenously. The model has a quadratic programming formulation which is then reduced by exploiting the structure. The reduced model is particularly well suited to solution using successive over-relaxation. 相似文献
5.
Attila Bernáth Tamás Király Erika Renáta Kovács Gergely Mádi-Nagy Gyula Pap Júlia Pap Jácint Szabó László Végh 《Central European Journal of Operations Research》2013,21(4):699-712
We investigate the multiplayer multicommodity flow problem: several players have different networks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value. We show that the social optimum can be computed by linear programming, and we propose algorithms based on column generation and Lagrangian relaxation. In contrast, we prove that it is hard to decide if an equilibrium solution exists, although some natural conditions guarantee its existence. 相似文献
6.
We study the heat, linear Schrödinger (LS), and linear KdV equations in the domain l(t) < x < ∞ , 0 < t < T , with prescribed initial and boundary conditions and with l(t) a given differentiable function. For the first two equations, we show that the unknown Neumann or Dirichlet boundary value can be computed as the solution of a linear Volterra integral equation with an explicit weakly singular kernel. This integral equation can be derived from the formal Fourier integral representation of the solution. For the linear KdV equation we show that the two unknown boundary values can be computed as the solution of a system of linear Volterra integral equations with explicit weakly singular kernels. The derivation in this case makes crucial use of analyticity and certain invariance properties in the complex spectral plane. The above Volterra equations are shown to admit a unique solution. 相似文献
7.
A huge body of empirical and theoretical literature has emerged on the relationship between foreign exchange (FX) uncertainty and international trade. Empirical findings about the impact of FX uncertainty on trade figures are at best weak and often ambiguous with respect to its direction. Almost all empirical contributions assume and estimate a linear relationship. Possible nonlinearity or state dependence of causal links between FX uncertainty and trade has been mostly ignored yet. In addition, widely used regression models have not been evaluated in terms of ex‐ante forecasting. In this paper we analyse the impact of FX uncertainty on sectoral categories of multilateral exports and imports for 15 industrialized economies. We particularly provide a comparison of linear and non‐linear models with respect to ex‐ante forecasting. In terms of average ranks of absolute forecast errors non‐linear models outperform both, a common linear model and some specification building on the assumption that FX uncertainty and trade growth are uncorrelated. Our results support the view that the relationship of interest might be non‐linear and, moreover, lacks of homogeneity across countries, economic sectors and when contrasting imports vs exports. Copyright © 2005 John Wiley & Sons, Ltd. 相似文献
8.
An algorithm based on a sequence of linear complementarity problems applied to a walrasian equilibrium model: An example 总被引:3,自引:0,他引:3
Lars Mathiesen 《Mathematical Programming》1987,37(1):1-18
The Walrasian equilibrium problem is cast as a complementarity problem, and its solution is computed by solving a sequence
of linear complementarity problems (SLCP). Earlier numerical experiments have demonstrated the computational efficiency of
this approach. So far, however, there exist few relevant theoretical results that characterize the performance of this algorithm.
In the context of a simple example of a Walrasian equilibrium model, we study the iterates of the SLCP algorithm. We show
that a particular LCP of this process may have no, one or more complementary solutions. Other LCPs may have both homogeneous
and complementary solutions. These features complicate the proof of convergence for the general case.
For this particular example, however, we are able to show that Lemke's algorithm computes a solution to an LCP if one exists,and that the iterative process converges globally. 相似文献
9.
In this paper an autonomous SIRS epidemic model with time delay is studied. The basic reproductive number R0 is obtained which determines whether the disease is extinct or not. When the basic reproductive number is greater than 1, it is proved that the disease is permanent in the population, and explicit formula are obtained by which the eventual lower bound of the fraction of infectious individuals can be computed. Throughout the total paper, we mainly use the technique of Lyapunov functional to establish the global stability of the infection-free equilibrium and the local stability of the endemic equilibrium but need another sufficient condition. 相似文献
10.
A numerical method based on a second-order accurate Godunov-type scheme is described for solving the shallow water equations on unstructured triangular-quadrilateral meshes. The bottom surface is represented by a piecewise linear approximation with discontinuities, and a new approximate Riemann solver is used to treat the bottom jump. Flows with a dry sloping bottom are computed using a simplified method that admits negative depths and preserves the liquid mass and the equilibrium state. The accuracy and performance of the approach proposed for shallow water flow simulation are illustrated by computing one- and two-dimensional problems. 相似文献
11.
Self-adaptive projection-based prediction-correction method for constrained variational inequalities
The problems studied in this paper are a class of monotone constrained variational inequalities VI (S, f) in which S is a convex set with some linear constraints. By introducing Lagrangian multipliers to the linear constraints, such problems
can be solved by some projection type prediction-correction methods. We focus on the mapping f that does not have an explicit form. Therefore, only its function values can be employed in the numerical methods. The number
of iterations is significantly dependent on a parameter that balances the primal and dual variables. To overcome potential
difficulties, we present a self-adaptive prediction-correction method that adjusts the scalar parameter automatically. Convergence
of the proposed method is proved under mild conditions. Preliminary numerical experiments including some traffic equilibrium
problems indicate the effectiveness of the proposed methods. 相似文献
12.
Richard C. Grinold 《Mathematical Programming》1978,15(1):26-35
An equilibrium model of a manpower system is developed based on the notion of a career flow. Institutional constraints and measures of system performance are linear functions of the career flow. A typical optimal design problem is formulated and a solution procedure is developed. The optimization problem is a generalized linear program in which columns are generated by solving a shortest path problem. Upper and lower bounds on the optimal value function can be developed at each stage of the calculations.This research was supported by ONR grant N00014-75-C-0619. 相似文献
13.
Yuriy S. Volkov 《Central European Journal of Mathematics》2012,10(1):352-356
We study the problem of interpolation by a complete spline of 2n − 1 degree given in B-spline representation. Explicit formulas for the first nand the last ncoefficients of B-spline decomposition are found. It is shown that other B-spline coefficients can be computed as a solution of a banded system of an equitype linear equations. 相似文献
14.
Å. Björck 《BIT Numerical Mathematics》1991,31(2):237-244
Perturbation bounds for the linear least squares problem min
x
Ax –b2 corresponding tocomponent-wise perturbations in the data are derived. These bounds can be computed using a method of Hager and are often much better than the bounds derived from the standard perturbation analysis. In particular this is true for problems where the rows ofA are of widely different magnitudes. Generalizing a result by Oettli and Prager, we can use the bounds to compute a posteriori error bounds for computed least squares solutions. 相似文献
15.
Xing Cai Bjørn Fredrik Nielsen Aslak Tveito 《Numerical Linear Algebra with Applications》2007,14(5):459-467
We discuss the efficiency of the conjugate gradient (CG) method for solving a sequence of linear systems; Aun+1 = un, where A is assumed to be sparse, symmetric, and positive definite. We show that under certain conditions the Krylov subspace, which is generated when solving the first linear system Au1 = u0, contains the solutions {un} for subsequent time steps. The solutions of these equations can therefore be computed by a straightforward projection of the right‐hand side onto the already computed Krylov subspace. Our theoretical considerations are illustrated by numerical experiments that compare this method with the order‐optimal scheme obtained by applying the multigrid method as a preconditioner for the CG‐method at each time step. Copyright © 2007 John Wiley & Sons, Ltd. 相似文献
16.
Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be
used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct
from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial
linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation
with various decomposition methods to yield further improvement in computed bounds. In this paper, we describe a framework
within which most of these methods can be viewed from a common theoretical perspective. We then discuss how the framework
can be extended to obtain a decomposition-based separation technique we call decompose and cut. As a by-product, we describe how these methods can take advantage of the fact that solutions with known structure, such
as those to a given relaxation, can frequently be separated much more easily than arbitrary real vectors. 相似文献
17.
Sufficient conditions are given for the asymptotic constancy of the solutions of a linear system of difference equations with
delays. Moreover, it is shown that the limits of the solutions, as t→∞, can be computed in terms of the initial function and a special matrix solution of the corresponding adjoint equation. 相似文献
18.
Horst W. Hamacher 《Annals of Operations Research》1995,57(1):65-72
It is shown that the problem of finding theK best solutions of a linear integer network flow problem can be solved by a polynomial time algorithm. This algorithm can be used in order to solve a multiple-criteria network flow problem which minimizes the maximum ofQ objectives.Partially supported by grants of the Deutsche Forschungsgemeinschaft and the HC&M programme of the European Union under ERBCHRXCT 930087. 相似文献
19.
Walter Gautschi 《Numerical Algorithms》2000,25(1-4):213-222
Currently, the method of choice for computing the (n+2)-point Gauss–Lobatto quadrature rule for any measure of integration is to first generate the Jacobi matrix of order n+2 for the measure at hand, then modify the three elements at the right lower corner of the matrix in a manner proposed in 1973 by Golub, and finally compute the eigenvalues and first components of the respective eigenvectors to produce the nodes and weights of the quadrature rule. In general, this works quite well, but when n becomes large, underflow problems cause the method to fail, at least in the software implementation provided by us in 1994. The reason is the singularity (caused by underflow) of the 2×2 system of linear equations that is used to compute the modified matrix elements. It is shown here that in the case of arbitrary Jacobi measures, these elements can be computed directly, without solving a linear system, thus allowing the method to function for essentially unrestricted values of n. In addition, it is shown that all weights of the quadrature rule can also be computed explicitly, which not only obviates the need to compute eigenvectors, but also provides better accuracy. Numerical comparisons are made to illustrate the effectiveness of this new implementation of the method. 相似文献
20.
主要研究简单网络流对策中相对N-核的算法.当网络中最大流值等于1时,证明相对N-核与对策的核心相同,不一定是单点集;而当网络中最大流值大于1时,利用Kopelowitz's序列线性规划方法和线性规划对偶理论,证明相对N-核与N-核相同(同为单点集),并且可在局中人个数的多项式时间内得到求解. 相似文献