A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound. 相似文献
The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed. 相似文献
An implicit enumeration algorithm is developed to determine the set of efficient points in zero-one multiple criteria problems. The algorithm is specialized for the solution of a particular class of facility location problems. The procedure is complemented with the use of the utility function of the decision maker to identify a subset of efficient point candidates for the final selection. Computational results are provided and discussed. 相似文献
This paper describes the background of the Office of Management Budget Circular A-21, “Principles for Determining Costs Applicable to Grants, Contracts, and Other Agreements with Educational Institutions,” that describes the requirement for effort reporting. A sampling procedure is proposed as an alternative to 100% reporting. 相似文献
A single component system is assumed to progress through a finite number of increasingly bad levels of deterioration. The system with level i (0 ≤ i ≤ n) starts in state 0 when new, and is definitely replaced upon reaching the worthless state n. It is assumed that the transition times are directly monitored and the admissible class of strategies allows substitution of a new component only at such transition times. The durations in various deterioration levels are dependent random variables with exponential marginal distributions and a particularly convenient joint distribution. Strategies are chosen to maximize the average rewards per unit time. For some reward functions (with the reward rate depending on the state and the duration in this state) the knowledge of previous state duration provides useful information about the rate of deterioration. 相似文献
In this paper we precisely define the two types of simulations (terminating and steady-state) with regard to analysis of simulation output and discuss some common measures of performance for each type. In addition, we conclude, on the basis of discussions with many simulation practitioners, that both types of simulations are important in practice. This is contrary to the impression one gets from reading the simulation literature, where the steady-state case is almost exclusively considered. Although analyses of terminating simulations are considerably easier than are those of steady-state simulations, they have not received a careful treatment in the literature. We discuss and give empirical results for fixed sample size, relative width, and absolute width procedures that can be used for constructing confidence intervals for measures of performance in the terminating case. 相似文献
This note consists of developing a method for enforcing additional constraints to linear fractional programs and showing its usefulness in solving integer linear fractional programs. 相似文献
This paper obtains the uniformly minimum variance unbiased estimates of two indices of performance of a system which alternates between two states “up” or “down” in accordance with a Markov process. The two indices are (1) operational readiness, which measures the probability that the system will be up when needed; and (2) operational reliability, which measures the probability that the system will be up during the entire time of need. For the purpose of obtaining these estimates, two types of observations are considered: (a) those which reveal only the state of system at isolated time-points, and (b) those which continuously record the duration of the “up” and “down” times of the system. 相似文献