An application of linear programming to contingency planning: A tactical airlift system analysis

A linear programming application for the selection of aircraft for a tactical airlift fleet is described.     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.     

On computing the expected discounted return in a markov chain

The discounted return associated with a finite state Markov chain X₁, X₂… is given by g(X₁)+ αg(X₂) + α²g(X₃) + …, where g(x) represents the immediate return from state x. Knowing the transition matrix of the chain, it is desired to compute the expected discounted return (present worth) given the initial state. This type of problem arises in inventory theory, dynamic programming, and elsewhere. Usually the solution is approximated by solving the system of linear equations characterizing the expected return. These equations can be solved by a variety of well-known methods. This paper describes yet another method, which is a slight modification of the classical iterative scheme. The method gives sequences of upper and lower bounds which converge mono-tonely to the solution. Hence, the method is relatively free of error control problems. Computational experiments were conducted which suggest that for problems with a large number of states, the method is quite efficient. The amount of computation required to obtain the solution increases much slower with an increase in the number of states, N, than with the conventional methods. In fact, computational time is more nearly proportional to N², than to N³.     

A note on the optimal scheduling of two parallel processors

The problem of minimizing mean flow time of two parallel processors is discussed. Prior results are briefly reviewed. A dynamic programming algorithm is presented which minimizes mean flow time for a set of n preordered jobs on two nonequivalent parallel processors. The algorithm is illustrated with an example problem. The computational experience is presented which illustrates the efficiency of the algorithm.     

Adjacent vertices on transportation polytopes

To solve linear fixed charge problems with Murty's vertex ranking algorithm, one uses a simplex algorithm and a procedure to determine the vertices adjacent to a given vertex. In solving fixed charge transportation problems, the simplex algorithm simplifies to the stepping-stone algorithm. To find adjacent vertices on transportation polytopes, we present a procedure which is a simplification of a more general procedure for arbitrary polytopes.     

A theory of ideal linear weights for heterogeneous combat forces

Detailed combat simulations can produce effectiveness tables which measure the effectiveness of each weapon class on one side of an engagement, battle, or campaign to each weapon class on the other. Effectiveness tables may also be constructed in other ways This paper assumes that effectiveness tables are given and shows how to construct from them a system of weapon weights each of which is a weighted average of the effects of a given weapon against each of the enemy's weapons. These weights utilize the Perron- Frobenius theory of eigenvectors of nonnegative matrices. Methods of calculation are discussed and some interpretations are given for both the irreducible and reducible cases.     

A new approach for dealing with the startup problem in discrete event simulation

This article proposes a practical, data-based statistical procedure which can be used to reduce or remove bias owing to artificial startup conditions in simulations aimed at estimating steady-state means. We discuss results of experiments designed to choose good parameter values for this procedure, and present results of extensive testing of the procedure on a variety of stochastic models for which partial analytical results are available. The article closes with two illustrations of the application of the procedure to more complex statistical problems which are more representative of the kinds of purposes for which real-world steady-state simulation studies might be undertaken.