资源描述：
《离散优化ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散优化的应用日程安排资本预算广告投放运输问题项目评价等等9.1用离散优化模型定量描述一个管理问题我们将通过三个管理问题的实例来介绍离散优化模型的应用。它们分别是:实例9.1一架飞机的制造问题。实例9.2一个资本运算问题。实例9.3一个战略重新布置的问题。实例9.1一架飞机的制造问题(1)CRISP商务飞机制造公司生产四种类型小型商务飞机,分别为:AR1型,具有一个座位。AR2型,具有二个座位。AR4型,具有四个座位。AR6型,具有六个座位。飞机的制造是以月为单位进行的。表9.1说明了CRISP公司的有关飞机制造的重要信息。实例9.1一架飞机的制造问题(2)表9.1:CRISP公司飞
2、机制造的相关信息AR1AR2AR4AR6联邦航空局允许的最大产量8171115建造飞机所需要的天数47911建造一架飞机需要的管理人员1122一架飞机的利润($1000)6284103125实例9.1一架飞机的制造问题(3)表9.1的第一行说明了联邦航空局允许每种飞机在下个月的最大产量。表9.1的第二行说明了建造每种飞机所需要的时间(以天为单位)。表9.1的第三行说明了生产每种飞机所需要管理人员数目。表9.1的最后行说明了每种飞机的单位利润。在下个月,CRISP公司可用的管理人员总数为60人。CRISP公司的生产能力为9架/天,按每月30天计算,下一个月可以得到的制造天数为270天。
3、实例9.1一架飞机的制造问题(4)CRISP公司的主管想要确定在下一个月里每种飞机的生产数量,以便使公司的利润最大化。定义下述决策变量。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约束条件
4、为:建造时间:4A1+7A2+9A4+11A6≤270管理人员:A1+A2+2A4+2A6≤60AR1产量:A1≤8AR2产量:A2≤17AR4产量:A4≤11AR6产量:A6≤15非负性:A1,A2,A4,A6≥0整数要求:A1,A2,A4,A6是整数实例9.1一架飞机的制造问题(6)把上述问题表示成电子表格形式,并且用EXCEL的规划求解进行求解(将在后面介绍)我们将获得CRISP公司的最优生产计划,参见表9.2。表9.2飞机类型决策变量下一个月最优生产数量AR1A18AR2A217AR4A41AR6A610实例9.1一架飞机的制造问题(7)注意在表9.2中,决策变量的取值都是整
5、数。这个计划的利润为:利润=(62×8+84×17+103×1+125×10)×1000=3277000(美元)用于CRISP公司的生产计划模型是一个线性离散(或整数)优化模型的实例。线性离散(或整数)优化模型的定义为:如果所有的决策变量被要求是非负整数,并且所有的约束和目标函数都是线性函数,那么该优化模型被称为一个线性离散(或整数)优化模型。实例9.2一个资本预算问题(1)K&A公司是一家中型建筑管理公司,公司正在考虑下一年可能要投资的工程项目。表9.3说明了每个工程所需要的投资,以及每个工程在未来三年中的预期利润。表9.3工程1工程2工程3工程4投资(百万$)8654预期利润(百
6、万$)12876实例9.2一个资本预算问题(2)公司准备在下一年投入1,500万美元,希望选择使总预期利润最大化的那些工程。设定决策变量。设Xi表示工程是Xi被选中的决策变量,并且定义Xi如下:如果工程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=0X2,X3,X4都是二态变量。实例9.2一个资本预算问题(3)K&A公
7、司的资本预算模型为下列优化模型。最大化:12X1＋8X2＋7X3＋6X4约束条件为:预算:8X1＋6X2＋5X3＋4X4≤15二态性:X1,X2,X3,X4是二态变量我们可以把这个问题表示成电子表格的形式,并且计算出结果(将在后面介绍),参见表9.4。我们看到在表9.4中,决策变量的取值都是二态的,即0和1。根据表9.4中的数据,最优工程的选择是工程2,工程3以及工程4。在这种方案之下的利润为:12×0+8×1+7×1+6×1=21实例9.2一个资本预算问
