Search

The article presents a solution to a large-scale traveling-salesman problem which shows that a certain tour of 49 cities, one in each of the 48 states and Washington, D.C., has the shortest road distance. A brief history of the problem is provided. A city in each state including the District of Columbia was selected to try the optimal path method on a large problem. The devices in obtaining solutions include the use of undirected tours, the imposition of linear conditions to characterize the tours, the speeding up of the iterative process and the use of a combinatorial approach.

A supplement to the article "Smooth Patterns of Production," written by A.J. Hoffman and Walter Jacobs, which appeared in the first volume of the periodical "Management Science" published in 1954, is provided. The author suggests a method of interpreting the mathematical theorem used by Hoffman and Jacob to measure the cost of speeding up industrial product production. It is suggested that the conclusions reached in the initial article depend on the cumulative delivery requirement variable. The author also critiques an algorithm included in theorem 4, which deals with product management and scheduling and is also discussed in the aforementioned article by Hoffman and Jacobs.

The article discusses the use of linear programming in U.S. industry. Three aspects of the application of linear programming are presented, including model building, mathematics, and computation. Many real-world industry cases have been related to finding the most economical way of transporting materials between various sources and destinations, and have been solved by special algorithms. In the mathematics of linear programming there are four main areas of research, including computational techniques that take advantage of special features of problems, methods of performing sensitivity analyses for the coefficients of the problem, methods that relate to dynamic problems, and stochastic techniques for handling uncertainty.

The article discusses the "transportation problem," which is a class of linear programming problems involving the selection of the most economical shipping routes for a commodity from given sources to given destinations. The transportation problem has been typically approached either as a specialized type of linear programming problem or as a method of representation of some combinatorial problems. The author asserts that a third method is possible, which is applicable for the determination of optimum linked paths over a series of points, or "transhipment." The transhipment problem is more complex than shipping an item from one point to another, because points can now be both origins and destinations. The question resembles a combinatorial problem but may be solved by linear programming.

In this paper, it is shown that the "caterer" problem, a problem in mathematical economics and logistics which has been discussed by Jacobs, Gaddum, Hoffman and Sokolowsky, and Prager, can be reduced to the problem of determining the maximum of the linear form Ln = ∑I=1nv1, subject to a series of constraints of the form V1 ≦ b1, v1 +v2 ≦ b2, v1 + v2 +v3 ≦ b2, ߪ, v1 + v2 + … + vK ≦ bK, v2 + v3 + … + vK+1 ≦ bK+1, …, vb-h+1 + … + Vn ≦ bn, 0 ≦ rI, I = 1, 2, … , n, under an assumption concerning the nonaccumulation of dirty laundry. This maximization problem is solved explicitly, using the functional equation technique of dynamic programming. [ABSTRACT FROM AUTHOR]

The article reports on the computational solution of linear programming equations involving almost-block-diagonal matrices. The author focuses on dynamic programming methods that can be used to solve weakly coupled and multi-stage economic systems. He suggests that most economic and industrial problems can be reduced to the problem of maximizing the linear form. It is suggested that finding the mathematical solutions to multi-dimensional problems is important because of the wide range of values of the solution's parameters. Dantzig's simplex algorithm enables programming problems of this type to be solved using digital computers.

A concave programming problem is presented, which is a model for an operations-research problem arising in both military and commercial applications It is amenable to linear programming methods and can he solved by a sequence of applications of the simplex algorithm [ABSTRACT FROM AUTHOR]

While the linear programming concept and the formulation of a specific model have value in themselves, the technique would fall short of its promise without efficient computing procedures. The simplex method has proved to be the most successful approach but it still leaves a wide range for detailed algorithms. At first, the method was applied by hand or with the aid of punched-card equipment. With the advent of internally-stored-program computers, automatic routines were designed. However, the early machines were adequate only for small problems and the original simplex method was not efficient for many LP models. A program of development was started at RAND to provide better computing techniques. Using first the IBM Model II CEC, then the 701 and now the 704, general LP routines of considerable power and flexibility have been developed. Future improvements will probably be possible only from higher level abstractions which take advantage of structure in the model matrix or which produce more efficient forms of the inverse of a sparse matrix. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to illustrate some applications of the functional equation technique of the theory of dynamic programming to a general class of problems arising in the study of networks, particularly those arising in transportation theory. [ABSTRACT FROM AUTHOR]

A summary of the important variations on the simplex method is presented, with an emphasis placed on the connection between these techniques, the revised simplex method, and the dual theorem. Only elementary matrix algebra is employed to enable the nonmathematician to utilize the various algorithms. Specifically, the dual simplex algorithm, parametric programming, and techniques for additional and secondary constraints, and for upper bounded variables are discussed. [ABSTRACT FROM AUTHOR]