We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that is closest to the source node from amongst all possible candidates. We prove that...
详细信息
We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that is closest to the source node from amongst all possible candidates. We prove that this algorithm requires at most nm pivots to solve a problem with n nodes and m arcs, and give implementations of it which run in O(n2m) time. Our algorithm is, as far as we know, the first strongly polynomial primal algorithm for solving the maximum flow problem.
We show that a variant of Karmarkar's projective algorithm for linearprogramming can be viewed as following the approach of Dantzig-Wolfe decomposition. At each iteration, the current primal feasible solution gen...
详细信息
We show that a variant of Karmarkar's projective algorithm for linearprogramming can be viewed as following the approach of Dantzig-Wolfe decomposition. At each iteration, the current primal feasible solution generates prices which are used to form a simple subproblem. The solution to the subproblem is then incorporated into the current feasible solution. With a suitable choice of stepsize a constant reduction in potential function is achieved at each iteration. We also use our analysis to motivate a new primal simplex pivot rule that is closely related to rules used by E. Klotz and L. Schrage.
A new feasible direction method for linearprogramming problems is presented. The method is not boundary following. The method proceeds from a feasible interior point in a direction that improves the objective functio...
详细信息
A new feasible direction method for linearprogramming problems is presented. The method is not boundary following. The method proceeds from a feasible interior point in a direction that improves the objective function until a point on a constraint surface is met. At this point searches are initiated in the hyperplane of constant function value by using projections of the bounding constraints until n bounding constraints are identified that yield a vertex as candidate solution. If the vertex is not feasible of feasible with a worse function value, the next iteration is started from the centre of the simplex defined by the identified points on the bounding constraint surfaces. Otherwise the feasible vertex is tested for optimality. If not optimal a perturbed point with improved function value on an edge emanating from the vertex is calculated from which the next iteration is started. The method has successfully been applied to many test problems.
We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear progr...
详细信息
We define a function of the interior of the feasible region of Karmarkar's canonical linear program with the property that its supremum is bounded above by one, if and only if the optimal value of the linear program is zero. We use this function to obtain data-dependent steps for Karmarkar's algorithm. The corresponding reduction in the potential function improves upon the data-independent reduction derived by Padberg. We analyze the general step and consider its potential practical advantages.
In order to handle multiobjective linearprogramming problems containing fuzzy parameters, the authors have already proposed four kinds of α-feasibility and β-Pareto optimality, based on the four kinds of index intr...
详细信息
In order to handle multiobjective linearprogramming problems containing fuzzy parameters, the authors have already proposed four kinds of α-feasibility and β-Pareto optimality, based on the four kinds of index introduced by Dubois et al. This paper discusses the proposed concepts of four kinds of β-Pareto optimality in further detail, in order to indicate problems with β-Pareto optimality. As a means of coping with those problems, four kinds of γ-Pareto optimal solutions are introduced. Then the concept of (α, γ)-Pareto optimal solution is introduced, by considering simultaneously the α-feasibility and the γ-Pareto optimality. It is shown that the set of (α, γ)-Pareto optimal solutions, which can be regarded as the most optimistic and the most pessimistic, can be found using linearprogramming.
This paper describes an application of linearprogramming for the analysis of plane strain rigid-plastic flow. First, linearprogramming and the theory of a rigid-plastic material are briefly revised. The implementati...
详细信息
This paper describes an application of linearprogramming for the analysis of plane strain rigid-plastic flow. First, linearprogramming and the theory of a rigid-plastic material are briefly revised. The implementation of linearprogramming for rigid-plastic flow is then described. The method is to subdivide the material into rigid triangular blocks which may slide upon each other, dissipating energy at a rate proportional to the rate of sliding. Many different modes of deformation are possible;linearprogramming is used to select the mode that gives the least rate of total energy dissipation. The indentation of a strip by blunt-nosed indenters is used as an example. Results of the linearprogramming method are compared with the exact slip line field solutions.
This paper considers multi-objective programming problems with fuzzy parameters, and newly defines the concepts of four types of α-feasibility and β-Pareto optimality. The relations between these concepts is discuss...
详细信息
This paper considers multi-objective programming problems with fuzzy parameters, and newly defines the concepts of four types of α-feasibility and β-Pareto optimality. The relations between these concepts is discussed in some detail. Four types of (α, β) Pareto optimal solutions, which simultaneously consider the proposed α-feasibility and β-Pareto optimality, are introduced. The possibility of deriving these solutions using linearprogramming is shown. The relationship of this approach to the already proposed extended concept of the Pareto optimal solution is also discussed.
In this paper, we propose an efficient and specific algorithm for solving large-scale 0-1 GP problems in particular structures, which are termed GUB structures. Furthermore, to illustrate the effectiveness of the algo...
详细信息
In this paper, we propose an efficient and specific algorithm for solving large-scale 0-1 GP problems in particular structures, which are termed GUB structures. Furthermore, to illustrate the effectiveness of the algorithm proposed here, we introduce two numerical examples from among the problems of system reliability, and compare the algorithm proposed with previous methods.
Recently T. Terlaky has proposed a new pivoting rule for the criss-cross simplex method for linearprogramming and he proved that his rule is convergent. In this note we show that the required number of iterations may...
详细信息
Recently T. Terlaky has proposed a new pivoting rule for the criss-cross simplex method for linearprogramming and he proved that his rule is convergent. In this note we show that the required number of iterations may be exponential in the number of variables and constraints of the problem.
We present an algorithm for solving a large class of semi-infinite linearprogramming problems. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an Ε-optimal solutio...
详细信息
We present an algorithm for solving a large class of semi-infinite linearprogramming problems. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an Ε-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an Ε-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an Ε-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.
暂无评论