第九章离散优化.ppt
《第九章离散优化.ppt》由会员分享,可在线阅读,更多相关《第九章离散优化.ppt(49页珍藏版)》请在三一文库上搜索。
1、,离散优化的应用,日程安排 资本预算 广告投放 运输问题 项目评价 等等,9.1用离散优化模型定量描述一个管理问题,我们将通过三个管理问题的实例来介绍离散优化模型的应用。 它们分别是: 实例9.1 一架飞机的制造问题 。 实例9.2 一个资本运算问题 。 实例9.3 一个战略重新布置的问题 。,实例9.1一架飞机的制造问题 (1),CRISP商务飞机制造公司生产四种类型小型商务飞机,分别为: AR1型,具有一个座位。 AR2型,具有二个座位。 AR4型,具有四个座位。 AR6型,具有六个座位。 飞机的制造是以月为单位进行的。 表9.1说明了CRISP公司的有关飞机制造的重要信息。,实例9.1一
2、架飞机的制造问题 (2),表9.1: CRISP公司飞机制造的相关信息,实例9.1一架飞机的制造问题 (3),表9.1的第一行说明了联邦航空局允许每种飞机在下个月的最大产量。 表9.1的第二行说明了建造每种飞机所需要的时间(以天为单位)。 表9.1的第三行说明了生产每种飞机所需要管理人员数目。 表9.1的最后行说明了每种飞机的单位利润。 在下个月, CRISP公司可用的管理人员总数为60人。 CRISP公司的生产能力为9架/天,按每月30天计算,下一个月可以得到的制造天数为270天。,实例9.1一架飞机的制造问题 (4),CRISP公司的主管想要确定在下一个月里每种飞机的生产数量,以便使公司的
3、利润最大化。 定义下述决策变量 。 A1=下一个月生产AR1型飞机的数目。 A2 =下一个月生产AR2型飞机的数目。 A4=下一个月生产AR4型飞机的数目。 A6=下一个月生产AR6型飞机的数目。 在这个问题中,每个决策变量必须是一个非负的整数值,即数的形式是0,1,2,3,。 所以CRISP公司的生产计划问题的模型必须包括对决策变量的下述约束: A1, A2 , A4, A6是整数,实例9.1一架飞机的制造问题 (5),CRISP公司的生产计划模型为: 最大化: 62A1+84A2+103A4+125A6 约束条件为: 建造时间: 4A1+7A2+9A4+11A6270 管理人员: A1+
4、A2+2A4+2A660 AR1产量: A1 8 AR2产量: A2 17 AR4产量: A4 11 AR6产量: A6 15 非负性: A1, A2,A4,A60 整数要求: A1, A2,A4,A6是整数,实例9.1一架飞机的制造问题 (6),把上述问题表示成电子表格形式,并且用EXCEL的规划求解进行求解(将在后面介绍)我们将获得CRISP公司的最优生产计划,参见表9.2。 表9.2,实例9.1一架飞机的制造问题 (7),注意在表9.2中,决策变量的取值都是整数。 这个计划的利润为: 利润=(628+ 8417 + 1031+ 12510) 1000=3277000(美元) 用于CRIS
5、P公司的生产计划模型是一个线性离散(或整数)优化模型的实例。 线性离散(或整数)优化模型的定义为:如果所有的决策变量被要求是非负整数,并且所有的约束和目标函数都是线性函数,那么该优化模型被称为一个线性离散(或整数)优化模型。,实例9.2一个资本预算问题 (1),K&A公司是一家中型建筑管理公司,公司正在考虑下一年可能要投资的工程项目。 表9.3说明了每个工程所需要的投资,以及每个工程在未来三年中的预期利润。 表9.3,实例9.2一个资本预算问题 (2),公司准备在下一年投入1,500万美元,希望选择使总预期利润最大化的那些工程。 设定决策变量。设 Xi表示工程是Xi被选中的决策变量,并且定义X
6、i如下: 如果工程1被选中,则X1=1 如果工程1没有被选中,则X1=0 如果变量X被要求只取数值0或1,那我们称这个变量X为二态变量。定义X2,X3,X4为: 如果工程2被选中,则X2=1 如果工程2没有被选中,则X2=0 如果工程3被选中,则X3=1 如果工程3没有被选中,则X3=0 如果工程4被选中,则X4=1 如果工程4没有被选中,则X4=0 X2,X3,X4都是二态变量。,实例9.2一个资本预算问题 (3),K&A公司的资本预算模型为下列优化模型。 最大化: 12X18 X27X36X4 约束条件为: 预算: 8X16X25X34X415 二态性: X1,X2,X3,X4是二态变量
7、我们可以把这个问题表示成电子表格的形式,并且计算出结果(将在后面介绍),参见表9.4 。 我们看到在表9.4中,决策变量的取值都是二态的,即0和1。根据表9.4中的数据,最优工程的选择是工程2,工程3以及工程4 。在这种方案之下的利润为: 120+ 81+ 71+ 61=21,实例9.2一个资本预算问题 (4),表9.4: K&A公司的资本预算问题的最优解,实例9.2一个资本预算问题 (5),K&A公司的资本预算问题的优化模型是一个线性二态化模型的实例。 线性二态化优化模型的定义为: 如果所有的决策变量被要求是二态变量(即0和1),并且并且所有的约束和目标函数都是线性函数,那么该优化模型被称为
8、一个线性二态优化模型。 一个线性二态优化模型也被称为线性0-1整数优化模型。 二态决策变量可以极大地增强特定类型的约束能力。例如,我们可以考虑以下附加约束: (1)公司最多可以投资两个工程。该约束被表示为: X1X2X3X42,实例9.2一个资本预算问题 (6),(2)如果工程4被选中,那么工程3必须被选择。该约束可被表示为: X3X40 (3)由于相关法律原因,公司不可以同时投资于工程1和工程3。该约束可被表示为: X1X31 如果我们把上述三个条件增加到资本预算模型中,那么新的线性二态优化模型为:,实例9.2一个资本预算问题 (7),最大化: 12X18 X27X36X4 约束条件为: 预
9、算: 8X16X25X34X415 两个工程最大数: X1X2X3X42 工程3和工程4: X3X42 工程1和工程3: X1X31 二态性: X1,X2,X3,X4是二态变量,实例9.2一个资本预算问题 (8),在次对上述问题利用EXCEL规划求解进行求解,求解结果参见表9.5。 表9.5,实例9.3一个战略重新布置的问题 (1),TRD公司是一家大型计算机制造企业。 目前, TRD公司有三个面向欧洲客户服务的服务中心,分别为:伦敦,马德里以及巴黎。 七个主要客户对TRD公司服务及时性提出投诉,这些客户反映它们需要等待两天时间才能获得从某个服务中心运来的计算机配件。 同时,TRD公司的运输成
10、本以及维持服务中心的运营成本一直在增加。 TRD公司考虑重新布置欧洲服务中心的位置,并希望将中心数目由目前3个减少到2个。 公司也考虑将汉堡和罗马作为可能的服务中心。 表9.6给出5个可能的服务中心(将从中选出两个)的年运营成本。,实例9.3一个战略重新布置的问题 (2),表9.6: TRD公司5个可能的服务中心,实例9.3一个战略重新布置的问题 (3),TRD公司的主要客户位于5个国家:英国,德国,瑞士,意大利和法国。表9.7说明了TRD公司的主要客户分布在5个国家的百分比。 表9.7,实例9.3一个战略重新布置的问题 (4),表9.8说明了单位配件从每个潜在的服务中心(共5个)到5个国家的
11、平均运输时间。 表9.8,实例9.3一个战略重新布置的问题 (5),公司目标是选择服务中心的位置使服务中心年度总经营成本最小化。 但是需要满足客户的要求: (1)从任何一个服务中心到任何一个国家的平均运输时间不超过1.5天。 (2)从任何一个服务中心到五个国家的总平均运输时间不超过1.1天(相当于对需求(1)再进行算术平均,共有5个值)。 设j=1,2,3,4,5分别表示5个潜在的服务中心位置, i=1,2,3,4,5分别表示5个国家。 定义二态决策变量:如果位置j被选中,yj=1,如果位置j没有被选中,yj=0,实例9.3一个战略重新布置的问题 (6),此外,对于i=1,2,3,4,5和j=
12、1,2,3,4,5。定义 xij=来自国家i的服务请求由服务中心j提供服务的比例 年运营成本为: 成本=20 y115 y2 22 y3 21 y4 16 y5 来自英国的服务请求被分解到5个服务中心,所以英国(i=1)的服务请求比例之和必须等于1: 比例1: x11 x12 x13 x14 x151 类似地,对于其他国家(i=2,3,4,5),我们将有类似的约束:,实例9.3一个战略重新布置的问题 (7),比例2: x21 x22 x23 x24 x251 比例3: x31 x32 x33 x34 x351 比例4: x41 x42 x43 x44 x451 比例5: x51 x52 x53
13、 x54 x551 定义决策变量wi,分别表示从5个中心到国家i的平均运输时间(天)。根据表9.8中的数据,我们可以把w1, w2 , w3 , w4 ,和w5表示为: w1 0.5x112.5x121.5x132.0x143.0x15 w2 2.0x213.0x221.0x230.5x242.0x25 w3 3.0x312.0x322.0x331.5x341.0x35 w4 3.0x411.0x422.0x432.0x440.5x45 w5 1.5x512.0x520.5x531.0x542.0x55,实例9.3一个战略重新布置的问题 (8),由于从5个中心到一个国家的平均运输时间不超过1.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第九 离散 优化
链接地址:https://www.31doc.com/p-3003808.html