扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
宇宙、量子和人类心灵
-
>
考研数学专题练1200题
-
>
希格斯:“上帝粒子”的发明与发现
-
>
神农架叠层石:10多亿年前远古海洋微生物建造的大堡礁
-
>
二十四史天文志校注(上中下)
-
>
声音简史
-
>
浪漫地理学:追寻崇高景观
整数规划:基础、扩展及应用 版权信息
- ISBN：9787030720641
- 条形码：9787030720641 ; 978-7-03-072064-1
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>
整数规划:基础、扩展及应用 本书特色
适读人群 ：高等院校经济管理类和理工类等专业本科生、研究生的必修教材，又可作为研究人员、专业人员整数规划历史可以追溯到20世纪50年代,美国学者丹齐格（G.B. Dantzig）首次发现可以通过0-1变量来刻画优化模型中的固定费用、变量上界、非凸分片线性函数等.此后, 丹齐格等对旅行商问题(traveling salesman problem,TSP)的研究,成为分支定界法和现代混合整数规划算法的开端. 1958年,戈莫里（R.E.Gomory）提出了求解一般整数线性规划模型的收敛算法——割平面方法,至此整数规划成为优化领域的一个独立分支. ?随着整数规划理论和算法的不断发展以及计算机计算速度和功能的迅猛提升,整数规划已逐渐成为应用*广泛的优化方法之一,在社会、军事、生物、计算机以及经济等各大领域得到了更广泛的应用和长足的发展. 《整数规划：基础、扩展及应用》是电子科技大学、四川大学、中国科学技术大学三位教授多年一线教学经验的总结，作为整数规划课程教材本书聚焦于大规模整数规划模型的求解方法和策略, 深入浅出地阐明了求解大规模整数规划模型主流方法的基本思想、原理、执行步骤以及在实际问题中的应用,是一本研究性与教学性并重的专业教材.
整数规划:基础、扩展及应用 内容简介
整数规划是运筹学与优化领域中一个极其重要的研究方向，整数规划理论和方法在管理科学、工业工程、金融工程、经济和其他领域有着广泛的应用。本书是整数规划领域的入门与提高教材，注重理论与实际相结合，紧密结合经济管理类专业的特点，系统、深入地讲述求解大规模整数规划问题的主流方法与理论，符号新工科人才培养理念与要求，是一本凸显前沿性、交叉性与综合性的教材。全书共分为引言、整数规划模型、线性规划、准确离散优化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders分解算法和启发式算法共9章，每章都加入了众多案例，涉及算法和分析都配有计算练习并介绍了相关阅读材料。本书主要介绍求解大规模整数规划问题的主流方法与理论。全书共分为引言、整数规划模型、线性规划、准确离散优化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders分解算法和启发式算法共9章。
整数规划:基础、扩展及应用 目录
目录
前言
第1章 引言 1
1.1 *优化 1
1.2 整数规划 2
1.3 整数规划的发展历程 4
1.3.1 模型和应用角度 4
1.3.2 模型求解角度 5
1.4 整数规划的求解软件 6
1.5 本书结构 8
第2章 整数规划建模 9
2.1 背包模型 9
2.1.1 模型介绍 9
2.1.2 应用实例 10
2.2 广义指派模型 14
2.2.1 模型介绍 14
2.2.2 应用实例 15
2.3 集合包装、覆盖和划分模型 18
2.3.1 模型介绍 18
2.3.2 应用实例 18
2.4 含固定成本的整数规划模型 27
2.4.1 设施选址模型 28
2.4.2 网络设计模型 32
2.5 旅行商模型 36
2.5.1 模型介绍 36
2.5.2 模型应用 39
习题二 42
第3章 线性规划 44
3.1 线性规划的规范型 44
3.1.1 线性规划模型的一般形式 44
3.1.2 线性规划模型的标准型 44
3.1.3 线性规划模型的规范型 45
3.1.4 线性规划模型的矩阵形式 48
3.2 线性规划的基本定理 50
3.2.1 凸集与极点 50
3.2.2 基本定理 52
3.3 单纯形法 56
3.3.1 单纯形法的思想 56
3.3.2 单纯形法的步骤 56
3.3.3 单纯形法一般步骤 63
3.3.4 单纯形法的矩阵形式 64
3.4 对偶理论 66
3.4.1 对偶问题的基本形式 66
3.4.2 对偶问题的性质 69
3.4.3 对偶问题的经济学解释 71
3.4.4 对偶单纯形法 73
习题三 77
第4章 精确离散优化方法 84
4.1 全枚举法 84
4.1.1 全枚举法介绍 84
4.1.2 全枚举法复杂度分析 85
4.2 模型松弛 86
4.3 分支定界 89
4.3.1 分支定界介绍 89
4.3.2 分支定界算法 98
4.3.3 分支定界算法的进一步讨论 105
4.4 分支定界算法的应用 109
4.4.1 背包问题 109
4.4.2 购买商品问题 113
习题四 119
第5章 割平面法 123
5.1 有效不等式 123
5.1.1 有效不等式定义 123
5.1.2 强有效不等式 126
5.1.3 多面体、面和刻面 128
5.2 Chvatal-Gomory割平面 130
5.3 Gomory割平面 133
5.3.1 纯整数线性规划模型 133
5.3.2 混合整数线性规划模型 139
5.4 混合整数舍入切 140
5.5 覆盖不等式 142
5.6 分支定切算法 144
习题五 147
第6章 列生成算法 152
6.1 Dantzig-Wolfe分解 153
6.1.1 基本定理 153
6.1.2 Dantzig-Wolfe分解 153
6.1.3 块角结构 155
6.2 列生成算法 157
6.2.1 列生成算法 157
6.2.2 列生成算法的改进策略 167
6.3 分支定价算法 173
6.3.1 分支定价算法思想 173
6.3.2 分支策略 176
6.4 分支定价定切算法 177
6.4.1 分支定价定切算法思想 177
6.4.2 常见鲁棒切 179
6.4.3 非鲁棒切 181
6.5 列生成算法的应用 185
6.5.1 乘务调度问题 185
6.5.2 平行机调度问题 188
习题六 191
第7章 拉格朗日松弛算法 195
7.1 拉格朗日原问题和对偶问题 195
7.2 拉格朗日松弛的进一步讨论 198
7.2.1 等式约束的松弛 198
7.2.2 含两类约束的拉格朗日松弛 198
7.3 拉格朗日对偶问题的求解算法 200
7.3.1 次梯度算法 200
7.3.2 外逼近算法 204
7.3.3 Bundle算法 207
7.4 拉格朗日松弛算法的应用 210
7.4.1 广义指派问题 210
7.4.2 开放车间调度问题 212
习题七 215
第8章 Benders分解算法 219
8.1 Benders分解算法 219
8.1.1 Benders重表示 220
8.1.2 Benders分解算法 222
8.2 改进策略 229
8.2.1 Benders主问题加速策略 229
8.2.2 Benders切的选择策略 231
8.2.3 基于CPLEX的Benders分支定切算法 232
8.3 经典Benders分解算法的扩展 234
8.3.1 整数Benders分解算法 234
8.3.2 逻辑Benders分解算法 237
8.4 Benders分解算法的应用 239
8.4.1 无容量限制的多仓库选址分配问题 239
8.4.2 概率旅行商问题 242
8.4.3 带有准备时间的不相关平行机调度问题 245
习题八 249
第9章 启发式算法 252
9.1 精确整数优化方法的局限性 252
9.2 局部搜索算法 253
9.3 元启发式方法 256
9.3.1 禁忌搜索算法 257
9.3.2 模拟退火算法 262
9.3.3 遗传算法 267
习题九 272
参考文献 274
展开全部
整数规划:基础、扩展及应用 节选
**章引言 1.1*优化 *优化是一门适应性强、内容丰富的学科领域，不仅在学术界一直受到学者的关注，而且在社会生活领域对实际问题的解决也发挥着至关重要的作用.*优化研究是指在一定约束条件下，从众多可行选择中选出*优方案，使系统的目标函数在约束条件下达到*大或*小.它通过组建模型，掌握相关要素之间的关联，推测各种可行的办法以及可能发生的结果，从而选取能完成既定任务的*佳决策方案. 一个*优化模型，也称为数学规划模型，通常包含以下三个基本要素. 决策变量 *优化问题待定的量值，通过模型计算来确定的决策因素. 目标函数 度量决策方案优劣的标准，通常是与决策变量有关的待求极值(*大值或*小值)函数. 约束条件 限制决策选择的约束，即求目标函数极值时，决策变量必须满足的限制.*基本的约束条件是明确变量的类型. *优化模型的一般形式为 min或max目标函数(可以是多个) s.t. 主约束; 变量类型约束.(1.1) 其中s.t.代表subjectto(使服从). 将问题的决策用决策变量表示，其目标是在满足给定约束的条件下，寻求能够*大化或者*小化目标函数的决策变量取值. (单目标)*优化模型的一般代数形式为 min或maxf(x1， ，xn) s.t. 其中，x1， ，xn是决策变量，f(x1， ，xn)是目标函数，gi(x1， ，xn)(i=1， ，m)是约束函数，参数bi(i=1，2， ，m)是约束右端系数，每一个约束都可以是“≤”，“=”或者“≥”的形式. 决策变量的某个取值组合称为模型(1.2)的一个解.满足模型(1.2)的所有约束条件的解称为一个可行解，所有可行解构成的集合称为可行域.可行域中能使目标函数达到*优的解称为*优解.求解模型(1.2)的方法称为优化算法. 当f(x1， ，xn)和gi(x1， ，xn)(i=1， ，m)是决策变量x1， ，xn的线性函数时，称模型(1.2)为线性规划模型. 1.2整数规划 当决策变量中含有取值被约束为整数的变量(即存在整数变量)时，称模型(1.2)为整数规划模型.其中，所有决策变量都是整数变量的优化问题称为纯整数规划或全整数规划模型，而部分变量是整数变量的优化问题称为混合整数规划模型.目标函数和约束函数均是线性函数的整数规划模型，称为整数线性规划模型;否则，称为整数非线性规划模型. 取值为0或1的整数变量称为0-1变量或逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否选择某个特定方案.如当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述.含有0-1变量的整数规划模型称为0-1整数规划模型.0-1整数规划模型在整数规划中具有重要地位，一方面，许多实际问题都可以归结为该类问题，另一方面，任何不含有无界变量的整数规划模型都与0-1整数规划模型等价，此外许多非线性规划模型也可以转化为等价的0-1整数规划模型. 整数规划是运筹学和管理科学中使用*广泛的优化模型之一.整数规划在现实生活中尤其是企业的管理和运营中应用广泛.在资源有限的条件下，针对提升生产和运营效率的问题进行建模优化，如原料分配、生产调度等;同时也可以针对其他计划问题进行建模优化，如生产计划问题、车辆路径问题、物流运输问题、设施选址、资金预算计划等.此外，整数规划的应用领域还包括：公共交通调度和班次安排、民航航班与机组调度安排、电厂发电计划、通信与网络设计、金融投资组合、大规模集成电路设计等.许多组合优化、图论以及计算逻辑问题，也都可以归结为整数规划问题.尽管整数规划模型在解空间结构上优于连续型模型，然而其求解计算的复杂程度却更高，目前一些著名的难题都是整数规划问题.因此，如何求解整数规划模型是学界研究的关键. 在求解整数规划模型时，如果可行域有界，*简单的求解方法是穷举所有的可行整数解，然后代入目标函数进行比较，得到*优解.当问题规模较小时，可以轻易穷举所有满足约束条件的整数解，这时穷举的方法是可行且有效的.然而，当问题规模变大或可行域无界时，难以在短时间内甚至无法穷举所有整数解.此时穷举法失效，需要设计有效的优化算法进行模型求解. 目前，关于整数规划模型的求解方法主要包括以下三种：精确算法、启发式算法和近似算法. 精确算法是指能够求出问题*优解的算法.整数规划精确算法的一般步骤如下： 生成一个相关问题，称为原问题的衍生问题; 在衍生问题基础上，进一步生成一个更易于求解的松弛问题; 通过求解松弛问题间接得到原问题的解. 由于整数线性规划模型与线性规划模型有着密切的关系，而线性规划模型易于求解，因此，整数规划模型的精确算法通常是针对相应线性规划模型的*优解设计有效的算法，主要包括分支定界算法、分支定切算法、分支定价算法和分支定价定切算法.分支定界算法的主要思路是求解整数规划模型对应的线性规划模型，把其可行域反复地分割为越来越小的子集(每个子集对应一个子线性规划模型的可行域)，这称为分支;然后计算每一支对应子整数规划模型的一个目标下界(对于*小值问题)，这称为定界;在每次分析后，凡是界限超出已知*好可行解目标值的那些子集不再进一步分支.因此许多子集可不予考虑，这称为剪枝.加快分支定界算法收敛速度的一种有效途径是加强每一支对应子整数规划模型的目标下界.常用的方法包括 动态地增加相应线性规划模型的有效不等式(切)，相应方法称为分支定切算法; 将相应线性规划模型转化为等价的Dantzig-Wolfe模型(丹齐格–沃尔夫模型)，进而利用列生成方法进行求解，相应方法称为分支定价算法; 针对每一支相应的Dantzig-Wolfe模型，既通过列生成方法进行求解，又动态地加切，相应方法称为分支定价定切算法. 启发式算法没有严格的理论分析，是算法设计者根据观察到的经验或问题结构性质设计的，在可接受的花费(指计算时间和空间)下给出待解决整数规划模型每一个实例的一个可行解.因此，该可行解与*优解的偏离程度一般不能被预计.当精确算法运行时间长或者无法在有限的时间内求出*优解时，启发式算法可作为备选方法.通常，许多*优化问题往往需要庞大的计算量.虽然启发式算法不能求出精确的*优值，但其至少在可控范围内找到相对较好的可行解，因此启发式算法在现实生活中应用广泛.目前，启发式算法包括构造型方法、局部搜索算法、松弛方法、智能算法等. 近似算法没有严格的定义，一般来说能求出可行解的算法都能归为近似算法.该类算法是针对特定问题使用贪婪策略、限制、松弛等方法设计的，需要进行算法的近似比和复杂度分析.因此，该类算法的求解规模通常是受限制的，*后获得的解也可能不是*优解.但相比于启发式算法，该类算法可以有效度量求得的可行解与*优解的偏离程度.常见的近似算法有贪婪算法、局部搜索算法、松弛算法、近似动态规划等. 1.3整数规划的发展历程 整数规划的历史可以追溯到20世纪50年代，美国学者G.B.Dantzig(丹齐格)首次发现可以通过0-1变量来刻画*优化模型中的固定费用、变量上界、非凸分片线性函数等.此后，Dantzig等对旅行商问题(traveling salesman problem，TSP)的研究，成为分支定界法和现代混合整数规划算法的开端.1958年，R.E.Gomory(戈莫里)提出了求解一般整数线性规划模型的收敛算法——割平面方法，至此整数规划成为*优化领域的一个独立分支.近年来，随着整数规划理论和算法的不断发展以及计算机计算速度和功能的迅猛提升，整数规划已逐渐成为应用*广泛的*优化方法之一，在社会、军事、生物、计算机以及经济等各大领域得到了更广泛的应用和长足的发展. 1.3.1模型和应用角度 整数规划在实际应用中十分广泛，很多优化问题都可以抽象为同一类整数规划模型.如经典的旅行商问题、背包问题(knapsack problem)、切割下料(cutting stock problem)问题等.其中研究*为广泛的问题为旅行商问题，其在运筹学和理论计算机科学中扮演着非常重要的角色，目前许多优化方法都将其作为一个测试基准.旅行商问题是指给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的*短回路.旅行商问题*初应用在交通运输领域，例如飞机航线安排、邮件派送、快递服务、校车行进路线设计等.随着时间的推移，其应用范围扩展到了许多其他领域，例如电路板印制、晶体结构分析、数据串聚类等. 整数规划在背包问题方面的研究*早可追溯到1897年，至今已经延续了一个多世纪.其问题可以描述为：给定一组物品，每种物品都有自己的重量和价值，如何选择物品才能在限定总重量内使得背包内物品的总价值*高.自从背包问题被提出之后，众多学者对其进行了深入细致的研究和拓展，关于背包问题理论的文献和研究也是不计其数.同时，背包问题在现实中也有着广泛的应用，很多实际问题都被抽象为背包问题，例如股市投资、国家预算、资源分配、工业生产和运输等.因此，背包问题也是组合优化领域中重要的基石之一. 切割下料问题是整数规划在生产领域中*经典的应用之一.其问题可以描述为：给定一组原材料，如何通过切割、剪裁、冲压等手段，按照工艺要求将原材料加工成规定大小的成材，从而使所用材料*少或利润*大.此外，随着越来越多的复杂系统使用数学框架建模，集划分问题(set partition problem)、选址问题(facility location problem)、网络设计问题(network design problem)等一系列整数规划问题都广泛应用于生产以及生活的方方面面，未来将会有更多的整数规划应用模型被发掘. 目前，整数规划应用研究的总体发展趋势主要有两个方面：.1整数规划与管理科学、网络科学、生命科学、服务科学等学科的交叉融合日益增强;.2现有算法往往还不能解决交通规划、生产调度、通信、金融投资等领域中出现的大规模混合整数规划模型，因此整数规划研究正朝着大规模混合整数规划模型的算法设计方向发展. 1.3.2模型求解角度 由于整数约束使得整数规划模型变得难以求解，目前整数规划模型求解算法的效率通常比不上求解线性规划模型的单纯形法.影响求解算法计算时间的*大因素是整数变量的数目，以及问题是否具有容易处理的特殊结构.在整数变量数目一定时，0-1整数规划模型通常比一般整数规划模型更容易求解.针对具有特殊结构的大规模0-1整数规划模型，采用特殊的算法求解通常更加容易;而不具有特殊结构的问题，即使整数变量数目较少也难以求解.此外，基于实际问题建立的整数规划模型通常含有不相关或冗余信息，这些信息也会降低算法求解效率. 自20世纪50年代以来，针对整数线性规划的研究一直是整数规划研究的核心内容.一般整数线性规划模型的求解算法主要是基于分支定界的算法.目前提高分支定界算法效率的主要途径有两个：.1提高求解线性松弛模型的速度;.2利用割平面和有效不等式加快收敛速度.一方面，分支定界算法需要求解许多可行域不断缩小的线性规划子问题，改进的单纯形算法(对偶单纯形算法)可以利用热启动方法加速求解子问题;另一方面，自从割平面方法被提出以来，基于不同问题结构性质的有效不等式理论得到了很好发展.针对背包问题、旅行商问题和网络流相关问题等，通过许多简单或复杂的强有效不等式以及结合这些有效不等式的分支切割方法，大大提高了分支定界算法的速度和效率.针对具有特殊结构的大规模问题，如具有分块结构的大规模整数线性规划模型，Dantzig-Wolfe分解和Benders分解(本德尔斯分解)是有效的分解方法，列生成和Benders分解算法分别是求解相应分解模型的高
整数规划:基础、扩展及应用 作者简介
殷允强，电子科技大学经济与管理学院教授、博士生导师，国家万人计划青年拔尖人才，四川省杰青，四川省海内外引进高层次人才.主要从事智能决策与优化，生产与物流运作管理，数据挖掘等方面的研究. 主持国家自然科学基金项目4项，国家社科重大项目1项（子课题负责人），四川省杰出青年科技人才项目、国家留学基金委中法蔡元培国际合作项目等省部级项目多项.2014-2021连续8年入选Elsevier 中国高被引学者榜单.以第一或通讯作者在NRL、EJOR、TRE、Omega、IEEE Transactions on Cybernetics、IEEE Transactions on SMC等国际主流期刊发表SCI论文70余篇. 现任Complex & Intelligent Systems、International Journal of Production Research等多本SCI期刊的副主编、首席客邀编辑，中国管理科学与工程学会理事，中国优选法统筹法与经济数学研究会船海经济管理专业委员会副理事长、智能决策与博弈分会秘书长，以及中国运筹学会排序专业委员会等多个分会的（常务）理事. 王杜娟，四川大学商学院教授、博士生导师，入选四川省海内外引进高层次人才千人、四川省特聘专家、四川大学首批“双百人才工程”百人计划.主要从事生产与物流运作管理、商务智能与数据挖掘、决策优化理论与方法等领域的教学和科研工作. 主持国家自然科学基金项目、四川省科技计划项目、中国博士后科学基金特别资助项目等10余项，作为主要完成人参与国家自然科学基金重点项目、科技部科技支撑计划项目等10项.以第一/通讯作者在NRL、EJOR、Omega、IEEE SMC、JBR、IJPE、ANOR等国内外重要期刊发表高水平论文50余篇，出版学术专著3部. 现任SCI期刊Complex & Intelligent Systems副主编，中国物流学会常务理事、中国自动化学会大数据专委会副主任、中国仿真学会智能仿真优化与调度专委会委员，以及中国运筹学会排序专委会等多个分会的理事. 余玉刚，中国科学技术大学教授，博士生导师，基金委国家创新群体项目负责人，基金委重大项目负责人，国家杰出青年基金等领军人才获得者，中国高被引学者(Elsevier, 2014-2021, 连续8年)；现任中国科学技术大学校党委委员，管理学院执行院长，国际金融研究院院长，现代物流与供应链安徽省重点实验室主任. 研究成果主要集中在基于颠覆技术和数据的现代物流和现代供应链管理领域，包括机器人物流、平台供应链、双碳供应链、数据科学等.相关研究发表学术期刊论文150余篇，其中40余篇发表在FMS的A类期刊，近30篇发表在《管理世界》、《系统工程理论与实践》等中文期刊，15篇发表（含录用）在M&SOM(Manufacturing and Service Operations Management)、TS(Transportation Science)、ISR(Information Systems Research)、POM(Production and Operations Management)、IISE Transactions顶级期刊. 相关研究获一项教育部人文社会科学一等奖，一项教育部自然科学一等奖，1篇论文入选十二五《国家自然科学基金资助项目优秀成果选编》，2篇论文被IIE Transactions主编选为“featured article”并在美国工业工程师协会行业期刊IE Magazine杂志专栏介绍，多篇论文被Science direct评为“top 25 hottest articles”，一篇论文被Elsevier出版社选为Elsevier经济学期刊中大陆作者发表的“Most Cited Articles”(2004-2008)，获美国电子与电气工程师协会IEEE ICNSC会议(10th IEEE International Conference on Networking, Sensing and Control, April 10-12, 2013, France)的最佳应用论文奖，美国工业与系统工程协会（IISE）年会最佳应用论文提名奖，中国系统工程学会 理论贡献奖（2016），中国物流与采购联合会科技进步奖一等奖，获得多项国家发明专利等.
书友推荐
本类畅销
-
普林斯顿微积分读本-(修订版)
¥69.3¥99 -
怎样解题
¥17.2¥29 -
数学-应用与思考
¥16.1¥32.8 -
高等代数思想方法分析及应用研究
¥25.3¥76 -
高等代数典型问题研究与实例探析
¥30.4¥92 -
数字唬人:用常识看穿无所不在的数字陷阱
¥16¥36.8
