Suchergebnisse

AbstractA FORTRAN II transportation code, using Kuhn's Hungarian Method, was reported upon at the RAND Symposium on Mathematical Programming in March 1959. The algorithm was based upon a proof of the König‐Egervary theorem, presented by the present author at the 1958 Symposium on Combinatorial Problems sponsored by the American Mathematical Society. The code was entirely rewritten (in FORTRAN II), during the 1959 IBM Summer Institute on Combinatorial Problems, and several problems were run at the IBM Research Center to obtain data regarding computing times and frequencies of various internal loops. A CLOCK Subroutine yields readings, in hundredths of minutes, for each time through selected portions of the computing run. The version reported upon at RAND solved a 29 × 116 pseudorandom transportation problem in 8.01 min, as compared with 3.17 min using the fastest competing code (SHARE 464) then available. The present version solved this same problem in 2.87 min, and another 29 × 116 problem in 1.89 min. This paper presents the algorithm and reports upon computing experience.

AbstractThis note describes the construction of an example in which the usual iterative method for linear programming may fail unless special techniques for overcoming degeneracy are used.

AbstractIf a linear programming problem involves two objective functions, it is desirable to learn all solutions depending on the relative weight attached to the two functions. This paper presents details of an algorithm which finds these solutions systematically.

AbstractA computationally simple method for approximating the optimal solution to transportation problems is described. Also, a method to deal with fixed charges is proposed. The computational algorithms have been designed primarily to handle very large numbers of transportation problems each involving a small number of origins and destinations as is frequently the situation in the Navy supply system. The results of empirical tests of the effectiveness of the methods are summarized.

AbstractThis article is concerned with von Neumann's algorithm for solving a matrix game. Some of the numerical comparisons, made between this algorithm and three others from the literature, have been abstracted for discussion. In general, the performance of von Neumann's algorithm is inferior to other methods for solving matrix games; Dantzig's Simplex Method converges in fewer iterations; and Brown's Fictitious Play requires a much simpler arithmetic process and fewer iterations for a similar convergence.

AbstractAn algorithm is presented for solving the transportation problem when the shipping cost over each route is a convex function of the number of units shipped by this route.The algorithm can also be used when the shipping costs are linear, whether or not there are capacity restrictions on the number of units that may be shipped over each route. But it does not skem to be any better than other standard methods for these problems, such as those given by Ford and Fulkerson [6], [7].