Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy primal simpl...Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy primal simplex method proposed by Ganesan and Veeramani [1] and the fuzzy dual simplex method proposed by Ebrahimnejad and Nasseri [2]. The former method is not applicable when a primal basic feasible solution is not easily at hand and the later method needs to an initial dual basic feasible solution. In this paper, we develop a novel approach namely the primal-dual simplex algorithm to overcome mentioned shortcomings. A numerical example is given to illustrate the proposed approach.展开更多
We apply the simplex algorithm which is a branch of linear programming to efficiently determine the allocation of resources required to operate a company in the software development field. The main aim of applying thi...We apply the simplex algorithm which is a branch of linear programming to efficiently determine the allocation of resources required to operate a company in the software development field. The main aim of applying this technique is to maximize the profit of a company under certain limitations. This <span>can be done using the trial-and-error approach. However, this tedious</span> process can be replaced by user-level tools such as Excel which are based on linear programming that will give more accurate results. Small software companies cannot afford to hire a high number of senior programmers to produce the required level of quality and to keep up with the demand for adding new features. On the other hand, lowering the quality of the product will reduce the number of customers and decrease profit. Another aspect is maximizing the utilization of hosting servers which are required for providing the services to customers since the cost of buying servers and maintaining them is extremely high. The simplex algorithm in linear programming will take the specified <span>constraints into account to compute the optimal allocation of the available</span> <span>resources to maximize profit and limit the cost. This paper will present a</span> <span>model that uses the simplex algorithm with a set of constraints to determine</span> how many projects of each type a company should take in one period of time.展开更多
In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, an...In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, and then the primal pivot rule to achieve optimality. The second algorithm, a modification of the first, is designed to handle highly degenerate problems more efficiently. Some interesting results concerning merit of the perturbation are established. Numerical results from preliminary tests are also reported. [ABSTRACT FROM AUTHOR]展开更多
Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule...Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.展开更多
This paper works on a modified simplex algorithm for the local optimization of Continuous Piece Wise Linear（CPWL） programming with generalization of hinging hyperplane objective and linear constraints. CPWL programm...This paper works on a modified simplex algorithm for the local optimization of Continuous Piece Wise Linear（CPWL） programming with generalization of hinging hyperplane objective and linear constraints. CPWL programming is popular since it can be equivalently transformed into difference of convex functions programming or concave optimization. Inspired by the concavity of the concave CPWL functions, we propose an Objective Variation Simplex Algorithm（OVSA）, which is able to find a local optimum in a reasonable time. Computational results are presented for further insights into the performance of the OVSA compared with two other algorithms on random test problems.展开更多
First, the main procedures and the distinctive features of the most-obtuse-angle（MOA）row or column pivot rules are introduced for achieving primal or dual feasibility in linear programming. Then, two special auxilia...First, the main procedures and the distinctive features of the most-obtuse-angle（MOA）row or column pivot rules are introduced for achieving primal or dual feasibility in linear programming. Then, two special auxiliary problems are constructed to prove that each of the rules can be actually considered as a simplex approach for solving the corresponding auxiliary problem. In addition, the nested pricing rule is also reviewed and its geometric interpretation is offered based on the heuristic characterization of an optimal solution.展开更多
The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). O...The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.展开更多
The purpose of this research paper is to introduce Easy Simplex Algorithm which is developed by author. The simplex algorithm first presented by G. B. Dantzing, is generally used for solving a Linear programming probl...The purpose of this research paper is to introduce Easy Simplex Algorithm which is developed by author. The simplex algorithm first presented by G. B. Dantzing, is generally used for solving a Linear programming problem (LPP). One of the important steps of the simplex algorithm is to convert all unequal constraints into equal form by adding slack variables then proceeds to basic solution. Our new algorithm i) solves the LPP without equalize the constraints and ii) leads to optimal solution definitely in lesser time. The goal of suggested algorithm is to improve the simplex algorithm so that the time of solving an LPP will be definitely lesser than the simplex algorithm. According to this Easy Simplex (AHA Simplex) Algorithm the use of Big M method is not required.展开更多
The algorithm under this name, together with the variants, is a method that solves the problems of optimal flow and costs. Examples of such problems are planning and procurement, scheduling by contractors, distributio...The algorithm under this name, together with the variants, is a method that solves the problems of optimal flow and costs. Examples of such problems are planning and procurement, scheduling by contractors, distribution and supply systems, transport on the road or rail network, electricity transmission, computer and telecommunications networks, pipe transmission systems (water, oil, …), and the like. The main goal of any business organization is to increase profits and satisfy its customers. Because business is an integral part of our environment, their goals will be limited by certain environmental factors and economic conditions. The out-of-kilter algorithm is used to solve a complex allocation problem involving interactive and conflicting personal choices subject to interactive resource constraints. The paper presents an example of successful use of this algorithm and proposes an extension to the areas of corporate and social planning. Customer demand, warehousing, and factory capacity were used as input for the model. First, we propose a linear programming approach to determine the optimal distribution pattern to reduce overall distribution costs. The proposed model of linear programming is solved by the standard simplex algorithm and the Excel-solver program. It is noticed that the proposed model of linear programming is suitable for finding the optimal distribution pattern and total minimum costs.展开更多
Oil product pipelines have features such as transporting multiple materials, ever-changing operating conditions, and synchronism between the oil input plan and the oil offloading plan. In this paper, an optimal model ...Oil product pipelines have features such as transporting multiple materials, ever-changing operating conditions, and synchronism between the oil input plan and the oil offloading plan. In this paper, an optimal model was established for a single-source multi-distribution oil pro- duct pipeline, and scheduling plans were made based on supply. In the model, time node constraints, oil offloading plan constraints, and migration of batch constraints were taken into consideration. The minimum deviation between the demanded oil volumes and the actual offloading volumes was chosen as the objective function, and a linear programming model was established on the basis of known time nodes＇ sequence. The ant colony optimization algo- rithm and simplex method were used to solve the model. The model was applied to a real pipeline and it performed well.展开更多
文摘Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy primal simplex method proposed by Ganesan and Veeramani [1] and the fuzzy dual simplex method proposed by Ebrahimnejad and Nasseri [2]. The former method is not applicable when a primal basic feasible solution is not easily at hand and the later method needs to an initial dual basic feasible solution. In this paper, we develop a novel approach namely the primal-dual simplex algorithm to overcome mentioned shortcomings. A numerical example is given to illustrate the proposed approach.
文摘We apply the simplex algorithm which is a branch of linear programming to efficiently determine the allocation of resources required to operate a company in the software development field. The main aim of applying this technique is to maximize the profit of a company under certain limitations. This <span>can be done using the trial-and-error approach. However, this tedious</span> process can be replaced by user-level tools such as Excel which are based on linear programming that will give more accurate results. Small software companies cannot afford to hire a high number of senior programmers to produce the required level of quality and to keep up with the demand for adding new features. On the other hand, lowering the quality of the product will reduce the number of customers and decrease profit. Another aspect is maximizing the utilization of hosting servers which are required for providing the services to customers since the cost of buying servers and maintaining them is extremely high. The simplex algorithm in linear programming will take the specified <span>constraints into account to compute the optimal allocation of the available</span> <span>resources to maximize profit and limit the cost. This paper will present a</span> <span>model that uses the simplex algorithm with a set of constraints to determine</span> how many projects of each type a company should take in one period of time.
文摘In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, and then the primal pivot rule to achieve optimality. The second algorithm, a modification of the first, is designed to handle highly degenerate problems more efficiently. Some interesting results concerning merit of the perturbation are established. Numerical results from preliminary tests are also reported. [ABSTRACT FROM AUTHOR]
基金supported by National Natural Science Foundation of China under the Projects 10871043 and 70971136
文摘Recently, computational results demonstrated remarkable superiority of a so-called ＂largest-distance＂ rule and ＂nested pricing＂ rule to other major rules commonly used in practice, such as Dantzig＇s original rule, the steepest-edge rule and Devex rule. Our computational experiments show that the simplex algorithm using a combination of these rules turned out to be even more efficient.
基金supported by the National Natural Science Foundation of China (Nos. 61473165 and 61134012)the National Key Basic Research and Development (973) Program of China (No. 2012CB720505)
文摘This paper works on a modified simplex algorithm for the local optimization of Continuous Piece Wise Linear（CPWL） programming with generalization of hinging hyperplane objective and linear constraints. CPWL programming is popular since it can be equivalently transformed into difference of convex functions programming or concave optimization. Inspired by the concavity of the concave CPWL functions, we propose an Objective Variation Simplex Algorithm（OVSA）, which is able to find a local optimum in a reasonable time. Computational results are presented for further insights into the performance of the OVSA compared with two other algorithms on random test problems.
基金The National Natural Science Foundation of China(No.10371017).
文摘First, the main procedures and the distinctive features of the most-obtuse-angle（MOA）row or column pivot rules are introduced for achieving primal or dual feasibility in linear programming. Then, two special auxiliary problems are constructed to prove that each of the rules can be actually considered as a simplex approach for solving the corresponding auxiliary problem. In addition, the nested pricing rule is also reviewed and its geometric interpretation is offered based on the heuristic characterization of an optimal solution.
文摘The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.
文摘The purpose of this research paper is to introduce Easy Simplex Algorithm which is developed by author. The simplex algorithm first presented by G. B. Dantzing, is generally used for solving a Linear programming problem (LPP). One of the important steps of the simplex algorithm is to convert all unequal constraints into equal form by adding slack variables then proceeds to basic solution. Our new algorithm i) solves the LPP without equalize the constraints and ii) leads to optimal solution definitely in lesser time. The goal of suggested algorithm is to improve the simplex algorithm so that the time of solving an LPP will be definitely lesser than the simplex algorithm. According to this Easy Simplex (AHA Simplex) Algorithm the use of Big M method is not required.
文摘The algorithm under this name, together with the variants, is a method that solves the problems of optimal flow and costs. Examples of such problems are planning and procurement, scheduling by contractors, distribution and supply systems, transport on the road or rail network, electricity transmission, computer and telecommunications networks, pipe transmission systems (water, oil, …), and the like. The main goal of any business organization is to increase profits and satisfy its customers. Because business is an integral part of our environment, their goals will be limited by certain environmental factors and economic conditions. The out-of-kilter algorithm is used to solve a complex allocation problem involving interactive and conflicting personal choices subject to interactive resource constraints. The paper presents an example of successful use of this algorithm and proposes an extension to the areas of corporate and social planning. Customer demand, warehousing, and factory capacity were used as input for the model. First, we propose a linear programming approach to determine the optimal distribution pattern to reduce overall distribution costs. The proposed model of linear programming is solved by the standard simplex algorithm and the Excel-solver program. It is noticed that the proposed model of linear programming is suitable for finding the optimal distribution pattern and total minimum costs.
基金part of the Program of"Study on the mechanism of complex heat and mass transfer during batch transport process in products pipelines"funded under the National Natural Science Foundation of China(grant number 51474228)
文摘Oil product pipelines have features such as transporting multiple materials, ever-changing operating conditions, and synchronism between the oil input plan and the oil offloading plan. In this paper, an optimal model was established for a single-source multi-distribution oil pro- duct pipeline, and scheduling plans were made based on supply. In the model, time node constraints, oil offloading plan constraints, and migration of batch constraints were taken into consideration. The minimum deviation between the demanded oil volumes and the actual offloading volumes was chosen as the objective function, and a linear programming model was established on the basis of known time nodes＇ sequence. The ant colony optimization algo- rithm and simplex method were used to solve the model. The model was applied to a real pipeline and it performed well.
