A generalized-indices transportation problem

A generalized-indices transportation problem is formulated and an algorithm is presented for its solution. The algorithm is an extension of the modi-method. A theorem on the number of independent variables in the generalized-indices transportation problem is proved. An example problem is solved for the four-indices transportation problem. A computer program has been written to solve any four-indices problem.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

A transportation problem with competition

The classic transportation problem can be generalized with many carriers and one owner. From the formulation the competition in sense of game theory naturally appears. Here we present and solve this problem using a generalized n-person game. Besides the same composition properties about solutions and regarding zones, related results are considered. Finally, the problem in which there is a modification of the set of destinations assigned to the carriers is also studied.     

Auxiliary procedures for solving long transportation problems

An efficient auxiliary algorithm for solving transportation problems, based on a necessary but not sufficient condition for optimum, is presented.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

The dynamic transportation problem: A survey

The dynamic transportation problem is a transportation problem over time. That is, a problem of selecting at each instant of time t, the optimal flow of commodities from various sources to various sinks in a given network so as to minimize the total cost of transportation subject to some supply and demand constraints. While the earliest formulation of the problem dates back to 1958 as a problem of finding the maximal flow through a dynamic network in a given time, the problem has received wider attention only in the last ten years. During these years, the problem has been tackled by network techniques, linear programming, dynamic programming, combinational methods, nonlinear programming and finally, the optimal control theory. This paper is an up-to-date survey of the various analyses of the problem along with a critical discussion, comparison, and extensions of various formulations and techniques used. The survey concludes with a number of important suggestions for future work.     

Efficient computational devices for the capacitated transportation problem

This paper presents the details for applying and specializing the work of Ellis Johnson [10] and [11] to develop a primal code for the well-known capacitated transportation problem. The code was developed directly from the work of Johnson, but is similar to codes developed by Glover, Karney, Klingman, and Napier [6] and Srinivasan and Thompson [14]. The emphasis in the presentation is the use of the graphical representation of the basis to carry out the revised simplex operations. This is a means of exploiting the special structure and sparseness of the constraint matrix to minimize computational effort and storage requirements. We also present the results of solving several large problems with the code developed.     

On three basic methods for solving bottleneck transportation problems

For solving transportation problems essentially three types of methods are known: primal methods, the Hungarian method and the shortest augmenting path method. In this paper we present the specialization of these approaches to the bottleneck transportation problem and report some computational experience.     

一类对固定目标的集群搜寻对策问题及求解

利用集群搜索对策的理论与方法 ,建立了集群对固定目标的一类搜索对策模型 ,给出了集群的ε -最优搜寻策略 ,并考虑了其在搜索过程中的应用     

A descent approach to solving the complementary programming problem

In recent years, much attention has focused on mathematical programming problems with equilibrium constraints. In this article we consider the case where the constraints are complementarity constraints. Problems of this type arise, for instance, in the design of traffic networks. We develop here a descent algorithm for this problem that will converge to a local optimum in a finite number of iterations. The method involves solving a sequence of subproblems that are linear programs. Computational tests comparing our algorithm with the branch-and-bound algorithm in [7] bear out the efficacy of our method. When solving large problems, there is a definite advantage to coupling both methods. A local optimum incumbent provided by our algorithm can significantly reduce the computational effort required by the branch-and-bound algorithm.     

The bottleneck transportation problem

The bottleneck transportation problem can be stated as follows: A set of supplies and a set of demands are specified such that the total supply is equal to the total demand. There is a transportation time associated between each supply point and each demand point. It is required to find a feasible distribution (of the supplies) which minimizes the maximum transportaton time associated between a supply point and a demand point such that the distribution between the two points is positive. In addition, one may wish to find from among all optimal solutions to the bottleneck transportation problem, a solution which minimizes the total distribution that requires the maximum time Two algorithms are given for solving the above problems. One of them is a primal approach in the sense that improving fcasible solutions are obtained at each iteration. The other is a “threshold” algorithm which is found to be far superior computationally.     

A note on a stochastic production-maximizing transportation problem

A stochastic production-maximizing problem with transportation constraints is considered where the production rates, R_ij, of man i — job j combinations are random variables rather than constants. It is shown that for the family of Weibull distributions (of which the Exponential is a special case) with scale parameters λ_ij and shape parameter β, the plan that maximizes the expected rate of the entire line is obtained by solving a deterministic fixed charge transportation problem with no linear costs and with “set-up” cost matrix ‖λ_ij‖.     

A streamlined simplex approach to the singly constrained transportation problem

A primal simplex procedure is developed to solve transportation problems with an arbitrary additional linear constraint. The approach is a specialization of the Double Reverse Method of Charnes and Cooper. Efficient procedures for pricing-out the basis, determining representations, and implementing the change of basis are presented. These procedures exploit the pure transportation substructure in such a manner that full advantage may be taken of the computational schemes and list structures used to store and update the basis in codifying the MODI method. Furthermore, the pricing-out and change-of-basis procedures are organized in a manner that permits the calculations for one to be utilized in the other. Computational results are presented which indicate that this method is at least 50 times faster than the state-of-the-art LP code, APEX-III. Methods for obtaining basic primal “feasible” starts and “good” feasible integer solutions are also presented.     

一类带容量限制的运输问题

考虑一类带容量限制的运输问题.采用构造辅助网络的方法,将运输网络中的每个配送中心均拆分成两个节点,构造出新弧,形成新的网络,把此类运输问题转换为最小费用流问题来解决.并在此基础上,考虑运输网络中配送中心的容量扩张问题.     

多目标广义指派问题的模糊匈牙利算法求解

提出和讨论了两类多目标的广义指派决策问题,分别给出了它们的多目标整数线性规划数学模型,并结合模糊理论与解决传统指派问题的匈牙利方法提出了一种新的求解算法:模糊匈牙利法.最后给出了一个数值例子.     

Note: A geometrical method of solving certain games

One of the diagrammatic methods for solving two-person 2 × n matrix games can be extended to solve m × n games where each column of the matrix is a concave function of the row number. This gives a simple proof of a theorem of Benjamin and Goldman that such games have solutions involving no more than two consecutive strategies for the row player, and no more than two strategies for the column player. Two extensions are discussed. © 1994 John Wiley & Sons, Inc.