The computational results of a new zero-one goal programming algorithm are compared with those obtained using the algorithm developed by Lee and Morris (1977). The proposed constraint aggregation and partitioning alg...
详细信息
The computational results of a new zero-one goal programming algorithm are compared with those obtained using the algorithm developed by Lee and Morris (1977). The proposed constraint aggregation and partitioning algorithm is based on an aggregation scheme that allows all constraints under consideration to be combined in one operation. The upper and lower bounds for the number of nonzero variables needed to satisfy each constraint and each priority level are determined by the algorithm, which then searches for the subprogram consisting of the first priority levels that can be achieved completely. By this process, the problem is partitioned according to priority level. The algorithm also derives the conditions needed to determine the range of nonzero variables that may provide complete achievement for a subprogram and also generate the optimal solution. The new algorithm is more accurate and more reliable and requires about 10% of the central processing unit time of the Lee and Morris algorithm.
Computational results are presented for Gass' Dualplex Method, which is designed to solve dual angular-structured linear programs. The test problem set includes a group of staircase problems from such diverse fie...
详细信息
Computational results are presented for Gass' Dualplex Method, which is designed to solve dual angular-structured linear programs. The test problem set includes a group of staircase problems from such diverse fields as economic development, agricultural planning, and cutting stock models. Every test problem is solved by an experimental dualplex code and an efficient commercial version of the simplex algorithm for comparative purposes. Based on the test problem results, the dualplex method is discovered to exhibit very good solution behavior and have steeper solution convergence than the commercial simplex code. The effort required to solve the Dualplex subproblem is reduced significantly for the test problem set by beginning the starting subproblem basis with a readily available advanced variable solution set.
The cybernetic importance of the work of the economist P. Sraffa is briefly introduced and then consideration is given to the use of linearprogramming technique in constructing the Sraffan system of production of com...
详细信息
The cybernetic importance of the work of the economist P. Sraffa is briefly introduced and then consideration is given to the use of linearprogramming technique in constructing the Sraffan system of production of commodities by means of commodities. It is concluded that linearprogramming, via the use of computers and computer languages, could be used to show how much profits can be obtained from systems of production with the available means of production.
From the point of view of overall performance, it is relevant in a large number of production and service activities involving distributed systems to assign the tasks to the different operational units trying to keep ...
详细信息
From the point of view of overall performance, it is relevant in a large number of production and service activities involving distributed systems to assign the tasks to the different operational units trying to keep the individual workloads well balanced. Simple static load-balancing problems may be stated as linear programs and solved at low computational cost. Possible extensions to the dynamical case are discussed. The problem of optimally sharing a given workload among a number of machines under a presently known load level is formulated both as a linear problem and as a partitioning problem. An interpretation of the problem in terms of scheduling theory is described, and an exact algorithm running in O(n log n) time is presented.
A constructive parameterization procedure for a class of operational stochastic linearprogramming problems is proposed which is based on predicting the base set of LLP solutions. The problem of predicting the composi...
详细信息
A constructive parameterization procedure for a class of operational stochastic linearprogramming problems is proposed which is based on predicting the base set of LLP solutions. The problem of predicting the composition of the base set is formally stated and methods of its solution are proposed.
In the formulation of linearprogramming problems, analysts may encounter situations requiring the use of free (unrestricted) variables. It is widely known that a free variable can be expressed as the difference of 2...
详细信息
In the formulation of linearprogramming problems, analysts may encounter situations requiring the use of free (unrestricted) variables. It is widely known that a free variable can be expressed as the difference of 2 nonnegative variables, thus offering a means of transforming any problem with free variables to the standard nonnegative model. However, it is not commonly known that the computational way of handling free variables is not to define them in terms of nonnegative variables; to define them as the difference of 2 nonnegative variables is computationally inefficient. Key theorems are proved demonstrating the role of free variables in an optimal solution.
A common warehouse/distribution problem is the unitization of pallet loads. A linearprogramming model has been developed to determine optimal stacking patterns on the basis of the dimensions of the boxes that constit...
详细信息
A common warehouse/distribution problem is the unitization of pallet loads. A linearprogramming model has been developed to determine optimal stacking patterns on the basis of the dimensions of the boxes that constitute the load. The desired dimensions of the finished load may be user specified. No restriction is placed on the number of boxes of various types that may be loaded. The developed model is two-dimensional and assumes that all boxes have the same height.
A multiple criteria de Novo program with fuzzy parameters is developed based on the possibility concept of fuzzy set. This approach is much more flexible than the standard de Novo programming and allows the decision m...
详细信息
A multiple criteria de Novo program with fuzzy parameters is developed based on the possibility concept of fuzzy set. This approach is much more flexible than the standard de Novo programming and allows the decision maker to choose his appropriate membership grades based on the risk factor he is willing to take. A numerical example is given to illustrate the approach.
A steepest edge active set algorithm is described which is suitable for solving linearprogramming problems where the constraint matrix is sparse and has more rows than columns. The algorithm uses a steepest edge crit...
详细信息
A steepest edge active set algorithm is described which is suitable for solving linearprogramming problems where the constraint matrix is sparse and has more rows than columns. The algorithm uses a steepest edge criterion for selecting the search direction at each iteration and recurrence relations are derived which enable it to execute efficiently. The canonical form for the active set method is convenient for many applications and may be exploited to devise a simple crash procedure which is employed prior to phase one. A complete two-phase algorithm which incorporates the crash procedure is outlined. Only one artificial variable is needed to determine if the linearprogramming problem has a feasible solution in phase one. Some computational results are given to illustrate the effectiveness of the algorithm for a range of sparse linearprogramming problems. Comparisons between the steepest edge criterion and the traditional Dantzig criterion suggest that the former usually requires fewer iterations and often leads to substantial savings for large problems.
The paper describes a refinement of L. V. Khachian's method of ellipsoids checking consistency of linear inequalities in polynomial time. The improvement consists of reducing the volumes of the ellipsoids, which l...
详细信息
The paper describes a refinement of L. V. Khachian's method of ellipsoids checking consistency of linear inequalities in polynomial time. The improvement consists of reducing the volumes of the ellipsoids, which leads to a lowering of the number of steps of the algorithm. The emphasis is put on the question of the numerical precision required to validate the theoretical results about complexity.
暂无评论