N车探险问题的一种ε-近似度的近似算法  

A Kind ofε-approximation Algorithm for the Exploration Problem with N Vehicles

作　　者：徐扬扬[1] 崔晋川[1] 

机构地区：[1]中国科学院数学与系统科学研究院应用数学研究所,北京100190

出　　处：《应用数学学报》2009年第6期1036-1043,共8页Acta Mathematicae Applicatae Sinica

基　　金：国家973计划(2006CB701306);中国科学院管理;决策与信息系统重点实验室基金资助项目

摘　　要：本文探讨了一类N车探险问题的近似算法,首先通过建模将N车问题转变为一个等价的非线性0-1混合整数规划问题,进而将该非线性0-1混合整数规划问题转化为一个一般的带约束非线性规划问题,并用罚函数的方法将得到的带约束非线性规划问题化为相应的无约束问题.我们证明了可通过求解该无约束非线性规划问题得到原N车问题的ε-近似度的近似解,并设计了一个收敛速度为二阶的迭代算法,文章最后给出算法实例.This paper studies a kind of approximation algorithm for the exploration problem with N vehicles. By modeling, the authors transform the original exploration problem to a nonlinear 0-1 mixed integer programming problem. Based on this model, then the authors transform it to a corresponding constrained nonlinear programming problem of the common style. After that, we transform it to a non-constrained nonlinear programming problem,with the method of penalizing function. At the same time, we prove that we could attain an ε-approximation solution by solving this non-constrained nonlinear programming problem, and design an iteration algorithm with 2-rate of convergence. Numerical examples are stated at last.

关 键 词：探险问题 N车问题 0-1混合整数规划问题 罚函数 ε-近似度的近似解 

分 类 号：O212.7[理学—概率论与数理统计]