Search

In an earlier paper 7, we suggested employing the sealed-bid auction as a format for modelling the marketing of a wide range of heterogeneous products, including the marketing of most brand names. The formation of prices in such markets is described as if it resulted from an actual sealed-bid auction, with buyers inspecting the goods offered by sale by the various manufacturers, and making sealed bids which later are opened by a hypothetical auctioneer. While surely putative, this model nevertheless seems superior to the standard assumptions of perfect competition where a homogeneous commodity is transacted and all buyers offer identical prices. Extending the use of the sealed bid auction, we here consider cases where the manufacturers or distributors promote their sales by advertising. While the maximum quantity demanded by each customer is fixed and given, his bids on the various brands are determined by the advertising and other promotional efforts. The bid response function for each consumer is supposed to be given and known. The preceding vertical production and distribution chain, from the supply of raw materials and primary commodities, via the successive processing, manufacturing and distribution of the product is described as a transshipment auction game. We formulate a complementarity model that in one step solves this entire logistics system, including a possible formation of coalitions between suppliers and/or distributors, the market prices of the various brands, the optimal distribution of the product, and the bids of the consumers. A numerical example is provided and the solution routine is discussed.

In this paper a local integral simplex method will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex method creates and solves a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc., and the solution to at least one of which is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is the optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n. Preliminary computational experience is given which indicates that global method has a low order polynomial empirical performance when solving such problems.

The purpose of this paper is to prove that the weighted uni- dimensional similarities problem with least absolute value metric (USPAM) is, in general, NP-Hard. In the first four sections of the paper, the USPAM problem and four lemmas are presented which will be used in Section 6 to prove the main theorem of this paper. It is shown that the simple max cut problem can, in a polynomial number of steps, be converted into a special case of the USPAM problem, which shows that the USPAM problem is NP-Hard. Finally, some special cases of the USPAM problem are described for which polynomial solutions exist.

A version of the primal transportation code is implemented on a 14 processor BBN Butterfly computer and solved a variety of large, fully dense, randomly generated transportation and assignment problems ranging in sizes up to m = n = 3000. The search phase of primal transportation algorIthm was well suited for implementation on the Butterfly, but the pivot phase could not be parallelized. Computational experience is presented showing that speedup factors for a parallel over a sequential computer of approximately 70 percent of the theoretical maximum were obtained. With the parallel code the empirical difficulty of solving an nxn transportation problem was proportional to n superscript a where a varied between 2.0 and 2.2.Four tables containing the run time information are presented. Additional information concerns the dispersion of run times, build initial tree time, search and pivot time, number of rows searched, number of pivots, and number of pivots per search. This information may be useful to others who are implementing the primal or other transportation algorithms on parallel computers.

This paper presents a heuristic algorithm for solving the facilities layout problem. The basic approach is the combination of a constructive method with exchange procedures, used repetitively. The constructive heuristic uses alternate costs, obtained in the process of computing the Gilmore-Lawler bounds, as the criterion for choosing the next assignment. Different partial solutions, to be used as starting points for multiple application of the constructive procedure, are obtained by development of a restricted breadth-first branch and bound tree. Computational results show that the method compares favourably with two competing procedures from the literature in finding solutions within 0.40% of the best known solutions for well known problems. Computing times are reasonable for problems with as many as 36 facilities. We also present a new best known solution for one version of the Steinberg problem, found in the process of experimentation. Keywords: Workplace layout, Problem solving, Health care facilities, Office buildings, Control systems, Production engineering, Backboard wiring.

We have solved a general inventory model with simultaneous price and production decisions. Both linear and non-linear (strictly convex) production cost cases are treated. Upper and lower bounds are imposed on state as well as control variables. The problem is solved by using the Lagrangian form of the maximum principle. Strong planning and strong forecast horizons are obtained. These arise when the state variable reaches its upper and lower bound. The existence of these horizons permits the decomposition of the whole problem into a set of smaller problems, which can be solved separately, and their solutions put together to form a complete solution to the problem. Finally, we derive a forward branch and bound algorithm to solve the problem. The algorithm is illustrated with a simple example.

In this paper our previous work on monopoly and oligopoly new product models is extended by the addition of pricing as well as advertising control variables. These models contain Bass's demand growth model, and the Vidale-Wolfe and Ozga advertising models, as well as the production learning curve model and an exponential demand function. The problem of characterizing an optimal pricing and advertising policy over time is an important question in the field of marketing as well as in the areas of business policy and competitive economics. These questions are particularly important during the introductory period of a new product, when the effects of the learning curve phenomenon and market saturation are most pronounced., Revision of report dated Jul 80.

We consider a production-inventory planning problem with time varying demands, convex production costs, and a warehouse capacity constraint. It is solved by use of the Lagrangian form of the maximum principle. The possible existence of strong planning and forecast horizons is demonstrated. When they exist, they permit the breaking up of the whole problem into a set of smaller problems which can be solved independently, because optimal decisions up to a strong planning horizon are completely independent of demand data beyond the next forecast horizon. A forward branch and bound algorithm is developed to determine such horizons and to solve the whole problem. (Author)

The use of the forward simplex algorithm of Aronson, Morton, and Thompson to solve the multi-stage personnel planning linear programming models of Charnes, Cooper, and Niehaus is described. Computational Results on randomly generated problems having up to 200 periods indicate that the forward simplex method requires CPU time and number of pivots which are linear in the number of periods. The standard simplex method requirements vary with at least the cube of the number of periods. For this reason the forward simplex method should be especially useful for solving real-time, conversational versions of personnel (and other) planning models. (Author)

A non candidate constraint in a linear program is one which never contains a pivot element during the course of solving the problem. Discovering non candidate constraints is computationally costly since their discovery, in general, depends on the actual sequence of pivots used. Knowing which constraints are non candidate is of great computational benefit since they need not be kept in updated form. Our experience indicates that from 50 to 80 percent of the constraints in randomly problems are non candidates at least part of the time. In this paper we present a learning approach to the identification of non candidate constraints. At each iteration we determine which constraints can potentially be pivotal; these are candidate constraints and all others are non candidate constraints on that step. On proceeding with the simplex method we update only the candidate constraints. If a non candidate constraint becomes candidate on a later step, we update it and add it to the candidate list. Although the constant checking of constraints to see whether they are changing from being candidate to non candidate is computationally costly, we obtain the computational benefit of having to keep in updated form a much smaller tableau. The net benefit of using this strategy is positive and results in a 25 to 50 percent reduction in total computation time. This paper describes the method in detail and gives computational results of testing it on a series of randomly generated problems. (Author)

The recursive algorithm is a polynomially bounded nonsimplex method for solving assignment problems. It begins by finding the optimum solution for a problem defined from the first row, then finding the optimum for a problem defined from rows one and two, etc., continuing until it solves the problem consisting of all the rows. It is thus a dimension expanding rather than an improvement method such as as the simplex. During the method the row duals are non-increasing and the column duals non-decreasing. Best and worst case behavior is analyzed. It is shown that some problems can be solved in one pass through the data, while others may require many passes. The number of zero shifts (comparable to degenerate pivots in the primal method) is shown to be at most n-squared/2. Extensive computational experience on the DEC-20 computer shows the method to be competitive for at least some kinds of assignment problems. Further tests on other computers are planned. (Author)

Given a set of users with known demands, a set of suppliers with known supplies, and known costs of shipping between suppliers and users the Bottleneck Single Source Transportation is that of assigning the users to the suppliers so that the following conditions are satisfied: the demand of each user is satisfied by a single supplier; the amount supplied by each supplier does not exceed its capacity; the maximum cost of supplying any user by its unique supplier is minimal. Applications of this problem include: voter redistricting, shipping perishable goods, assignment of city blocks to emergency facilities, and others. We first discuss a heuristic method which tries to find a feasible solution by assigning the users in order of decreasing demand to the suppliers according to certain orders. In our experience on randomly generated problems, the heuristic was able to find a good, and frequently an optimal feasible solution, most of the time. If the heuristic fails to find a solution, or finds a solution which is not known to be optimal, then a branch and bound algorithm, using ordinary bottleneck transportation problems as relaxations, is employed to find the optimum single source solution. Computational experience on some randomly generated problems up to 100 x 400 is presented which indicated that these problems can be solved in less than 2 minutes. Also several small problems with real data were solved; in all but one of these problems the heuristic succeeded in finding an optimal solution. (Author)

The multistage factory-warehouse location-allocation problem is to decide on locations of warehouses and shipping amounts from the factories through the warehouses to meet customer demands in such a way that the total fixed plus variable costs are minimized. Capacity constraints at factories and warehouses are also imposed. We present a cost operator algorithm for solving this problem. The algorithm takes into account the network structure and the submodularity of the objective function. Computational results with problems taken from the literature as well as new problems are provided. (Author)

Recent changes in a large scale macro planning model used to determine a 'best fit' of Naval Officers and billets are discussed. Problem reformulation from a linear program to a sparse transportation model is followed and the implementation of an advanced start procedure to achieve solution continuity is also presented. Suggestions are made for further research that would enhance the applicability of the model. (Author)

Various optimization techniques have been applied to meet manpower palnning and staffing goals. Attainment of these goals is usually accepted as a surrogate for attaining the maximum organizational effectiveness. However, the goals of most of these techniques are exogenous and the way they are determined has been generally ignored. This paper presents a novel formulation of manpower goals which is stated in terms of attaining optimal ratios of personnel desired between the various skills employed in an organization. This framework stresses the importance of the appropriate mixture of skills in the various units of an organization, not just the total number of people assigned. A technique called RATIO GOAL PROGRAMMING is presented and an example illustrates staffing an organization by minimizing a weighting of the squared deviations form the ideal ratios and the unit personnel ceilings. (Author)

A single source transportation problem is an ordinary transportation problem with the additional requirement that the entire demand at each demand location be supplied from a single supply location. It is a special case of Ross and Soland's generalized assignment problem. Such problems occur frequently in applications. This paper gives two heuristic solution methods and a branch and bound algorithm for solving single source transportation problems. A discussion of the branching rules, variable fixing rules, and the computation of weak lower bounds is given. Computational experience with the solution of randomly generated problems having up to 40,000 integer variables is reported. (Author)

The goal of this paper was to demonstrate the usefulness of a network transshipment model to approximate a linear programming model for manpower planning and design. The main advantages of the network model are: fast computing speeds, easy computation of effectiveness-cost trade-off curve, the availability of much managerial information contained in the dual matrix, and its usefulness in analyzing career paths. The only appreciable disadvantage is the difficulty of imposing extra constraints. In any specific instance, the latter difficulty can usually be overcome by employing parametric programming procedures as illustrated above.

A simple stochastic production-inventory model with quadratic cost functions is analyzed in detail. The inventory process is assumed to be driven by a white noise process resulting into an Ito stochastic differential equation. Both finite and infinite horizon versions of the problem are treated by a methodology based on the theory of stochastic integrals and differentials. Particular attention is given to illustrate the methodology, which is quite general and capable of dealing with more complicated problems. The paper concludes with some remarks in connection with the relationship of the results of this paper to the results in the deterministic case. (Author), Prepared in cooperation with Toronto Univ. (Ontario).

The assignment market game was defined by Shapley in 1955 and received a very full treatment by Shubik and Shapley in 1972. The present paper contains the following extensions: the assignment game is generalized to a market game; the two distinguished core points found for the assignment game are also shown to exist for the market game; in the non dual degenerate case it is shown that the skeletons of the buyer and seller cores are isomorphic k-graphs; and an algorithm is presented for computing skeletons of the buyer and seller cores of a market game. The results are illustrated with examples. At the end some remarks are made on the limiting sizes of cores. (Author)

The reassignment of naval officers at the end of their duty tours involves both gross and detailed planning considerations. The AMIS program for making gross assignments of officers to jobs was developed earlier by Cass, Charnes, Cooper, and Niehaus. To help with the detailed problem we have devised the bargaining assignment program BUPERS which is capable of quickly solving the problem of assigning several hundred officers to billets. Brief discussions of both these programs, are presented as well as a scoring program.

This paper generalizes the Barr-Shaftel auctioning model in several ways. It shows that the dual solutions they choose for prices and buyer surpluses is also the maximum buyer surplus solution. It shows that this solution can easily be found by means of a perturbation technique and relates the solution to core solutions of assignment market games, in the sense of Shapley and Shubik. It extends these models and theoretical results from an assignment to a transportation model. By adding seller reservation bids the symmetry of the auction process is increased in that it becomes pareto optimal for sellers as well as buyers. It proposes a fair bid auctioning process which has pareto optimality properties for both buyers and sellers, and which can be solved rapidly for problems having hundreds or thousands of buyers and sellers. Finally, it suggests that practical applications of these models to real auctioning situations is possible . Such applications could reduce the transaction cost and improve the speed of auction processes. (Author)

This paper analyzes capital budgeting decisions of business executives in an experimental setting. Two different data analysis techniques, a linear programming and a maximum likelihood method, are used to analyze preference judgements for hypothetical investment projects. For each of the twenty investment projects the following information was provided: a probability distribution of returns on investment, and magnitude of the investment, the number of additional men to be hired for implementing the investment, and the expected payback period for the investment. Five conclusions are demonstrated based on two independent experiments with business executives: Mean return on investment, and payback period, are the most important investment characteristics; Upper and middle management executives have almost identical preference structures; Downside variation of the return distribution has a stronger influence on investment decisions than overall variations; Usefulness of this methodology for (1) analyzing preference judgments of individual executives; (2) training purposes; and (3) as an aid to organizational decision making; and Both data analysis techniques give highly similar conclusions. (Author)

This paper considers the lot size model for the production and storage of a single commodity with limitations on production capacity and the possibility of not meeting demand, i.e., stockouts, at a penalty. The stockout option means that horizons can exist and permits the use of horizons to develop a forward algorithm for solving the problem. The forward algorithm is shown in the worst case to be asymptotically linear in computational requirements, in contrast to the case for the classical lot size model which has exponential computing requirements. Two versions of the model are considered: the first in which the upper bound on production is the same for every time period; and the second, in which the upper bound on production is permitted to vary each time period. In the first case the worst case computational difficulty increases in a cubic fashion initially, and then becomes linear. In the second case the initial increase is exponential before becoming linear. Besides the forward algorithm, a number of necessary conditions are derived which reduce the computational burden of solving the integer programming problem posed by the model.

A brief introduction to continuous mathematical control theory is presented. A model having two state variable accounts, cash and wheat, is defined by means of differential equations. Adjoint functions, the Hamiltonian function, and the optimum (bang-bang) policy are derived. Interpretations of the Hamiltonian and switching functions and a numerical example are given. The results are extended to the case where transaction costs and spoilage costs are incurred.

A maximum principle is obtained for stochastic networks that are defined by differing states of information. Using the Pontryagin maximum principle the authors define state and adjoint variables for each branch and find the relationships among them at tree nodes. An alternate approach is also made via dynamic programming which supplies intuitive interpretations for these relationships. Applications will include consumer style goods manufacturing. A simple application to a Christmas toy manufacturer's problem is given. (Author)

The paper extends some nonlinear programming techniques recently developed for the modular design problem to handle general nonlinear programs. The approach retains a basis restricted solution throughout and is shown to be an extension of the convex-simplex method to the case of nonlinear programs with nonlinear constraints. (Author)

Pursuing further the generalizations and extensions of the von Neumann model of the expanding economy, the authors discuss in the first paper two new aspects of the open model of 1969. The first is the determination of the control variables for the static case, and the authors give a numerical example. Then, second, the authors define the new dynamic model, which is a multi-period version with initial and final endowments. The control variables for this case are also discussed. The study is extended to the N-period case. The second paper discusses game theory in which the players may be persons, firms, countries. The paper discusses the concepts of strategy and resources, which may have to be closely related to the idea of a strategy., Prepared in cooperation with Carnegie-Mellon Univ., Pittsburgh, Pa. Graduate School of Industrial Administration, Contract N00014-67-A-0314-0007, Proj. NR-047-048.

In the paper the authors have devised methods for allocating overhead charges on the basis of mathematical programming models of the firm's production and sales possibilities. The basic scheme was to charge products on the basis of their utilization of the scarce resources of the firm. The prices for use of these resources were obtained from the dual variables associated with the constraints of profit-maximizing programming models. Special attention was given to traceable and avoidable overhead and overhead subsidies that arise because of sales and production interdependencies or managerial constraints. The objective, in all of these procedures, has been to devise a method for allocating overhead that does not distort the relative profitability of products so that managers would make identical product related decisions both before and after the overhead allocation. As such, the method captures a principal benefit of direct costing analysis while significantly extending this benefit to recognize scarce resource utilization and interaction with other products in reporting profitability. At the same time, the method avoids a difficulty of direct costing systems in that it is a full costing system with all overhead being allocated to products. Also the availability of the original programming model (before any overhead allocations) facilitates marginal analysis for short term product related decisions and expansion of scarce resources. (Author), Revision of report dated Aug 70.

Adjacent extreme point problems involving a tree basis (e.g., the transportation problem) require the determination of cycles which are created when edges not belonging to the basis are added to the basis-tree. The present paper offers an improvement over the predecessor-index method for finding such cycles and involves the use of a distance function defined on the nodes of the tree, in addition to the predecessor labels. It is shown that the relabeling associated with a basis change can be minimized by defining yet another function called the successor function. The algorithms for labeling and relabeling are then specialized for the specific case of transportation problems. (Author)

A computer code for the transportation problem that is even more efficient than the primal-dual method is developed in this paper. The code uses the well-known (primal) MODI method and is developed by a benefit-cost investigation the possible strategies for finding an initial solution, choosing the pivot element, finding the stepping-stone tour, etc. A modified row-minimum start rule, the row most negative rule for choice of pivot and a modified form of the predecessor index method for locating stepping-stone tours were found to perform best among the strategies examined. Efficient methods are devised for the relabeling that is involved in moving from one solution to another. Mean computation times for solving 175 x 175 transportation problems on the UNIVAC 1108 is 2-14 seconds depending on the data configuration. (Author)

The paper discusses a new method of simplifying games in extensive form which have both theoretical interest and are useful in the solution of actual games. The first method is that of partially normalizing the game at an information set and, if dominations are found, making local 'negative' decisions not to choose certain alternatives at the information set. Coupled with this idea is the reduction operation which actually eliminates parts of the game tree. These methods are shown to be powerful enough to eliminate all dominations in the strategy matrix, where one considers domination in three senses. (Author)

The rank of the n X n matrix (A - lambda I) is n- J(lambda) when lambda is an eigenvalue occurring in J(lambda) = or > 0 Jordan blocks of the Jordan normal form of A. An analogous expression for the rank of (A - lambda B) is derived for general m X n matrices. When J(lambda) 0, lambda is a rank-reducing number of (A - lambda I). It is shown how the rank-reducing properties of eigenvalues can be extended to m X n matrix expressions (A - lambda B). In particular a constructive way is given for deriving a polynomial P(lambda, A, B) whose roots are the only rank-reducing numbers of (A - lambda B). This polynomial is referred to as the characteristic polynomial of A relative to B.

Given m x n matrices A and B, by a solution to the pencil system of A relative to B we mean a triple lambda not equal to 0, x not equal to 9, y not equal to 0, where lambda is (x), x is 1 x m and y is n x 1, such that both x(A-lambda B) = 0 and (A-lambda B) y = 0. A canonical form is derived from which it is easy to state conditions for existence of such solutions. By further decomposing the canonical form it is shown that ordinary elimination methods and eigenvalue routines may be used to find pencil solutions. Next the relationship between matrix pencils and matrix games is studied. Finally, the relationship between game theory and dual systems of linear homogeneous equations is developed for both the real and complex cases and applied to pencil systems. (Author), Prepared in cooperation with Chicago Univ., Ill. Committee on Information Sciences. Grant NSF-GS-1541.

The authors extend the generalized von Neumann model to an open model by assuming that there are exogeneously determined export and import prices and that any amount can be exported or imported at these prices. The open model is characterized by means of seven axioms. It is shown, by applying the theory of linear programming, that if four economically reasonable assumptions hold, the open model has at least one solution in which at least one good with positive export price is exported and at least one good with positive import price is imported. It is also shown that, in general, a continuum of expansion rates can be achieved by varying certain control variables. The choice of these expansion rates gives indirectly the choice of a suitable sub-economy and also determined the exports and imports of the economy. (Author), Prepared in cooperation with Princeton Univ., N. J.

Some new results that relate matrix game theory to the eigenvectors and eigenvalues of square, real or complex, matrices are presented. Specifically, game-theoretics characterization are given for eigenvectors all of whole ccomponents are non-negative. Other results are also presented. (Author)

The Critical Path and Decision Critical Path Methods are extended to the case in which the (non-decision) jobs have distributions of job times. These new models are discussed in the light of recent literature on probabilistic programming. Also the practical problem of obtaining data and utilizing the results of computations is discussed. (Author)

A directed graph or digraph can be thought of as a communication network among a set of persons, where the vertices of the graph correspond to persons and edges of the graph to directed channels of communication from one person to another. A person is said to be able to 'reach' another if he can send a message to that person. The present paper gives an algorithm for finding the maximum number of edges that can be removed from a digraph without affecting its reachability properties. (Author)

A machine is to be bought, used for productive purposes for a length of time, and then sold. It is possible to do preventive maintenance while the machine is being used, if desired, in order to slow down the degradation of the machine's capability. The value of owning the machine is the sum of the discounted value of the machine when sold. In this paper a modification of a model due to B. Naslund for the problem is discussed. Using Pontryagin's maximum principle, the problem is treated as one of optimal control with the control variables being the use or nonuse of preventive maintenance and the selection of the sale date. It is shown that the optimal maintenance policy is bang-bang, and methods for finding the optimal sale date are determined. Simple examples show the various kinds of solutions that can be obtained with varying assumptions concerning the actual functions used in the model. (Author)

The essays are concerned with generalizations, extensions, and applications of the von Neumann model. The essays all have in common a 'how to' approach: Chapter II shows how to decompose a von Neumann model or an input-output model and how von Neumann expansion rates can be easily found once the decomposition is known; Chapter III shows how to find the von Neumann path and expansion rate; Chapter IV shows how to get onto the von Neumann path on an optimal way given a fixed-time constraint; and Chapter V shows how to introduce consumption into the closed von Neumann model or at least one way of attempting to do so. (Author), Doctoral thesis.

An algorithm is derived for determining whether a given ergodic matrix is regular or cyclic, and for putting it in canonical form in the latter case. It requires very little numerical computation and is suitable for hand use even for fairly large matrices. For large matrices, the corresponding program is considerably faster than previous ones. The paper also contains elementary independent proofs of several known results on ergodic matrices. (Author)

The first part of the paper is a theoretical study of v(B - alpha A) considered as a function of alpha, the expansion factor, where A and B are the input and output matrices of the model. Then a simple search algorithm is presented for computing the maximum and minimum expansion rates of the model. The algorithm uses the simplex method of linear programming as its basic subroutine. For a typical set of data, an expansion rate can be found to sufficient accuracy by solving 14 or fewer linear programming problems. With modern computers this is not a difficult task. The last part of the paper discusses the available data, in this case, input-output data, and gives the computational results found using it. Limitations of the data and conclusions drawn from it are discussed. The use of the model for economic planning and evaluation is considered. (Author)

A discrete maximum principle is derived from Kuhn-Tucker theory. Difference inequalities and state space constraints are included. An example is given illustrating the relationship of the present work to other maximum principles. (Author)

Conclusion: In any successful Management Science application at least the following steps must be carried out: (1) The problem must be identified and precisely characterized. (2) Data must be collected relevant to the problem. (3) A solution technique must be devised and tested with the actual data. Comparison with actual operations should be made. (4) A method for installing the solution into the operating situation must be devised and tested. (5) Before actual installation is attempted, a 'total systems' study should be made in order to be certain that (a) a valid problem is being solved, (b) the solution of this problem will not create difficulties in other parts of the system, (c) the solution technique is acceptable to the operating personnel who will have to implement it. The implication is that an organization that wants to have such problems solved will have to have an Operations Research department capable of carrying out at least steps (1), (2) and (5). Steps (3) and (4) can be done either by an 'in-house' O R group or else by a consulting firm. (Author)