This paper establishes theorems about the simultaneous variation of right-hand sides and cost coefficients in a linear program from a strictly complementary solution. Some results are extensions of those that have bee...
详细信息
This paper establishes theorems about the simultaneous variation of right-hand sides and cost coefficients in a linear program from a strictly complementary solution. Some results are extensions of those that have been proven for varying the right-hand side of the primal or the dual, but not both;other results are new. In addition, changes in the optimal partition and what that means in economic terms are related to the basis-driven approach, notably to the theory of compatibility. In addition to new theorems about this relation, the transition graph is extended to provide another visualization of the underlying economics.
This paper deals with multiobjective nonlinear programming problems with random variables in the objective functions. These random variables are characterized by possibility density functions. The existing results con...
详细信息
This paper deals with multiobjective nonlinear programming problems with random variables in the objective functions. These random variables are characterized by possibility density functions. The existing results concerning the qualitative analysis of basic notions in parametric nonlinear programming problems are reformulated to study the stability sets of the first, second, third and fourth kind for multiobjective nonlinear programming problems under the concept of a-possibility efficient. (C) 1999 Elsevier Science B.V. All rights reserved.
In this paper, the problem of solving multiparametric 0-1 mixed-integer linear programming models is considered. A novel Branch and Bound algorithm is described based on successive solutions of parametric linear progr...
详细信息
In this paper, the problem of solving multiparametric 0-1 mixed-integer linear programming models is considered. A novel Branch and Bound algorithm is described based on successive solutions of parametric linear programs where n right-hand side parameters are allowed to vary independently. Numerical examples are presented to illustrate the basic steps and the potential of the proposed procedure. (C) 1999 Elsevier Science B.V. All rights reserved.
We designed and implemented an algorithm to solve the continuous right-hand side parametric 0-1-Integer Linear programming (ILP) problem, that is to solve a family of 0-1-ILP problems in which the problems are related...
详细信息
We designed and implemented an algorithm to solve the continuous right-hand side parametric 0-1-Integer Linear programming (ILP) problem, that is to solve a family of 0-1-ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of nonparametric 0-1-Mixed Integer Linear programming (MILP) problems in order to obtain a complete parametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems. (C) 1999 Elsevier Science B.V. All rights reserved.
The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we st...
详细信息
The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we study a variant of the minimum cost flow problem where we are given a set R subset of or equal to A of arcs and require that each are in R must carry the same amount of flow. This problem, which we call the simple equal flow problem, arose while modeling a water resource system management in Sardinia, Italy. We consider the simple equal flow problem in a directed network with n nodes, m arcs, and where all are capacities and node supplies are integer and bounded by U. We develop several algorithms for the simple equal flow problem - the network simplex algorithm, the parametric simplex algorithm, the combinatorial parametric algorithm, the binary search algorithm, and the capacity scaling algorithm. The binary search algorithm solves the simple equal flow problem in O(log(nU)) applications of any minimum cost flow algorithm. The capacity scaling algorithm solves it in O(m(m + n log n) log (nU)) time, which is almost the same time needed to solve the minimum cost flow problem by the capacity scaling algorithm. These algorithms can be easily modified to obtain an integer solution of the simple equal flow problem.
In this paper, an O(n(2)) active set method is presented for minimizing the parametric quadratic function (1/2)x' Dx - a' x + lambda max(c-gamma' x,0) subject to l less than or equal to x less than or equa...
详细信息
In this paper, an O(n(2)) active set method is presented for minimizing the parametric quadratic function (1/2)x' Dx - a' x + lambda max(c-gamma' x,0) subject to l less than or equal to x less than or equal to b, for all nonnegative values of the parameter lambda . Here, D is a positive diagonal n x n matrix, a and gamma are arbitrary n-vectors, c is an arbitrary scalar, l and b are arbitrary n-vectors, such that l\leq b. An extension of this algorithm is presented for minimizing the parametric function (1/2)x' Dx-a'x + lambda \gamma' x - c\ subject to l less than or equal to x less than or equal to b. It is also shown that these problems arise naturally in a tax programming problem.
Safety stock levels of reparable spare parts in a hierarchical inventory structure are determined relative to the marginal improvement to end item availability provided by each stock level. This research is focused on...
详细信息
Safety stock levels of reparable spare parts in a hierarchical inventory structure are determined relative to the marginal improvement to end item availability provided by each stock level. This research is focused on the United States Air Force (USAF) hierarchical inventory and repair system as modeled by the Multi-Echelon-Technique-for-Recoverable-Item-Control (METRIC) methodology. A piecewise linear modeling framework is introduced based on output from the Aircraft Availability Model (AAM), a model that is part of the METRIC family of models. The underlying nature of the piecewise linear formulation provides integer stock levels with continuous decision variables. This model provides the highest attainable end-item availability relative to an inventory of reparable spare parts. Additionally, the model provides a robust platform for the conduct of extensive post-optimality analysis. While this research focuses on the METRIC family of models, the methodology developed may be applied to any hierarchical inventory of reparable spares that conforms to the model's underlying mathematical structure.
A bounded feedback control for asymptotic stabilization of linear systems is derived. The designed control law increases the feedback gain as the controlled trajectory converges towards the origin. A sequence of invar...
详细信息
A bounded feedback control for asymptotic stabilization of linear systems is derived. The designed control law increases the feedback gain as the controlled trajectory converges towards the origin. A sequence of invariant sets of decreasing size, associated with a (quadratic) Lyapunov function, are defined and related to each of them, the corresponding possible highest gain is chosen, while maintaining the input bounded. Gains as functions of the position are designed by explicitly solving a c-parameterized programming problem. The proposed method allows global asymptotic stabilization of open-loop stable systems, with inputs subject to magnitude bounds and globally bounded rates. In the general case of linear systems that are asymptotic null controllable with bounded input, the semiglobal stabilization is also addressed taking into account the problem of semiglobal rate-limited actuators. The method is illustrated with the global stabilization of an inertial navigator, and the stabilization of a nonlinear model of a crane with hanging load. Copyright (C) 1999 John Wiley & Sons, Ltd.
Based on die-design how charts and data bases collected from the literature, the collected flow chart and data bases of die design, the present paper develops a computer-aided die design system using Auto-Lisp. The de...
详细信息
Based on die-design how charts and data bases collected from the literature, the collected flow chart and data bases of die design, the present paper develops a computer-aided die design system using Auto-Lisp. The design characteristics of the die elements and the die assembly have been expressed in parametric form and programmed. The proposed system has an open architecture, therefore, according to the system structure, die-design engineers can extent the die element design data base and programs. So far, three die-design modules have been finalised, namely: forward extrusion;upsetting;and combined extrusion. With the aid of the proposed system, the functions of die element design, die assembly design, automatic graphics and dimensions generation, redesign, dimension constraint correlations and bill of materials will provide efficiency and convenience of die design. (C) 1999 Elsevier Science S.A. All rights reserved.
Jenkins developed an heuristic algorithm for performing the right-hand-side parametric analysis of a Mixed Integer Linear programming (MILP) problem with an approach completely different from all previous work in the ...
详细信息
Jenkins developed an heuristic algorithm for performing the right-hand-side parametric analysis of a Mixed Integer Linear programming (MILP) problem with an approach completely different from all previous work in the area: his method can use any software capable of solving MILP problems and able to perform parametric linear programming (PLP). There is no proof of completeness by using Jenkins's algorithm. In this paper we present results that allow us to verify the completeness of the parametrical analysis. Like Jenkins's algorithm our procedure is theoretically independent of the solution method to solve a point-value problem. (C) 1998 Elsevier Science B.V.
暂无评论