Today, in most cases, such as transportation, management, artificial intelligence, industries, decision-making, and in many real-life situations, we deal with uncertainty, imprecise boundaries, and qualitative informa...
详细信息
Today, in most cases, such as transportation, management, artificial intelligence, industries, decision-making, and in many real-life situations, we deal with uncertainty, imprecise boundaries, and qualitative information. In order to deal with these kinds of critical circumstances, we need to solve an optimization problem with interval-valued Fermatean fuzzy (IVFF) information. A few works have been done on transportation problems with Interval-valued Fermatean fuzzy sets (IVFFSs). In this paper, we first introduce a few new arithmetic operations on the set of IVFFSs. Second, we propose a linear programming problem (LPP) model under an interval-valued Fermatean fuzzy environment and study its Mathematical properties by establishing various theorems. Third, we propose a new simplex algorithm to solve a fully interval-valued Fermatean fuzzy Linear programming (IVFFLPP) problem and solve a few numerical problems to show the applicability of our proposed algorithm. Fourth, we discuss the formulation of the interval-valued Fermatean fuzzy assignment problem (IVFFAP) as a particular case of IVFFLPP and study its properties. Fifth, we establish a new algorithm for solving IVFFAP and solve two numerical problems to discuss the applicability, importance of the proposed algorithms.
The standard basis, which plays a fundamental role in simplex methodology, was recently extended to include a deficient case (with fewer columns than rows) by taking advantage of primal degeneracy. Computational resul...
详细信息
The standard basis, which plays a fundamental role in simplex methodology, was recently extended to include a deficient case (with fewer columns than rows) by taking advantage of primal degeneracy. Computational results have been favorable with dense implementations. In this paper, we propose a primal simplex algorithm using sparse LU factors of deficient bases. Amenable to real-world linear programming problems, which are often degenerate or even highly degenerate, the algorithm would solve them with potentially improved stability compared to the simplex algorithm. The proposed algorithm has been implemented and tested on a set of 50 Netlib test problems as well as a set of 15 much larger real-world problems, including 8 Kennington and 5 BPMPD problems. It significantly outperformed MINOS 5.3 in terms of both iteration counts and run time. In particular,. these results reveal that there is no inevitable correlation between an algorithm's inefficiency and degeneracy (contradicting common belief). (C) 2007 Elsevier Inc. All rights reserved.
simplex type algorithms perform successive pivoting operations (or iterations) in order to reach the optimal solution. The choice of the pivot element at each iteration is one of the most critical step in simplex type...
详细信息
simplex type algorithms perform successive pivoting operations (or iterations) in order to reach the optimal solution. The choice of the pivot element at each iteration is one of the most critical step in simplex type algorithms. The flexibility of the entering and leaving variable selection allows to develop various pivoting rules. In this paper, we have proposed some of the most well-known pivoting rules for the revised simplex algorithm on a CPU-GPU computing environment. All pivoting rules have been implemented in MATLAB and CUDA. Computational results on randomly generated optimal dense linear programs and on a set of benchmark problems (Netlib-optimal, Kennington, Netlib-infeasible, Meszaros) are also presented. These results showed that the proposed GPU implementations of the pivoting rules outperform the corresponding CPU implementations. (C) 2014 Elsevier Inc. All rights reserved.
A matrix N is Leontief if it has exactly one positive entry per column and there exists a nonnegative x such that Nx > 0. A Leontief flow problem is a linear-programming problem of the form min{c(inverted perpendic...
详细信息
A matrix N is Leontief if it has exactly one positive entry per column and there exists a nonnegative x such that Nx > 0. A Leontief flow problem is a linear-programming problem of the form min{c(inverted perpendicular)x\Nx = b;x greater than or equal to 0}, where N is a certain type of Leontief matrix. It is shown that for b > 0 this problem can be solved in O(n(2)U log npU) pivots by the simplex method using Dantzig's rule for choosing the entering variable, where n is the number of variables, p is the largest entry of N in absolute value, and U is a valid upper bound on any extreme-point solution. Classes of problems where this is a strongly polynomial bound are identified.
We present a new network simplex pivot selection rule, which we call the minimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks with n nodes, m...
详细信息
We present a new network simplex pivot selection rule, which we call the minimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks with n nodes, m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0,1}-valued penalty for each are of the network. The minimum ratio pivot rule is to select that eligible are as the entering are whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost how problem within O(n Delta) pivots and in O(Delta(m + n log n)) time, where Delta is any upper bound on the sum of all are flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n(2)) pivots and O(nm + n(2) log n) time. (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n(2)m log nC,n(2)m...
详细信息
Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n(2)m log nC,n(2)m(2) log n)) time, where n is the number of nodes in the network, m is the number of arcs, and C denotes the maximum absolute are costs if are costs are integer and proportional to otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the ''premultiplier algorithm''. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm log nC, nm(2) log n)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm log n). (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
This paper introduces a practical approach to interpret magnetic anomalies related to simple geometric-shaped models such as thin dike and horizontal cylinder. This approach is mainly based on both the deconvolution t...
详细信息
This paper introduces a practical approach to interpret magnetic anomalies related to simple geometric-shaped models such as thin dike and horizontal cylinder. This approach is mainly based on both the deconvolution technique and on the simplex algorithm for linear programming to best-estimate the model parameters, for example the depth to the top or to the center of a buried structure, the effective magnetization angle and the amplitude coefficient from magnetic anomaly profile. This approach has been tested first on synthetic data sets corrupted by different white Gaussian random noise levels to demonstrate the capability and the reliability of the method. The results acquired show that the estimated parameter values derived by this approach are close to the assumed true values of parameters. The validity of this approach is also demonstrated using real field magnetic anomalies from the United States and Brazil. A comparable and acceptable agreement is shown between the results derived by this approach and those from the real field data information.
This paper addresses an upper bound derived by Kitahara and Mizuno (Math Program A 137:579-586, 2013) on the number of basic feasible solutions of a linear program generated with the simplex algorithm. Their bound inc...
详细信息
This paper addresses an upper bound derived by Kitahara and Mizuno (Math Program A 137:579-586, 2013) on the number of basic feasible solutions of a linear program generated with the simplex algorithm. Their bound includes two parameters and , which are respectively the minimum and the maximum values of positive components in all basic feasible solutions. We show that is NP-hard to determine while can be computed in polynomial time. We also report some numerical results using alternative parameters for and gamma.
In this note, we show a mathematical error in paper ("An improved initial basis for the simplex algorithm" (Junior HV, Lins MPE. An improved initial basis for the simplex algorithm. Computers and Operations ...
详细信息
In this note, we show a mathematical error in paper ("An improved initial basis for the simplex algorithm" (Junior HV, Lins MPE. An improved initial basis for the simplex algorithm. Computers and Operations Research 2005;32: 1983-1993), and then offer a modified method using LU decomposition. Our preliminary computational results are very favorable. (C) 2006 Elsevier Ltd. All rights reserved.
In this study, we report a method for finding an analytical sequence that allows to simultaneously determine two analytes with very similar physical and chemical characteristics, such as amoxicillin and clavulanic aci...
详细信息
In this study, we report a method for finding an analytical sequence that allows to simultaneously determine two analytes with very similar physical and chemical characteristics, such as amoxicillin and clavulanic acid, using sequential injection analysis (SIA) with a diode-array spectrophotometric detector and multivariate curve resolution with alternating least squares (MCR-ALS). This method comprises two stages. In the first stage, a fractional factorial design (2(6-2)) is carried out in order to address the responses, reduce later experimentation and study how the factors, though confounded, interact with each other. In the second stage, optimization is carried out using the simplex algorithm. This method has advantages over response surface modelling, for example, when the number of significant factors is high. If simplex is begun in a suitable zone, the number of experiments may be considerably reduced. (c) 2006 Elsevier B.V All rights reserved.
暂无评论