- 1、本文档共9页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第二章整数规划讲解
第二章 整数规划
§1 概论
1.1 定义
规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
整数规划的分类
如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:
1o 变量全限制为整数时,称纯(完全)整数规划。
2o 变量部分限制为整数的,称混合整数规划。
整数规划特点
(i) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例1 原线性规划为
其最优实数解为:。
③有可行解(当然就存在最优解),但最优解值变差。
例2 原线性规划为
其最优实数解为:。
若限制整数得:。
(ii) 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类:
(i)分枝定界法—可求纯或混合整数线性规划。
(ii)割平面法—可求纯或混合整数线性规划。
(iii)隐枚举法—求解“0-1”整数规划:
①过滤隐枚举法;
②分枝隐枚举法。
(iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。
(v)蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统有哪些信誉好的足球投注网站,这就是分枝与定界内容。通常,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由Land Doig和Dakin等人提出的。由于这方法灵活且便于用计算机求解,所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。
设有最大化的整数规划问题,与它相应的线性规划为问题,从解问题开始,若其最优解不符合的整数条件,那么的最优目标函数必是的最优目标函数的上界,记作;而的任意可行解的目标函数值将是的一个下界。分枝定界法就是将的可行域分成子区域的方法。逐步减小和增大,最终求到。现用下例来说明:
例3 求解下述整数规划
解 (i)先不考虑整数限制,即解相应的线性规划,得最优解为:
可见它不符合整数条件。这时是问题的最优目标函数值的上界,记作。而显然是问题的一个整数可行解,这时,是的一个下界,记作,即。
(ii)因为当前均为非整数,故不满足整数要求,任选一个进行分枝。设选进行分枝,把可行集分成2个子集:
,
因为4与5之间无整数,故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下:
问题:
最优解为:。
问题:
最优解为:。
再定界:。
(iii)对问题再进行分枝得问题和,它们的最优解为
再定界:,并将剪枝。
(iv)对问题再进行分枝得问题和,它们的最优解为
无可行解。
将剪枝。
于是可以断定原问题的最优解为:
从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为:
开始,将要求解的整数规划问题称为问题,将与它相应的线性规划问题称为问题。
(i)解问题可能得到以下情况之一:
(a)没有可行解,这时也没有可行解,则停止.
(b)有最优解,并符合问题的整数条件,的最优解即为的最优解,则停止。
(c)有最优解,但不符合问题的整数条件,记它的目标函数值为。
(ii)用观察法找问题的一个整数可行解,一般可取,试探,求得其目标函数值,并记作。以表示问题的最优目标函数值;这时有
进行迭代。
第一步:分枝,在的最优解中任选一个不符合整数条件的变量,其值为,以表示小于的最大整数。构造两个约束条件
和
将这两个约束条件,分别加入问题,求两个后继规划问题和。不考虑整数条件求解这两个后继问题。
定界,以每个后继问题为一分枝标明求解的结果,与其它问题的解的结果中,找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中,找出目标函数值为最大者作为新的下界,若无作用。
第二步:比较与剪枝,各分枝的最优目标函数中若有小于者,则剪掉这枝,即以后不再考虑了。若大于,
文档评论(0)