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

1、线 性 规 划 模 型“线性规划能做什么？p线性规划的概念和研究的问题p线性规划是在一定的限制条件下使其规划问题的某个整体指标达到最优的方法。p线性规划在财贸金融、工农业生产、交通运输等领域的管理决策分析中均可帮助管理人员解决具体的实际问题。p用线性规划解决的比较简单的问题：1、产品生产的组合安排 2、原料搭配及下料 3、物资运输 4、投资问题等线性规划问题基本理论及方法p例：某工厂生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18

2、小时。已知每扇门的利润为300元，每扇窗的利润为500元。根据市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有的新产品均能销售出去。线性规划问题基本理论及方法车间车间单位产品的生产时间（小时）单位产品的生产时间（小时）每周可获得的生产每周可获得的生产时间（小时）时间（小时）门门窗窗1 11 10 04 42 20 02 212123 33 32 21818单位利润（元）单位利润（元）300300500500问题：该工厂如何安排这两种新产品的每周生产计划，才能使总利润最大？如果要增加资源，首先应该增加哪种资源？这些资源出租或出售，应如何定价？如果产品市场价格发生变化、产品

3、加工工艺发生改变，原 生产方案是否需要调整？主要内容主要内容p线性规划问题基本理论及方法p应用EXCEL工具求解线性规划问题p线性规划问题建模求解实例分析p线性规划问题的影子价格及灵敏度分析线性规划问题基本理论及方法p线性规划（Linear Programming）:运筹学中理论最完善、方法最成熟、应用最广泛的一个分支。p1939年，前苏联数学家康脱洛维奇（L.V.Kantorovich)提出，1947年，美国数学家丹捷格（G.B.Dantring)提出线性规划的求解方法单纯形法。p主要研究两类问题：n现有资源有限，如何合理安排，使以最少的人力、物力完成任务？n任务确定后，如何计划、安排，使在

4、完成任务的前提下，资源消耗最低？p可解决生产调度、合理下料、配料问题、产品配套问题、运输问题等问题。线性规划问题基本理论及方法p数学模型：有三个要素组成：n决策变量：一组定值代表所给问题的一个具体解决方案。一般要求其非负。n约束条件：反映所给问题的客观限制及完成任务的具体要求，一般表示为一组决策变量的线性线性等式或不等式。n目标函数：问题所要达到的目标。一般表示为决策变量的线性线性函数，取最大值或最小值。线性规划问题基本理论及方法p建模步骤：n确定决策变量：根据决策问题，确定x=(x1,x2,x3,xn)n找出约束条件：找出所有的限制条件，写出其表达式。n明确目标函数：写出目标函数的最大值（或

5、最小值）。线性规划问题基本理论及方法xcxcxnn.)zminmax(2211c?bxaxaxann11212111),(.bxaxaxann22222121),(.bxaxaxamnmnmm),(.22110,.,321xxxxnS.t线性规划问题基本理论及方法p假设：每周各生产门和窗x1、x2个。建立线性规划模型如下：Max Z=300 x1+500 x2 x14 2x212 3x1+2x218 x1、x20S.t线性规划问题基本理论及方法p例例1 1：红星重型机械厂的产品组合问题：红星重型机械厂的产品组合问题：红星机械厂开发出产品甲与产品乙。管理层决定近期红星机械厂开发出产品甲与产品乙。

6、管理层决定近期安排生产这两种产品。已知产品甲需要原料安排生产这两种产品。已知产品甲需要原料A A，产品乙，产品乙需要原料需要原料B B。由于两种产品都在一个设备上生产，且设。由于两种产品都在一个设备上生产，且设备工时有限，管理者必须合理安排两种产品的产量，备工时有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下获得最大利润。使得在资源有限的条件下获得最大利润。甲甲乙乙资源限制资源限制原料原料A A（吨）（吨）1 10 06 6原料原料B B（吨）（吨）0 02 28 8设备（单位设备工时）设备（单位设备工时）2 23 31818单位利润（万元）单位利润（万元）4 43 3线性规划问

7、题基本理论及方法p例2：美克制造公司的劳动力分配问题：美克制造公司生产三种产品，每单位产品的利润分别为100元、90元和95元。每个产品都要经过4个车间加工。假定每个车间的工人总工时是给定的，每单位产品在各车间需要的工时见表。决定三种产品的生产数量。车间车间单位产品需要工时（小时）单位产品需要工时（小时）总可用工时（小时）总可用工时（小时）产品产品1 1产品产品2 2产品产品3 31 11.01.00.80.81.21.2280028002 20.30.30.40.40.40.4180018003 30.90.91.21.20.60.6390039004 40.80.80.40.40.30.3

8、28002800单位利润（元）单位利润（元）10010090909595线性规划问题基本理论及方法p例例3 3：新农饲料公司饲料配制问题：新农饲料公司饲料配制问题：新农饲料公司希望用玉米和红薯两种原料配制一种混新农饲料公司希望用玉米和红薯两种原料配制一种混合饲料。由于玉米和红薯包含的营养成分和采购成本合饲料。由于玉米和红薯包含的营养成分和采购成本都不相同，公司管理层希望能够确定混合饲料中玉米都不相同，公司管理层希望能够确定混合饲料中玉米和红薯的数量，使得饲料能够以最低的成本达到给定和红薯的数量，使得饲料能够以最低的成本达到给定的营养要求。收集资料如下：的营养要求。收集资料如下：营养成分营养成分

9、每千克玉米每千克玉米每千克红薯每千克红薯最低要求量最低要求量碳水化合物（克）碳水化合物（克）8 84 42020蛋白质（克）蛋白质（克）3 36 61818维生素（克）维生素（克）1 15 51616采购成本（元）采购成本（元）0.80.80.50.5线性规划问题基本理论及方法p求解步骤：n找出初始基本可行解（一般选择原点）；n检验初始基本可行解是否为最优解；n如果不是，寻找新的基本可行解；n再次进行检验，直到找出最优解为止。p对于两个变量的线性规划问题，可用图解法；对于两个以上变量问题，采用单纯形法求解。n图解法、单纯形法例。线性规划问题基本理论及方法p图解法求解步骤：n建立x1Ox2平面直

10、角坐标系。n将所有约束条件的临界值（直线）标于坐标系中，得出可行域（所有可行解的集合）。n给目标函数赋一值，在坐标系中划出相应直线，在可行域中移动，找出其极值方向的交点，即为该问题的最优解。线性规划问题基本理论及方法p解的性质:n线性规划问题的可行域都是凸多边形（可能无界）；n可行域的顶点为基本可行解，若存在最优解，一定在顶点上达到；n如果同时在两个顶点达到最优解，该直线上任意一点均为最优解，此时为无穷多最优解。n求解原理：从可行域中的某一顶点开始，逐一进行比较，使目标函数最优的顶点即为最优解。线性规划问题基本理论及方法p线性规划的基本原理（以例图解法说明）：n解的类型：一定无解一定无解解的结

11、果解的结果有可行域有可行域无可行域无可行域可行域有界可行域有界可行域无界可行域无界唯一解唯一解无穷解无穷解唯一解唯一解无穷解无穷解无解无解线性规划问题基本理论及方法p单纯形法求解步骤：n将线性规划模型转化为标准型（目标函数求极大、约束条件为等式、决策变量大于0）；n找出初始基本可行解（即：m个约束条件中存在m个单位列向量，组成单位矩阵）；n检验初始基本可行解是否为最优解？（若所有非基变量的检验数j0，则基本可行解为最优解）；n如果不是最优解，进行迭代，求出新的基本可行解。（根据最小比值原则选择出基变量和进基变量）p单纯形法计算过程在单纯形表中具体实现。应用应用EXCELEXCEL工具求解线性规

12、划问题工具求解线性规划问题一、在EXCEL电子表格中建立线性规划模型1、把相关数据输入到EXCEL电子表格中应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题2、主要求解结果 两种新产品x1、x2每周的产量；两种新产品每周各实际使用的工时（不能 超过计划工时）；两种新产品的总利润z。应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题3、主要结果的计算方法（1）两种新产品的每周产量：C12、D12，试验解为0。（2）实际使用工时计算（三种方法）分别在E7、E8、E9中输入相应的计算公式：E7：C7*C12+D7*D12；E8：C8*C12+D8*D12；E9：

13、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应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题（3）总利润计算：在G12单元格输入公式：=C4*C12+D4*D12 或：=SUMPRODUCT（C4：D4，C12：D12）应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题p收集问题数据；p在EXCEL表格中输入数据（数据单元格）；p确定决策变量单元格（可变单元格）；p输入

14、约束条件左边的公式（输出单元格）,使用SUMPRODUCT函数简化输入；p输入目标函数公式（目标单元格）。使用SUMPRODUCT函数简化输入。在EXCEL中建立线性规划模型步骤总结应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题二、在EXCEL电子表格中求解线性规划模型1、求解参数设置：“工具”规划求解“，弹出“规划求解参数”对话框，设置求解相关参数。应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题2、约束的设置：单击“添加”，弹出“添加约束”，添加约束条件。应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题3、求解选项设置：单击“选

15、项”，弹出“规划求解选项”对话框。选择“采用线性模型”和“假定非负”。应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题4、求解及结果 单击“求解”，开始规划求解。弹出“规划求解结果”对话框。选择“保存规划求解结果”。应用应用EXCELEXCEL工具求解线性规划问题工具求解线性规划问题5、电子表格显示结果：单击“确定”，在电子表格的可变单元格、输出单元格及目标单元格出现求解结果。p输入数据p标识数据p每个数据对应唯一单元格p在电子表格中显示完整模型p数据、公式分离p保持简单化p使用相对和绝对地址简化公式并复制p使用边框、底色区分单元格类型p例1-3建模求解要点回顾应用应用EX

16、CELEXCEL工具求解线性规划问题工具求解线性规划问题四、线性规划问题解的表现 EXCEL建模求解，其解的结果在“规划求解结果”对话框中提示：1、唯一最优解为”找到一个解“2、无穷多最优解为”满足条件有多个解“3、无解为”未找到可行解“线性规划问题建模求解实例分析一、生产计划问题例1：某工厂生产甲、乙、丙三种产品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可自行生产，但产品丙必须在本厂铸造才能保证质量。数据见表。问：公司为了获得最大利润，甲、乙、丙三种产品应各生产多少件？甲、乙两种产品的铸件应由本公司铸造和由外包协作各多少件?线性规划问题建模求解实例分析产品甲产

17、品甲产品乙产品乙产品丙产品丙工时限制工时限制单件铸造工时（小时）单件铸造工时（小时）51078000单件机加工工时（小时）单件机加工工时（小时）64812000单件装配工时（小时）单件装配工时（小时）32210000自产铸件成本（元自产铸件成本（元/件）件）354外协铸件成本（元外协铸件成本（元/件）件）56-机加工成本（元机加工成本（元/件）件）213装配成本（元装配成本（元/件）件）322产品售价（元产品售价（元/件）件）231816线性规划问题建模求解实例分析例2：某工厂生产某工厂生产A A、B B种产品，均需经过两道工序，每生产种产品，均需经过两道工序，每生产1 1吨吨A A产品需要产

18、品需要经过第一道工序加工经过第一道工序加工2 2小时，第二道工序加工小时，第二道工序加工3 3小时；每生产小时；每生产1 1吨吨B B产品需产品需要经过第一道工序加工要经过第一道工序加工3 3小时，第二道工序加工小时，第二道工序加工4 4小时。可供利用的第一小时。可供利用的第一道工序工时为道工序工时为1515小时；第二道工序工时为小时；第二道工序工时为2525小时。小时。生产产品生产产品B B的同时可产出副产品的同时可产出副产品C C，每生产，每生产1 1吨产品吨产品B B，可同时得到，可同时得到2 2吨产品吨产品C C而不需要外加任何费用。副产品而不需要外加任何费用。副产品C C一部分可以赢

19、利，但剩下的一部分可以赢利，但剩下的只能报废，报废需要有一定的费用。只能报废，报废需要有一定的费用。出售产品出售产品A A每吨能赢利每吨能赢利400400元；出售产品元；出售产品B B每吨能赢利每吨能赢利800800元；出售元；出售副产品副产品C C每吨能赢利每吨能赢利300300元；当剩余的产品元；当剩余的产品C C报废时，每吨损失费为报废时，每吨损失费为200200元。经市场预测，在计划期内产品元。经市场预测，在计划期内产品C C的最大销售量为的最大销售量为5 5吨。吨。问：如何安排问：如何安排A A、B B两种产品的产量可使工厂总盈利最大？两种产品的产量可使工厂总盈利最大？线性规划问题建

20、模求解实例分析二、生产存储问题 某公司根据订单生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用见表。已知公司每月的生产能力为100，每月仓库容量为50.问：如何确定产品未来半年内每月最佳生产量和存储量，才能使总费用最少？月份月份123456需求量需求量504050455530单位生产费用单位生产费用825775850850775825单位存储费用单位存储费用403035204040线性规划问题建模求解实例分析线性规划问题建模求解实例分析三、项目投资问题1、某公司有100万元的资金可供投资,该公司有六个可选的投资项目,其各种数据见下表.该公司的目标:投资风险最小,每年红利至少6.5万

21、元,最低平均增长率为12%,最低平均信用度为7.投资项目投资项目风险风险(%)红利红利(%)增长率增长率(%)信用度信用度11842242657103109122447810512615468886线性规划问题建模求解实例分析p假设：xi为每种投资项目投资额。建立线性规划模型如下：MinZ=0.18x1+0.06x2+0.10 x3+0.04x4+0.12x5+0.08x6 x1+x2+x3+x4+x5+x6=100 0.04x1+0.05x2+0.09x3+0.07x4+0.06x5+0.08x6 6.5 0.22x1+0.07x2+0.12x3+0.08x4+0.15x5+0.08x6 1

22、2 4x1+10 x2+2x3+10 x4+4x5+6x6 700 x1、x2、x3、x4、x5、x6 0线性规划问题建模求解实例分析2、证券投资问题：一证券投资者将1000万元资金用于证券投资。已知各种证券（A、B、C、D、E、F）的评级、到期年限、每年税后收益见表。管理者对投资者提出下列要求（1）国债投资额不能少于300万元；（2）投资证券的平均评级不超过1.5；（3）投资证券的平均到期年限不超过5年。问：每种证券投资多少可以使得税后收益最大？证券名称证券名称证券类型证券类型评级评级到期年限（年）到期年限（年）每年税后收益（每年税后收益（%）A地方债券地方债券294.3B基金基金2124.

23、4C国债国债153.2D国债国债143.0E地方债券地方债券433.2F基金基金544.5线性规划问题建模求解实例分析3、连续投资优化 某部门在今后五年内考虑给下列项目投资：项目A：从第一年到第四年每年年初都可以投资，并于次年年 末收回本利115%；项目B：第三年初可以投资，到第五年末能收回本利125%，但规定最大投资额不超过4万元；项目C：第二年年初可以投资，到第五年末能收回本利 140%，但规定最大投资额不超过3万元；项目D：五年内每年年初都可以购买公债，于当年年末归还 并加利息6%；该部门现有资金10万元，问应该如何确定这些项目的每年投资额，使得第五年末拥有的资金本利总额最大？线性规划问

24、题建模求解实例分析四、背包问题1、有一艘货轮，它的容积为5400m3，其最大允许载重量3000t，现有三种大批量的货物待运，已知有关数据如下。问：该货轮应装载商品1、2、3个多少件，其运费收入为最大？商品商品每件体积（每件体积（m3/件）件）每件重量（每件重量（t/件）件）运价（元运价（元/件）件）11081000256700375600线性规划问题建模求解实例分析2、某航运公司有一条三个舱口的货轮，它们的载容量和载重量见表。待运货物的品种、数量、体积、重量见表。为了保证航行的安全，要求各船按照确定的载重量装货，2号舱对1号舱的载重量比值、2号舱对3号舱的载重量比值允许在10%的范围内变动，3

25、号舱对1号舱的载重量比值允许在5%的范围内变动。问：如何合理配载，才能使总的运费收入达到最大？线性规划问题建模求解实例分析p2、舱号舱号载容量（载容量（m3）载重量（载重量（t）136002800242003200330002400货物种类货物种类 数量（件）数量（件）体积（体积（m3/件）件）重量（重量（t/件）件）运费（元运费（元/件）件）15008615002100043800360054900线性规划问题建模求解实例分析五、套裁下料问题:某工厂要做100套钢架，每套钢架分别需要长度为2.9米、2.1米和1.5米得圆钢各一套。已知原料每根长7.4米，问应如何下料，可使所用原料最省？线性规

26、划问题建模求解实例分析六、营养配餐问题:假设一个成年人每周需要从食物中获取2500卡路里热量、100g蛋白质、1000mg维生素和400mg钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成分以及市场价格见表。问如果每人每周四种食品总食用量限制在4.5kg，如何选择才能使在满足营养的前提下使购买食品的总费用最小？食品名称食品名称热量热量（卡路里）（卡路里）蛋白质蛋白质（g）维生素维生素（mg）钙钙（mg）价格价格（元（元/kg）猪肉（猪肉（kg)150010018020020鸡蛋（鸡蛋（kg)1000120501008大米（大米（kg)60025501503.5蔬菜水果（蔬菜水果（

27、kg)18015300502需求量需求量25001001000400线性规划问题建模求解实例分析七、人力资源分配例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点点最低需求

28、最低需求人数（人）人数（人）86152025231810薪水（元）薪水（元）2630282220202224线性规划问题建模求解实例分析例2：某快餐店坐落在一个远离市区的旅游点中，平时游客不多，而在除冬季外每个双休日游客都比较多。该快餐店有两名正式职工，正式职工每天工作8小时，且每个时间段都至少有一名正式职工在上班，其余工作有临时工来承担，临时工每班工作4小时。在双休日每天上午10时开始营业到下午10时关门。根据游客就餐情况，在双休日每个营业时间段所需职工数（包括正式工和临时工）见表。已知一名正式职工10点开始上班，工作4小时后休息1小时，而后再工作4小时；另一名正式职工13点开始上班，工作4

29、小时后休息1小时，而后再工作4小时。临时工每小时的工资为4元。线性规划问题建模求解实例分析时间段时间段所需职工数所需职工数时间段时间段所需职工数所需职工数10:0010:0011:0011:009 916:0016:0017:0017:003 311:0011:0012:0012:00101017:0017:0018:0018:006 612:0012:0013:0013:00101018:0018:0019:0019:00121213:0013:0014:0014:009 919:0019:0020:0020:00121214:0014:0015:0015:003 320:0020:0021

30、:0021:007 715:0015:0016:0016:003 321:0021:0022:0022:007 7 在满足对职工需求的条件下，如何安排临时工的班次，使得使用临时工的成本为最小？这时付给临时工的工资总额是多少？一共需要安排多少个班次的临时工？如果可以安排每班工作3小时的临时工班次，是否可使总成本更小。线性规划问题建模求解实例分析八、其它 例1：某市场调查公司受某公司委托，调查消费者对某种新产品的了解和反应情况。该公司对调查公司提出如下要求：（1）共对500个家庭进行调查；（2）在被调查家庭中，至少有200个是没有孩子的家庭，同时至少有200个是有孩子的家庭；（3）至少对300个被

31、调查家庭采用问卷式书面调查，对其余家庭可采用口头调查；（4）在有孩子的被调查家庭中，至少对50%的家庭采用问卷式书面调查；（5）在没有孩子的被调查家庭中，至少对60%的家庭采用问卷式书面调查。调查费用见表。问：市场调查公司应如何进行调查，使得在满足公司要求的条件下，使得总调查费用 最少？家庭类型家庭类型调查费用（元）调查费用（元）问卷式书面调查问卷式书面调查口头调查口头调查有孩子家庭有孩子家庭5030没有孩子家庭没有孩子家庭4025线性规划问题建模求解实例分析例2：巨斯特石油公司混合问题：巨斯特石油公司要生产两种汽油产品。一种是一般汽油，另一种是特殊汽油。公司来炼油厂希望通过合成4类石油成分来

32、生产这两种汽油产品。两种汽油的售价、4类石油成分成本均不同。公司希望确定一种混合这4类石油成分以生产两种汽油产品的方案来获得最大利润。石油成分石油成分单位成本单位成本（$）最大供应量最大供应量（加仑）（加仑）一般汽油一般汽油产品要求产品要求特殊汽油特殊汽油产品要求产品要求成分成分10.856000最多最多30%最少最少25%成分成分21.1512000最少最少35%最多最多40%成分成分31.3611000最多最多20%最少最少30%成分成分41.201300025%18%线性规划问题的影子价格及灵敏度分析p对偶问题：线性规划的一个有趣现象。任何一个线性规划问题都有一个与之相对应的对偶问题，在

33、求出一个问题的最优解的同时，也得出其对偶问题的最优解。xcxcxnn.zmax2211cbxaxaxann11212111.bxaxaxann22222121.bxaxaxamnmnmm.22110,.,321xxxxnS.tS.tybybymmm.inw2211bcyayayamm11221111.cyayayamm22222112.cyayayanmmnnn.22110,.,321yyyym线性规划问题的影子价格及灵敏度分析 原问题 对偶问题Max Z=300 x1+500 x2 x14 2x212 3x1+2x218 x1、x20S.tMin W=4y1+12y2+18y3 y1+3y3

34、300 2y2+2y3500 y1、y2、y30S.t线性规划问题的影子价格及灵敏度分析p影子价格：经济学的一个重要概念，又称预测价格。指某种产品或资源增加一个单位所带来的总收益的增加量（反映一种资源在最优方案条件下单位资源提供的目标函数值的增量）。是一种资源效用价值的估价。p对偶问题的第i个对偶变量就是原问题第i个约束条件的影子价格。如前例：x*=(2,6)；y*=(0,150,100)。车间2的总工时由12变为13时，可使所获总利润增加150元。p实际意义：n当考虑通过增加资源以增加收益，应选择影子价格最大的资源；n当某种资源的影子价格高于（或低于）该资源的市场价格时，公司应考虑对该种资源

35、进行购买（或出售、租）；n影子价格帮助管理人员判断某种产品是否值得生产（或制定新产品价格）；线性规划问题的影子价格及灵敏度分析p灵敏度分析：在用线性规划方法解决实际问题时，把cj、aij、bi均当成确定的常量系数是不符合实际的。因此所得出的最优解和最优值也不是一尘不变的。其原因：n这些数据是通过统计、预测或经验得出；n受政策因素、市场条件、科技进步、资源供应状况等因素影响。因此，线性规划还需考虑：n当上述系数中的一个或几个因素发生变化，原来的最优解是否发生变化？n这些系数在什么范围内变化，原来的最优解或最优值不变？n如果系数发生变化引起最优解发生变化，新的最优解和最优值如何得到？线性规划问题的

36、影子价格及灵敏度分析 线性规划问题的灵敏度分析是在求出最优解的基础上，进一步讨论当c cj j、b bi i、a aijij发生变化时，对最优解的影响。判断某一系数发生变化，原最优解是否发生变化？怎样得出使原最优解不变的系数变化范围。当最优解发生变化时，怎样求出新的最优解。线性规划问题的影子价格及灵敏度分析1、单个cj变动p例：如果门的单位利润由原来的300元提升到500元，最优解是否会改变？对总利润会产生怎样的影响？p方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解有影响。线性规划问题的影子价格及灵敏度分析p方法2：应

37、用敏感性报告寻找允许变化范围 对原电子表格模型运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。线性规划问题的影子价格及灵敏度分析比较两种方法的比较两种方法的区别？区别？线性规划问题的影子价格及灵敏度分析2 2、多个、多个c cj j变动变动p例：如果把门的单位利润由300元提高到450元，同时把窗的单位利润由500元减少到400元，原来的最优解和最优值是否会发生变化？p方法1：应用电子表格进行分析 改变EXCEL模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。线性规划问题的影子价格及灵敏度分析

38、p方法2：应用敏感性报告及百分之百法则进行分析 对原电子表格模型，运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。运用百分之百法则进行判断。百分之一百法则：对于所有变化的目标函数决策变量系数（或约束条件右边常数），当其所有允许增加百分比和允许减少百分比之和不超过百分之一百时，最优解不变。线性规划问题的影子价格及灵敏度分析p允许增加量百分比=实际增加量（上限-现在值）/允许增加量p允许减少量百分比=实际减少量（现在值-下限）/允许减少量p例：门300450；窗500400p例：门300600；窗500300p如果超过100%，用电子表格模型重

39、新求解p思考：当结果刚好为100%时，最优解变吗？线性规划问题的影子价格及灵敏度分析p应用规则：n当允许增加量（减少量）为无穷大时，则对于任一个增加量（减少量），其允许增加（或减少）的百分比都看成零。n百分之一百法则是判断最优解变与不变的充分条件，但不是必要条件。n不能应用于目标函数决策变量系数和约束条件右端常数同时变化的情况。线性规划问题的影子价格及灵敏度分析3 3、单个、单个b bi i变动变动p例：如果车间2的可用工时由12小时增加到13小时，原来的最优解和最优值是否发生变化？p方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是

40、否对原最优解、最优值有影响。分析：2101820的不同结果？线性规划问题的影子价格及灵敏度分析p方法2：应用敏感性报告寻找允许变化范围 对原电子表格模型运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。线性规划问题的影子价格及灵敏度分析4 4、多个、多个b bi i变动变动p例：如果车间2的可用工时由12小时增加到13小时，车间3的可用工时由18小时减少到17小时，原来的最优解和最优值是否发生变化？p方法1：应用电子表格进行分析 改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。线性规

41、划问题的影子价格及灵敏度分析p方法2：应用敏感性报告及百分之百法则进行分析 对原电子表格模型，运行EXCEL”规划求解”功能，得出“规划求解结果”对话框，选择右端“敏感性报告”选项，得出相应结果。运用百分之百法则进行判断。n例：车间2：1213，车间3：1817n例：车间2：1216，车间3：1815线性规划问题的影子价格及灵敏度分析5 5、a aijij变化变化p例：由于车间2采用新的生产工艺，生产一扇窗由原来的2小时下降到1.5小时，原来的最优解和最优值是否发生变化？p解决方法：改变电子表格模型中相应的参数，再运行EXCEL”规划求解”功能，得出结果，看其是否对原最优解、最优值有影响。线性

42、规划问题的影子价格及灵敏度分析6 6、增加一个新变量增加一个新变量p例：由于市场变化，工厂考虑增加一种新产品防盗门的生产，假设每周产量为x3，单位利润为400元，生产一个防盗门占用车间1、2、3各2、1、1工时。其最优解和最优值是多少？p解决方法：在原电子表格模型中增加一列，输入防盗门的相关数据，修改相应的计算公式形成新的电子表格模型，再运行EXCEL”规划求解”功能，得出新的最优解、最优值。线性规划问题的影子价格及灵敏度分析7 7、增加一个约束条件、增加一个约束条件p例：由于电力紧张，在原来生产计划中增加一个约束条件，假设两种产品每件需要消耗电力为20kw、10kw，工厂总供电能力为90kw

43、。其最优解和最优值是多少？p解决方法：在原电子表格模型中增加一行，输入电力消耗的相关数据，修改相应的计算公式形成新的电子表格模型，再运行EXCEL”规划求解”功能，得出新的最优解、最优值。线性规划问题的影子价格及灵敏度分析综合练习综合练习 某工厂利用原材料甲、乙、丙生产产品A、B、C。相关资料见表。问：怎样安排生产，使利润最大？产品B的单位利润在什么范围内变化时，最优解不变？若增加1公斤原材料甲，总利润增加多少？甲、乙、丙三种原材料哪种有剩余，剩余多少？原材料乙的市场价格为1.2元/公斤。若要转卖原材料乙，工厂应要价多少，为什么？由于市场变化，产品B、C的单价利润变为2元、4元，这时应如何调整生产计划？线性规划问题的影子价格及灵敏度分析若另有两种新产品D、E,其中D需甲、乙、丙三种原材料分别为1、2、1；其中E需甲、乙、丙三种原材料分别为2、2、2。单位产品利润分别为2、3.问这两种产品的生产在经济上是否合算？通过对生产工艺改进，每生产一件A需要三种原材料分别为1、1、1.对原计划有何影响？ABC可供原材料（公斤）可供原材料（公斤）甲甲211200乙乙123500丙丙221600每件产品利润（元）每件产品利润（元）413