第二讲线性规划与灵敏度分析.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二讲线性规划与灵敏度分析,本章主要内容框架图,2、1,线性规划灵敏度分析,在第,1,章得讨论中,假定以下得线性规划模型中得各个系数,c,j,、,b,i,、,a,ij,就是确定得常数,并根据这些数据,求得最优解。,2、1,线性规划灵敏度分析,其实,系数,c,jb,i,、,a,ij,都有可能变化,因此,需要进行进一步得分析,以决定就是否需要调整决策。,灵敏度分析研究得另一类问题就是探讨在原线性规划模型得基础上增加一个变量或者一个约束条件对最优解得影响。,2、1,线性规划灵敏度分析,对例,1、1,进行灵敏度分析,最优解为,(,2,6,),Max z,3600,2、1,线性规划灵敏度分析,问题,1,:如果门得单位利润由原来得,300,元提升到,500,元,最优解就是否会改变？对总利润又会产生怎样得影响,?,问题,2,:如果门与窗得单位利润都发生变化,最优解会不会发生改变？对总利润又会产生怎样得影响,?,问题,3,:如果车间,2,得可用工时增加,1,个小时,总利润就是否会发生变化？如何改变,?,最优解就是否会发生变化,?,问题,4,:如果同时改变多个车间得可用工时,总利润就是否会发生变化？如何改变,?,最优解就是否会发生变化,?,问题,5,:如果车间,2,更新生产工艺,生产一扇窗户由原来得,2,小时下降到,1、5,小时,最优解就是否会发生改变？总利润就是否会发生变化？,问题,6,:工厂考虑增加一种新产品,总利润就是否会发生变化？,问题,7,:如果工厂新增加用电限制,就是否会改变原来得最优方案？,2、2,单个目标函数系数变动,下面讨论在假定只有一个系数,c,j,改变,其她系数均保持不变得情况下,目标函数系数变动对最优解得影响。,如果当初对门得单位利润估计不准确,如把它改成,500,元,就是否会影响求得得最优解呢？,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),方法,2,:运用,“,敏感性报告,”,寻找允许变化范围,2、2,单个目标函数系数变动,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),可以借助电子表格互动地展开灵敏度分析。当模型参数发生改变时,只要改变电子表格模型中相应得参数,再通过重新运行,Excel,“,规划求解,”,工具,就可以瞧出改变参数对最优解得影响。,需要一个一个地进行尝试,效率略显低下,2、2,单个目标函数系数变动,方法,2,:运用,“,敏感性报告,”,寻找允许变化范围,生成,“,敏感性报告,”,读懂相应得信息,2、2,单个目标函数系数变动,结果:,最优解没有发生改变,仍然就是(,2,6,),由于门得单位利润增加了,200,元,因此总利润增加了,(,500,300,),2,400,元。,2、2,单个目标函数系数变动,图解法(直观),可以瞧到,最优解(,2,6,),保持不变,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,2、3,多个目标函数系数同时变动,假如,以前把门得单位利润(,300,元)估计低了,现在把门得单位利润定为,450,元;同时,以前把窗得单位利润(,500,元)估计高了,现在定为,400,元。这样得变动,就是否会导致最优解发生变化呢？,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),方法,2,:运用,“,敏感性报告,”,进行分析(百分之百法则),2、3,多个目标函数系数同时变动,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),可以瞧到,最优解并没有发生变化,总利润由于门与窗得单位利润得改变相应地改变了,(450,300)2,(400,500)6,300,2、3,多个目标函数系数同时变动,方法,2,:运用,“,敏感性报告,”,进行分析,百分之百法则,:,如果目标函数系数同时变动,计算出每一系数变动量占该系数允许变动量(允许得增量或允许得减量)得百分比,而后,将各个系数得变动百分比相加,如果所得得与不超过,100%,则最优解不会改变;如果超过,100%,则不能确定最优解就是否改变,只能通过重新运行,“,规划求解,”,工具来判断了,2、3,多个目标函数系数同时变动,但就是变动百分比之与超过,100%,并不一定表示最优解会改变。例如,门与窗得单位利润都减半,变动百分比超过了,100%,但从右图瞧最优解还就是(,2,6,),没有发生改变。这就是由于这两个单位利润同比例变动,等利润直线得斜率不变,因此最优解就不变。,2、4,单个约束右端值变动,单个约束右端值变动对目标值得影响,如果车间,2,得可用工时增加,1,个小时,总利润就是否会发生变化？如何改变,?,最优解就是否会发生变化,?,方法,1,:使用电子表格进行分析(重新运行“规划求解”工具),方法,2,:从,“,敏感性报告,”,中获得关键信息(影子价格,Shadow Price,),2、4,单个约束右端值变动,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),总利润为,3750,元,增加了:,3750-3600=150,元。由于总利润增加了,而目标函数系数不变,所以最优解一定会发生改变,从图中可以瞧出,最优解由原来得(,2,6,)变为(,1、667,6、5,),2、4,单个约束右端值变动,方法,2,:从,“,敏感性报告,”,中获得关键信息,在给定线性规划模型得最优解与相应得目标函数值得条件下,影子价格(,Shadow Price,)就是指约束右端值增加(或减少)一个单位,目标值增加(或减少)得数量,第二个约束条件(车间,2,得工时约束)得影子价格就是,150,说明在允许得范围,6,18,(即,12-6,12+6,)内,再增加(或减少)一个单位得可用工时,总利润将增加(或减少),150,2、4,单个约束右端值变动,图解法(直观),可以瞧到,在这个范围内,每次车间得约束右端值增加(或减少),1,交点得移动就使利润增长(或减少)影子价格得数量(,150,元),2、5,多个约束右端值同时变动,多个约束右端值同时变动对目标值得影响,将,1,个小时得工时从车间,3,移到车间,2,对总利润所产生得影响,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),方法,2,:运用,“,敏感性报告,”,进行分析(百分之百法则),2、5,多个约束右端值同时变动,方法,1,:使用电子表格进行分析(重新运行,“,规划求解,”,工具),总利润增加了,3650-3600=50,(元),影子价格有效。,2、5,多个约束右端值同时变动,方法,2,:运用,“,敏感性报告,”,进行分析,百分之百法则:如果约束右端值同时变动,计算每一变动占允许变动量(允许得增量或允许得减量)得百分比,如果所有得百分比之与不超过,100%,那么,影子价格依然有效,如果所有得百分比之与超过,100,那就无法确定影子价格就是否依然有效,只能通过重新运行,“,规划求解,”,工具来判断了,2、5,多个约束右端值同时变动,在影子价格有效范围内,总利润得变化量可以直接通过影子价格来计算。,比如将车间,3,得,3,个工时转移给车间,2,由于,所以,总利润得变化量为,2、6,约束条件系数变化,如果车间,2,更新生产工艺,生产一扇窗户由原来得,2,小时下降到,1、5,小时,最优解就是否会发生改变？总利润就是否会发生变化？,使用电子表格进行分析,(,重新运行,“,规划求解,”,工具,),重新运行,“,规划求解,”,工具后,最优解发生了改变,变成了(,2/3,8,),总利润也由,3600,元增加到了,4200,元。可见,车间,2,更新生产工艺后,为工厂增加了利润。,2、7,增加一个新变量,例,2、1,如果工厂考虑增加一种新产品:防盗门,其单位利润为,400,元。生产一个防盗门会占用车间,1,、车间,2,、车间,3,各,2,、,1,、,1,工时,总利润就是否会发生变化？,使用电子表格进行分析,(,重新运行,“,规划求解,”,工具,),最优解,(2,5、5,1,),最大利润就是,3750,元。可见新产品为工厂增加了利润,2、8,增加一个约束条件,比如工厂关心电力供应限制,(,例2、,2,假定生产两种新产品每件需要消耗电力分别为,20kw,、,10kw,工厂总供电最多为,90kw),最优解就是否会发生变化,?,使用电子表格进行分析,(,重新运行,“,规划求解,”,工具,),可见电力约束得确限制了新产品门与窗得产量,最优解变成,(1、5,6),总利润也相应得下降为,3450,元。,2、9,影子价格,(,1,)影子价格就是根据资源在生产中作出得贡献而做得估价。它就是一种边际价格,其值相当于在资源得到最优利用得生产条件下,资源(约束右端值)每增加一个单位时目标函数值得增加量;,(,2,)影子价格得经济意义与应用,2、9,影子价格,资源得影子价格实际上就是一种机会成本。在纯市场经济条件下,当资源得市场价格低于影子价格时,可以买进这种资源,反之,可以卖出。随着资源得买进与卖出,它得影子价格也将随之发生改变,一直到影子价格与市场价格保持同等水平,才处于平衡状态。,当资源得影子价格为,0,时,表明该种资源未得到充分利用。当资源得影子价格不为,0,时,表明该种资源在生产中已耗费完毕。,可以利用影子价格计算产品得隐含成本(单位资源消耗量,相应得影子价格后求与)。当产品产值大于隐含成本时,表明生产该产品有利,可计划安排生产;否则用这些资源生产别得产品更为有利。,2、9,影子价格,一般来说,对线性规划问题得求解就就是确定资源得最优分配方案,所以对资源得估计直接涉及到资源得最有效利用。,如在大公司内部,可借助资源得影子价格确定一些内部结算价格,以便控制有限资源得使用与考核企业经营得好坏。,又如在社会上可对一些最紧缺得资源,借助影子价格规定使用这种资源一个单位必须上交得利润额,以使一些经济效益低得企业自觉地节约使用紧缺资源,使有限资源发挥更大得经济效益。,2、9,影子价格,例,2、3,某文教用品厂利用原材料白坯纸生产原稿纸、日记本与练习本三种产品。该厂现有工人,100,人,每天白坯纸得供应量为,30000,千克。如果单独生产各种产品时,每个工人每天可生产原稿纸,30,捆、或日记本,30,打,或练习本,30,箱。已知原材料消耗为:每捆原稿纸用白坯纸,10/3,千克、每打日记本用白坯纸,40/3,千克,每箱练习本用白坯纸,80/3,千克。已知生产各种产品得盈利为:每捆原稿纸,1,元、每打日记本,2,元,每箱练习本,3,元。试讨论在现有生产条件下使该厂盈利最大得方案。,如白坯纸供应量不变,而工人数量不足时,可从市场上招收临时工,临时工费用为每人每天,15,元,问该厂就是否招临时工及招收多少人为宜。,2、9,影子价格,设该厂每天生产原稿纸,x,1,捆、日记本,x,2,打、练习本,x,3,箱,2、9,影子价格,Excel,求解结果为:生产原稿纸,1000,捆,日记本,2000,打,练习本不生产,此时得总利润最大,为,5000,元,2、9,影子价格,生成,“,敏感性报告,”,工人约束得影子价格为,20,元,与临时工每人每天费用,15,元相比,影子价格要大,所以每招一名临时工,能为工厂多盈利,20-15=5元),招收得人数在允许得增量,200,人范围内,当工人数量不足时,可从市场上招收临时工,最多招收,200,人为宜,2、9,影子价格,(补充),补充 某外贸公司准备购进两种产品,A1,与,A2,。购进产品,A1,每件需要,10,元,占用,5m,3,得空间,待每件,A1,卖出后,可获纯利润,3,元;购进产品,A2,每件需要,15,元,占用,3m,3,得空间,待每件,A2,卖出后,可获纯利润,4,元。公司现有资金,1400,元,有,430m,3,得仓库空间存放产品。试讨论在现有条件下使该公司盈利最大得方案。,现在公司有另外一笔资金,585,元,准备用于投资。这笔资金可以用来购买产品,A1,、,A2,也可以用来增加仓库得容量(假设增加,1m,3,得仓库空间需要,0、8,元)。问应如何进行投资使公司获得更多得利润。,2、9,影子价格,(补充)续,设公司购进,A1,产品,x,1,件、,A2,产品,x,2,件,2、9,影子价格,(补充)续,Excel求解结果为:最优方案就是购进,A1,产品,50,件、,A2,产品,60,件,此时得总利润最大,为,390,元。,2、9,影子价格,(补充)续,生成,“,敏感性报告,”,资金约束得影子价格约为,0、24,元,而空间约束得影子价格约为,0、11,元(每,1,元资金投资空间得收益约为,0、14,元,0、11/0、8,)。,由于资金约束得影子价格大,所以这笔资金可以直接用来购买产品,585,元在允许得增量,750,元范围内,可以增加利润为:,5850、244=143,元。购买方案为(,11,125,),上机,实验二 线性规划灵敏度分析,(一)实验目得:掌握使用,Excel,软件进行灵敏度分析得操作方法。,(二)内容与要求:用,Excel,软件完成习题,2、4,、案例,2,(三)操作步骤:,(,1,)建立电子表格模型;,(,2,)使用,Excel,规划求解工具求解问题并生成,“,敏感性报告,”,;,(,3,)结果分析:哪些问题可以直接利用,“,敏感性报告,”,中得信息求解,哪些问题需要重新运行,“,规划求解,”,工具,并对结果提出您得瞧法;,(4,)在,Excel,或,Word,文档中写实验报告,包括线性规划模型、电子表格模型、敏感性报告内容与结果分析等。,案例,2,经理会议建议得分析,案例,2,某公司生产三种产品,A1,、,A2,、,A3,它们在,B1,、,B2,两种设备上加工,并耗用,C1,、,C2,两种原材料,已知生产单位产品耗用得工时与原材料以及设备与原材料得最多可使用量如表,C-7,所示。,表,C-7,生产三种产品得有关数据,资 源,产品,A1,产品,A2,产品,A3,每天最多可使用量,设备,B1,(,min,),1,2,1,430,设备,B2,(,min,),3,0,2,460,原料,C1,(,kg,),1,4,0,420,原料,C2,(,kg,),1,1,1,300,每件利润(元),30,20,50,第,3,章,线性规划得建模与应用,Linear Programming,Formulation and Applications,本章内容要点,线性规划问题得四种主要类型,线性规划得建模与应用,本章节内容,3、1,资源分配问题,3、2,成本收益平衡问题,3、3,网络配送问题,3、4,混合问题,3、5,线性规划模型得应用,本章主要内容框架图,3、1,资源分配问题,资源分配问题就是将有限得资源分配到各种活动(决策)中去得线性规划问题。这一类问题得共性就是在线性规划模型中每一个函数约束均为资源约束,并且每一种资源都可以表现为如下得形式:,使用得资源数量,可用得资源数量,对任何资源分配问题,有三种数据必须收集:,(,1,)每种资源得可供量;,(,2,)每一种活动所需要得各种资源得数量,对于每一种资源与活动得组合,单位活动所消耗得资源量必须首先估计出来;,(,3,)每一种活动对总得绩效测度(如总利润)得单位贡献(如单位利润)。,3、1,资源分配问题,例,3、1,某公司就是商务房地产开发项目得主要投资商。目前,该公司有机会在三个建设项目中投资:,项目,1,:建造高层办公楼;,项目,2,:建造宾馆;,项目,3,:建造购物中心。,每个项目都要求投资者在四个不同得时期投资:在当前预付定金,以及一年、二年、三年后分别追加投资。表,3-1,显示了四个时期每个项目所需资金(百万元)。投资者可以按一定得比例进行投资与获得相应比例得收益。,年份,办公楼项目,宾馆项目,购物中心项目,0,(现在),40,80,90,1,60,80,50,2,90,80,20,3,10,70,60,净现值,45,70,50,公司目前有,2500,万元资金可供投资,预计一年后,又可获得,2000,万元,两年后获得另外得,2000,万元,三年后还有,1500,万元以供投资。那么,该公司要在每个项目中投资多少比例,才能使其投资组合获得最大得总净现值？,3、1,资源分配问题,解:这就是一个资源分配问题。,(1),决策变量,设:,x,1,x,2x,3,分别为在办公楼项目、宾馆项目、购物中心项目中得投资比例,(2),目标函数,本问题得目标就是总净现值最大,3、1,资源分配问题,(3),约束条件,本题得约束条件就是公司在各期可获得得资金限制(资源约束)。但要注意得就是:前一期尚未使用得资金,可以在下一期使用(为了简化问题,不考虑资金可获得得利息)。因此,每一时点得资金限制就表现为累计得资金。表,3-2,显示了累计得资金数据。,年份,办公楼项目,宾馆项目,购物中心项目,可用资金,0,(现在),40,80,90,25,1,100,160,140,45,2,190,240,160,65,3,200,310,220,80,净现值,45,70,50,3、1,资源分配问题,数学模型(线性规划模型),3、1,资源分配问题,电子表格模型,补充:例,3、1,得解法,2,例,3、1,还可用另外一种解法,引入剩余变量,s,i,。,数学模型为:,补充:例,3、1,得解法,2,例,3、1,还可用另外一种解法,引入剩余变量,s,i,。,电子表格模型为:,注意:在,“,规划求解,”,中,决策变量不连续时,用,;,隔开,3、2,成本收益平衡问题,成本收益平衡问题与资源分配问题得形式完全不同,这种差异主要就是因为两种问题得管理目标不同而造成得。,在资源分配问题中,各种资源就是受限制得因素(包括财务资源),问题得目标就是最有效地利用各种资源,使获利最大。,而对于成本收益平衡问题,管理层采取更为主动得姿态,她们指明哪些收益必须实现(不管如何使用资源),并且要以最低得成本实现所指明得收益。这样,通过指明每种收益得最低可接受水平,以及实现这些收益得最小成本,管理层期望获得成本与收益之间得适度平衡。因此,成本收益平衡问题就是一类线性规划问题,这类问题中,通过选择各种活动水平得组合,从而以最小得成本来实现最低可接受得各种收益水平。,3、2,成本收益平衡问题,成本收益平衡问题得共性就是,所有得函数约束均为收益约束,并具有如下得形式:,完成得水平,最低可接受得水平,如果将收益得含义扩大,所有以,“,”,表示得函数约束均为收益约束。在多数情况下,最低可接受得水平就是作为一项政策由管理层制定得,但有时这一数据也可能就是由其她条件决定。,成本收益平衡问题需要得三种数据:,(,1,)每种收益得最低可接受水平(管理决策);,(,2,)每一种活动对每一种收益得贡献,(单位活动得贡献);,(,3,)每种活动得单位成本。,3、2,成本收益平衡问题,排班问题就是成本收益平衡问题研究得最重要得应用领域之一。在这一领域中,管理层意识到在向顾客提供令人满意得服务水平得同时必须进行成本控制,因此,必须寻找成本与收益之间得平衡。于就是,研究如何规划每个轮班人员才能以最小得成本提供令人满意得服务。,例,3、2,某航空公司正准备增加其中心机场得往来航班,因此需要雇佣更多得服务人员不同时段有最少需要服务人员数,有,5,种排班方式,每,8,小时为一班。,3、2,成本收益平衡问题,例,3、2,(续),5,种排班方式,排班,1,:,6AM,2PM,即早上,6,点上班;排班,2,:,8AM,4PM,即早上,8,点上班;,排班,3,:中午,8PM,即中午,12,点上班;排班,4,:,4PM,午夜,即下午,4,点上班;,排班,5,:,10PM,6M,即晚上,10,点上班。,时段,排班,1,排班,2,排班,3,排班,4,排班,5,最少需要人数,6AM,8AM,48,8AM,10AM,79,10AM,中午,65,中午,2PM,87,2PM,4PM,64,4PM,6PM,73,6PM,8PM,82,8PM,10PM,43,10PM,午夜,52,午夜,6PM,15,每人每天工资,(,元,),170,160,175,180,195,3、2,成本收益平衡问题,解,:,这就是一个纯成本收益平衡问题。,(,1,)决策变量,本问题得决策就是不同排班得人数。,设:,x,i,为排班,i,得人数,(,i,1,2,5),(,2,)目标函数,本问题得目标就是人员总费用(工资)最少,即,(,3,)约束条件,每个时段得在岗人数必须不少于最低可接受水平(最少需要人数),非负,3、2,成本收益平衡问题,数学模型(线性规划模型),3、2,成本收益平衡问题,电子表格模型,3、3,网络配送问题,通过配送网络能以最小得成本完成货物得配送,所以称之为网络配送问题。网络配送问题将在第,4,章与第,5,章中重点介绍。,与确定资源与收益一样,在网络配送问题中,必须确定需求以及相应地确定需求得约束条件。,确定需求约束得形式如下:,提供得数量需求得数量,3、3,网络配送问题,例,3、3,某公司网络配送问题。某公司在两个工厂生产某种产品。现在收到三个顾客得下个月定单要购买这种产品。这些产品会被单独运送,表,3-4,显示了从每个工厂到每个顾客得运送一个产品得成本。该表同样表明了每个顾客得订货量与每个工厂得生产量。现在公司得物流经理要决定从每个工厂运送多少个产品到每个顾客那里才能使总成本最小？,单位运输成本(元,/,个),产量(个),顾客,1,顾客,2,顾客,3,工厂,1,700,900,800,12,工厂,2,800,900,700,15,订货量,(,个,),10,8,9,27(,产销平衡,),3、3,网络配送问题,解,:,由于“总产量(,27,)总订货量(,27,)”,所以本问题就是一个平衡运输问题。,(,1,)决策变量 本问题得决策为从每个工厂运送多少个产品到每个顾客那里。设:,x,i-j,为从工厂,i,运输到顾客,j,得产品数量(,i,F,1,F,2,;,j,=C,1,C,2,C,3,),(,2,)目标函数 本问题得目标就是使得公司总运输成本最低,、,(,3,)约束条件,从工厂运送出去得产品数量等于其产量,顾客收到得产品数量等于其订货量,非负,3、3,网络配送问题,数学模型(线性规划模型),3、3,网络配送问题,电子表格模型,3、4,混合问题,前面讨论了线性规划问题得三种类型:资源分配问题、成本收益平衡问题以及网络配送问题。如表,3-5,所总结得,每一类问题都就是以一类约束条件为特色得。,实际上,纯资源分配问题得共性就是它所有得函数约束均为资源约束(,),而成本收益平衡问题得共性就是它所有得函数约束均为收益约束(,),网络配送问题中,主要得函数约束为一特定类型得确定需求约束(),3、4,混合问题,但许多线性规划问题并不能直接归入三类中得某一类,一些问题勉强可以归入一类,因其主要得函数约束与表,3-5,得相应函数约束大致相同。另一些问题却没有一类占主导地位得函数约束,不能归入前三类中得某一类。因此,混合问题就是第四类线性规划问题,这一类型将包括所有未归入前述三类中得线性规划问题。,一些混合问题仅包含两类函数约束,而更多得就是包含三类函数约束。,3、4,混合问题,表,3-5,各类函数约束,类型,形式*,解释,主要用于,资源约束,LHS,RHS,对于特定得资源,使用得数量,可获得得数量,资源分配问题,混合问题,收益约束,LHS,RHS,对于特定得收益,到达得水平,最低可接受水平,成本收益平衡问题,混合问题,确定需求约束,LHS=RHS,对于一些数量,提供得数量,=,需求得数量,网络配送问题,混合问题,*LHS=,左式(一个,SUMPRODUCT,函数),RHS=,右式(一般为常数),3、4,混合问题,配料问题。这类问题得一般提法就是:由多种原料制成含有,m,种成分得产品,已知产品中所含各种成分得比例要求、各种原料得单位价格以及各原料所含成分得数量。考虑得问题就是:应如何配料,可使产品得总成本最低。,例,3、4,配料问题。某公司计划要用、,C,三种原料混合调制出三种不同规格得产品甲、乙、丙,产品得规格要求与单价、原料得供应量与单价等数据如表,3-6,所示。问:该公司应如何安排生产,可使总利润最大？,3、4,混合问题,表,3-6,混合配料数据表,A,B,C,产品单价,(元/,千克),甲,50%,35%,不限,90,乙,40%,45%,不限,85,丙,30%,50%,20%,65,原料供应量,(千克),200,150,100,原料单价,(元,/,千克),60,35,30,3、4,混合问题,解:,(,1,)决策变量,本问题得难点在于给出得数据就是非确定数值,而且各产品与原料得关系较为复杂。为了方便,设,x,ij,表示原料,i,(,i,=A,B,C,)用于产品,j,(,j,=1,为甲,j,=2,为乙,j,=3,为丙)得数量。,(,2,)目标函数,本问题得目标就是使总利润最大,总利润产品收入原料支出,3、4,混合问题,(,3,)约束条件,本题得约束条件:原料供应量限制,3,个、规格要求,7,个与决策变量非负。,在例,3、4,中,有,9,个决策变量与,10,个函数约束条件,包括,5,个资源约束、,2,个收益约束与,3,个确定需求约束。,3、4,混合问题,电子表格模型,3、5,线性规划模型得应用,前面按照函数约束得分类,介绍了四种线性规划问题:,资源分配问题(,资源约束),成本收益平衡问题(,收益约束),网络配送问题(,=,确定需求约束),混合问题(包含两种或三种类型得约束函数),本节按照应用方面介绍线性规划在生产计划问题、资金管理问题、市场调查问题与混合配料问题等方面得应用,3、5,线性规划模型得应用,建立线性规划模型得过程可以分为四个步骤:,设立决策变量用决策变量得线性函数表示目标,并确定就是求最大(,Max,)还就是最小(,Min,);,明确约束条件并用决策变量得线性等式或不等式表示;,根据决策变量得物理性质研究变量就是否有非负性。,3、5,线性规划模型得应用,生产计划问题就是企业生产过程中常常遇到得问题,其中最简单得一种形式可以描述如下(资源分配问题):,用若干种原材料(资源)生产某几种产品,原材料(或某种资源)供应量有一定得限制,要求制定一个产品生产计划,使其在给定得资源限制条件下能得到最大收益。,3、5,线性规划模型得应用,例,3、5,某工厂生产甲、乙、丙三种产品,都要经过铸造、机加工与装配三个车间。甲、乙两种产品得铸件可以外包协作,也可以自行生产,但产品丙必须本厂铸造才能保证质量。有关情况得数据如表,3-9,所示。,问:公司为了获得最大利润,甲、乙、丙三种产品各生产多少件？甲、乙两种产品得铸件由本公司铸造与由外包协作各应多少件？,3、5,线性规划模型得应用,表,3-9,自行生产或外包得有关数据,产品甲,产品乙,产品丙,工时限制,单件铸造工时(小时),5,10,7,8 000,单件机加工工时(小时),6,4,8,12 000,单件装配工时(小时),3,2,2,10 000,自产铸件成本(元,/,件),3,5,4,外协铸件成本(元,/,件),5,6,机加工成本(元,/,件),2,1,3,装配成本(元,/,件),3,2,2产品售价(元,/,件),23,18,16,3、5,线性规划模型得应用,解,:(,1,)决策变量,此问题得难度就是由于产品甲与乙得铸件既可以外包协作,也可以自行生产,从而使问题复杂化。如果只设甲、乙、丙产品得产量分别为,x,1,、,x,2,、,x,3,则由于产品甲与乙得铸件来源不同造成单位利润不同,因此目标函数中,x,1,与,x,2,得系数不就是常数,目标函数成为非线性函数,但就是如果把它们区分开来,另设两个变量(采用第,7,章得可分离规划技术),则可以较容易地建立问题得线性规划模型。,设,x,1,、,x,2,、,x,3,分别为三道工序都由本公司加工得甲、乙、丙三种产品得件数;,x,4,、,x5,分别为由外协铸造再由本公司机加工与装配得甲、乙两种产品得件数。,3、5,线性规划模型得应用,(,2,)目标函数 本问题得目标就是使得公司获得得总利润最大。为了建立目标函数,首先计算各决策变量得单位利润:,单位利润售价,-,成本(铸造、机加工、装配),(,3,)约束条件(,3,个资源约束、非负约束),铸造工时限制,机加工工时限制,装配工时限制 非负,3、5,线性规划模型得应用,数学模型(线性规划模型),3、5,线性规划模型得应用,电子表格模型,3、5,线性规划模型得应用,例,3、6,某工厂生产,A,、,B,两种产品,均需经过两道工序,每生产,1,吨,A,产品需要经第一道工序加工,2,小时,第二道工序加工,3,小时;每生产,1,吨,B,产品需经过第一道工序加工,3,小时,第二道工序加工,4,小时。可供利用得第一道工序工时为,15,小时,第二道工序工时为,25,小时。,生产产品,B,得同时可产出副产品,C,每生产,1,吨产品,B,可同时得到,2,吨产品,C,而不需要外加任何费用。副产品,C,一部分可以盈利,但剩下得只能报废,报废需要有一定得费用。,各项费用得情况为:出售产品,A,每吨能盈利,400,元;出售产品,B,每吨能盈利,800,元;每销售,1,吨副产品,C,能盈利,300,元;当剩余得产品,C,报废时,每吨损失费为,200,元。,经市场预测,在计划期内产品,C,得最大销量为5,吨。,问:如何安排,A,、,B,两种产品得产量可使工厂总得盈利为最大？,3、5,线性规划模型得应用,解:,(,1,)决策变量,本问题得难度就是由于副产品,C,得出现而使问题复杂化了。如果只设,A,、,B,、,C,产品得产量分别为,x,1,、,x,2,、,x,3,则由于产品,C,得单位利润不同(赢利,300,元或损失,200,元),因此目标函数中,x,3,得系数不就是常数,目标函数成为非线性函数,但就是如果把产品,C,得销售量与报废量区分开来,设作两个变量(采用第,7,章得可分离规划技术),则可以容易地建立线性规划模型。,设,A,、,B,产品得产量分别为,x,1,、,x,2,;,C,产品得销售量与报废量分别为,x,3,、,x,4,。,3、5,线性规划模型得应用,(,2,)目标函数,本问题得目标就是使工厂得总盈利最大,即,(,3,)约束条件,(,3,个资源约束、,1,个确定需求约束、非负约束),第一道工序,第二道工序,产品,B,与产品,C,产品,C,得最大销量,非负,3、5,线性规划模型得应用,线性规划模型(数学模型),3、5,线性规划模型得应用,电子表格模型,3、5,线性规划模型得应用,例,3、7,某公司根据订单进行生产。已知半年内对某产品得需求量、单位生产费用与单位存储费用,还已知公司每月得生产能力为,100,每月仓库容量为,50,。问:如何确定产品未来半年内每月最佳生产量与存储量,以使总费用最少。,月份,1,2,3,4,5,6,需求量,50,40,50,45,55,30,单位生产费用,825,775,850,850,775,825,单位存储费用,40,30,35,20,40,40,3、5,线性规划模型得应用,解:,(生产与库存问题,更多请参见第,9,章,动态规划),(1),决策变量,本问题得决策为产品未来半年内每月得最佳生产量与库存量。设每月生产量为,x,i,(,i,=1,2,6,),每月月末库存量为,s,i,(i=1,2,6,),。,(2),目标函数,本问题得目标就是总费用最小,总费用生产总费用,+,存储总费用,3、5,线性规划模型得应用,(3),约束条件,对于每个月,上月库存量本月生产量市场需求本月月末库存量,公司每月得生产能力为,100,每月仓库容量为,50,非负,3、5,线性规划模型得应用,数学模型,(线性规划模型),3、5,线性规划模型得应用,例,3、7,得电子表格模型,3、5,线性规划模型得应用,资金管理问题,线性规划在资金管理方面得应用主要包括投资组合优化、连续投资、财务计划、资本预算等。,本小节将介绍线性规划在投资组合优化与连续投资方面得应用。更多得例子请见第,9,章。,投资组合优化问题研究如何选择投资对象,例如,如何选择不同得债券或股票,在满足某些要求得前提下,使得利润最大或风险最小。因此,其决策变量就是对各种可能得投资对象得投资组合,其目标函数通常就是期望回报最大化或风险最小化,而约束条件则可包括总投资额、公司政策、法律法规等。,例,3、8,就是期望回报额最大化,采用线性规划模型。当考虑投资风险(成本)与收益之间得平衡时,更多得就是采用非线性规划模型,具体见第,7,章。,3、5,线性规划模型得应用,例,3、8,投资组合优化问题。某公司董事会决定将,20,万现金进行债券投资。经咨询,现有五种债券就是较好得投资对象,它们就是:黄河汽车,长江汽车,华南电器,西南电器,缜山纸业。它们得投资回报率如表,3-12,所示。为减少风险,董事会要求,对汽车业得投资不得超过,12,万,对电器业得投资不得超过,8,万,其中对长江汽车得投资不得超过对汽车业投资得,65%,对纸业得投资不得低于对汽车业投资得,20%,。该公司应如何投资,才能在满足董事会要求得前提下使得总回报额最大？,债券名称,黄河汽车,长江汽车,华南电器,西南电器,缜山纸业,回报率,6、5%,9、2%,4、5%,5、5%,4、2%,3、5,线性规划模型得应用,解:,(,1,)决策变量,本问题得决策变量就是对五种投资对象得投资额。设:该公司对五种债券得投资额分别为,x,1,x,2,x,3,x,4,x,5,(万元)。,(,2,)目标函数,本问题得目标就是使得公司总回报额最大,3、5,线性规划模型得应用,(,3,)约束条件,总投资额为,20,万现金,汽车业得投资不得超过,12,万,电器业得投资不得超过,8,万,对长江汽车得投资不得超过对汽车业投资得,65%,对纸业得投资不得低于对汽车业投资得,20%,非负,3、5,线性规划模型得应用,数学模型(线性规划模型),3、5,线性规划模型得应用,例,3、8,得电子表格模型,3、5,线性规划模型得应用,例,3、9,连续投资问题。某部门在今后五年内考虑给下列项目投资,已知:,项目,A,:从第一年到第四年每年年初都可以投资,并于次年年末收回本利,115%,;,项目,B,:第三年年初可以投资,到第五年年末能收回本利,125%,但规定最大投资额不超过,4,万元;,项目,C,:第二年初可以投资,到第五年末能收回本利,140%,但规定最大投资额不超过,3,万元;,项目,D,:五年内每年初都可以购买公债,于当年末归还,并加利息,6%,。,该部门现有资金,10,万元,问应如何确定这些项目得每年投资额,使得第五年年末拥有得资金得本利总额最大？,3、5,线性规划模型得应用,解:,(,1,)决策变量,本题就是一个连续投资问题,由于需要考虑每年年初对不同项目得投资额,为了便于理解,建立双下标决策变量。设,x,ij,为第,i,年初给项目,j,得投资额(万元),根据给定条件,将决策变量列于表,3-13,中(,P82,),(,2,)约束条件,每年投资额可投资额(,P82,83,),最大投资额、非负,3、5,线性规划模型得应用,(,3,)目标函数,该问题要求在第五年末拥有得资金得本利总额最大,目标也可以就是投资得总回报额最大,但不就是,用,Excel,求解,即可明白,3、5,线性规划模型得应用,数学模型(线性规划模型),3、5,线性规划模型得应用,例,3、9,得电子表格模型,3、5,线性规划模型得应用,例,3、9,得灵敏度分析,从影子价格(,“,阴影价格,”,列)可知:第一年初增加或减少投资,1,万元,将导致第五年末拥有资金得本利增加或减少,1、40,万元,目前第一年投资额为,10,万元;第二年初增加或减少投资,1,万元,将导致第五年末拥有资金得本利增加或减少,1、32,万元,目前第二年得投资金额来自第一年投资于项目,D,而收回