整数规划问题--毕业论文.doc

该【整数规划问题--毕业论文 】是由【久阅文学】上传分享，文档一共【35】页，该文档可以免费在线阅读，需要了解更多关于【整数规划问题--毕业论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。整数规划问题--毕业论文
目录
摘要 I
Abstract II
引言 1
1整数规划问题 1
1
2
2
2整数规划问题的计算方法 2
2
3
3整数规划问题的应用 4
4
4
6
10
12
12
14
17
20
20
21
23
24
(TSP) 26
结论 27
致谢 27
参考文献 28
II
I
II
I
Applicationofintegerprogrammingproblems
Abstract:Integerprogrammingisanoptimizationproblemwithintegervariables,whichmaximizeorminimizethemultiplefunctionsoffullorpartialvariablesforinteger,,mainlyduetoalargenumberofproblemsineconomicmanagementbeabstractedasamodel,itisfoundthatmanyareinseparable,thereforewhentheyaretakenasvariablesintotheplanning,,manyoptimizationproblemswithintegerofeconomic,management,communicationandengineeringcanbeusetobuildmodel.
Thispaperdiscussesthetheoreticalbasisofintegerprogramming,
II
II
.Finally,,andfurtherimproveandenrichintegerprogrammingtheory.
Keywords:IntegerProgramming;Practicalapplication;0-1integerlinearprogramming;Mathematicalmodel
II
II
引言
整数规划(IntegerProgramming,IP)是规划论中近30年才发展起来一个重要分支。整数规划与组合最优化从广泛的意义上说,两者的领域是一致的,都是在有限个可供选择的方案中,寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如,背包(或装载)问题、固定费用问题、有效探险队问题(组合学的覆盖问题)、送货问题等。因此整数规划的应用范围是极其广泛的。它不仅在工业、工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。
此外,整数规划还可以描述和处理互斥决策问题。如运作管理中的决策问题:工厂选址、超市选址、人员的工作指派、设备购置和配置、系统可靠性设计、机床加工任务的均衡分派、线路设计中的接点串联设计等;物流管理中,物流中心的定点决策;以及金融和项目投资中的组合投资和项目选择等等。其规划模型中往往可以引入逻辑变量(即变量仅取0或1两个值)来反映冲突因素和抉择。另外,整数规划还可以实现不相容状态下,分散模型的模式统一,加强系统研究的集成性。
因此,整数规划模型不同于前述的线性规划范畴,而属于一种新的类型。整数规划在实践中有比线性规划更为广泛的应用空间,对整数规划问题的探究是十分有必要的。
1整数规划问题

要求一部分或全部决策变量必须取整数值的规划问题称为整数规划(integerprogramming,简记IP)。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题(slackproblem)。若松弛问题是一个线性规则,则称该整数规划为整数线性规划(integerlinearprogramming,简记ILP)

整数规划问题按决策变量取值可分为下列几种类型:
(pureintegerprogramming):指全部决策变量都必须取整数值的整数规划。有时,也称为全整数规划。
(mixedintegerprogramming):指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数规划。
-1型整数规划(zero—oneintegerprogramming):指决策变量只能取值0或1的整数规划。

2整数规划问题的计算方法

分支定界法是在20世纪60年代初由LandDoing和Dakin等人提出的适合于解纯整数或混合整数规划问题的方法。
分支定界法的主要思路是首先求解整数规划的伴随规划,如果求得的最优解不符合整数条件,则增加新约束——缩小可行域;将原整数规划问题分支——分为两个子规划,再解子规划的伴随规划,以此类推,最后得到原整数规划的伴随规划。这就是所谓的“分支”。
所谓“定界”,是在分支过程中,若某个后继问题恰巧获得整数规划问题的一个可行解,那么,它的目标函数值就是一个“界限”,可以作为衡量处理其它分支的一个依据。
“分支”为整数规划最优解的出现创造了条件,而“定界”则可以提高搜索的效率。
分支定界法的计算步骤
第一步:计算原问题目标函数值的初始上界
第二步:计算原问题目标函数值的初始下界
第三步:增加约束条件将原问题分支
第四步:分别求解一对分支
第五步:修改上、下界
第六步:比较上、下界大小,如有上界=下界,停止计算,找到最优解,否则转3

割平面法由高莫瑞(Gomory)于1958年提出。其基本思想是放宽变量的整数约束,首先求对应的松弛问题最优解,当某个变量不满足整数约束时,寻找一个约束方程并添加到松弛问题中,其作用是割掉非整数部分,缩小原松弛问题的可行域,最后逼近整数问题的最优解。
增加的新约束称为割平面方程或切割方程
(1)设是相应线性规划最优解中为分数值的一个基变量,则由单纯形表的最终表得到
()
(2)将拆分成整数部分N和非负真分数之和,即:
()
表示不超过的最大整数。
将()式代入(1)式
()
其中,
就是割平面方程的最基本形式。
割平面法解整数规划问题的基本步骤
第一步:用单纯形法解松弛问题,得到最优单纯形表。
第二步:求一个割平面方程,加到最优单纯形表中,用对偶单纯形法继续求解。
第三步:若没有得到整数最优解,则继续作割平面方程,转第二步。
3整数规划问题的应用


设有个投资项目及年内逐年投入资金矩阵,其中为第年的投资金额,以及投资矩阵,其中为第年项目所需投入资金。利润矩阵,为项目的利润。
投资问题即在提供的资金的容许条件下,求利润最高的投资决策。
设