运筹学整数规划和分配问题新.pptx
《运筹学整数规划和分配问题新.pptx》由会员分享,可在线阅读,更多相关《运筹学整数规划和分配问题新.pptx(69页珍藏版)》请在咨信网上搜索。
1、作业:作业:P125 4.1 4.2 4.3(a)4.4第四章第四章 整数规划与分配问题整数规划与分配问题第一节第一节 整数规划的特点及应用整数规划的特点及应用一、整数规划的一般形式一、整数规划的一般形式定义:一部分或全部决策变量必须取整数定义:一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数值的规划问题称为整数规划。不考虑整数条件,由余下的目标函数和约束条件构成条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题。的规划问题称为该整数规划的松弛问题。若松弛问题是线性规划,则该整数规划称若松弛问题是线性规划,则该整数规划称为整数线性规划。为整数线性规划。整数
2、线性规划的一般形式:不考虑整数要求时,不考虑整数要求时,最优解为:最优解为:X=(3.25,2.5)X=(3.25,2.5)T T Z=13 Z=13 (见下页图解法)(见下页图解法)考虑整数要求时,最优解为:考虑整数要求时,最优解为:X=(4 X=(4,1),1)T T Z=14Z=14凑整凑整 (3 3,2 2)可行,非最优,)可行,非最优,Z=13Z=13。(4 4,3 3),(),(4 4,2 2),(),(3 3,3 3)不可行不可行二、整数规划的分类二、整数规划的分类1.1.全整数线性规划全整数线性规划 决策变量全部取整数,约束系数和约束常数项决策变量全部取整数,约束系数和约束常数
3、项也取整数的整数线性规划。也取整数的整数线性规划。2.2.纯整数线性规划纯整数线性规划 决策变量全部取整数,约束系数和约束常数项决策变量全部取整数,约束系数和约束常数项可取非整数的整数线性规划。可取非整数的整数线性规划。纯整数线性规划可化为全整数线性规划。纯整数线性规划可化为全整数线性规划。3.3.混合整数线性规划混合整数线性规划 决策变量中有一部分取整数值,另一部分可取决策变量中有一部分取整数值,另一部分可取非整数值的整数线性规划。非整数值的整数线性规划。4.0-14.0-1整数线性规划整数线性规划 决策变量只能取决策变量只能取0 0或或1 1的整数线性规划。的整数线性规划。三、三、0-1变
4、量(或称逻辑变量)在模型中变量(或称逻辑变量)在模型中的应用的应用 整数规划模型对研究管理问题有重要整数规划模型对研究管理问题有重要意义。很多不能归结为线性规划数学模意义。很多不能归结为线性规划数学模型的管理问题,却可以通过设置逻辑变型的管理问题,却可以通过设置逻辑变量建立起整数规划数学模型。量建立起整数规划数学模型。第二节第二节 分配问题分配问题(指派问题)与匈牙利法指派问题)与匈牙利法 2-1 2-1 问题的提出及数学模型问题的提出及数学模型 假设有假设有m m项任务分配给项任务分配给m m个人去完成,并个人去完成,并指定每个人完成其中一项,每项任务也只由指定每个人完成其中一项,每项任务也
5、只由一个人完成,问应如何分配任务,才能使总一个人完成,问应如何分配任务,才能使总效率最高?(或总费用最少,花费的总时间效率最高?(或总费用最少,花费的总时间最少等等。)最少等等。)设每个人完成不同任务的耗费见下面的设每个人完成不同任务的耗费见下面的效率矩阵,通常要求效率矩阵,通常要求a aijij00。则分配问题的数学模型为则分配问题的数学模型为2-2 2-2 匈牙利法匈牙利法定理定理1.1.如果从分配问题效率矩阵如果从分配问题效率矩阵(a(aijij)的每一的每一行元素中分别减去(或加上)一个常数行元素中分别减去(或加上)一个常数u ui i (称为该行的位势);从每一列中分别减去(称为该行
6、的位势);从每一列中分别减去(或加上)一个常数(或加上)一个常数 v vj j (称为该列的位势)(称为该列的位势);得到一个新的效率矩阵;得到一个新的效率矩阵b bijij,其中,其中b bijij=a=aijij-u ui i-v-vj j ,则,则a aijij的最优解等价于的最优解等价于b bijij的最优解。的最优解。定理定理2.2.若效率矩阵若效率矩阵A A的元素可分成的元素可分成0 0与非与非0 0两两部分,则覆盖所有部分,则覆盖所有0 0元素的最少直线数等于位元素的最少直线数等于位于于不同行不同列不同行不同列的的0 0元素的最大个数。元素的最大个数。匈牙利法的步骤:匈牙利法的步
7、骤:第一步第一步 效率矩阵每行都减去该行的最小元素;效率矩阵每行都减去该行的最小元素;第二步第二步 效率矩阵每列都减去该列的最小元素;效率矩阵每列都减去该列的最小元素;此时,效率矩阵的此时,效率矩阵的每行每列每行每列都有都有0 0元素。元素。第三步第三步 寻找位于寻找位于不同行不同列不同行不同列的的0 0元素,也就是元素,也就是寻找能覆盖所有寻找能覆盖所有0 0元素的最少直线数。元素的最少直线数。方法:方法:1.1.从从只有一个只有一个0 0元素元素的行开始,对的行开始,对0 0元素打上(元素打上()号,然后对打()号,然后对打()的)的0 0元素所在元素所在列列画一条直线,画一条直线,依次进
8、行到最后一行;依次进行到最后一行;2.2.从只有一个从只有一个0 0元素的列开始,对元素的列开始,对0 0元素打上(元素打上()号,)号,然后对打(然后对打()的)的0 0元素所在元素所在行行画一条直线,画一条直线,依次进行到最后一列;依次进行到最后一列;3.3.重复重复1.1.、2.2.两个步骤,可能出现三种情况:两个步骤,可能出现三种情况:(1 1)若能找到)若能找到m m个位于不同行不同列的个位于不同行不同列的0 0元素(即元素(即带(带()的)的0 0元素),则令(元素),则令(0 0)处的)处的x xijij=1,=1,求解结求解结束;束;(2 2)若有形成闭回路的)若有形成闭回路的
9、0 0元素,则任选一个打(元素,则任选一个打(),然后对每个间隔的),然后对每个间隔的0 0元素打(元素打(),同时对打),同时对打()的)的0 0元素所在行(或列)画一条直线。元素所在行(或列)画一条直线。(3 3)若位于不同行不同列的)若位于不同行不同列的0 0元素元素 即带(即带()的)的0 0元素元素 少于少于m m,转第四步。,转第四步。第四步第四步 为产生为产生m m个位于不同行不同列的个位于不同行不同列的0 0元素,元素,用定理一对效率矩阵进行调整,使之生成新的用定理一对效率矩阵进行调整,使之生成新的0 0元素。方法:元素。方法:1.1.在效率矩阵未被直线覆盖的元素中找出最小在效
10、率矩阵未被直线覆盖的元素中找出最小元素元素k k;2.2.效率矩阵未被直线覆盖的行都减效率矩阵未被直线覆盖的行都减k;k;3.3.效率矩阵被直线覆盖的列都加效率矩阵被直线覆盖的列都加k;k;4.4.转回第三步。转回第三步。2-3 特殊情况的处理特殊情况的处理1.人数多于任务数,加虚拟任务。人数多于任务数,加虚拟任务。设有设有n人,人,m项任务,项任务,nm,则增加则增加n-m项任务。项任务。2.人数少于任务数,加虚拟人员。人数少于任务数,加虚拟人员。设有设有n人,人,m项任务,项任务,nm,则增加则增加m-n项任务。项任务。此时,效率矩阵的元素全成为负值,不符合要此时,效率矩阵的元素全成为负值
11、,不符合要求,根据定理求,根据定理1 1,令,令变换后的效率矩阵每行都加变换后的效率矩阵每行都加M M即可。即可。3.对求最大值问题的处理对求最大值问题的处理设目标函数为设目标函数为可将其变换为可将其变换为作业:作业:P126 4.7P126 4.7(a)4.8(a)a)4.8(a)第三节第三节 分枝定界法分枝定界法一、分枝定界法的基本思想一、分枝定界法的基本思想 先不考虑整数解的限制,用单纯形法求先不考虑整数解的限制,用单纯形法求解其松弛问题,如果求得的解恰好是整数解,解其松弛问题,如果求得的解恰好是整数解,则得整数规划最优解,停止计算。否则,将则得整数规划最优解,停止计算。否则,将松弛问题
12、分解为两个子问题(也称后继问题)松弛问题分解为两个子问题(也称后继问题),每个子问题都是在原松弛问题的基础上增,每个子问题都是在原松弛问题的基础上增加一个变量取整数的约束条件,这样就缩小加一个变量取整数的约束条件,这样就缩小了原来的可行域,然后用单纯形法求解,直了原来的可行域,然后用单纯形法求解,直至得到最终结果。至得到最终结果。二、分枝定界法的步骤(最大值问题)二、分枝定界法的步骤(最大值问题)第一步第一步 寻找替代问题并求解寻找替代问题并求解 设原整数规划问题为设原整数规划问题为IPIP,其松弛问题为,其松弛问题为L L0 0。用单纯形法求。用单纯形法求L L0 0,若若L L0 0无可行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 整数 规划 分配 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。