In the hierarchical structure system of multilevel programming, the high-level decision-making situations often require the inclusion of zero-one variables that represent "yes-no" decisions. The zero-one de...
详细信息
In the hierarchical structure system of multilevel programming, the high-level decision-making situations often require the inclusion of zero-one variables that represent "yes-no" decisions. The zero-one decision variables controlled by the high-level decision maker are combined with the real-valued decision variables controlled by the low-level decision maker into the 2-level programming model. The mixed-integer, 2-level, linearprogramming problem is then formulated. The exact and the heuristic solution procedures are developed and based on the branch-and-bound technique for solving the problem. These solutions were coded in FORTRAN V, and various problems generated at random were solved on a CDC CYBER 840 computer system. When the number of high-level variables increases, the execution time of exact algorithm increases approximately exponentially. The fewer low-level variables there are, the slower the execution time grows, and the execution time with a heuristic algorithm is much less than with an exact algorithm.
For many years, the simplex methods have been considered the most efficient practical solution methods for linearprogramming problems. Even such promising recent developments as Karmarkar's (1984) algorithm or o...
详细信息
For many years, the simplex methods have been considered the most efficient practical solution methods for linearprogramming problems. Even such promising recent developments as Karmarkar's (1984) algorithm or other interior point methods have not been able to change this view. An attempt is made to maintain the proven advantages of the simplex methods while allowing moves through the interior of the given polytope. New strategies for the modification of a primal simplex method called external pivoting are explored. Three strategies are developed and tested on a series of randomly generated problems. Although the proposed hybrid methods produced only moderate savings when applied to smaller problems, the savings in terms of iterations and computer time increased with the problem size and became quite substantial.
This paper presents a microcomputer system, MicroOR/LP, that addresses the major optimization problem classes with solution methods which are based on linearprogramming. This system is predicted upon an algebraic mod...
详细信息
This paper presents a microcomputer system, MicroOR/LP, that addresses the major optimization problem classes with solution methods which are based on linearprogramming. This system is predicted upon an algebraic modeling language that makes it possible to formulate linear programs, quadratic programs, separable programs and integer (mixed as well as binary) programs within the MicroOR/LP system in a form which is very close to their standard mathematical representations. The system provides a text editor working environment with pulldown menus for command selection. All modeling activities are performed from within the text editor, no other software is required.
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.
Many students find the translation of a verbal description of a problem into the appropriate mathematical model a difficult task. We describe how semantic networks can be used to assist in the structuring of complicat...
详细信息
Many students find the translation of a verbal description of a problem into the appropriate mathematical model a difficult task. We describe how semantic networks can be used to assist in the structuring of complicated models and thereby facilitate the modeling process.
We show that the linearprogramming problem can be solved by an application of the maximum entropy method. The optimal value of the objective function is that at which the maximum entropy algorithm fails.
We show that the linearprogramming problem can be solved by an application of the maximum entropy method. The optimal value of the objective function is that at which the maximum entropy algorithm fails.
It is shown that, for any fixed dimension d, the linearprogramming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM (concurrent-read-concurrent-write parallel random-access machine) wi...
详细信息
ISBN:
(纸本)081862082X
It is shown that, for any fixed dimension d, the linearprogramming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM (concurrent-read-concurrent-write parallel random-access machine) with O(n) processors almost surely in constant time. The algorithm always finds the correct solution. With nd/log2d processors, the probability that the algorithm will not finish within O(d2log2d) time tends to zero exponentially with n.
We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time Ο(m). The other constructs convex hulls of n points in Rd, d > 3, in expected time Ο(n⌈d/2⌉...
详细信息
ISBN:
(纸本)0897913620
We present two randomized algorithms. One solves linear programs involving m constraints in d variables in expected time Ο(m). The other constructs convex hulls of n points in Rd, d > 3, in expected time Ο(n⌈d/2⌉). In both bounds d is considered to be a constant. In the linearprogramming algorithm the dependence of the time bound on d is of the form d!. The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses.
A mathematical computer programming system, MPS, implements the simplex algorithm developed for solving the linearprogramming (LP) problem. With the fast growing personal computer (PC) technology and the advent of so...
详细信息
ISBN:
(纸本)0818620315
A mathematical computer programming system, MPS, implements the simplex algorithm developed for solving the linearprogramming (LP) problem. With the fast growing personal computer (PC) technology and the advent of software packages for the MPS PC, a class of learn-by-doing MPS users has emerged. Motivated by the fact that entering most LP data into a computer is a time consuming, confusing, and error prone task for the end users, the authors study the MPS PC user's requirements for LP data entry and describe the design of the user-friendly-front-end program to aid in this process. The program is implemented currently in LOTUS 1-2-3 macros;covenants on that prototype are provided.
The parallel complexity of solving linearprogramming problems is studied in the context of interior point methods. If n and m, respectively, denote the number of variables and the number of constraints in the given p...
详细信息
The parallel complexity of solving linearprogramming problems is studied in the context of interior point methods. If n and m, respectively, denote the number of variables and the number of constraints in the given problem, an algorithm that solves linearprogramming problems in O((mn)1/4 (log 1 n)3L) time using O(M(n)m/n + 1n3) processors is given. (M(n) is the number of operations for multiplying two n × n matrices.) This gives an improvement in the parallel running time for n = o(m). A typical case in which n = o(m) is the dual of the uncapacitated transportation problem. The algorithm solves the uncapacitated transportation problem in O((VE)1/4(log V)3 (log Vγ)) time using O(V3) processors, where V (E) is the number of nodes (edges) and γ is the largest magnitude of an edge cost or a demand at a node. As a by-product, a better parallel algorithm for the assignment problem for graphs of moderate density is obtained.
暂无评论