清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第5章 整数线性规划 第1节 整数线性规划问题的提出、第2节 分支定界解法、第3节 割平面解法、第4节 0-1型整数线性规划

运筹学 (第三版) 《运筹学》教材编写组 第5章整数线性规划 第1-4节 清华大学出版社
运筹学 (第三版) 《运筹学》教材编写组 第5章 整数线性规划 第1-4节 清华大学出版社

第5章整数线性规划 第1节整数线性规划问题的提出 第2节分支定界解法 第3节割平面解法 第4节0-1型整数线性规划 第5节指派问题
第5章 整数线性规划 • 第1节 整数线性规划问题的提出 • 第2节 分支定界解法 • 第3节 割平面解法 • 第4节 0-1型整数线性规划 • 第5节 指 派 问 题 •

第1节整数线性规划问题的提出 在前面讨论的线性规划问题中,有些最优解可能是 分数或小数,但对于某些具体问题,常有要求解答 必须是整数的情形(称为整数解)。例如,所求解是机 器的台数、完成工作的人数或装货的车数等,分数 或小数的解答就不合要求。为了满足整数解的要求, 初看起来,似乎只要把已得到的带有分数或小数的 解经过“舍入化整”就可以了。但这常常是不行的 因为化整后不见得是可行解;或虽是可行解,但不 定是最优解。因此,对求最优整数解的问题,有 必要另行研究。我们称这样的问题为整数线性规划 ( integer linear programming),简称IP,整数线性规 划是最近几十年来发展起来的规划论中的一个分支
第1节 整数线性规划问题的提出 • 在前面讨论的线性规划问题中,有些最优解可能是 分数或小数,但对于某些具体问题,常有要求解答 必须是整数的情形(称为整数解)。例如,所求解是机 器的台数、完成工作的人数或装货的车数等,分数 或小数的解答就不合要求。为了满足整数解的要求, 初看起来,似乎只要把已得到的带有分数或小数的 解经过“舍入化整”就可以了。但这常常是不行的, 因为化整后不见得是可行解;或虽是可行解,但不 一定是最优解。因此,对求最优整数解的问题,有 必要另行研究。我们称这样的问题为整数线性规划 (integer linear programming),简称ILP,整数线性规 划是最近几十年来发展起来的规划论中的一个分支

·整数线性规划中如果所有的变数都限制为(非负) 整数,就称为纯整数线性规划φ pure integer linear programming或称为全整数线性规划(all integer linear programming);如果仅一部分变数 限制为整数,则称为混合整数计划( mixed integer linear programming)。整数线性规划的 种特殊情形是0-1规划,它的变数取值仅限于0 或1。本章最后讲到的指派问题就是一个0-1规 划问题
• 整数线性规划中如果所有的变数都限制为(非负) 整数,就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming);如果仅一部分变数 限制为整数,则称为混合整数计划(mixed integer linear programming)。整数线性规划的一 种特殊情形是0-1规划,它的变数取值仅限于0 或1。本章最后讲到的指派问题就是一个0-1规 划问题

ρ现举例说明用前述单纯形法求得的解不能保证 是整数最优解。例1某厂拟用集装箱托运甲乙两 种货物,每箱的体积、重量、可获利润以及托 运所受限制如表5-1所示。问两种货物各托运多 箱,可使获得利润为最大?表5-1 货物体积(m/箱)重量(00/0销)利润(100元/箱) 甲 20 10 托运限制 24m3 1300kg
• 现举例说明用前述单纯形法求得的解不能保证 是整数最优解。例1某厂拟用集装箱托运甲乙两 种货物,每箱的体积、重量、可获利润以及托 运所受限制如表5-1所示。问两种货物各托运多 少箱,可使获得利润为最大?表5-1 货物 体积(m3 /箱) 重量(100kg/箱) 利润(100 元/箱) 甲 乙 5 4 2 5 20 10 托运限制 24m3 1300kg

现在我们解这个问题,设x1,x2分别为甲、乙两 种货物的托运箱数(当然都是非负整数)。这是 个(纯)整数线性规划问题,用数学式可表示为: maxz=20x1+10x2① 5x1+4X,≤24 ② x1+5x2≤13③(5.1) ≥0 x1,x,整数
• 现在我们解这个问题,设x1,x2分别为甲、乙两 种货物的托运箱数(当然都是非负整数)。这是一 个(纯)整数线性规划问题,用数学式可表示为: max z =20x1 +10x2 ① 5x1 +4x2≤24 ② 2x1 +5x2≤13 ③ (5.1) x1,x2≥0 ④ x1,x2整数 ⑤

它和线性规划问题的区别仅在于最后的条件⑤。现在我 们暂不考虑这一条件,即解①~④(以后我们称这样的问 题为与原问题相应的线性规划问题), 很容易求得最优解为x1=4.8,x2=0,maxz96 z=96 AC
它和线性规划问题的区别仅在于最后的条件⑤。现在我 们暂不考虑这一条件,即解①~④(以后我们称这样的问 题为与原问题相应的线性规划问题), 很容易求得最优解为:x1=4.8,x2=0,max z=96

但x1是托运甲种货物的箱数,现在它不是整数,所以 不合条件⑤的要求。 是不是可以把所得的非整数的最优解经过“化整” 就可得到合于条件⑤的整数最优解呢?如将(x1=4.8, x2=O)凑整为(x1=5,ⅹ2=0),这样就破坏了条件②(关 于体积的限制),因而它不是可行解;如将(x148 x2=0)舍去尾数0.8,变为(x14,x2=0),这当然满足 各约束条件,因而是可行解,但不是最优解,因为 当x1=4,x2=0,时z-80 非整数的最优解在C(48,0)点达到
但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. • 非整数的最优解在C(4.8,0)点达到

但当x1=4,x2=1(这也是可行解)时,z-90 本例还可以用图解法来说明。见图5 96 △C 0 345 7
但当x1 =4,x2 =1(这也是可行解)时,z=90。 本例还可以用图解法来说明。见图 5-1

图中画(+)号的点表示可行的整数解。凑整的 (5,0)点不在可行域内,而C点又不合于条件 ⑤。为了满足题中要求,表示目标函数的z的 等值线必须向原点平行移动,直到第一次遇 到带“+"号B点(x=4,x2=1)为止。这样,z的 等值线就由z=96变到z=90,它们的差值 △z=96-90=6 表示利润的降低,这是由于变量的不可分性 (装箱)所引起的
• 图中画(+)号的点表示可行的整数解。凑整的 (5,0)点不在可行域内,而C点又不合于条件 ⑤。为了满足题中要求,表示目标函数的z的 等值线必须向原点平行移动,直到第一次遇 到带“+”号B点(x1 =4,x2 =1)为止。这样,z的 等值线就由z=96变到z=90,它们的差值 • Δz=96-90=6 • 表示利润的降低,这是由于变量的不可分性 (装箱)所引起的
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第4章 目标规划 第3节 解目标规划的单纯形法、第4节 灵敏度分析、第5节 应用举例.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第4章 目标规划 第1节 目标规划的数学模型、第2节 解目标规划的图解法.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第3章 运输问题 第1节 运输问题的数学模型 第2节 表上作业法.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第3章 运输问题 第3节 产销不平衡的运输问题及其求解方法 第4节 应用举例.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第2章 对偶理论和灵敏度分析 第7节 灵敏度分析、第8节 参数线性规划.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第2章 对偶理论和灵敏度分析 第5节 对偶问题的经济解释(影子价格)、第6节 偶单纯形法.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第2章 对偶理论和灵敏度分析 第4节 线性规划的对偶理论.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第2章 对偶理论和灵敏度分析 第3节 对偶问题的提出.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第2章 对偶理论和灵敏度分析 第2节 改进单纯形法.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第2章 对偶理论和灵敏度分析 第1节 单纯形法的矩阵描述.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第6节 应用举例.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第5节 单纯形法的进一步讨论.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第4节 单纯型法的计算步骤.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第3节 单纯形法.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第2节 线性规划问题的几何意义.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第1节 线性规划问题及其数学模型.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第15章 单目标决策 第5节 效用理论在决策中的应用 第6节 决策树.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第15章 单目标决策 第1节 决策的分类 第2节 决策过程 第3节 不确定型的决策 第4节 风险决策.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第13章 存储论 第3节 随机性存贮模型、第4节 其它类型存贮问题.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第13章 存储论 第1节 存储论的基本概念、第2节 确定性存贮模型.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第5章 整数线性规划 第5节 指派问题.ppt
- 清华大学出版社:《运筹学》课程教学资源(PPT课件讲稿,教材第三版)第1章 线性规划与单纯形法 第1节 线性规划问题及其数学模型.pps
- 清华大学:《管理学原理》课程教学资源(PPT课件)复习辅导(管理中的一些热点问题).ppt
- 清华大学:《管理学原理》课程教学资源(PPT课件)第二章 决策与计划.ppt
- 清华大学:《管理学原理》课程教学资源(PPT课件)第三章 组织.ppt
- 清华大学:《管理学原理》课程教学资源(PPT课件)第四章 领导与激励.ppt
- 清华大学:《管理学原理》课程教学资源(PPT课件)第五章 控制.ppt
- 清华大学:《管理学原理》课程教学资源(PPT课件)第一章 管理原理概述.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第一章 管理与管理者.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第七章 沟通.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第三章 计划.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第二章 管理思想的演进.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第五章 领导.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第八章 控制.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第六章 激励.ppt
- 《管理学》课程教学资源(PPT课件讲稿)第四章 组织.ppt
- 仓库生产绩效管理(PPT讲稿).ppt
- 中国人民大学:《管理学原理》课程参考书籍PDF电子版(编写:杨文士).pdf
- 东北财经大学出版社:市场营销经典译丛《服务营销精要》教学资源(案例).pdf
- 东北财经大学出版社:市场营销经典译丛《服务营销精要》教学课件PPT讲稿(概念、策略和案例,共十六章).ppt