第九章离散优化.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.

14、5天,我们加入下列约束。 时间约束: w11.5, w2 1.5, w3 1.5 , w4 1.5 , w5 1.5 此外,还要保证从中心到5个国家的平均运输时间不超过1.1天。利用表9.7中的数据,我们有以下约束(用客户比例加权): 总运输时间:0.25w10.30 w2 0.15 w3 0.10 w4 0.20w5 1.1 如果yj=0,那么对于所有i=1,2,3,4,5来说xij=0 。那么有: 逻辑:对于所有的i=1,2,3,4,5和j=1,2,3,4,5, xijyj,实例9.3一个战略重新布置的问题 (9),最后, 由于公司希望服务中心的数目为2个(原来为3个),所以,服务中心的数

15、目应当大于2个或者小于3个,那么我们将加上以下约束条件: 数目2个: y1 y2 y3 y4 y52 数目3个: y1 y2 y3 y4 y53 注意到,这个优化模型有35个决策变量,即25个变量xij, 5个变量wi以及5个二态变量yj 。 最后,我们把TRD公司的服务中心重新布置问题表示为下述离散优化模型:,实例9.3一个战略重新布置的问题 (10),最小化 20 y115 y2 22 y3 21 y4 16 y5 约束条件为: 比例1: x11 x12 x13 x14 x151 比例2: x21 x22 x23 x24 x251 比例3: x31 x32 x33 x34 x351 比例4

16、: x41 x42 x43 x44 x451 比例5: x51 x52 x53 x54 x551 运输时间1: w1 0.5x112.5x121.5x132.0x143.0x15 运输时间2: w2 2.0x213.0x221.0x230.5x242.0x25 运输时间3: w3 3.0x312.0x322.0x331.5x341.0x35 运输时间4: w4 3.0x411.0x422.0x432.0x440.5x45 运输时间5: w5 1.5x512.0x520.5x531.0x542.0x55 时间约束: w11.5, w2 1.5, w3 1.5 , w4 1.5 , w5 1.5

17、总运输时间: 0.25w10.30 w2 0.15 w3 0.10 w4 0.20w5 1.1 逻辑:对于所有的i=1,2,3,4,5和j=1,2,3,4,5, xijyj 数目2: y1 y2 y3 y4 y52 数目3: y1 y2 y3 y4 y53 非负性: xij0,其中i=1,2,3,4,5和j=1,2,3,4,5 整数性: yj是二态变量,其中i=1,2,3,4,5,实例9.3一个战略重新布置的问题 (11),我们可以把上述TRD公司的服务中心重新布置的离散优化问题表示成电子表格的形式,并且利用EXCEL的规划求解功能进行计算(我们将在后面介绍如何求解一个离散优化问题),其结果参

18、见表9.9,表9.10和表9.11 。,实例9.3一个战略重新布置的问题 (12),表9.9,实例9.3一个战略重新布置的问题 (13),表9.10 决策变量xij的最优值,实例9.3一个战略重新布置的问题 (14),表9.11 运输时间的决策变量wi的最优值,实例9.3一个战略重新布置的问题 (15),我们来研究这个最优解。 根据表9.9,服务中心的最优选择是巴黎和罗马,总成本为: 200+ 150+ 221+ 210+ 161=38 根据表9.9 ,我们有: 所有来自英国的客户应向巴黎服务中心请求服务。 91.7%的德国客户应向巴黎服务中心请求服务,剩下的8.3%的德国客户应向罗马服务中心

19、请求服务。 TRD公司所面临的战略重新布置问题的优化模型是一个混合整数优化模型,其定义为:,实例9.3一个战略重新布置的问题 (16),如果一些决策变量要求要么是非负整数,要么是二态变量,而其余决策变量被允许是普通决策变量,并且所有的约束和目标函数都是线性函数,那么该优化模型被称为一个混合整数优化模型。,9.1离散优化问题类型小结,三种类型的离散优化模型。 一个整数优化模型是所有的决策变量被要求是非负整数,并且所有的约束和目标函数都是线性函数。 一个二态优化模型是所有决策变量被要求是二态变量,并且所有的约束和目标函数都是线性函数。 一个混合整数优化模型是一些决策变量要求要么是非负整数,要么是二

20、态变量,而其余决策变量被允许是普通决策变量,并且所有的约束和目标函数都是线性函数。,9.2具有两个变量的离散优化模型的图形分析(1),我们以两个变量的离散优化模型为例研究其几何特征。 考虑下列整数优化问题(IM): 最大化 150X+112Y 约束条件: 7.5X+6Y90 8X+12Y138 55X+33Y600 X,Y是整数 我们构造IM问题的可行域的图形,参见图9.1。,9.2具有两个变量的离散优化模型的图形分析(2),Y,X,图9.1,。,。,。,。,。,。,。,。,。,。,。,。,。,9.2具有两个变量的离散优化模型的图形分析(3),设点(X,Y)属于上述多边形中的整数点,所有整数点

21、的集合就是整数优化问题IM的可行域。我们可以观测到: IM的可行域可行域是一个离散点的集合,是多边形的子集。 该可行域不存在的顶点。 可行域的边界并不一定对应着两个约束相遇的地方。,9.3离散优化问题的计算机求解(1),电子表格软件EXCEL可以用来求解一个离散优化问题。 考虑实例9.1的CRISP公司的生产计划模型为: 最大化: 62A1+84A2+103A4+125A6 约束条件为: 建造时间: 4A1+7A2+9A4+11A6270 管理人员: A1+ A2+2A4+2A660 AR1产量: A1 8 AR2产量: A2 17 AR4产量: A4 11 AR6产量: A6 15 非负性:

22、 A1, A2,A4,A60 整数要求: A1, A2,A4,A6是整数,9.3离散优化问题的计算机求解(2),实例9.1的电子表格的表示形式。,9.3离散优化问题的计算机求解(3),作业(5),P491 练习9.3 P493 练习9.5 P493 练习9.6,9.6案例分析-Dellmar公司的供应链管理(1),Dellmar公司是一家商用空调系统制造商 。公司一年前引进的空调系统CAP非常成功。产品的订单一直在上升。 但是这款产品的成功却暴露了Dellmar公司物流系统的不足。国内和区域分发中心对CAP进出的耽搁使客户的订单受到不同程度的延误。 过高的库存和运输成本也引起Dellmar公司

23、管理层的关注。在2月份,库存和运输成本超过了140万美元。 公司管理层希望制定能够将产品迅速交给客户同时降低库存和运输成本的解决方案。,9.6案例分析-Dellmar公司的供应链管理(2),CAP空调系统的供应链 Dellmar公司在NH制造工厂制造CAP系统。这个工厂每月可以生产5万部CAP系统。 公司正在考虑扩大每月10%的生产能力,每月须额外支付财务和运营成本为55,000美元。 Dellmar公司将国内销售区域划分为三个区域:东部,西部和中西部。每个区域由一个区域销售分发中心提供服务。 Dellmar公司还经营着两个国内分发中心,一个位于Ohio (为中西部和西部提供服务),另一个位于

24、NJ(为中西部和东部提供服务) 。 CAP空调系统首先由NH工厂运输到两个国内分发中心库存。然后,再运输到三个区域销售分发中心。 运输的时间为每月一次。,9.6案例分析-Dellmar公司的供应链管理(3),运输和库存成本 CAP空调系统从工厂运输到一个国内分发中心,或者从一个国内分发中心运输到任何一个区域分发中心,单位运输成本是每系统10美元。 安排货运的固定运输成本参见表9.15 。 在Ohio和NJ国内分发中心的库存成本是每月每件5美元。 而在区域销售分发中心的单位库存成本是每月每件10美元。,9.6案例分析-Dellmar公司的供应链管理(4),表9.15,9.6案例分析-Dellma

25、r公司的供应链管理(5),CAP空调系统的需求 CAP空调系统在未来两个月的需求情况参见表9.16 。 9.16: 4月5月的CAP空调系统的需求预测,9.6案例分析-Dellmar公司的供应链管理(6),库存 表9.17说明了CAP空调系统在3月底每个分发中心的库存量。 表9.17: 3月底的CAP空调系统的库存量,9.6案例分析-Dellmar公司的供应链管理(7),问题 (1)公司管理层要决定每月制造多少件CAP空调系统,以及每月运送多少件系统到分发中,以便使运输和库存的总成本最小化。 (2)目前,在任何一个分发中心,没有任何用于CAP空调系统的最小库存量政策。为了预防对CAP空调系统的

26、突然大量需求,公司正在考虑在每个分发中心(国内以及区域的分发中心)每月增加最小库存量到500件或者可能的1,000件。 (3)公司想要做出一个有关是否增加NH工厂的生产能力的建议。,9.6案例分析-Dellmar公司的供应链管理(8),作业 (1)构造一个在4月和5月期间,使运输和库存的总成本最小化的离散优化模型。 (2)在2月,运输和库存的总成本是140万美元,而且3月的预估成本也是140万美元。利用(1)中的模型, Dellmar公司在4月和5月份的平均成本是多少? Dellmar公司的生产和运输调度计划是什么? Dellmar公司在每个分发中心应该保持多少库存量? (3)如果Dellmar公司决定增加10%的生产能力,对运输和库存的总成本的影响是什么? (4)公司正考虑在分发中心增加最小库存量,按每月从0增加到500甚至1,000件CAP空调系统。假设当前的生产能力是每月50,000件,制定上述政策是可行的吗?这个政策的变化对运输和库存的总成本有何种影响? (5)你对Dellmar公司的库存政策,运输计划,和产能做出什么样的调整。,