Parametric studies in transportation-type problems

In this paper we present some results in parametric studies on several transportation-type problems. Specifically, a characterization is obtained for the optimal values of the variables in the problem of determining an optimal growth path in a logistics system. We also derive an upper bound beyond which the optimal growth path remains the same. The results are then extended to the goal programming model and the prespecified market growth rate problem.     

The economic effects of inspector error on attribute sampling plans

In this paper the effects of inspector error on a cost-based quality control system are investigated. The system examined is of a single sampling plan design involving several cost components. Both type I and type II inspector errors are considered. The model employs a process distribution, thus assuming that a stochastic process of some kind governs the quality of incoming lots. Optimal plan design is investigated under both error-free and error-prone inspection procedures and some comparisons are made.     

Target selection in lanchester combat: Heterogeneous forces and time-dependent attrition-rate coefficients

We develop solutions to two fire distribution problems for a homogeneous force in Lanchester combat against heterogeneous enemy forces. The combat continues over a period of time with a choice of tactics available to the homogeneous force and subject to change with time. In these idealized combat situations the lethality of each force's fire (as expressed by the Lanchester attrition-rate coefficient) depends upon time. Optimal fire distribution rules are developed through the combination of Lanchester-type equations for combat attrition and deterministic optimal control theory (Pontryagin maximum principle). Additionally, the theory of state variable inequality constraints is used to treat the nonnegativity of force levels. The synthesis of optimal fire distribution policies was facilitated by exploiting special mathematical structures in these problems.     

Finding equivalent transportation formulations for constrained transportation problems

This paper describes a procedure for determining if constrained transportation problems (i.e., transportation problems with additional linear constraints) can be transformed into equivalent pure transportation problems by a linear transformation involving the node constraints and the extra constraints. Our results extend procedures for problems in which the extra constraints consist of bounding certain partial sums of variables.     

On nash subsets and mobility chains in bimatrix games

This work is concerned with constructing, analyzing, and finding “mobility chains” for bimatrix games, sequences of equilibrium points along which it is possible for the two players to progress, one equilibrium point at a time, to an equilibrium point that is preferred by both players. The relationship between mobility chains and Nash subsets is established, and some properties of maximal Nash subsets are proved.     

Algorithms for minimizing total cost,bottleneck time and bottleneck shipment in transportation problems

We consider the transportation problem of determining nonnegative shipments from a set of m warehouses with given availabilities to a set of n markets with given requirements. Three objectives are defined for each solution: (i) total cost, TC, (ii) bottleneck time, BT (i.e., maximum transportation time for a positive shipment), and (iii) bottleneck shipment, SB (i.e., total shipment over routes with bottleneck time). An algorithm is given for determining all efficient (pareto-optimal or nondominated) (TC, BT) solution pairs. The special case of this algorithm when all the unit cost coefficients are zero is shown to be the same as the algorithms for minimizing BT. provided by Szwarc and Hammer. This algorithm for minimizing BT is shown to be computationally superior. Transportation or assignment problems with m=n=100 average about a second on the UNIVAC 1108 computer (FORTRAN V)) to the threshold algorithm for minimizing BT. The algorithm is then extended to provide not only all the efficient (TC, BT) solution pairs but also, for each such BT, all the efficient (TC, SB) solution pairs. The algorithms are based on the cost operator theory of parametric programming for the transportation problem developed by the authors.     

Multiperiod capacity expansion and shipment planning with linear costs

In this paper we consider a multiperiod deterministic capacity expansion and shipment planning problem for a single product. The product can be manufactured in several producing regions and is required in a number of markets. The demands for each of the markets are non-decreasing over time and must be met exactly during each time period (i.e., no backlogging or inventorying for future periods is permitted). Each region is assumed to have an initial production capacity, which may be increased at a given cost in any period. The demand in a market can be satisfied by production and shipment from any of the regions. The problem is to find a schedule of capacity expansions for the regions and a schedule of shipments from the regions to the markets so as to minimize the discounted capacity expansion and shipment costs. The problem is formulated as a linear programming model, and solved by an efficient algorithm using the operator theory of parametric programming for the transporation problem. Extensions to the infinite horizon case are also provided.     

Determining the most vital link in a flow network

The most vital link in a single commodity flow network is that are whose removal results in the greatest reduction in the value of the maximal flow in the network between a source node and a sink node. This paper develops an iterative labeling algorithm to determine the most vital link in the network. A necessary condition for an are to be the most vital link is established and is employed to decrease the number of ares which must be considered.