整数规划运筹学交大工商管理讲义PPT课件.ppt
《整数规划运筹学交大工商管理讲义PPT课件.ppt》由会员分享,可在线阅读,更多相关《整数规划运筹学交大工商管理讲义PPT课件.ppt(39页珍藏版)》请在咨信网上搜索。
1、第四章第四章 整数规划整数规划(Integer Programming,IP)整数规划整数规划(IntegerProgramming)主要是指整数线)主要是指整数线性规划。一个线性规划问题,如果要求部分决策变量性规划。一个线性规划问题,如果要求部分决策变量为整数,则构成一个整数规划问题。为整数,则构成一个整数规划问题。所有变量都要求为整数的称为所有变量都要求为整数的称为纯整数规划纯整数规划(PureIntegerProgramming)或称)或称全整数规划全整数规划(AllintegerProgramming););仅有一部分变量要求为整数的称为仅有一部分变量要求为整数的称为混合整数规划混合整
2、数规划(MixedIntegerProgramming););有的变量限制其取值只能为有的变量限制其取值只能为0或或1,这类特殊的整数规,这类特殊的整数规划称为划称为01规划规划(0-1IntegerProgramming)。整数规划的有关概念整数规划的有关概念一、整数规划问题一、整数规划问题例例4.1某工厂生产甲、乙两种设备,已知生产这两种设某工厂生产甲、乙两种设备,已知生产这两种设备需要消耗材料备需要消耗材料A、材料、材料B,有关数据如下,问这两种,有关数据如下,问这两种设备各生产多少使工厂利润最大?设备各生产多少使工厂利润最大?设备设备材材料料甲甲乙乙资源限量资源限量材料材料A(kg)2
3、314材料材料B(kg)10.54.5利润(元利润(元/件)件)32第一节第一节 整数规划问题及其数学模型整数规划问题及其数学模型解:解:设生产甲、乙这两种设备的数量分别为设生产甲、乙这两种设备的数量分别为x1、x2,由于是设备台数,则其变量都要求为整数,建立模由于是设备台数,则其变量都要求为整数,建立模型如下:型如下:Maxz=3x1+2x22x1+3x214x1+0.5x24.5x1、x20,且为整数且为整数要求该模型的解,不考虑整数约束条件,用单纯形法要求该模型的解,不考虑整数约束条件,用单纯形法对相应线性规划求解,其最优解为:对相应线性规划求解,其最优解为:x13.25x22.5max
4、z14.75凑整得到的凑整得到的(4,2)不在可行域范围内。不在可行域范围内。(3,2)点尽管在可行域内,但没有使目标达到极大化。点尽管在可行域内,但没有使目标达到极大化。(4,1)使目标函数达到最大,即使目标函数达到最大,即z14。二、整数规划数学模型的一般形式二、整数规划数学模型的一般形式由上述例子可得出整数规划数由上述例子可得出整数规划数学模型的一般形式:学模型的一般形式:Maxz=CXAX=bX0,且为整数或部分且为整数或部分为整数为整数若称该整数规划问题为若称该整数规划问题为原问题原问题,则线性规划问题:则线性规划问题:Maxz=CXAX=bX0为原问题对应的为原问题对应的松驰问题松
5、驰问题(LPRelaxation)。显然,原问题与松弛问显然,原问题与松弛问题有如下关系:题有如下关系:1)松弛问题可行域包含原松弛问题可行域包含原问题可行域;问题可行域;2)若两者都有最优解,则若两者都有最优解,则松弛问题最优解大于原松弛问题最优解大于原问题最优解;问题最优解;3)若松弛问题最优解为整若松弛问题最优解为整数解,则该最优解就是数解,则该最优解就是原问题最优解。原问题最优解。整数规划常用的解法有分枝定界法和割平面法,它整数规划常用的解法有分枝定界法和割平面法,它们适用于解纯整数规划问题和混合整数规划问题。们适用于解纯整数规划问题和混合整数规划问题。一、分枝定界法一、分枝定界法 基
6、本思想基本思想二、割平面法二、割平面法 基本思想基本思想三、整数规划的计算机解法三、整数规划的计算机解法 计算机求解举例计算机求解举例第二节第二节 整数规划的解法整数规划的解法第三节第三节 0 01 1整数规划整数规划一、一、0 01 1整数规划模型整数规划模型01整数规划在实际中应用较多。因为实际问题中经整数规划在实际中应用较多。因为实际问题中经常碰到大量的决策问题,要求回答常碰到大量的决策问题,要求回答“是否是否”或或“有有无无”问题,这类问题可以借助整数规划中的问题,这类问题可以借助整数规划中的01整整数变量,使许多复杂的、困难的问题相对变得简单。数变量,使许多复杂的、困难的问题相对变得
7、简单。01变量一般可表示为:变量一般可表示为:01整数规划的数学模型可表示为:整数规划的数学模型可表示为:第三节第三节 0 01 1整数规划整数规划二、二、0 01 1整数规划求解整数规划求解01整数规划的求解方法有穷举法、隐枚举法和分枝整数规划的求解方法有穷举法、隐枚举法和分枝定界法定界法.隐枚举法求解举例隐枚举法求解举例解:解:(1)先用试探的方法找出一个初始可行解,如)先用试探的方法找出一个初始可行解,如x1x20,x31。满足约束条件,选其作为初始可行。满足约束条件,选其作为初始可行解,目标函数解,目标函数z02。(2)附加过滤条件)附加过滤条件以目标函数作为过滤约束:以目标函数作为过
8、滤约束:4x13x22x3=2原模型变为:原模型变为:(3 3)求解)求解求解求解过程如表程如表4 46 6所示。所示。点点过滤条件过滤条件约束约束z值值4x13x22x32(0,0,0)T(0,0,1)T2(0,1,0)T(0,1,1)T54x13x22x35(1,0,0)T(1,0,1)T(1,1,0)T74x13x22x37(1,1,1)T9一、相互排斥的计划一、相互排斥的计划(Mutuallyexclusiveplanning)例例4.6某公司拟在市东、西、南三区中建立门市部,某公司拟在市东、西、南三区中建立门市部,有例有例7个点个点Ai(i1,2,7)可供选择,要求满)可供选择,要求
9、满足以下条件:足以下条件:1)在东区,在在东区,在A1,A2,A3三个点中至多选两个;三个点中至多选两个;2)在西区,在西区,A4,A5两个点中至少选一个;两个点中至少选一个;3)在南区,在南区,A6,A7两个点为互斥点。两个点为互斥点。4)选选A2点必选点必选A5点。点。若若Ai点投资为点投资为bi万元,每年可获利润为万元,每年可获利润为ci万元,投资万元,投资总额为总额为B万元,试建立利润最大化的万元,试建立利润最大化的01规划模型。规划模型。第四节 01整数规划应用(Applications)解:设决策变量为解:设决策变量为建立建立01规划模型如下:规划模型如下:例例4.7某产品有某产品
10、有A1和和A2两种型号,需要经过两种型号,需要经过B1、B2、B3三道工序,单位工时和利润、各工序每周工时限制见表所三道工序,单位工时和利润、各工序每周工时限制见表所示,问工厂如何安排生产,才能使总利润最大?(示,问工厂如何安排生产,才能使总利润最大?(B3工工序有两种加工方式序有两种加工方式B31和和B32,产品为整数)。,产品为整数)。二、互排斥的约束条件二、互排斥的约束条件(Mutuallyexclusiveconstraints)工序工序型号型号B1B2B3利润利润(元(元/件)件)B31B32A1A20.30.70.20.10.30.50.20.42540每周工时每周工时(小时小时/
11、月月)250100150120解:设解:设A1、A2产品的生产数量分别为产品的生产数量分别为x1、x2件,在不件,在不考虑考虑B31和和B32相互排斥的情况下,问题的数学模型为相互排斥的情况下,问题的数学模型为工序工序B3只能从两种加工方式中选择一种,那么约束条件只能从两种加工方式中选择一种,那么约束条件(1)和()和(2)就成为相互排斥的约束条件。为了统一在一)就成为相互排斥的约束条件。为了统一在一个问题中,引入个问题中,引入0-1变量变量则数学模型为则数学模型为一般地,在建立数学模型时,若需从一般地,在建立数学模型时,若需从p个约束条件个约束条件中选择中选择q个约束条件,则可以引入个约束条
12、件,则可以引入p个个0-1变量变量那么约束条件组那么约束条件组例例4.8某公司制造小、中、大三种尺寸的容器,所需某公司制造小、中、大三种尺寸的容器,所需资源为金属板、劳动力和机器设备,制造一个容器所资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如下表所示:不考虑固定费用,需的各种资源的数量如下表所示:不考虑固定费用,小、中、大号容器每售出一个其利润分别为小、中、大号容器每售出一个其利润分别为4万元、万元、5万元、万元、6万元,可使用的金属板有万元,可使用的金属板有500吨,劳动力有吨,劳动力有300人人/月,机器有月,机器有100台台/月,另外若生产,不管每种容器月,另外若生
13、产,不管每种容器生产多少,都需要支付一笔固定费用:小号为生产多少,都需要支付一笔固定费用:小号为100万元,万元,中号为中号为150万元,大号为万元,大号为200万元。问如何制定生产计万元。问如何制定生产计划使获得的利润对大?划使获得的利润对大?三、固定成本问题三、固定成本问题(Fixedcostproblem)解解:设:设x1、x2、x3分别为小号容器、中号容器、大号容器分别为小号容器、中号容器、大号容器的生产数量。不考虑固定费用,则问题的数学模型为的生产数量。不考虑固定费用,则问题的数学模型为资源资源小号容器小号容器中号容器中号容器大号容器大号容器金属板(吨)金属板(吨)248劳动力(人劳
14、动力(人/月)月)234机器设备(台机器设备(台/月)月)123若考虑固定费用就必须引入若考虑固定费用就必须引入01变量:变量:则该问题的数学模型为则该问题的数学模型为例例4.9某城市消防队布点问题。该城市共有某城市消防队布点问题。该城市共有6个区,每个区都可以建消个区,每个区都可以建消防站,市政府希望设置的消防站最少,但必须满足在城市任何地区发防站,市政府希望设置的消防站最少,但必须满足在城市任何地区发生火警时,消防车要在生火警时,消防车要在15分钟内赶到现场。据实地测定,各区之间消分钟内赶到现场。据实地测定,各区之间消防车行驶的时间见表防车行驶的时间见表49,请帮助该市制定一个布点最少的计
15、划。,请帮助该市制定一个布点最少的计划。地区地区1地区地区2地区地区3地区地区4地区地区5地区地区6地区地区101016282720地区地区210024321710地区地区316240122721地区地区428321201525地区地区527172715014地区地区620102125140四、布点问题四、布点问题 (LocationProblem)表表49 消防车在各区间行驶时间表消防车在各区间行驶时间表 单位:单位:min本问题的约束方程是要保证每个地区都有一个消防站本问题的约束方程是要保证每个地区都有一个消防站在在15分钟行程内。如地区分钟行程内。如地区1,由表,由表49可知,在地区可知
16、,在地区1及地区及地区2内设消防站都能达到此要求,即内设消防站都能达到此要求,即x1x21因此本问题的数学模型为:因此本问题的数学模型为:minzx1x2x3x4x5x6x1x21x1x2x61x3x41x3x4x51x4x5x61x2x5x61xi1或或0(i1,6)解:引入解:引入01变量变量xi作决策变量,令作决策变量,令资金预算(资金预算(Capitalbudgetingproblem)冰冷电冰箱公司正在考虑冰冷电冰箱公司正在考虑4种投资方案,有关数据如下表。种投资方案,有关数据如下表。问题:问题:选择投资项目使总现值最大选择投资项目使总现值最大。五、其他案例五、其他案例冰冷电冰箱公司
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 整数 规划 运筹学 交大 工商管理 讲义 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。