运输问题表上作业法的一点注记

表上作业法是运输问题的经典算法,然而按照表上作业法闭回路构建方法有时竟然不能成功,为此本文重新设计了新的闭回路构建方法,改进了表上作业法.     

平衡和不平衡运输问题与分配问题的通用迭代算法

将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。     

关于L~1空间积分方程特征值探究

在L~1空间中讨论积分方程的特征值问题,利用连续函数的性质,对已有的部分离散法进一步改进,并举出具体算例将两种算法通过Matlab作图进行对比,说明改善后的部分离散法求出的数值解更佳.     

最佳粮库地址的选择

管理部门通常要选择适当的地方建造粮库 ,所需服务范围已知 ,各部门运输量给定 .需为他们选择合适的地方 ,使总运费最少 .某乡的九个村 (A,B,C,… ,H,I)如图 1 ,各村距离给出 ,并标明它们各自上缴公粮数 .管理部门希望在村内或道路上建立一个粮库 ,最大限度地减少运输费用 .问题的解法有几种方案 ,对于本题来说 ,穷举搜索法是可行的 .另外 ,我们提出一种分析求解法 ,可找到优化解 .它利用图论的基础知识先求出图 1的各顶点间的最小路径 ,再进一步求出图的绝对中心 (即粮库的地址 ) ,其中的有关计算利用了 C++语言程序 .在此基础上 ,还可对问题的参数作更精细的分析 .概括地说 ,穷举搜索法对于简单的区域是行之有效的 .但对于更加一般化的问题 ,利用计算机可快捷准确地得到答案 .通过建立模型 ,我们得到下面两个结论 :(1 )我们找到最优解是 E点 ,其总运费为 1 2 775元 .(2 )模型具有广泛性 ,对于更一般的区域 ,可利用计算机总可以求出最优解 .     

可分离的二次背包问题的一种直接算法

研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题（P1）和（P2）.重点是求解（P2）问题的最优解,通过分析（P2）问题的结构特点,假设固定一次项后问题的最优解和相应不等式的拉格朗日乘子已求出,通过比较拉格朗日乘子和（P2）问题的一次项系数来调节λ的大小,从而求出（P2）问题的最优解.对于（P1）问题,改进了Bretthauer和Shetty给出的算法（Bretthauer K M,Shetty B.A pegging algorithm for the nonlinear resource allocation problem.Computers and Operations Research,2002,29（5）：505-527）.此算法的计算复杂性为O（n）.数值算例表明,将这种固定变量算法和文中的定理5结合起来,能够快速有效地求解此类更一般的二次背包问题.     

指派问题的表上作业解法

解极小化的指派问题常用匈牙利解法,但我们从指派问题的数学模型的特征中发现,它还可以采用解运输问题的表上作业法去求解,中通过实例说明其算法,并且可以看出这种解法与匈牙利方法一样简单方便。     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

有界变量线性规划的基线算法

本文对有界变量线性规划的算法进行了研究，得到了一种解此问题的新算法。文中根据基线算法的算法原理，通过对BL表的旋转，在各变量满足界约束的条件下，使目标函数值不断增大，直至得到有界硬上界，从而得到问题的最优解。文中给出了有界变量线性规划基线算法的计算步骤，并给出了一个例子。与单纯形法相比，采用基线算法解有界变量线性规划操作更简单。迭代次数少，解题速度更快。     

一种用于线性规划算法的换基准则

本文就线性规划中的对偶单纯形法和运输问题中的表上作业法选取出基变量或者对基变量的准则进行改进,从而得出一种新的换基准则.按该方法进行优化运算,可以使算法的迭代次数减到最少,从而加快了运算速度.     

支持向量机中一种参数优化选取方法

本文给出一种支持向量机中的参数优化选取方法. 它是通过遗传算法和确定性算法相结合解平衡约束优化问题,求出二分类支持向量机(SVM)中的正则参数C,本文将C作为优化问题中的变量来处理.遗传算法用来求解以C为变量的优化问题, 而确定性算法对每一个C值求解约束.数值计算的结果表明,用文中所述的方法求得的C值能明显提高支持向量机的泛化性能.     

A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems

In this study, we improved the variable neighborhood search (VNS) algorithm for solving uncapacitated multilevel lot-sizing (MLLS) problems. The improvement is twofold. First, we developed an effective local search method known as the Ancestors Depth-first Traversal Search (ADTS), which can be embedded in the VNS to significantly improve the solution quality. Second, we proposed a common and efficient approach for the rapid calculation of the cost change for the VNS and other generate-and-test algorithms. The new VNS algorithm was tested against 176 benchmark problems of different scales (small, medium, and large). The experimental results show that the new VNS algorithm outperforms all of the existing algorithms in the literature for solving uncapacitated MLLS problems because it was able to find all optimal solutions (100%) for 96 small-sized problems and new best-known solutions for 5 of 40 medium-sized problems and for 30 of 40 large-sized problems.     

A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem

This paper presents an efficient solution algorithm for the multiconstraint zero-one knapsack problem through a branch and bound search process. The algorithm has been coded in FORTRAN; and a group of thirty 5-constraint knapsack problems with 30-90 variables were run on IBM 360/75 using two other codes as well, in order to compare the computational efficiency of the proposed method with that of the original Balas and an improved Balas additive algorithms. The computational results show that the proposed method is markedly faster with regard to the total as well as the individual solution times for these test problems, and such superiority becomes more evident as the number of variables and the difficulty of the problems increase. The results also indicated that the original Balas method is extremely inefficient for the type of problems being considered here. The total solution time for the thirty problems is 13 min for the proposed method, 109 min for the improved Balas algorithm, and over 380 min for the original Balas algorithm. Extension of the solution algorithm to the generalized knapsack problem is also suggested.     

Observer-based robust adaptive variable universe fuzzy control for chaotic system

A novel observer-base output feedback variable universe adaptive fuzzy controller is investigated in this paper. The contraction and expansion factor of variable universe fuzzy controller is on-line tuned and the accuracy of the system is improved. With the state-observer, a novel type of adaptive output feedback control is realized. A supervisory controller is used to force the states to be within the constraint sets. In order to attenuate the effect of both external disturbance and variable parameters on the tracking error and guarantee the states to be within the constraint sets, a robust controller is appended to the variable universe fuzzy controller. Thus, the robustness of system is improved. By Lyapunov method, the observer-controller system is shown to be stable. The overall adaptive control algorithm can guarantee the global stability of the resulting closed-loop system in the sense that all signals involved are uniformly bounded. In the paper, we apply the proposed control algorithms to control the Duffing chaotic system and Chua’s chaotic circuit. Simulation results confirm that the control algorithm is feasible for practical application.     

Optimal control of bioprocess systems using hybrid numerical optimization algorithms

In the paper, we consider the bioprocess system optimal control problem. Generally speaking, it is very difficult to solve this problem analytically. To obtain the numerical solution, the problem is transformed into a parameter optimization problem with some variable bounds, which can be efficiently solved using any conventional optimization algorithms, e.g. the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. However, in spite of the improved Broyden–Fletcher–Goldfarb–Shanno algorithm is very efficient for local search, the solution obtained is usually a local extremum for non-convex optimal control problems. In order to escape from the local extremum, we develop a novel stochastic search method. By performing a large amount of numerical experiments, we find that the novel stochastic search method is excellent in exploration, while bad in exploitation. In order to improve the exploitation, we propose a hybrid numerical optimization algorithm to solve the problem based on the novel stochastic search method and the improved Broyden–Fletcher–Goldfarb–Shanno algorithm. Convergence results indicate that any global optimal solution of the approximate problem is also a global optimal solution of the original problem. Finally, two bioprocess system optimal control problems illustrate that the hybrid numerical optimization algorithm proposed by us is low time-consuming and obtains a better cost function value than the existing approaches.     

改进鲸鱼优化算法在电力负荷调度中的应用

为了提高鲸鱼优化算法(WOA)的全局优化性能, 提出了一种基于黄金分割搜索的改进鲸鱼优化算法(GWOA)。首先利用黄金分割搜索对WOA的初始种群进行初始化, 使得初始种群能够尽可能的靠近全局最优解, 然后利用黄金分割搜索所形成的变区间, 进行变区间黄金分割非均匀变异操作, 以增加WOA的粒子多样性和提高粒子跳出局部最优陷阱的能力, 从而改善WOA的寻优性能。选取了15个大规模测试函数进行数值仿真测试, 仿真结果和统计分析表明GWOA的寻优性能要优于对比文献的改进鲸鱼优化算法(IWOA)。此外, 将GWOA用于对工程实际应用领域中的电力负荷优化调度问题进行实例分析, 实例应用结果表明, GWOA能有效对电力负荷优化调度问题进行寻优求解。     

A dynamic genetic algorithm based on continuous neural networks for a kind of non-convex optimization problems

This paper presents a kind of dynamic genetic algorithm based on a continuous neural network, which is intrinsically the steepest decent method for constrained optimization problems. The proposed algorithm combines the local searching ability of the steepest decent methods with the global searching ability of genetic algorithms. Genetic algorithms are used to decide each initial point of the steepest decent methods so that all the initial points can be searched intelligently. The steepest decent methods are employed to decide the fitness of genetic algorithms so that some good initial points can be selected. The proposed algorithm is motivated theoretically and biologically. It can be used to solve a non-convex optimization problem which is quadratic and even more non-linear. Compared with standard genetic algorithms, it can improve the precision of the solution while decreasing the searching scale. In contrast to the ordinary steepest decent method, it can obtain global sub-optimal solution while lessening the complexity of calculation.     

A hybrid metaheuristic algorithm for dynamic rail car fleet sizing problem

The aim of this paper is to present a model and a solution method for rail freight car fleet sizing problem. The mathematical model is dynamic and multi-periodic and car demands and travel times are assumed deterministic, and the proposed solution method is hybridization of genetic algorithms and simulated annealing algorithms. Experimental analysis is conducted using several test problems. The results of the proposed algorithm and CPLEX software are compared. The results show high efficiency and effectiveness of the proposed algorithm. The solution method is applied to solve fleet sizing problem in the Iran Railways as a case study.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

改进二元分布估计算法求解置换流水车间调度问题

针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm, I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。     

Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.