运筹08(第四章整数规划)
43页1、2018/10/16,1,运筹学 OPERATIONS RESEARCH,2018/10/16,2,第四章 整数规划与分配问题 (Integer Programming, IP),整数规划的有关概念及特点 整数规划的求解方法:分枝定界法、割平面法 指派问题及匈牙利解法 整数规划的应用,2018/10/16,3,纯整数规划:在整数规划中,如果所有的变量都为非负整 数,则称为纯整数规划问题; 混合整数规划:如果有一部分变量为非负整数,则称之为混合整数规划问题。0-1变量:在整数规划中,如果变量的取值只限于0和1,这 样的变量我们称之为0-1变量。 0-1规划:在整数规划问题中,如果所有的变量都为0-1变量,则称之为0-1规划。,1 整数规划的有关概念及特点,一、 概念,整数规划: 要求决策变量取整数值的规划问题。(线性整数规划、非线性整数规划等),2018/10/16,4,求整数解的线性规划问题,不是用四舍五入法或去尾法对 性规划的非整数解加以处理就能解决的,用枚举法又往往 会计算量太大,所以要用整数规划的特定方法加以解决。例: 求解下列整数规划:,二、 整数规划的求解特点,2018/10
2、/16,5,分析: 若当作一般线性规划求解,图解法的结果如下。,1、非整数规划最优解 显然不是整数规划的可行解。 2、四舍五入后的结果 也不是整数规划的可行解。,3、可行解是阴影区域交叉点,可比较这些点对应的函数值,找出最优。,2018/10/16,6,2 应用举例,一、 逻辑变量在数学模型中的应用,1、m个约束条件中只有k个起作用 设有m个约束条件,定义0-1整型变量:M是任意大正数。,第i个约束起作用 第i个约束不起作用,则原约束中只有k个真正起作用的情况可表示为:,2018/10/16,7,2、约束条件右端项是r个可能值中的一个,则通过定义,约束条件右端项不是bi 约束条件右端项是bi,可将上述条件表示为,2018/10/16,8,3、两组条件中满足其中一组 例如表示条件:若 ,则 ;否则 时,则通过定义,第i组条件起作用,i=1,2 第i组条件不起作用,可将上述条件表示为,又:M是任意大正数,,2018/10/16,9,定义,4、表示含有固定费用的函数 例如: 表示产品 j 的生产数量,其生产费用函数为:,目标函数:,其中 是与产量无关的生产准备费用,则原问题可表示为,2018
3、/10/16,10,二、 应用举例,例1: 书P120,例3,解:设 表示学生i在周j日的值班时间。,目标函数,约束条件,每天开放14小时,大学生值班不少于8小时,设,学生i个在周j不值班 学生i个在周j值班,2018/10/16,11,研究生值班不少于7小时,每周不超过3次,每天不超过3人,每天有一研究生,值班不超过每人可安排的时间,表示学生i在周j日的最多可值班时间。,2018/10/16,12,例2: 书P120,例4,解:设 表示代号为j的包装箱的订做数量。,不订j包装箱 订j包装箱,目标函数,约束条件,2018/10/16,13,2018/10/16,14,例3(固定成本问题) 高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如表所示。每种容器售出一只所得的利润分别为 4万元、5万元、6万元,可使用的金属板有500吨,劳动力有300人/月,机器有100台/月,此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是l00万元,中号为 150 万元,大号为200万元。现在要制定一个生产计划,使获得的利润为
4、最大。,2018/10/16,15,解:这显然是一个整数规划的问题。设x1,x2, x3 分别为小号容器、中号容器和大号容器的生产数量。各 种容器的固定费用只有在生产该种容器时才投入,为了说明固定费用的这 种性质,设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0(当不生产第 i种容器即 xi = 0 时)。引入约束 xi M yi ,i =1,2,3,M充分大,以保证当 yi = 0 时,xi = 0 。 建立如下的数学模型:Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 5002x1 + 3x2 + 4x3 300x1 + 2x2 + 3x3 100xi M yi ,i =1,2,3,M充分大xi 0 yj 为0-1变量,i = 1,2,3,2018/10/16,16,3 指派问题及匈牙利解法,一、 指派问题与模型,m项任务分配给m个人去完成,每人只能完成其中一项,每项任务只能分给一人完成,应如何分配使得效率最高?aij是第j个人完成第i项任务的效率。,2018/10/16,17,
《运筹08(第四章整数规划)》由会员kms****20分享,可在线阅读,更多相关《运筹08(第四章整数规划)》请在金锄头文库上搜索。
高三文科数学(长方体模型1)
高一生物:必修2 1.1孟德尔的豌豆杂交实验
遗传学第1章 绪言
高等代数课件--第三章 线性方程组§3.3 线性相关性
高二数学(1.1-1空间几何体及棱柱、棱锥的结构特征)
递回关系与演算法分析
过程是vb的基本组成单位
营养器官的生长
细菌真菌在生物圈中的作用课件(济南版七年级上)
自动化-ab变频器的原理及其应用
网络操作系统-第16章 windows server 2003安全管理
网络安全+第4讲+防火墙
素材-接触网施工技术-双线隧道吊柱安装
系统结构第5章
计算机体系结构实验2008
计算机系统安全
高考词汇总常用词v
软件测试tmap
电脑文件被删除怎么恢复图文教程
电子教案--第9章
2023-10-12 28页
2022-07-12 126页
2022-06-07 89页
2022-06-07 158页
2022-06-07 60页
2022-06-07 122页
2022-06-07 76页
2022-06-07 79页
2022-06-06 38页
2022-06-06 47页