物流系统优化线性规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线 性 规 划 模 型,1,“,线性规划能做什么？,2,线性规划的概念和研究的问题,线性规划是在一定的限制条件下使其规划问题的某个整体指标达到最优的方法。,线性规划在财贸金融、工农业生产、交通运输等领域的管理决策分析中均可帮助管理人员解决具体的实际问题。,用线性规划解决的比较简单的问题：,1,、产品生产的组合安排,2,、原料搭配及下料,3,、物资运输,4,、投资问题等,3,线性规划问题基本理论及方法,例：某工厂生产两种新产品：门和窗。经测算，每生产一扇门需要在车间,1,加工,1,小时、在车间,3,加工,3,小时；每生产一扇窗需要在车间,2,和车间,3,各加工,2,小时。而车间,1,每周可用于生产这两种新产品的时间为,4,小时、车间,2,为,12,小时、车间,3,为,18,小时。已知每扇门的利润为,300,元，每扇窗的利润为,500,元。根据市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有的新产品均能销售出去。,4,线性规划问题基本理论及方法,车间,单位产品的生产时间（小时）,每周可获得的生产时间（小时）,门,窗,1,1,0,4,2,0,2,12,3,3,2,18,单位利润（元）,300,500,问题：,该工厂如何安排这两种新产品的每周生产计划，才能使总利润最大？,如果要增加资源，首先应该增加哪种资源？,这些资源出租或出售，应如何定价？,如果产品市场价格发生变化、产品加工工艺发生改变，原,生产方案是否需要调整？,5,主要内容,线性规划问题基本理论及方法,应用,EXCEL,工具求解线性规划问题,线性规划问题建模求解实例分析,线性规划问题的影子价格及灵敏度分析,6,线性规划问题基本理论及方法,线性规划（,Linear Programming,）,:,运筹学中理论最完善、方法最成熟、应用最广泛的一个分支。,1939,年，前苏联数学家康脱洛维奇（,L.V.Kantorovich),提出，,1947,年，美国数学家丹捷格（,G.B.Dantring),提出线性规划的求解方法,单纯形法。,主要研究两类问题：,现有资源有限，如何合理安排，使以最少的人力、物力完成任务？,任务确定后，如何计划、安排，使在完成任务的前提下，资源消耗最低？,可解决生产调度、合理下料、配料问题、产品配套问题、运输问题等问题。,7,线性规划问题基本理论及方法,数学模型：,有三个要素组成：,决策变量：,一组定值代表所给问题的一个具体解决方案。一般要求其非负。,约束条件：,反映所给问题的客观限制及完成任务的具体要求，一般表示为一组决策变量的,线性,等式或不等式。,目标函数：,问题所要达到的目标。一般表示为决策变量的,线性,函数，取最大值或最小值。,8,线性规划问题基本理论及方法,建模步骤：,确定决策变量：根据决策问题，确定,x=(x,1,x,2,x,3,x,n,),找出约束条件：找出所有的限制条件，写出其表达式。,明确目标函数：写出目标函数的最大值（或最小值）。,9,线性规划问题基本理论及方法,S.t,10,线性规划问题基本理论及方法,假设：每周各生产门和窗,x,1,、,x,2,个。,建立线性规划模型如下：,Max Z=300 x,1,+500 x,2,x,1,4,2x,2,12,3x,1,+2x,2,18,x,1,、,x,2,0,S.t,11,线性规划问题基本理论及方法,例,1,：红星重型机械厂的产品组合问题：,红星机械厂开发出产品甲与产品乙。管理层决定近期安排生产这两种产品。已知产品甲需要原料,A,，产品乙需要原料,B,。由于两种产品都在一个设备上生产，且设备工时有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下获得最大利润。,甲,乙,资源限制,原料,A,（吨）,1,0,6,原料,B,（吨）,0,2,8,设备（单位设备工时）,2,3,18,单位利润（万元）,4,3,12,线性规划问题基本理论及方法,例,2,：美克制造公司的劳动力分配问题：,美克制造公司生产三种产品，每单位产品的利润分别为,100,元、,90,元和,95,元。每个产品都要经过,4,个车间加工。假定每个车间的工人总工时是给定的，每单位产品在各车间需要的工时见表。决定三种产品的生产数量。,车间,单位产品需要工时（小时）,总可用工时（小时）,产品,1,产品,2,产品,3,1,1.0,0.8,1.2,2800,2,0.3,0.4,0.4,1800,3,0.9,1.2,0.6,3900,4,0.8,0.4,0.3,2800,单位利润（元）,100,90,95,13,线性规划问题基本理论及方法,例,3,：新农饲料公司饲料配制问题：,新农饲料公司希望用玉米和红薯两种原料配制一种混合饲料。由于玉米和红薯包含的营养成分和采购成本都不相同，公司管理层希望能够确定混合饲料中玉米和红薯的数量，使得饲料能够以最低的成本达到给定的营养要求。收集资料如下：,营养成分,每千克玉米,每千克红薯,最低要求量,碳水化合物（克）,8,4,20,蛋白质（克）,3,6,18,维生素（克）,1,5,16,采购成本（元）,0.8,0.5,14,线性规划问题基本理论及方法,求解步骤：,找出初始基本可行解（一般选择原点）；,检验初始基本可行解是否为最优解；,如果不是，寻找新的基本可行解；,再次进行检验，直到找出最优解为止。,对于,两个变量,的线性规划问题，可用图解法；对于,两个以上变量,问题，采用单纯形法求解。,图解法、单纯形法例。,15,线性规划问题基本理论及方法,图解法求解步骤：,建立,x,1,Ox,2,平面直角坐标系。,将所有约束条件的临界值（直线）标于坐标系中，得出可行域（所有可行解的集合）。,给目标函数赋一值，在坐标系中划出相应直线，在可行域中移动，找出其极值方向的交点，即为该问题的最优解。,16,线性规划问题基本理论及方法,解的性质,:,线性规划问题的可行域都是凸多边形（可能无界）；,可行域的顶点为基本可行解，若存在最优解，一定在顶点上达到；,如果同时在两个顶点达到最优解，该直线上任意一点均为最优解，此时为无穷多最优解。,求解原理：从可行域中的某一顶点开始，逐一进行比较，使目标函数最优的顶点即为最优解。,17,线性规划问题基本理论及方法,线性规划的基本原理,（以例图解法说明）：,解的类型：,一定无解,解的结果,有可行域,无可行域,可行域有界,可行域无界,唯一解,无穷解,唯一解,无穷解,无解,18,线性规划问题基本理论及方法,单纯形法求解步骤：,将线性规划模型转化为标准型（目标函数求极大、约束条件为等式、决策变量大于,0,）；,找出初始基本可行解（即：,m,个约束条件中存在,m,个单位列向量，组成单位矩阵）；,检验初始基本可行解是否为最优解？（若所有非基变量的检验数,j0,，则基本可行解为最优解）；,如果不是最优解，进行迭代，求出新的基本可行解。（根据最小比值原则选择出基变量和进基变量）,单纯形法计算过程在单纯形表中具体实现。,19,应用,EXCEL,工具求解线性规划问题,一、在,EXCEL,电子表格中建立线性规划模型,1,、把相关数据输入到,EXCEL,电子表格中,20,应用,EXCEL,工具求解线性规划问题,2,、主要求解结果,两种新产品,x,1,、,x,2,每周的产量；,两种新产品每周各实际使用的工时（不能,超过计划工时）；,两种新产品的总利润,z,。,21,应用,EXCEL,工具求解线性规划问题,3,、主要结果的计算方法,（,1,）两种新产品的每周产量：,C12,、,D12,，试验解为,0,。,（,2,）实际使用工时计算,（,三种方法）,分别在,E7,、,E8,、,E9,中输入相应的计算公式：,E7,：,C7*C12+D7*D12,；,E8,：,C8*C12+D8*D12,；,E9,：,C9*C12+D9*D12,复制、粘贴方法：,在,E7,中输入：,C7*$C$12+D7*$D$12,，然后复制,E7,单元格到,E8,、,E9,公式法：,在,E7,中输入：,=SUMPRODUCT,（,C7,：,D7,，,$C$12,，,$D$12,）,复制,E7,单元格到,E8,、,E9,22,应用,EXCEL,工具求解线性规划问题,（,3,）总利润计算：,在,G12,单元格输入公式：,=C4*C12+D4*D12,或：,=SUMPRODUCT,（,C4,：,D4,，,C12,：,D12,）,23,应用,EXCEL,工具求解线性规划问题,收集问题数据；,在,EXCEL,表格中输入数据（,数据单元格,）；,确定决策变量单元格（,可变单元格,）；,输入约束条件左边的公式（,输出单元格,）,使用,SUMPRODUCT,函数简化输入；,输入目标函数公式（,目标单元格,）。使用,SUMPRODUCT,函数简化输入。,在,EXCEL,中建立线性规划模型步骤总结,24,应用,EXCEL,工具求解线性规划问题,二、在,EXCEL,电子表格中求解线性规划模型,1,、求解参数设置：,“,工具,”,”,规划求解,“,，弹出,“,规划求解参数,”,对话框，设置求解相关参数。,25,应用,EXCEL,工具求解线性规划问题,2,、约束的设置：,单击,“,添加,”,，弹出,“,添加约束,”,，添加约束条件。,26,应用,EXCEL,工具求解线性规划问题,3,、求解选项设置：,单击,“,选项,”,，弹出,“,规划求解选项,”,对话框。选择,“,采用线性模型,”,和,“,假定非负,”,。,27,应用,EXCEL,工具求解线性规划问题,4,、求解及结果,单击,“,求解,”,，开始规划求解。弹出,“,规划求解结果,”,对话框。选择,“,保存规划求解结果,”,。,28,应用,EXCEL,工具求解线性规划问题,5,、电子表格显示结果：,单击,“,确定,”,，在电子表格的可变单元格、输出单元格及目标单元格出现求解结果。,29,输入数据,标识数据,每个数据对应唯一单元格,在电子表格中显示完整模型,数据、公式分离,保持简单化,使用相对和绝对地址简化公式并复制,使用边框、底色区分单元格类型,例,1-3,建模求解要点回顾,30,应用,EXCEL,工具求解线性规划问题,四、线性规划问题解的表现,EXCEL,建模求解，其解的结果在,“,规划求解结果,”,对话框中提示：,1,、唯一最优解为,”,找到一个解,“,2,、无穷多最优解为,”,满足条件有多个解,“,3,、无解为,”,未找到可行解,“,31,线性规划问题建模求解实例分析,一、生产计划问题,例,1,：,某工厂生产甲、乙、丙三种产品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可自行生产，但产品丙必须在本厂铸造才能保证质量。数据见表。问：公司为了获得最大利润，甲、乙、丙三种产品应各生产多少件？甲、乙两种产品的铸件应由本公司铸造和由外包协作各多少件,?,32,线性规划问题建模求解实例分析,产品甲,产品乙,产品丙,工时限制,单件铸造工时（小时）,5,10,7,8000,单件机加工工时（小时）,6,4,8,12000,单件装配工时（小时）,3,2,2,10000,自产铸件成本（元,/,件）,3,5,4,外协铸件成本（元,/,件）,5,6,-,机加工成本（元,/,件）,2,1,3,装配成本（元,/,件）,3,2,2,产品售价（元,/,件）,23,18,16,33,线性规划问题建模求解实例分析,例,2,：,某工厂生产,A,、,B,种产品，均需经过两道工序，每生产,1,吨,A,产品需要经过第一道工序加工,2,小时，第二道工序加工,3,小时；每生产,1,吨,B,产品需要经过第一道工序加工,3,小时，第二道工序加工,4,小时。可供利用的第一道工序工时为,15,小时；第二道工序工时为,25,小时。,生产产品,B,的同时可产出副产品,C,，每生产,1,吨产品,B,，可同时得到,2,吨产品,C,而不需要外加任何费用。副产品,C,一部分可以赢利，但剩下的只能报废，报废需要有一定的费用。,出售产品,A,每吨能赢利,400,元；出售产品,B,每吨能赢利,800,元；出售副产品,C,每吨能赢利,300,元；当剩余的产品,C,报废时，每吨损失费为,200,元。经市场预测，在计划期内产品,C,的最大销售量为,5,吨。,问：如何安排,A,、,B,两种产品的产量可使工厂总盈利最大？,34,线性规划问题建模求解实例分析,二、生产存储问题,某公司根据订单生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用见表。已知公司每月的生产能力为,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,35,线性规划问题建模求解实例分析,三、项目投资问题,1,、某公司有,100,万元的资金可供投资,该公司有六个可选的投资项目,其各种数据见下表,.,该公司的目标,:,投资风险最小,每年红利至少,6.5,万元,最低平均增长率为,12%,最低平均信用度为,7.,投资项目,风险,(%),红利,(%),增长率,(%),信用度,1,18,4,22,4,2,6,5,7,10,3,10,9,12,2,4,4,7,8,10,5,12,6,15,4,6,8,8,8,6,36,线性规划问题建模求解实例分析,假设：,x,i,为每种投资项目投资额。建立线性规划模型如下：,MinZ=0.18x,1,+0.06x,2,+0.10 x,3,+0.04x,4,+0.12x,5,+0.08x,6,x,1,+x,2,+x,3,+x,4,+x,5,+x,6,=100,0.04x,1,+0.05x,2,+0.09x,3,+0.07x,4,+0.06x,5,+0.08x,6,6.5,0.22x,1,+0.07x,2,+0.12x,3,+0.08x,4,+0.15x,5,+0.08x,6,12,4x,1,+10 x,2,+2x,3,+10 x,4,+4x,5,+6x,6,700,x,1,、,x,2,、,x,3,、,x,4,、,x,5,、,x,6,0,37,线性规划问题建模求解实例分析,2,、证券投资问题：,一证券投资者将,1000,万元资金用于证券投资。已知各种证券（,A,、,B,、,C,、,D,、,E,、,F,）的评级、到期年限、每年税后收益见表。管理者对投资者提出下列要求（,1,）国债投资额不能少于,300,万元；（,2,）投资证券的平均评级不超过,1.5,；（,3,）投资证券的平均到期年限不超过,5,年。问：每种证券投资多少可以使得税后收益最大？,证券名称,证券类型,评级,到期年限（年）,每年税后收益（,%,）,A,地方债券,2,9,4.3,B,基金,2,12,4.4,C,国债,1,5,3.2,D,国债,1,4,3.0,E,地方债券,4,3,3.2,F,基金,5,4,4.5,38,线性规划问题建模求解实例分析,3,、连续投资优化,某部门在今后五年内考虑给下列项目投资：,项目,A,：从第一年到第四年每年年初都可以投资，并于次年年,末收回本利,115%,；,项目,B,：第三年初可以投资，到第五年末能收回本利,125%,，,但规定最大投资额不超过,4,万元；,项目,C,：第二年年初可以投资，到第五年末能收回本利,140%,，但规定最大投资额不超过,3,万元；,项目,D,：五年内每年年初都可以购买公债，于当年年末归还,并加利息,6%,；,该部门现有资金,10,万元，问应该如何确定这些项目的每年投资额，使得第五年末拥有的资金本利总额最大？,39,线性规划问题建模求解实例分析,四、背包问题,1,、,有一艘货轮，它的容积为,5400m,3,，其最大允许载重量,3000t,，现有三种大批量的货物待运，已知有关数据如下。问：该货轮应装载商品,1,、,2,、,3,个多少件，其运费收入为最大？,商品,每件体积（,m,3,/,件）,每件重量（,t/,件）,运价（元,/,件）,1,10,8,1000,2,5,6,700,3,7,5,600,40,线性规划问题建模求解实例分析,2,、某航运公司有一条三个舱口的货轮，它们的载容量和载重量见表。待运货物的品种、数量、体积、重量见表。为了保证航行的安全，要求各船按照确定的载重量装货，,2,号舱对,1,号舱的载重量比值、,2,号舱对,3,号舱的载重量比值允许在,10%,的范围内变动，,3,号舱对,1,号舱的载重量比值允许在,5%,的范围内变动。问：如何合理配载，才能使总的运费收入达到最大？,41,线性规划问题建模求解实例分析,2,、,舱号,载容量（,m,3,）,载重量（,t,）,1,3600,2800,2,4200,3200,3,3000,2400,货物种类,数量（件）,体积（,m,3,/,件）,重量（,t/,件）,运费（元,/,件）,1,500,8,6,1500,2,1000,4,3,800,3,600,5,4,900,42,线性规划问题建模求解实例分析,五、套裁下料问题,:,某工厂要做,100,套钢架，每套钢架分别需要长度为,2.9,米、,2.1,米和,1.5,米得圆钢各一套。已知原料每根长,7.4,米，问应如何下料，可使所用原料最省？,43,线性规划问题建模求解实例分析,六、营养配餐问题,:,假设一个成年人每周需要从食物中获取,2500,卡路里热量、,100g,蛋白质、,1000mg,维生素和,400mg,钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成分以及市场价格见表。问如果每人每周四种食品总食用量限制在,4.5kg,，如何选择才能使在满足营养的前提下使购买食品的总费用最小？,食品名称,热量,（卡路里）,蛋白质,（,g,）,维生素,（,mg,）,钙,（,mg,）,价格,（元,/kg,）,猪肉（,kg),1500,100,180,200,20,鸡蛋（,kg),1000,120,50,100,8,大米（,kg),600,25,50,150,3.5,蔬菜水果（,kg),180,15,300,50,2,需求量,2500,100,1000,400,44,线性规划问题建模求解实例分析,七、人力资源分配,例,1,：话务员排班问题：,某急救中心雇佣多名话务员工作，他们每天工作,3,节，每节,3,小时。每节开始时间为午夜、凌晨,3,点、凌晨,6,点、上午,9,点、中午,12,点、下午,3,点、下午,6,点和晚上,9,点。为方便话务员上下班，管理层安排每位话务员每天连续工作,3,节。不同时间，由于业务量不同，需要的话务员人数也不相同，公司付得薪水也不相同。问：如何安排话务员才能保证服务人数又使总成本最低？,工作时间,0-3,点,3-6,点,6-9,点,9-12,点,12-15,点,15-18,点,18-21,点,21-24,点,最低需求人数（人）,8,6,15,20,25,23,18,10,薪水（元）,26,30,28,22,20,20,22,24,45,线性规划问题建模求解实例分析,例,2,：,某快餐店坐落在一个远离市区的旅游点中，平时游客不多，而在除冬季外每个双休日游客都比较多。该快餐店有两名正式职工，正式职工每天工作,8,小时，且每个时间段都至少有一名正式职工在上班，其余工作有临时工来承担，临时工每班工作,4,小时。在双休日每天上午,10,时开始营业到下午,10,时关门。根据游客就餐情况，在双休日每个营业时间段所需职工数（包括正式工和临时工）见表。,已知一名正式职工,10,点开始上班，工作,4,小时后休息,1,小时，而后再工作,4,小时；另一名正式职工,13,点开始上班，工作,4,小时后休息,1,小时，而后再工作,4,小时。临时工每小时的工资为,4,元。,46,线性规划问题建模求解实例分析,时间段,所需职工数,时间段,所需职工数,10:00,11:00,9,16:00,17:00,3,11:00,12:00,10,17:00,18:00,6,12:00,13:00,10,18:00,19:00,12,13:00,14:00,9,19:00,20:00,12,14:00,15:00,3,20:00,21:00,7,15:00,16:00,3,21:00,22:00,7,在满足对职工需求的条件下，如何安排临时工的班次，使得使用临时工的成本为最小？这时付给临时工的工资总额是多少？一共需要安排多少个班次的临时工？如果可以安排每班工作,3,小时的临时工班次，是否可使总成本更小。,47,线性规划问题建模求解实例分析,八、,其它,例,1,：,某市场调查公司受某公司委托，调查消费者对某种新产品的了解和反应情况。该公司对调查公司提出如下要求：,（,1,）共对,500,个家庭进行调查；,（,2,）在被调查家庭中，至少有,200,个是没有孩子的家庭，同时至少有,200,个是有孩子的家庭；,（,3,）至少对,300,个被调查家庭采用问卷式书面调查，对其余家庭可采用口头调查；,（,4,）在有孩子的被调查家庭中，至少对,50%,的家庭采用问卷式书面调查；,（,5,）在没有孩子的被调查家庭中，至少对,60%,的家庭采用问卷式书面调查。,调查费用见表。问：市场调查公司应如何进行调查，使得在满足公司要求的条件下，,使得总调查费用,最少？,家庭类型,调查费用（元）,问卷式书面调查,口头调查,有孩子家庭,50,30,没有孩子家庭,40,25,48,线性规划问题建模求解实例分析,例,2,：巨斯特石油公司混合问题：,巨斯特石油公司要生产两种汽油产品。一种是一般汽油，另一种是特殊汽油。公司来炼油厂希望通过合成,4,类石油成分来生产这两种汽油产品。两种汽油的售价、,4,类石油成分成本均不同。公司希望确定一种混合这,4,类石油成分以生产两种汽油产品的方案来获得最大利润。,石油成分,单位成本,（,$,）,最大供应量,（加仑）,一般汽油,产品要求,特殊汽油,产品要求,成分,1,0.85,6000,最多,30%,最少,25%,成分,2,1.15,12000,最少,35%,最多,40%,成分,3,1.36,11000,最多,20%,最少,30%,成分,4,1.20,13000,25%,18%,49,线性规划问题的影子价格及灵敏度分析,对偶问题：,线性规划的一个有趣现象。任何一个线性规划问题都有一个与之相对应的对偶问题，在求出一个问题的最优解的同时，也得出其对偶问题的最优解。,S.t,S.t,50,线性规划问题的影子价格及灵敏度分析,原问题 对偶问题,Max Z=300 x,1,+500 x,2,x,1,4,2x,2,12,3x,1,+2x,2,18,x,1,、,x,2,0,S.t,Min W=4y,1,+12y,2,+18y,3,y,1,+3y,3,300,2y,2,+2y,3,500,y,1,、,y,2,、,y,3,0,S.t,51,线性规划问题的影子价格及灵敏度分析,影子价格：经济学的一个重要概念，又称预测价格。指某种产品或资源增加一个单位所带来的总收益的增加量（反映一种资源在最优方案条件下单位资源提供的目标函数值的增量）。是一种资源效用价值的估价。,对偶问题的第,i,个对偶变量就是原问题第,i,个约束条件的影子价格。如前例：,x*=(2,6),；,y*=(0,150,100),。车间,2,的总工时由,12,变为,13,时，可使所获总利润增加,150,元。,实际意义：,当考虑通过增加资源以增加收益，应选择影子价格最大的资源；,当某种资源的影子价格高于（或低于）该资源的市场价格时，公司应考虑对该种资源进行购买（或出售、租）；,影子价格帮助管理人员判断某种产品是否值得生产（或制定新产品价格）；,52,线性规划问题的影子价格及灵敏度分析,灵敏度分析：,在用线性规划方法解决实际问题时，把,c,j,、,a,ij,、,b,i,均当成确定的常量系数是不符合实际的。因此所得出的最优解和最优值也不是一尘不变的。其原因：,这些数据是通过统计、预测或经验得出；,受政策因素、市场条件、科技进步、资源供应状况等因素影响。,因此，线性规划还需考虑：,当上述系数中的一个或几个因素发生变化，原来的最优解是否发生变化？,这些系数在什么范围内变化，原来的最优解或最优值不变？,如果系数发生变化引起最优解发生变化，新的最优解和最优值如何得到？,53,线性规划问题的影子价格及灵敏度分析,线性规划问题的灵敏度分析是在求出最优解的基础上，进一步讨论当,c,j,、,b,i,、,a,ij,发生变化时，对最优解的影响。,判断某一系数发生变化，原最优解是否发生变化？,怎样得出使原最优解不变的系数变化范围。,当最优解发生变化时，怎样求出新的最优解。,54,线性规划问题的影子价格及灵敏度分析,1,、单个,c,j,变动,例：如果门的单位利润由原来的,300,元提升到,500,元，最优解是否会改变？对总利润会产生怎样的影响？,方法,1,：应用电子表格进行分析,改变电子表格模型中相应的参数，再运行,EXCEL,”,规划求解,”,功能，得出结果，看其是否对原最优解有影响。,55,线性规划问题的影子价格及灵敏度分析,方法,2,：应用敏感性报告寻找允许变化范围,对原电子表格模型运行,EXCEL,”,规划求解,”,功能，得出,“,规划求解结果,”,对话框，选择右端,“,敏感性报告,”,选项，得出相应结果。,56,线性规划问题的影子价格及灵敏度分析,比较两种方法的区别？,57,线性规划问题的影子价格及灵敏度分析,2,、多个,c,j,变动,例：如果把门的单位利润由,300,元提高到,450,元，同时把窗的单位利润由,500,元减少到,400,元，原来的最优解和最优值是否会发生变化？,方法,1,：应用电子表格进行分析,改变,EXCEL,模型中相应的参数，再运行,EXCEL,”,规划求解,”,功能，得出结果，看其是否对原最优解、最优值有影响。,58,线性规划问题的影子价格及灵敏度分析,方法,2,：应用敏感性报告及百分之百法则进行分析,对原电子表格模型，运行,EXCEL,”,规划求解,”,功能，得出,“,规划求解结果,”,对话框，选择右端,“,敏感性报告,”,选项，得出相应结果。运用百分之百法则进行判断。,百分之一百法则：,对于所有变化的目标函数决策变量系数（或约束条件右边常数），当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，最优解不变。,59,线性规划问题的影子价格及灵敏度分析,允许增加量百分比,=,实际增加量（上限,-,现在值）,/,允许增加量,允许减少量百分比,=,实际减少量（现在值,-,下限）,/,允许减少量,例：门,300,450,；窗,500,400,例：门,300,600,；窗,500,300,如果超过,100%,，用电子表格模型重新求解,思考：当结果刚好为,100%,时，最优解变吗？,60,线性规划问题的影子价格及灵敏度分析,应用规则：,当允许增加量（减少量）为无穷大时，则对于任一个增加量（减少量），其允许增加（或减少）的百分比都看成零。,百分之一百法则是判断最优解变与不变的充分条件，但不是必要条件。,不能应用于目标函数决策变量系数和约束条件右端常数同时变化的情况。,61,线性规划问题的影子价格及灵敏度分析,3,、单个,b,i,变动,例：如果车间,2,的可用工时由,12,小时增加到,13,小时，原来的最优解和最优值是否发生变化？,方法,1,：,应用电子表格进行分析,改变电子表格模型中相应的参数，再运行,EXCEL,”,规划求解,”,功能，得出结果，看其是否对原最优解、最优值有影响。,分析：,2,10,18,20,的不同结果？,62,线性规划问题的影子价格及灵敏度分析,方法,2,：,应用敏感性报告寻找允许变化范围,对原电子表格模型运行,EXCEL,”,规划求解,”,功能，得出,“,规划求解结果,”,对话框，选择右端,“,敏感性报告,”,选项，得出相应结果。,63,线性规划问题的影子价格及灵敏度分析,4,、多个,b,i,变动,例：如果车间,2,的可用工时由,12,小时增加到,13,小时，车间,3,的可用工时由,18,小时减少到,17,小时，原来的最优解和最优值是否发生变化？,方法,1,：应用电子表格进行分析,改变电子表格模型中相应的参数，再运行,EXCEL,”,规划求解,”,功能，得出结果，看其是否对原最优解、最优值有影响。,64,线性规划问题的影子价格及灵敏度分析,方法,2,：应用敏感性报告及百分之百法则进行分析,对原电子表格模型，运行,EXCEL,”,规划求解,”,功能，得出,“,规划求解结果,”,对话框，选择右端,“,敏感性报告,”,选项，得出相应结果。运用百分之百法则进行判断。,例：车间,2,：,12,13,，车间,3,：,18,17,例：车间,2,：,12,16,，车间,3,：,18,15,65,线性规划问题的影子价格及灵敏度分析,5,、,a,ij,变化,例：由于车间,2,采用新的生产工艺，生产一扇窗由原来的,2,小时下降到,1.5,小时，原来的最优解和最优值是否发生变化？,解决方法：,改变电子表格模型中相应的参数，再运行,EXCEL,”,规划求解,”,功能，得出结果，看其是否对原最优解、最优值有影响。,66,线性规划问题的影子价格及灵敏度分析,6,、,增加一个新变量,例：由于市场变化，工厂考虑增加一种新产品,防盗门的生产，假设每周产量为,x,3,，单位利润为,400,元，生产一个防盗门占用车间,1,、,2,、,3,各,2,、,1,、,1,工时。其最优解和最优值是多少？,解决方法：,在原电子表格模型中增加一列，输入防盗门的相关数据，修改相应的计算公式形成新的电子表格模型，再运行,EXCEL,”,规划求解,”,功能，得出新的最优解、最优值。,67,线性规划问题的影子价格及灵敏度分析,7,、增加一个约束条件,例：由于电力紧张，在原来生产计划中增加一个约束条件，假设两种产品每件需要消耗电力为,20kw,、,10kw,，工厂总供电能力为,90kw,。其最优解和最优值是多少？,解决方法：,在原电子表格模型中增加一行，输入电力消耗的相关数据，修改相应的计算公式形成新的电子表格模型，再运行,EXCEL,”,规划求解,”,功能，得出新的最优解、最优值。,68,线性规划问题的影子价格及灵敏度分析,综合练习,某工厂利用原材料甲、乙、丙生产产品,A,、,B,、,C,。相关资料见表。问：,怎样安排生产，使利润最大？,产品,B,的单位利润在什么范围内变化时，最优解不变？,若增加,1,公斤原材料甲，总利润增加多少？,甲、乙、丙三种原材料哪种有剩余，剩余多少？,原材料乙的市场价格为,1.2,元,/,公斤。若要转卖原材料乙，工厂应要价多少，为什么？,由于市场变化，产品,B,、,C,的单价利润变为,2,元、,4,元，这时应如何调整生产计划？,69,线性规划问题的影子价格及灵敏度分析,若另有两种新产品,D,、,E,其中,D,需甲、乙、丙三种原材料分别为,1,、,2,、,1,；其中,E,需甲、乙、丙三种原材料分别为,2,、,2,、,2,。单位产品利润分别为,2,、,3.,问这两种产品的生产在经济上是否合算？,通过对生产工艺改进，每生产一件,A,需要三种原材料分别为,1,、,1,、,1.,对原计划有何影响？,A,B,C,可供原材料（公斤）,甲,2,1,1,200,乙,1,2,3,500,丙,2,2,1,600,每件产品利润（元）,4,1,3,70,