A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equ...A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equaling to zero, the bilevel linear fractional-linear programming is transformed into a traditional sin- gle level programming problem, which can be transformed into a series of linear fractional programming problem. Thus, the modi- fied convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming. Finally, an example demonstrates the feasibility of the proposed algorithm.展开更多
Two-Line Element(TLE)datasets are the only orbital data source of Earth-orbiting space objects for many civil users for their research and applications.The datasets have uneven qualities that may affect the reliabilit...Two-Line Element(TLE)datasets are the only orbital data source of Earth-orbiting space objects for many civil users for their research and applications.The datasets have uneven qualities that may affect the reliability of the propagated positions of space objects using a single TLE.The least squares approach to use multiple TLEs also suffers from the poor quality of some TLEs,and reliable error information cannot be available.This paper proposes a simplex algorithm to estimate an optimal TLE from multiple TLEs and obtain the uncertainty of each element.It is a derivative-free technique that can deal with various orbit types.Experiments have demonstrated that using the TLE estimated from the simplex method is more reliable,stable,and effective than those from the batch least squares method.As an application example,the optimal TLE and its uncertainty are used for predicting the fallen area,keeping the actual fallen site in the prediction areas.展开更多
This work presents an application of the Simplex Method for solving an optimal planning problem for cancer treatment by radiotherapy. Linear Programming can aid the optimal planning for radiation therapy, where the co...This work presents an application of the Simplex Method for solving an optimal planning problem for cancer treatment by radiotherapy. Linear Programming can aid the optimal planning for radiation therapy, where the concern is to apply a high enough radiation in the tumor while saving significantly healthy regions or critical organs.展开更多
In this paper, a new hybrid algorithm based on exploration power of a new improvement self-adaptive strategy for controlling parameters in DE （differential evolution） algorithm and exploitation capability of Nelder-...In this paper, a new hybrid algorithm based on exploration power of a new improvement self-adaptive strategy for controlling parameters in DE （differential evolution） algorithm and exploitation capability of Nelder-Mead simplex method is presented （HISADE-NMS）. The DE has been used in many practical cases and has demonstrated good convergence properties. It has only a few control parameters as number of particles （NP）, scaling factor （F） and crossover control （CR）, which are kept fixed throughout the entire evolutionary process. However, these control parameters are very sensitive to the setting of the control parameters based on their experiments. The value of control parameters depends on the characteristics of each objective function, therefore, we have to tune their value in each problem that mean it will take too long time to perform. In the new manner, we present a new version of the DE algorithm for obtaining self-adaptive control parameter settings. Some modifications are imposed on DE to improve its capability and efficiency while being hybridized with Nelder-Mead simplex method. To valid the robustness of new hybrid algorithm, we apply it to solve some examples of structural optimization constraints.展开更多
A new partial pricing column rule is proposed to the basis-deficiency-allowing simplex method developed by Pan.Computational results obtained with a set of small problems and a set of standard NETLIB problems show its...A new partial pricing column rule is proposed to the basis-deficiency-allowing simplex method developed by Pan.Computational results obtained with a set of small problems and a set of standard NETLIB problems show its promise of success.展开更多
In this study we discuss the use of the simplex method to solve allocation problems whose flow matrices are doubly stochastic. Although these problems can be solved via a 0 - 1 integer programming method, H. W. Kuhn [...In this study we discuss the use of the simplex method to solve allocation problems whose flow matrices are doubly stochastic. Although these problems can be solved via a 0 - 1 integer programming method, H. W. Kuhn [1] suggested the use of linear programming in addition to the Hungarian method. Specifically, we use the existence theorem of the solution along with partially total unimodularity and nonnegativeness of the incidence matrix to prove that the simplex method facilitates solving these problems. We also provide insights as to how a partition including a particular unit may be obtained.展开更多
This study adopts the Dantzig’s Simplex method to investigate optimization of sand casting parameters for optimum service performance. Some process variables and mechanical properties were adapted into the Simplex me...This study adopts the Dantzig’s Simplex method to investigate optimization of sand casting parameters for optimum service performance. Some process variables and mechanical properties were adapted into the Simplex method. Aluminium alloy samples were cast, machined and subjected to a series of mechanical tests. From the body of data collected, linear functions and constraint equations were formulated and employed in the Dantzig’s Simplex method for optimization of process parameters. The results showed that the Simplex method can be adapted for studying performance opti- mization of castings.展开更多
Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to...Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is C_(n)^(m),our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.展开更多
In this paper, we investigate the quadratic approximation methods. After studying the basic idea of simplex methods, we construct several new search directions by combining the local information progressively obtained...In this paper, we investigate the quadratic approximation methods. After studying the basic idea of simplex methods, we construct several new search directions by combining the local information progressively obtained during the iterates of the algorithm to form new subspaces. And the quadratic model is solved in the new subspaces. The motivation is to use the information disclosed by the former steps to construct more promising directions. For most tested problems, the number of functions evaluations have been reduced obviously through our algorithms.展开更多
A simplex method of orbit determination （SMOD） is presented to solve the problem of orbit determination for maneuvering satellites subject to small and continuous thrust. The objective function is established as the...A simplex method of orbit determination （SMOD） is presented to solve the problem of orbit determination for maneuvering satellites subject to small and continuous thrust. The objective function is established as the sum of the nth powers of the observation errors based on global positioning satellite （GPS） data. The convergence behavior of the proposed method is analyzed using a range of initial orbital parameter errors and n values to ensure the rapid and accurate convergence of the SMOD. For an uncontrolled satellite, the orbit obtained by the SMOD provides a position error compared with GPS data that is commensurate with that obtained by the least squares technique. For low Earth orbit satellite control, the precision of the acceleration produced by a small pulse thrust is less than 0.1% compared with the calibrated value. The orbit obtained by the SMOD is also compared with weak GPS data for a geostationary Earth orbit satellite over several days. The results show that the position accuracy is within 12.0 m. The working efficiency of the electric propulsion is about 67% compared with the designed value. The analyses provide the guidance for subsequent satellite control. The method is suitable for orbit determination of maneuvering satellites subject to small and continuous thrust.展开更多
The branch-and-bound method with the revised dual simplex for bounded variables is very effective in solving relatively large-size integer linear programming problems. This paper, based on the general forms of the pen...The branch-and-bound method with the revised dual simplex for bounded variables is very effective in solving relatively large-size integer linear programming problems. This paper, based on the general forms of the penalties by Beale and Small and the stronger penalties by Tomlin, describes the modifications of these penalties used for the method of bounded variables. The same examples from Petersen are taken and the satisfactory results are shown in comparison with those obtained by Tomlin.展开更多
目的 Linear Programming的simplexmethod建模求最优解。方法应用simplexmethod.结果建立了LinearProgramming的数学模型并用simplexmethod求得了最优解.结论因为单纯形表反映了Linear Programming的所有信息,故用simplexmethod可简便...目的 Linear Programming的simplexmethod建模求最优解。方法应用simplexmethod.结果建立了LinearProgramming的数学模型并用simplexmethod求得了最优解.结论因为单纯形表反映了Linear Programming的所有信息,故用simplexmethod可简便地求得最优解.simplexmethod的基本思路是:先将Linear Programming用sim-plexmethod划为标准型,根据问题的标准型,进行初等行变换,将主元素列除主元素化为1外其余的元素均化为0,当基变量值全为非负时,问题就得到了最优解.展开更多
Since the simplex method[1]of linear programming was established in 1947. It has been im proving unceasingly. But a major breakthrough has not been been,only a little quantity of computation was decreased. In this pap...Since the simplex method[1]of linear programming was established in 1947. It has been im proving unceasingly. But a major breakthrough has not been been,only a little quantity of computation was decreased. In this paper,the computation of the first stage of artificial basis method[l] is omited. Therefore, computational quantity is decreased greatly.展开更多
For physical ozone absorption without reaction,two parametric estimation methods,i.e.the common linear least square fitting and non-linear Simplex search methods,were applied,respectively,to determine the ozone mass t...For physical ozone absorption without reaction,two parametric estimation methods,i.e.the common linear least square fitting and non-linear Simplex search methods,were applied,respectively,to determine the ozone mass transfer coefficient during absorption and both methods give almost the same mass transfer coefficient.While for chemical absorption with ozone decomposition reaction,the common linear least square fitting method is not applicable for the evaluation of ozone mass transfer coefficient due to the difficulty of model linearization for describing ozone concentration dissolved in water.The nonlinear Simplex method obtains the mass transfer coefficient by minimizing the sum of the differences between the simulated and experimental ozone concentration during the whole absorption process,without the limitation of linear relationship between the dissolved ozone concentration and absorption time during the initial stage of absorption.Comparison of the ozone concentration profiles between the simulation and experimental data demonstrates that Simplex method may determine ozone mass transfer coefficient during absorption in an accurate and high efficiency way with wide applicability.展开更多
A PID parameters tuning and optimization method for a turbine engine based on the simplex search method was proposed. Taking time delay of combustion and actuator into account, a simulation model of a PID control syst...A PID parameters tuning and optimization method for a turbine engine based on the simplex search method was proposed. Taking time delay of combustion and actuator into account, a simulation model of a PID control system for a turbine engine was developed. A performance index based on the integral of absolute error （IAE） was given as an objective function of optimization. In order to avoid the sensitivity that resulted from the initial values of the simplex search method, the traditional Ziegler-Nichols method was used to tune PID parameters to obtain the initial values at first, then the simplex search method was applied to optimize PID parameters for the turbine engine. Simulation results indicate that the simplex search method is a reasonable and effective method for PID controller parameters tuning and optimization.展开更多
The paper presents an approach for avoiding and minimizing the complementary pivots in a simplex based solution method for a quadratic programming problem. The linearization of the problem is slightly changed so that ...The paper presents an approach for avoiding and minimizing the complementary pivots in a simplex based solution method for a quadratic programming problem. The linearization of the problem is slightly changed so that the simplex or interior point methods can solve with full speed. This is a big advantage as a complementary pivot algorithm will take roughly eight times as longer time to solve a quadratic program than the full speed simplex-method solving a linear problem of the same size. The strategy of the approach is in the assumption that the solution of the quadratic programming problem is near the feasible point closest to the stationary point assuming no constraints.展开更多
The Grey Wolf Optimization(GWO)algorithm is acknowledged as an effective method for rock acoustic emission localization.However,the conventional GWO algorithm encounters challenges related to solution accuracy and con...The Grey Wolf Optimization(GWO)algorithm is acknowledged as an effective method for rock acoustic emission localization.However,the conventional GWO algorithm encounters challenges related to solution accuracy and convergence speed.To address these concerns,this paper develops a Simplex Improved Grey Wolf Optimizer(SMIGWO)algorithm.The randomly generating initial populations are replaced with the iterative chaotic sequences.The search process is optimized using the convergence factor optimization algorithm based on the inverse incompleteГfunction.The simplex method is utilized to address issues related to poorly positioned grey wolves.Experimental results demonstrate that,compared to the conventional GWO algorithm-based AE localization algorithm,the proposed algorithm achieves a higher solution accuracy and showcases a shorter search time.Additionally,the algorithm demonstrates fewer convergence steps,indicating superior convergence efficiency.These findings highlight that the proposed SMIGWO algorithm offers enhanced solution accuracy,stability,and optimization performance.The benefits of the SMIGWO algorithm extend universally across various materials,such as aluminum,granite,and sandstone,showcasing consistent effectiveness irrespective of material type.Consequently,this algorithm emerges as a highly effective tool for identifying acoustic emission signals and improving the precision of rock acoustic emission localization.展开更多
基金supported by the National Natural Science Foundation of China(70771080)the Special Fund for Basic Scientific Research of Central Colleges+2 种基金China University of Geosciences(Wuhan) (CUG090113)the Research Foundation for Outstanding Young TeachersChina University of Geosciences(Wuhan)(CUGQNW0801)
文摘A global convergent algorithm is proposed to solve bilevel linear fractional-linear programming, which is a special class of bilevel programming. In our algorithm, replacing the lower level problem by its dual gap equaling to zero, the bilevel linear fractional-linear programming is transformed into a traditional sin- gle level programming problem, which can be transformed into a series of linear fractional programming problem. Thus, the modi- fied convex simplex method is used to solve the infinite linear fractional programming to obtain the global convergent solution of the original bilevel linear fractional-linear programming. Finally, an example demonstrates the feasibility of the proposed algorithm.
基金supported by Chongqing Municipal Natural Science Foundation of General Program(CSTB2022NSCQMSX1093)the Science and Technology Research Program of Chongqing Municipal Education Commission(Grant No.KJQN202200701)China Postdoctoral Science Foundation(2021M703487).
文摘Two-Line Element(TLE)datasets are the only orbital data source of Earth-orbiting space objects for many civil users for their research and applications.The datasets have uneven qualities that may affect the reliability of the propagated positions of space objects using a single TLE.The least squares approach to use multiple TLEs also suffers from the poor quality of some TLEs,and reliable error information cannot be available.This paper proposes a simplex algorithm to estimate an optimal TLE from multiple TLEs and obtain the uncertainty of each element.It is a derivative-free technique that can deal with various orbit types.Experiments have demonstrated that using the TLE estimated from the simplex method is more reliable,stable,and effective than those from the batch least squares method.As an application example,the optimal TLE and its uncertainty are used for predicting the fallen area,keeping the actual fallen site in the prediction areas.
文摘This work presents an application of the Simplex Method for solving an optimal planning problem for cancer treatment by radiotherapy. Linear Programming can aid the optimal planning for radiation therapy, where the concern is to apply a high enough radiation in the tumor while saving significantly healthy regions or critical organs.
文摘In this paper, a new hybrid algorithm based on exploration power of a new improvement self-adaptive strategy for controlling parameters in DE （differential evolution） algorithm and exploitation capability of Nelder-Mead simplex method is presented （HISADE-NMS）. The DE has been used in many practical cases and has demonstrated good convergence properties. It has only a few control parameters as number of particles （NP）, scaling factor （F） and crossover control （CR）, which are kept fixed throughout the entire evolutionary process. However, these control parameters are very sensitive to the setting of the control parameters based on their experiments. The value of control parameters depends on the characteristics of each objective function, therefore, we have to tune their value in each problem that mean it will take too long time to perform. In the new manner, we present a new version of the DE algorithm for obtaining self-adaptive control parameter settings. Some modifications are imposed on DE to improve its capability and efficiency while being hybridized with Nelder-Mead simplex method. To valid the robustness of new hybrid algorithm, we apply it to solve some examples of structural optimization constraints.
基金This work is supported by the NSF of China,No.10371017NSF Grant of Hangzhou Dianzi University KYS091504025.
文摘A new partial pricing column rule is proposed to the basis-deficiency-allowing simplex method developed by Pan.Computational results obtained with a set of small problems and a set of standard NETLIB problems show its promise of success.
文摘In this study we discuss the use of the simplex method to solve allocation problems whose flow matrices are doubly stochastic. Although these problems can be solved via a 0 - 1 integer programming method, H. W. Kuhn [1] suggested the use of linear programming in addition to the Hungarian method. Specifically, we use the existence theorem of the solution along with partially total unimodularity and nonnegativeness of the incidence matrix to prove that the simplex method facilitates solving these problems. We also provide insights as to how a partition including a particular unit may be obtained.
文摘This study adopts the Dantzig’s Simplex method to investigate optimization of sand casting parameters for optimum service performance. Some process variables and mechanical properties were adapted into the Simplex method. Aluminium alloy samples were cast, machined and subjected to a series of mechanical tests. From the body of data collected, linear functions and constraint equations were formulated and employed in the Dantzig’s Simplex method for optimization of process parameters. The results showed that the Simplex method can be adapted for studying performance opti- mization of castings.
基金supported by National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Based on the existing pivot rules,the simplex method for linear programming is not polynomial in the worst case.Therefore,the optimal pivot of the simplex method is crucial.In this paper,we propose the optimal rule to find all the shortest pivot paths of the simplex method for linear programming problems based on Monte Carlo tree search.Specifically,we first propose the SimplexPseudoTree to transfer the simplex method into tree search mode while avoiding repeated basis variables.Secondly,we propose four reinforcement learning models with two actions and two rewards to make the Monte Carlo tree search suitable for the simplex method.Thirdly,we set a new action selection criterion to ameliorate the inaccurate evaluation in the initial exploration.It is proved that when the number of vertices in the feasible region is C_(n)^(m),our method can generate all the shortest pivot paths,which is the polynomial of the number of variables.In addition,we experimentally validate that the proposed schedule can avoid unnecessary search and provide the optimal pivot path.Furthermore,this method can provide the best pivot labels for all kinds of supervised learning methods to solve linear programming problems.
基金This work was partially supported by the Doctoral Foundation of Hebei University(Grant No.Y2006084)the National Natural Science Foundation of China(Grant No.10231060)
文摘In this paper, we investigate the quadratic approximation methods. After studying the basic idea of simplex methods, we construct several new search directions by combining the local information progressively obtained during the iterates of the algorithm to form new subspaces. And the quadratic model is solved in the new subspaces. The motivation is to use the information disclosed by the former steps to construct more promising directions. For most tested problems, the number of functions evaluations have been reduced obviously through our algorithms.
基金supported by the National Natural Science Foundation of China(Grant No.11503096)the State Key Laboratory of Geo-information Engineering(Grant No.SKLGIE2014-M-2-3)
文摘A simplex method of orbit determination （SMOD） is presented to solve the problem of orbit determination for maneuvering satellites subject to small and continuous thrust. The objective function is established as the sum of the nth powers of the observation errors based on global positioning satellite （GPS） data. The convergence behavior of the proposed method is analyzed using a range of initial orbital parameter errors and n values to ensure the rapid and accurate convergence of the SMOD. For an uncontrolled satellite, the orbit obtained by the SMOD provides a position error compared with GPS data that is commensurate with that obtained by the least squares technique. For low Earth orbit satellite control, the precision of the acceleration produced by a small pulse thrust is less than 0.1% compared with the calibrated value. The orbit obtained by the SMOD is also compared with weak GPS data for a geostationary Earth orbit satellite over several days. The results show that the position accuracy is within 12.0 m. The working efficiency of the electric propulsion is about 67% compared with the designed value. The analyses provide the guidance for subsequent satellite control. The method is suitable for orbit determination of maneuvering satellites subject to small and continuous thrust.
文摘The branch-and-bound method with the revised dual simplex for bounded variables is very effective in solving relatively large-size integer linear programming problems. This paper, based on the general forms of the penalties by Beale and Small and the stronger penalties by Tomlin, describes the modifications of these penalties used for the method of bounded variables. The same examples from Petersen are taken and the satisfactory results are shown in comparison with those obtained by Tomlin.
文摘目的 Linear Programming的simplexmethod建模求最优解。方法应用simplexmethod.结果建立了LinearProgramming的数学模型并用simplexmethod求得了最优解.结论因为单纯形表反映了Linear Programming的所有信息,故用simplexmethod可简便地求得最优解.simplexmethod的基本思路是:先将Linear Programming用sim-plexmethod划为标准型,根据问题的标准型,进行初等行变换,将主元素列除主元素化为1外其余的元素均化为0,当基变量值全为非负时,问题就得到了最优解.
基金science fund for middle age and young scholar of Ministry of Posts andTelecommunications, P. R. China
文摘Since the simplex method[1]of linear programming was established in 1947. It has been im proving unceasingly. But a major breakthrough has not been been,only a little quantity of computation was decreased. In this paper,the computation of the first stage of artificial basis method[l] is omited. Therefore, computational quantity is decreased greatly.
基金Project(2011467001)supported by the Ministry of Environment Protection of ChinaProject(2010DFB94130)supported by the Ministry of Science and Technology of China
文摘For physical ozone absorption without reaction,two parametric estimation methods,i.e.the common linear least square fitting and non-linear Simplex search methods,were applied,respectively,to determine the ozone mass transfer coefficient during absorption and both methods give almost the same mass transfer coefficient.While for chemical absorption with ozone decomposition reaction,the common linear least square fitting method is not applicable for the evaluation of ozone mass transfer coefficient due to the difficulty of model linearization for describing ozone concentration dissolved in water.The nonlinear Simplex method obtains the mass transfer coefficient by minimizing the sum of the differences between the simulated and experimental ozone concentration during the whole absorption process,without the limitation of linear relationship between the dissolved ozone concentration and absorption time during the initial stage of absorption.Comparison of the ozone concentration profiles between the simulation and experimental data demonstrates that Simplex method may determine ozone mass transfer coefficient during absorption in an accurate and high efficiency way with wide applicability.
文摘A PID parameters tuning and optimization method for a turbine engine based on the simplex search method was proposed. Taking time delay of combustion and actuator into account, a simulation model of a PID control system for a turbine engine was developed. A performance index based on the integral of absolute error （IAE） was given as an objective function of optimization. In order to avoid the sensitivity that resulted from the initial values of the simplex search method, the traditional Ziegler-Nichols method was used to tune PID parameters to obtain the initial values at first, then the simplex search method was applied to optimize PID parameters for the turbine engine. Simulation results indicate that the simplex search method is a reasonable and effective method for PID controller parameters tuning and optimization.
文摘The paper presents an approach for avoiding and minimizing the complementary pivots in a simplex based solution method for a quadratic programming problem. The linearization of the problem is slightly changed so that the simplex or interior point methods can solve with full speed. This is a big advantage as a complementary pivot algorithm will take roughly eight times as longer time to solve a quadratic program than the full speed simplex-method solving a linear problem of the same size. The strategy of the approach is in the assumption that the solution of the quadratic programming problem is near the feasible point closest to the stationary point assuming no constraints.
基金support from the National Science Foundation of China(52304137,5192780752274124,52325403)Tiandi Science and Technology Co.,Ltd.(2022-2-TDMS012 and SKLIS202417)Sichuan University(SKHL2215).
文摘The Grey Wolf Optimization(GWO)algorithm is acknowledged as an effective method for rock acoustic emission localization.However,the conventional GWO algorithm encounters challenges related to solution accuracy and convergence speed.To address these concerns,this paper develops a Simplex Improved Grey Wolf Optimizer(SMIGWO)algorithm.The randomly generating initial populations are replaced with the iterative chaotic sequences.The search process is optimized using the convergence factor optimization algorithm based on the inverse incompleteГfunction.The simplex method is utilized to address issues related to poorly positioned grey wolves.Experimental results demonstrate that,compared to the conventional GWO algorithm-based AE localization algorithm,the proposed algorithm achieves a higher solution accuracy and showcases a shorter search time.Additionally,the algorithm demonstrates fewer convergence steps,indicating superior convergence efficiency.These findings highlight that the proposed SMIGWO algorithm offers enhanced solution accuracy,stability,and optimization performance.The benefits of the SMIGWO algorithm extend universally across various materials,such as aluminum,granite,and sandstone,showcasing consistent effectiveness irrespective of material type.Consequently,this algorithm emerges as a highly effective tool for identifying acoustic emission signals and improving the precision of rock acoustic emission localization.
