第九章离散优化.pptVIP

离散优化的应用日程安排资本预算广告投放运输问题工程评价等等

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公司飞机制造的相关信息AR1AR2AR4AR6联邦航空局允许的最大产量8171115建造飞机所需要的天数47911建造一架飞机需要的管理人员1122一架飞机的利润($1000)6284103125

实例9.1一架飞机的制造问题(3)表9.1的第一行说明了联邦航空局允许每种飞机在下个月的最大产量。表9.1的第二行说明了建造每种飞机所需要的时间(以天为单位)。表9.1的第三行说明了生产每种飞机所需要管理人员数目。表9.1的最后行说明了每种飞机的单位利润。在下个月,CRISP公司可用的管理人员总数为60人。CRISP公司的生产能力为9架/天,按每月30天计算,下一个月可以得到的制造天数为270天。

实例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约束条件为:建造时间: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中,决策变量的取值都是整数。这个方案的利润为:利润=(62×8+84×17+103×1+125×10)×1000=3277000(美元)用于CRISP公司的生产方案模型是一个线性离散(或整数)优化模型的实例。线性离散(或整数)优化模型的定义为:如果所有的决策变量被要求是非负整数,并且所有的约束和目标函数都是线性函数,那么该优化模型被称为一个线性离散(或整数)优化模型。

实例9.2一个资本预算问题(1)工程1工程2工程3工程4投资(百万$)8654预期利润(百万$)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)KA公司的资本预算模型为以下优化模型。最大化:12X1＋8X2＋7X3＋6X4约束条件为:预算:8X1＋6X2＋5X3＋4X4≤15二态性:X1,X2,X3,X4是二态变量我们可以把这个问题表示