整数规划中的割平面法与分枝定界法比较
Comparisons between Plane-cutting and Branch Delimitation in Integer Plan
整数规划是规划论中较新的一个分枝,它是研究决策变量取整数的一类线性规划,主要的解法有割平面法和分枝定界法两种.对它们进行介绍后,通过求解具体问题进行分析比较.
达县师范高等专科学校,数学系,四川,达州,635000
年，卷(期)
机标分类号
本文读者也读过
加载中，请稍候
．客服电话
&&8:00-11:30,13:00-17:00(工作日)算法（12）

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯，还可以求解混合整数规划问题。
设最大化的整数规划问题为A, 相应的不含整数约束的线性规划为B, 若B 的最优解不符合A 的整数条件, 那么B 的最优目标函数值必为A 的最优目标函数值Z* 的一个上界, 记作Z; 而A 的任意可行解的目标函数值将是Z* 的一个下界, 记作Z。对B 的非整数解的相邻整数作附加条件, 从而形成两个分枝, 即两个子问题, 两个子问题的可行域中包含原整数规划问题的所有可行解。不断分枝, 逐步减小Z, 增大Z, 最终求得Z*
第1步：放宽或取消原问题的某些约束条件，如求解的条件。如果这时求出的最优解是原问题的，那么这个解就是原问题的最优解，计算结束。否则这个解的目标函数值是原问题的最优解的上界。
第2步：将放宽了某些约束条件的替代问题分成若干子问题，要求各子问题的解集合的并集要包含原问题的所有，然后对每个子问题求。这些子问题的中的最优者若是原问题的，则它就是原问题的，计算结束。否则它的目标函数值就是原问题的一个新的上界。另外，各子问题的最优解中，若有原问题的的，选这些可行解的最大目标函数值，它就是原问题的最优解的一个下界。
第3步：对的值已小于这个下界的子问题，其中必无原问题的最优解，可以放弃。对最优解（不是原问题的可行解）的目标函数值大于这个下界的子问题，都先保留下来，进入第4步。
第4步：在保留下的所有子问题中，选出的值最大的一个，重复第1步和第2步。如果已经找到该子问题的最优，那么其目标函数值与前面保留的其他问题在内的所有子问题的可行解中目标函数值最大者，将它作为新的下界，重复第3步，直到求出最优解。
还有一篇博客文章，写的很好，感谢原创作者&&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：165957次
积分：1987
积分：1987
排名：第17481名
原创：58篇
转载：78篇
评论：66条
(2)(3)(1)(1)(1)(1)(2)(7)(2)(7)(4)(3)(2)(6)(4)(2)(13)(10)(30)(4)(2)(9)(15)(6)出自 MBA智库百科()
整数规划(integer programming)
　　整数规划是指一类要求问题中的全部或一部分为整数的。是近三十年来发展起来的、规划论的一个分支. 整数规划问题是要求决策取整数值的或问题。
　　一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。
　　整数规划是从1958年由R.E.戈莫里提出之后形成独立分支的
，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即
，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是和，它们都是在上述框架下形成的。
　　在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用就比较方便。
　　整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、送货问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和等方面也有新的应用。
　　整数规划又分为：
　　1、：所有决策变量均要求为整数的整数规划
　　2、：部分决策变量均要求为整数的整数规划
　　3、：所有决策变量均要求为0－1的整数规划
　　4、：部分决策变量均要求为0－1的整数规划
　　整数规划与线性规划不同这处只在于增加了整数约束。不考虑整数约束所得到的线性规划称为。
　　在现实生活中，决策变量代表产品的件数、个数、台数、箱数、艘数、辆数等等，则变量就只能取整数值. 如实际上就是一个整数规划模型，该例的决策变量代表所截钢管的根数，显然只能取整数值。因而整数规划模型也有着广泛的应用领域，从 以下的几个例子中更可以窥其一斑。
　　[例1]　　某厂在一计划期内拟生产甲、乙两种大型设备. 该厂有充分的来加工制造这两种设备的全部零件，所需和能源也可满足供应，但A、B两种紧缺物资的供应受到严格限制，每台设备所需原材料如下 表所示. 问该厂在本计划期内应安排生产甲、乙设备多少台，才能使利润达到最大？
原料设备甲乙可供资源数量
A（吨）116
B（千克）5945
每台单位利润（万元）56　
设x1,x2分别为该计划期内生产甲、乙设备的台数，Z为生产这两种设备可获得的总利润.显然x1,x2都须是非负整数，因此它是一个(纯)整数规划问题，其为：
　　max　　 Z = 5x1 + 8x2
　　s.t.　　x1 + x26
　　　　　　5x1 + 9x245
　　　　　　x1,x2 0
　　　　　　x1,x2为整数
　　[例2]　　(投资决策模型)设有n个投资项目，其中第j个项目需要资金aj万元，将来可获利润cj万元。若现有资金总额为b万元，则应选择那些投资项目，才能获利最大？
　　这里j＝1，2，…n设Z为可获得的总利润(万元)，则该问题的数学模型为：
　　s.t.　
　　　　　xj=0　or　1(j = 1,2,&L,n)
　　[例3]　　(物资调拨模型)某厂拟用a元资金生产m种设备其中设备Ai为pi (i＝1，2，…，m)。预计将一台设备Ai在Bj处销售可获利xij元，则应如何调拨这些设备，才能使预计总利润为最大？
设yi为生产设备Ai的台数，xij为将设备Ai调拨到Bj处销售的台数，Z为预计总利润(元). 则该问题的数学模型为：
　　s.t.　　　(i = 1,2,&L,m)
　　　　　　　(j = 1,2,&L,n)
　　　　　
　　　　　
　　　　　xij,yi均为整数
　　[例4]　　(选址问题)某种商品有n个销地，各销地每月的分别为bj吨(j＝1，2，…，n).。现拟在m个地点中选址建厂，来生产这种产品以满足供应，且规 定一个地址最多只能建一个工厂。若选址i建厂，将来生产能力每月为ai吨，每月为di元(i＝1，2，…，m). 已知从i至销地j的运价为cij元/吨. 应如何选择厂址和安排调运，能使总的最少？
设每月从厂址i至销地j的运量为x_{ij}吨，z为每月的总费用(元)，
　　则该问题的数学模型为：
　　min　　
　　s.t.　　　　(i = 1,2,&L,m)
　　　　　　　　 (j = 1,2,&L,m)
　　　　　　0　or　1
　　求解整数规划的一种自然的想法是，能否用整数规划的线性松弛模型的最优解经过四舍五入得到整数规划的最优解呢？回答是否定的，因为这样四舍五入的结果甚至不是可行解。
　　整数规划比通常的线性规划更加难以求解，迄今求解整数规划其基本求解思路都是按一定的搜索规则，在整数规划的线性松弛模型的可行域内寻找出整数最优解（或确认无整数最优解），因此求整数规划的解需要更多的时间，现通用的解法，主要有、和等。
　　在经济建设中，总有各种各样的，每一种投资机会又有多种的，每一种投资方式都称为一个投资方案，所以经济建设中企业总有多方案可供选择，同时需要大量的，而是有限的，因此企业要根据有限的资源确定投资方案的顺序，使有限的资源取得最大的效益。即经济建设中企业要进行多方案的最佳选择。
　　一、多方案选择的传统方法
　　多方案的选择，必须明确各方案之间的关系，方案之间关系不同，其选择的方法也不同。方案之间的关系可以概括为互斥型、独立型和混合型。
　　1.的选择
　　就是相互之间存在互不相容、互相排斥关系的一组方案。互斥方案评比的实质是判断增量投资的经济合理性，评比的基本方法是，根据反映增量的指标的不同，可细分为静态的和、动态的差额和差额内部收益率法等。由于是客观存在、不容忽视的，动态评价方法对互斥方案的评价更为客观科学，因此，实际工作中，主要应用差额和差额内部收益率法评比互斥方案，其中由差额净现值法导出了最大准则和净年值最大准则，最大准则用于寿命期相同的互斥方案评比，净年值最大准则用于寿命期不同的互斥方案评比。用NPV和NAV评比互斥方案可以把绝对经济效果评价与相对经济效果比较结合起来，直接进行方案的选择，而△NPV和△IRR只适用于方案的比较而不适用于方案的选择。
　　2.独立型方案的选择
　　是相互之间互不影响的一组方案。受资源限制的的选择方法有两种，即独立方案的和。
　　(1)独立方案的互斥化法。该方法首先把各独立方案形成互斥的方案组合；其次选出能满足资金限制的方案组合；最后用互斥方案评选方法评选最优方案组。
　　该方法的优点是保证能选出受资源限制的情况下最大的方案组合。其不足是当独立方案数目较多时，形成的互斥方案组的数目众多，计算复杂：每一个独立方案都有拒绝或接受两种可能，如果有N个互相独立的方案，所形成的互斥方案组合就有2n个。
　　(2)独立方案的双向均衡排序法。该方法首先计算各的约束资源的，并由大到小排序，若约束资源是资金，其效率指标为NPVR或IRR；其次依次计算各方案的资源代价率及各方案组的资源总代价，各方案的资源代价率即各方案的资源消耗量，各方案组资源总代价即各方案组的资源?肖耗总量；第三画图并标注有关约束条件，如资源限额、等；最后选出最优方案组。
　　该方法在资源充分利用的前提下，才能保证所选取的方案组是取得最大的方案组，但是若所选取的方案组没有使资源完全用尽，那么该方案组可能不是真正的最优方案组。
　　3.的选择
　　即互相之间既有互相独立、又有互相排斥关系的一组方案，也称为层混方案，即方案之间的关系分为两个层次，高层是互相独立的项目，而低层则由构成每个独立项目的互斥方案组成。受资源限制的混合方案的评选也分为互斥化法和双向均衡排序法。
　　(1)层混方案的互斥化法。该方法的评选步骤和优点与独立方案的互斥化法相同，只是在形成互斥方案组合时，是从互相独立的每个项目中，至多选出一个方案来形成各种互斥的组合。
　　该方法的不足也是当方案数目较多时，计算非常复杂。例如：共有M个互相独立的项目，第t个项目有Nt个互斥方案，可以组成互相排斥的方案组合数是：。
　　(2)层混方案的双向均衡排序法。该方法用增量效率指标来反映互斥方案的经济效果，所以也称增量效率指标排序法。具体步骤：
淘汰无资格方案：若,则方案k为无资格方案，即如果一笔基础投资的利用效率低于其增量投资的利用效率，那么就认为该基础投资方案是无资格方案，应予以淘汰；
计算有资格方案的约束资源的增量效率指标，并按该指标由大到小排序，受资金限制的层混方案的约束资源增量效率指标为△IRR、△NPVR、△R／△I等；
计算资源代价率及资源代价并绘图；
标注资源约束条件，如资源限额、等；
比选最优方案组。
　　该方法的不足是如果资源约束线分割了方案，那么所选择的方案组可能不是真正的最优方案组；如果被分割的方案恰好包含无资格方案，那么真正的最优方案组可能恰恰包含被当作无资格方案淘汰掉的方案。
　　二、整数规划在多方案选择中的应用
　　传统方法一般只能对受一种的多方案进行选择，而整数规划可以解决受多种资源约束的多方案选择问题，并克服传统方法的不足，保证选出受资源限制情况下的收益最大的方案组合。
　　1.评选目标
　　考虑到方案间的可能不相等，用净年值最大作为评选目标。
　　目标函数：
　　(CI & CO)tj方案j在第t年的；m：方案的总个数；n：方案i的；Xj：决策变量，Xj = 0表示放弃i方案，Xj = 1表示接受方案。
　　2.结束条件
　　由具体情况而定，一般由资源约束和关系约束组成：
　　(1)(资金、人工、设备、原材料等):且，式中：Ctj：方案i在第t年耗用的资源量；Bt：第t年的资源可用量；B：资源总量。
　　(2)关系约束：
互斥方案的约束：,表示m个方案中最多只能选取一个。
独立方案的约束：,示m个方案中每一个都可以被选中。
混合方案的约束:且，式中：K为互相独立的项目数；m1为第k个项目的互斥方案数目。
从属关系约束，表示A方案只有当B方案选用时才有意义，即不选用B方案就不能选用A方案。
严格互补关系约束：XC & XD = 0，表示C方案和方案D必须同时选用或同时不选用。
　　三、整数规划对混合案选择的例证
　　例如某石化下属三个工厂各自独立，分别提出互斥型投资方案，如表。各投资方案的有效期均为l0年，基准收益率为10%。如果这个仅有80000万元可供投资，应如何选择方案对公司最有利?
方案AlA2A3BlB2B3B4ClC2
投资300004000050000l00002000030000400002000030000
年净收益97001080013800l63051007170866050008400
　　解：设目标函数为净年值最大，则目标函数：
　　math>\max NAV=\sum_{j=1}^9\sum_{t=0}^10(CI-CO)_{tj}(P/F,10%,t)(A/P,10%,10)\cdot X_j,X_j=0,1&/math&。
　　约束条件：。
　　计算结果为：Xl = 1,X2 = 0,X3 = 0,X4 = 0,X5 = 1,X6 = 0,X7 = 0,X8 = 0,X9 = 1。
　　即应选择Al、B2、C2三个方案。
王军.整数规划在多方案选择中的应用[J].技术经济,2004,(2)
本条目对我有帮助46
&&如果您认为本条目还有待完善，需要补充新内容或修改错误内容，请。
本条目相关文档
& 38页& 70页& 69页& 16页& 55页& 38页& 16页& 33页& 9页& 16页
本条目由以下用户参与贡献
,,,,,,,,,.
(window.slotbydup=window.slotbydup || []).push({
id: '224685',
container: s,
size: '728,90',
display: 'inlay-fix'
评论(共7条)提示:评论内容为网友针对条目"整数规划"展开的讨论，与本站观点立场无关。
发表评论请文明上网，理性发言并遵守有关规定。
以上内容根据网友推荐自动排序生成君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
分枝定界法
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口以下试题来自：
单项选择题下列说法正确的是（）
A、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解。
B、用割平面法求解整数规划问题，构造的解割平面有可能切去一些不属于最优解的整数解。
C、用分支定界发求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪支。
D、整数规划问题的最优值优于其相应的线性规划问题的最优值。
为您推荐的考试题库
您可能感兴趣的试卷
你可能感兴趣的试题
A、原问题有最优解，对偶问题可能没有最优解
B、原问题与对偶问题可能都没有最优解
C、可能一个问题有最优解，另一个问题具有无界解
D、原问题与对偶问题都具有最优解
A、-1/3X4-1/3X5&=2/3
B、X4-X5&=-2
C、X4+X5+S=2
D、-1/3X4-1/3X5+S=-2/3
A、使原问题保持可行
B、使对偶问题保持可行
C、逐步消除原问题不可行性
D、逐步消除对偶问题不可行性
A、目标函数系数与某约束系数对应成比例
B、最优表中存在非基变量的检验数为0
C、可行解集合无界
D、存在基变量等于0
5.问答题 1.悲观法（min-max法）此方法也称Wald法。对于谨慎的决策者来说，由于害怕决策失误可能造成较大的损......