清华大学出版社:《运筹学》课程电子教案(PPT课件讲稿)第6章 整数规划

第6章整数规划 第1整数线性规划间题的提出 第2节分支定界解法 第3节割平面解法 第4节使用 MATLAB求解整数规划问题 第5节0-1型整数线性规划 第6节指派问题 清华大学出版社
清华大学出版社 2 第6章 整数规划 ◼第1节 整数线性规划问题的提出 ◼第2节 分支定界解法 ◼第3节 割平面解法 ◼第4节 使用MATLAB求解整数规划问题 ◼第5节 0-1型整数线性规划 ◼第6节 指派问题

第1节整数线性规划问题的提出 令在前面讨论的线性规划问题中,有些最优解可能是分 数或小数,但对于某些问题,常要求解必须是整数(称 为整数解)。例如,所求解是机器的台数、完成工作的 人数或装货的车数等。 令为满足整数解的要求,初看起来,似乎只要把已得到 的带有分数或小数的解经过“舍入化整”就可以了。 但这常常是不行的,因为化整后不见得是可行解;或 虽是可行解,但不一定是最优解。 令因此,对求最优整数解的问题,有必要另行研究。我 们称这样的问题为整数线性规划( integer linear programmIng),简称‖LP。 清华大学出版社
清华大学出版社 3 第1节 整数线性规划问题的提出 ❖ 在前面讨论的线性规划问题中,有些最优解可能是分 数或小数,但对于某些问题,常要求解必须是整数(称 为整数解)。例如,所求解是机器的台数、完成工作的 人数或装货的车数等。 ❖ 为满足整数解的要求,初看起来,似乎只要把已得到 的带有分数或小数的解经过“舍入化整”就可以了。 但这常常是不行的,因为化整后不见得是可行解;或 虽是可行解,但不一定是最优解。 ❖ 因此,对求最优整数解的问题,有必要另行研究。我 们称这样的问题为整数线性规划(integer linear programming),简称ILP

第1节整数线性规划问题的提出 整数线性规划的分类 如果所有的变量都限制为(非负)整数,就称为纯整数线性规 划( pure integer linear programming)或称为全整数线性规划 (all integer linear programming o如果仅一部分变量限制为整数,则称为混合整数规划(mied integer linear programming 整数线性规划的一种特殊情形是0-1规划,即变量的取值仅 限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。 清华大学出版社
清华大学出版社 4 第1节 整数线性规划问题的提出 ❖ 整数线性规划的分类 如果所有的变量都限制为(非负)整数,就称为纯整数线性规 划(pure integer linear programming)或称为全整数线性规划 (all integer linear programming) 如果仅一部分变量限制为整数,则称为混合整数规划(mixed integer linear programming)。 整数线性规划的一种特殊情形是0-1规划,即变量的取值仅 限于0或1。本章最后讲到的指派问题就是一个0-1规划问题

第1节整数线性规划问题的提出 令现举例说明用单纯形法求得的解不能保证是整数最优 解 令例1某厂拟用集装箱托运甲乙两种货物,每箱的体积、 重量、可获利润以及托运所受限制如表5-1所示。问 两种货物各托运多少箱,可使获得利润为最大? 表5-1 货物体积(m/箱)重量(00g箱)利润(10元/箱) 甲 5 2 20 4 10 托运限制「24m 1300kg 清华大学出版社
清华大学出版社 5 第1节 整数线性规划问题的提出 ❖ 现举例说明用单纯形法求得的解不能保证是整数最优 解。 ❖ 例1 某厂拟用集装箱托运甲乙两种货物,每箱的体积、 重量、可获利润以及托运所受限制如表5-1所示。问 两种货物各托运多少箱,可使获得利润为最大? 货物 体积(m3 /箱) 重量(100kg/箱) 利润(100 元/箱) 甲 乙 5 4 2 5 20 10 托运限制 24m3 1300kg 表5-1

第1节整数线性规划问题的提出 解:设x,x2分别为甲、乙两种货物的托运箱数(当然 都是非负整数),这就是一个(纯)整数线性规划问题, 用数学模型可表示为: maxz=20x1+10x2① 5X1+4x2<24 2x1+5X2<13 ②③④⑤ (5.1) X1,X2≥0 x1,x,整数 该问题和线性规划问题的区别仅在于最后一个约束条件⑤ 现在我们暂不考虑这一条件,即解由①~④构成的线性规划问题 (以后我们称这样的问题为与原问题相应的线性规划问题) 清华大学出版社
清华大学出版社 6 第1节 整数线性规划问题的提出 ❖ 解:设x1,x2分别为甲、乙两种货物的托运箱数(当然 都是非负整数),这就是一个(纯)整数线性规划问题, 用数学模型可表示为: max z =20x1+10x2 ① 5x1+4x2 ≤24 ② 2x1+5x2 ≤13 ③ (5.1) x1,x2 ≥0 ④ x1,x2整数 ⑤ 该问题和线性规划问题的区别仅在于最后一个约束条件⑤。 现在我们暂不考虑这一条件,即解由①~④构成的线性规划问题 (以后我们称这样的问题为与原问题相应的线性规划问题)

第1节整数线性规划问题的提出 令容易求得相应的线性规划问题的最优解为 x1=4.8,x2=0,max=96 z=96 C 1234567 清华大学出版社
清华大学出版社 7 第1节 整数线性规划问题的提出 ❖ 容易求得相应的线性规划问题的最优解为 x1=4.8,x2=0,max z=96

第1节整数线性规划问题的提出 令现在来分析上述线性规划问题的最优解是否是整数规 划问题的最优解 因为x1表示的是托运甲种货物的箱数,目前得到的最优解不 是整数,所以不合条件⑤的要求 o是不是可以把所得的非整数最优解经过“化整”就可得到合 于条件⑤的整数最优解呢? 口如将x1-48,x2=0)凑整为(x1=5,x2=0),这样就破坏了条件② (关于体积的限制),因而它不是可行解 口如将(x1=48,x2=0)舍去尾数0.8,变为(x4,x2=0),这当然满 足各约束条件,因而是可行解,但不是最优解,因为当x=4, x2=0,时z80;而当x=4,x2=1(这也是可行解)时,z90 清华大学出版社
清华大学出版社 8 第1节 整数线性规划问题的提出 ❖ 现在来分析上述线性规划问题的最优解是否是整数规 划问题的最优解 因为x1表示的是托运甲种货物的箱数,目前得到的最优解不 是整数,所以不合条件⑤的要求。 是不是可以把所得的非整数最优解经过“化整”就可得到合 于条件⑤的整数最优解呢? 如将(x1=4.8,x2=0)凑整为(x1=5,x2=0),这样就破坏了条件② (关于体积的限制),因而它不是可行解; 如将(x1=4.8,x2=0)舍去尾数0.8,变为(x1=4,x2=0),这当然满 足各约束条件,因而是可行解,但不是最优解,因为当x1=4, x2=0, 时z=80;而当x1=4,x2=1(这也是可行解)时,z=90

第1节整数线性规划问题的提出 本例还可以用图解法来说明。见图5-1 01234567 图51 图中画(+)号的点表示可行的整数解。凑整得到的(5,0)点不在可行域内, 而C点又不合于条件⑤。为了满足题中要求,表示目标函数的z的等值线 必须向原点平行移动,直到第一次遇到带“+”号B点(x=4,x2=1)为止。 这样,z的等值线就由z96变到z90,它们的差值为△z=96-90=6,表示 利润的降低,这是由于变量的不可分性(装箱)所引起的。 清华大学出版社
清华大学出版社 9 第1节 整数线性规划问题的提出 本例还可以用图解法来说明。见图 5-1 图中画(+)号的点表示可行的整数解。凑整得到的(5,0)点不在可行域内, 而C点又不合于条件⑤。为了满足题中要求,表示目标函数的z的等值线 必须向原点平行移动,直到第一次遇到带“+”号B点(x1=4,x2=1)为止。 这样,z的等值线就由z=96变到z=90,它们的差值为Δz=96-90=6,表示 利润的降低,这是由于变量的不可分性(装箱)所引起的。 图5-1

第1节整数线性规划问题的提出 令由上例看出,将其相应的线性规划的最优解经过“化整” 来解原整数线性规划,虽是最容易想到的,但常常得不 到整数线性规划的最优解,甚至根本不是可行解。因此 有必要对整数线性规划的解法进行专门研究。 清华大学出版社
清华大学出版社 10 第1节 整数线性规划问题的提出 ❖ 由上例看出,将其相应的线性规划的最优解经过“化整” 来解原整数线性规划,虽是最容易想到的,但常常得不 到整数线性规划的最优解,甚至根本不是可行解。因此 有必要对整数线性规划的解法进行专门研究

第2节分支定界解法 令在求解整数线性规划时,如果可行域是有界的,首先容 易想到的方法就是穷举所有可行的整数解,即列出图5-1 中所有标有“+〃的整数点,然后比较它们的目标函数值, 从而确定最优解。 对于规模较小的问题,变量个数很少,可行解的组合数 也较小时,这个方法是可行的,也是有效的。 o如在例1中,变量只有x和x。由条件②,x所能取的整数值为0 为 个。因此所有可能的整数组合(不都是可行的)数是3×5=15个, 穷举法还是勉强可用的。 令对于大型问题,可行的整数组合数会很大 例如在指派问题中,将n项任务指派n个人去完成,不同的指派 方案共有n!种,当n=10时,可能的指派方案数超过300万;当 n=20,超过2×108。显然,穷举法是不可取的。 清华大学出版社
清华大学出版社 11 第2节 分支定界解法 ❖ 在求解整数线性规划时,如果可行域是有界的,首先容 易想到的方法就是穷举所有可行的整数解,即列出图5-1 中所有标有“+”的整数点,然后比较它们的目标函数值, 从而确定最优解。 ❖ 对于规模较小的问题,变量个数很少,可行解的组合数 也较小时,这个方法是可行的,也是有效的。 如在例1中,变量只有x1和x2。由条件②,x1所能取的整数值为0、 1、2、3、4共5个;由条件③,x2所能取的整数值为0、1、2共3 个。因此所有可能的整数组合(不都是可行的)数是3×5=15个, 穷举法还是勉强可用的。 ❖ 对于大型问题,可行的整数组合数会很大。 例如在指派问题中,将n项任务指派n个人去完成,不同的指派 方案共有n!种,当n=10时,可能的指派方案数超过300万;当 n=20,超过2×1018。显然,穷举法是不可取的
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 德克士炸鸡店消费需求研究报告(PPT)德克士炸鸡店市场研究报告.ppt
- 日照职业技术学院:《市场调查与分析预测》课程教学资源(PPT课件讲稿)模块五 市场调研报告.ppt
- 《企业战略管理》课程教学资源(PPT课件讲稿)第七章 企业职能战略.ppt
- 《物流管理理论与实务》课程教学资源(PPT课件讲稿)配送中心管理.ppt
- 《竞争情报》课程教学资源(PPT课件讲稿)第七章 竞争情报传播.ppt
- 《管理学》课程教学资源(PPT课件)目标管理.ppt
- 中国医科大学网络教育学院:《现代管理心理学》课程教学资源(PPT课件讲稿)第九章 现代管理心理与领导公关论.ppt
- 《旅游学概论》课程教学资源(专升本课程考试大纲).doc
- 《配送管理实务》课程教学资源(PPT课件)第3章 仓储与配送设施、设备.ppt
- 《物流管理理论与实务》课程教学资源(PPT课件讲稿)实务篇(共五章).ppt
- 《公共管理学》课程教学资源(PPT课件讲稿)第五章 公共管理的运作过程.ppt
- 《全面质量管理》课程教学资源(PPT课件讲稿,共四部分九单元).ppt
- 日照职业技术学院:《民航服务礼仪》课程教学资源(教案)简易化妆.pdf
- 日照职业技术学院:《特许经营与管理》课程教学资源(PPT课件)第四章 受许人加盟创业和融资决策.ppt
- 《逻辑学》课程教学资源(PPT课件讲稿)命题逻辑.pptx
- 企业新晋员工职业化训练教程(PPT讲稿).ppt
- 《企业经营战略》课程教学资源(PPT课件讲稿)第五章 企业经营战略.ppt
- 瓮福集团十年顶层战略(总纲).pptx
- 《计算机软件技术基础》课程教学资源(PPT课件讲稿)第二部分 操作系统 第九章 存储管理.ppt
- 《管理学原理》课程教学资源(PPT课件讲稿)第九章 组织设计.ppt
- 《人力资源管理》教学资源(PPT讲稿)第二章 人力资源管理的有效技能.ppt
- 《国际营销学》课程电子教案(PPT课件讲稿,共九章).ppt
- 《文化产业管理学》课程考核大纲.doc
- 《运筹学》课程教学资源(PPT课件讲稿)运输问题.ppt
- 清华大学出版社:《运筹学》课程电子教案(PPT课件讲稿)第4章 运输问题.ppt
- 《管理学原理与方法》课程教学资源(PPT课件)第七章 计划与计划工作.ppt
- 《商务谈判实务》课程教学资源(PPT课件讲稿)第四章 商务谈判准备.ppt
- 西安电子科技大学:《跨文化沟通与管理》课程教学资源(PPT课件)Chapter 03 组织文化与多样性 Organizational Cultures and Diversity.ppt
- 《旅游学概论》课程教学资源(考试大纲).doc
- 东北财经大学出版社出版:《分销渠道管理》教材电子教案(PPT课件)第1章 营销渠道管理概论(作者:胡介埙).ppt
- 《药品经营质量管理规范》学习资料(PPT讲稿,2012年版).ppt
- 日照职业技术学院:《市场调查与分析预测》课程教学资源(PPT课件讲稿)项目四 测量技术(主讲:周小兰).ppt
- 学校管理制度:长春科技学院管理制度汇编(共十四篇).doc
- 《管理学》课程教学资源(PPT课件讲稿)第四章 计划与计划工作.ppt
- 《医院管理学》课程教学资源(PPT课件讲稿)第六章 医院质量管理.ppt
- 转型发展中的后勤服务与管理(PPT讲稿).ppt
- 《市场营销学》课程教学资源(PPT课件讲稿)第十四章 网络营销 e-Marketing.ppt
- 日照职业技术学院:《民航服务礼仪》课程教学资源(教案)正确的坐.pdf
- 机械工业出版社:普通高等教育规划教材《市场营销学》课程教学资源(PPT课件)第十二章 几种主要的新潮营销方式.ppt
- 中国医科大学网络教育学院:《现代管理心理学》课程教学资源(PPT课件讲稿)第三章 现代管理心理与领导结构.ppt