0-1型整数线性规划问题及在金融领域中的应用开题报告

整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划，是近三十年来发展起来的、规划论的一个分支。整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。变量全部或部分取整数的线性规划统称为整数线性规划（Integer Programming，简记为IP）。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。纯整数规划中的一种特殊情形是0-1整数规划，它的变量仅限于0或1。

0-1型整数规划是整数规划的特例，其数学模型的目标函数、约束条件与线性规划相同，不同的是其变量只能取0和1，分别表示两种截然相反的结果。0-1型整数规划应用很广，如背包问题，推销商问题，土木工程系统的最优工程配置问题，城建规划中的居民点、给水点、加油站和商业网点的最优布局问题，均可应用0- 1 型整数规划求得最优解。除此之外，它不仅在在工业、工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有许多新的应用，因此去研究整数线性规划的这种特殊规划对我们的生活和今后的研究都有着重要的意义。

之前也有很多学者教授研究过整数线性规划的算法，各种研究都各具特色，本文在前人的基础上进一步进行研究，尝试对0-1整数规划的几种常用算法进行探究。

(一)研究的内容

0-1整数规划是整数规划中的一种特殊情况，在整数规划中占有重要地位，许多实际问题都可归结为0-1整数规划进行研究。所以研究0-1整数规划具有重要的学术和生活意义。论文主要内容大致如下：

（1）介绍0-1整数规划的研究背景及意义，以及目前国内外研究现状、发展动态，介绍本文的主要研究内容。

（2）介绍0-1整数规划的相关概念、特点及其作用。

（3）研究求解0-1整数规划的穷举法、两种常用的隐枚举法以及进行改进的隐枚举法、组合直接搜寻法，对每种方法进行算法分析，实例运用，最后对不同的算法进行了评价。

整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。0-1整数规划不仅在整数规划中有着重要地位，因为像很多指派、选址、送货问题都可以用0-1整数规划来进行求解；另一方面，0-1整数规划还可以把许多非线性的规划问题转化为线性规划问题，大大简化对问题的求解。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。

国内外也有许多学者对求解0-1整数规划问题提出自己各自的看法。比如混沌遗传算法，采用幂函数载波技术提高混沌搜索的充分性与遍历性，以混沌搜索算法得出的优化个体作为遗传算法的新群体进行交叉、变异等操作，这种算法被用于解决片上网络映射A3MAP( architecture-aware analytic mapping) 0-1 整数规划问题，实验仿真证明，该算法的收敛速度和解的精度均优于A3MAPGA；再例如基于三螺旋结构的DNA链的独特结构，殷志祥首次将DNA计算应用到0-1整数规划问题的求解中并提出了生物算法；还有在Kenna和Erhard的二进制粒子群算法（BPSO）的基础上提出一种改进的二进制粒子群算法（IBPSO），在背包问题上的计算结果表明，与遗传算法相比，IBPSO具有更快的收敛速度。目前，用于求解0-1整数规划的几种通用方法为穷举法、隐枚举法、组合直接搜寻法。

[1]刁在筠，刘桂真.运筹学（第三版）[M].北京：高等教育出版社，2007

[2]张香云.线性规划[M].浙江：浙江大学出版社，2009

[3]张雅琴，王希云.分支定界法在最优化问题中的应用[J].经济技术协作信息，2007

[4]Ultrapatriotic C H,StieglitzK.Combinatorial Optimization:Algorithms and Complexity[M].NewJersey:Prentice-Hall,1982

[5]苟格.整数规划中的割平面法与分支定界法比较[J].达县师范高等专科学校学报（自然科学版），2005,15(2):18-21

[6]徐义春，肖人斌.一种改进的二进制粒子群算法.模式识别与人工智能，2007,2（6）：787-793

[7]祈荣宾，冯汝鹏.求解一类0-1整数规划问题的新方法--混沌搜索算法.控制与决策，2003,18（6）：712-715

[8]吴黎军，张华孝.一类0-1整数规划问题的单纯形解法.数学的实践与认识，2005，（3）：216-219

[9]李时.求解0-1整数规划的一种新方法--分层优选法.吉林工业大学学报，1993，（3）：110-116

[10]高培旺，范国兵.0-1整数线性规划的一种组合直接搜寻法.苏州科技学院学报（自然科学版），2004,21（1）：22-26

[11]Kennedy J,Esterhazy R C.ParticleSwarm Optimization,Proc of the IEEE International Conference on the NeuralNetworks.Perth,Australia,1995,IV:73-79

[12]Yin Z X,Shang F Y,Xu J.Thegeneral from of 0-1 programming problem based on the DNAcomputing.Bio-systems,2003,70(1):73-79

[13]Li Juan,Fang Ping,Zhou Ming.AHybrid Genetic Algorithm for Knapsack Problem.Journal of Nanchang Instituteof Aeronautical Technology,1998,12(3):31-35