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

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

2、每扇门的利润为300元，每扇窗的利润为500元。根据市场调查得到的这两种新产品的市场需求情况可以确定，按当前的定价可确保一切的新产品均能销售出去。线性规划问题根本实际及方法车间单位产品的生产时间（小时）每周可获得的生产时间（小时）门窗11042021233218单位利润（元）300500问题： 该工厂如何安排这两种新产品的每周消费方案，才干使总利润最大？ 假设要添加资源，首先应该添加哪种资源？ 这些资源出租或出卖，应如何定价？ 假设产品市场价钱发生变化、产品加工工艺发生改动，原 消费方案能否需求调整？主要内容线性规划问题根本实际及方法运用EXCEL工具求解线性规划问题线性规划问题建模求解实例分

3、析线性规划问题的影子价钱及灵敏度分析线性规划问题根本实际及方法线性规划Linear Programming:运筹学中实际最完善、方法最成熟、运用最广泛的一个分支。1939年，前苏联数学家康脱洛维奇L.V.Kantorovich)提出，1947年，美国数学家丹捷格G.B.Dantring)提出线性规划的求解方法单纯形法。主要研讨两类问题：现有资源有限，如何合理安排，使以最少的人力、物力完成义务？义务确定后，如何方案、安排，使在完成义务的前提下，资源耗费最低？可处理消费调度、合理下料、配料问题、产品配套问题、运输问题等问题。线性规划问题根本实际及方法数学模型：有三个要素组成：决策变量：一组定值代表

4、所给问题的一个详细处理方案。普通要求其非负。约束条件：反映所给问题的客观限制及完成义务的详细要求，普通表示为一组决策变量的线性等式或不等式。目的函数：问题所要到达的目的。普通表示为决策变量的线性函数，取最大值或最小值。线性规划问题根本实际及方法建模步骤：确定决策变量：根据决策问题，确定x=(x1,x2,x3,xn)找出约束条件：找出一切的限制条件，写出其表达式。明确目的函数：写出目的函数的最大值或最小值。线性规划问题根本实际及方法S.t线性规划问题根本实际及方法假设：每周各消费门和窗x1、x2个。 建立线性规划模型如下： Max Z=300 x1+500 x2 x14 2x212 3x1+2x

5、218 x1、x20S.t线性规划问题根本实际及方法例1：红星重型机械厂的产品组合问题： 红星机械厂开发出产品甲与产品乙。管理层决议近期安排消费这两种产品。知产品甲需求原料A，产品乙需求原料B。由于两种产品都在一个设备上消费，且设备工时有限，管理者必需合理安排两种产品的产量，使得在资源有限的条件下获得最大利润。甲乙资源限制原料A（吨）106原料B（吨）028设备（单位设备工时）2318单位利润（万元）43线性规划问题根本实际及方法例2：美抑制造公司的劳动力分配问题： 美抑制造公司消费三种产品，每单位产品的利润分别为100元、90元和95元。每个产品都要经过4个车间加工。假定每个车间的工人总工时

6、是给定的，每单位产品在各车间需求的工时见表。决议三种产品的消费数量。车间单位产品需要工时（小时）总可用工时（小时）产品1产品2产品311.00.81.2280020.30.40.4180030.91.20.6390040.80.40.32800单位利润（元）1009095线性规划问题根本实际及方法例3：新农饲料公司饲料配制问题： 新农饲料公司希望用玉米和红薯两种原料配制一种混合饲料。由于玉米和红薯包含的营养成分和采购本钱都不一样，公司管理层希望可以确定混合饲料中玉米和红薯的数量，使得饲料可以以最低的本钱到达给定的营养要求。搜集资料如下：营养成分每千克玉米每千克红薯最低要求量碳水化合物（克）84

7、20蛋白质（克）3618维生素（克）1516采购成本（元）0.80.5线性规划问题根本实际及方法求解步骤：找出初始根本可行解普通选择原点；检验初始根本可行解能否为最优解；假设不是，寻觅新的根本可行解；再次进展检验，直到找出最优解为止。对于两个变量的线性规划问题，可用图解法；对于两个以上变量问题，采用单纯形法求解。图解法、单纯形法例。线性规划问题根本实际及方法图解法求解步骤：建立x1Ox2平面直角坐标系。将一切约束条件的临界值直线标于坐标系中，得出可行域一切可行解的集合。给目的函数赋一值，在坐标系中划出相应直线，在可行域中挪动，找出其极值方向的交点，即为该问题的最优解。线性规划问题根本实际及方法

8、解的性质:线性规划问题的可行域都是凸多边形能够无界；可行域的顶点为根本可行解，假设存在最优解，一定在顶点上到达；假好像时在两个顶点到达最优解，该直线上恣意一点均为最优解，此时为无穷多最优解。求解原理：从可行域中的某一顶点开场，逐一进展比较，使目的函数最优的顶点即为最优解。线性规划问题根本实际及方法线性规划的根本原理以例图解法阐明：解的类型：一定无解解的结果有可行域无可行域可行域有界可行域无界独一解无穷解独一解无穷解无解线性规划问题根本实际及方法单纯形法求解步骤：将线性规划模型转化为规范型目的函数求极大、约束条件为等式、决策变量大于0；找出初始根本可行解即：m个约束条件中存在m个单位列向量，组成

9、单位矩阵；检验初始根本可行解能否为最优解？假设一切非基变量的检验数j0，那么根本可行解为最优解；假设不是最优解，进展迭代，求出新的根本可行解。根据最小比值原那么选择出基变量和进基变量单纯形法计算过程在单纯形表中详细实现。运用EXCEL工具求解线性规划问题一、在EXCEL电子表格中建立线性规划模型1、把相关数据输入到EXCEL电子表格中运用EXCEL工具求解线性规划问题2、主要求解结果 两种新产品x1、x2每周的产量； 两种新产品每周各实践运用的工时不能 超越方案工时； 两种新产品的总利润z。运用EXCEL工具求解线性规划问题3、主要结果的计算方法1两种新产品的每周产量：C12、D12，实验解为

10、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中输入：=SUMPRODUCTC7：D7，$C$12，$D$12 复制E7单元格到E8、E9运用EXCEL工具求解线性规划问题3总利润计算： 在G12单元格输入公式： =C4*C12+D4*D12 或： =SUMPRODUCTC4：D4，C12：D12运用EXCEL工具求解线性规划问题搜集问题数据；

11、在EXCEL表格中输入数据数据单元格；确定决策变量单元格可变单元格；输入约束条件左边的公式输出单元格,运用SUMPRODUCT函数简化输入；输入目的函数公式目的单元格。运用SUMPRODUCT函数简化输入。在EXCEL中建立线性规划模型步骤总结运用EXCEL工具求解线性规划问题二、在EXCEL电子表格中求解线性规划模型1、求解参数设置： “工具规划求解“，弹出“规划求解参数对话框，设置求解相关参数。运用EXCEL工具求解线性规划问题2、约束的设置： 单击 “添加，弹出“添加约束，添加约束条件。运用EXCEL工具求解线性规划问题3、求解选项设置： 单击“选项，弹出“规划求解选项对话框。选择“采用

12、线性模型和“假定非负。运用EXCEL工具求解线性规划问题4、求解及结果 单击“求解，开场规划求解。弹出“规划求解结果对话框。选择“保管规划求解结果。运用EXCEL工具求解线性规划问题5、电子表格显示结果： 单击“确定，在电子表格的可变单元格、输出单元格及目的单元格出现求解结果。输入数据标识数据每个数据对应独一单元格在电子表格中显示完好模型数据、公式分别坚持简单化运用相对和绝对地址简化公式并复制运用边框、底色区分单元格类型例1-3建模求解要点回想运用EXCEL工具求解线性规划问题四、线性规划问题解的表现 EXCEL建模求解，其解的结果在“规划求解结果对话框中提示： 1、独一最优解为找到一个解“

13、2、无穷多最优解为满足条件有多个解“ 3、无解为未找到可行解“线性规划问题建模求解实例分析一、消费方案问题例1：某工厂消费甲、乙、丙三种产品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可自行消费，但产品丙必需在本厂铸造才干保证质量。数据见表。问：公司为了获得最大利润，甲、乙、丙三种产品应各消费多少件？甲、乙两种产品的铸件应由本公司铸造和由外包协作各多少件?线性规划问题建模求解实例分析产品甲产品乙产品丙工时限制单件铸造工时（小时）51078000单件机加工工时（小时）64812000单件装配工时（小时）32210000自产铸件成本（元/件）354外协铸件成本（元/件

14、）56-机加工成本（元/件）213装配成本（元/件）322产品售价（元/件）231816线性规划问题建模求解实例分析例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每吨能

15、赢利300元；当剩余的产品C报废时，每吨损失费为200元。经市场预测，在方案期内产品C的最大销售量为5吨。 问：如何安排A、B两种产品的产量可使工厂总盈利最大？线性规划问题建模求解实例分析二、消费存储问题 某公司根据订单消费。知半年内对某产品的需求量、单位消费费用和单位存储费用见表。知公司每月的消费才干为100，每月仓库容量为50.问：如何确定产品未来半年内每月最正确消费量和存储量，才干使总费用最少？ 月份123456需求量504050455530单位生产费用825775850850775825单位存储费用403035204040线性规划问题建模求解实例分析三、工程投资问题1、某公司有100万

16、元的资金可供投资,该公司有六个可选的投资工程,其各种数据见下表.该公司的目的:投资风险最小,每年红利至少6.5万元,最低平均增长率为12%,最低平均信誉度为7.投资项目风险(%)红利(%)增长率(%)信用度11842242657103109122447810512615468886线性规划问题建模求解实例分析假设：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

17、6.5 0.22x1+0.07x2+0.12x3+0.08x4+0.15x5+0.08x6 12 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年。问：每种证券投资多少可以使得税后收益最大？ 证券名称证券类型评级到期年限（年）每年税后收益（%）

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

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

20、值允许在5%的范围内变动。问：如何合理配载，才干使总的运费收入到达最大？线性规划问题建模求解实例分析2、 舱号载容量（m3）载重量（t）136002800242003200330002400货物种类数量（件）体积（ m3 /件）重量（ t /件）运费（元/件）15008615002100043800360054900线性规划问题建模求解实例分析五、套裁下料问题: 某工厂要做100套钢架，每套钢架分别需求长度为2.9米、2.1米和1.5米得圆钢各一套。知原料每根长7.4米，问应如何下料，可使所用原料最省？ 线性规划问题建模求解实例分析六、营养配餐问题: 假设一个成年人每周需求从食物中获取2500

21、卡路里热量、100g蛋白质、1000mg维生素和400mg钙。假设市场上只需四种食品可供选择，它们每千克所含热量和营养成分以及市场价钱见表。问假设每人每周四种食品总食用量限制在4.5kg，如何选择才干使在满足营养的前提下使购买食品的总费用最小？ 食品名称热量（卡路里）蛋白质（ g）维生素（ mg）钙（mg）价格（元/kg）猪肉（kg)150010018020020鸡蛋（kg)1000120501008大米（kg)60025501503.5蔬菜水果（kg求量25001001000400线性规划问题建模求解实例分析七、人力资源分配例1：话务员排班问题： 某急救中心雇佣多名

22、话务员任务，他们每天任务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点最低需求人数（人）86152025231810薪水（元）2630282220202224线性规划问题建模求解实例分析例2：某快餐店坐落在一个远离市区的旅游点中，平常游客不多，而在除冬季外每个双

23、休日游客都比较多。该快餐店有两名正式职工，正式职工每天任务8小时，且每个时间段都至少有一名正式职工在上班，其他任务有暂时工来承当，暂时工每班任务4小时。在双休日每天上午10时开场营业到下午10时关门。根据游客就餐情况，在双休日每个营业时间段所需职工数包括正式工和暂时工见表。 知一名正式职工10点开场上班，任务4小时后休憩1小时，而后再任务4小时；另一名正式职工13点开场上班，任务4小时后休憩1小时，而后再任务4小时。暂时工每小时的工资为4元。线性规划问题建模求解实例分析时间段所需职工数时间段所需职工数10:0011:00916:0017:00311:0012:001017:0018:00612

24、:0013:001018:0019:001213:0014:00919:0020:001214:0015:00320:0021:00715:0016:00321:0022:007 在满足对职工需求的条件下，如何安排暂时工的班次，使得运用暂时工的本钱为最小？这时付给暂时工的工资总额是多少？一共需求安排多少个班次的暂时工？假设可以安排每班任务3小时的暂时工班次，能否可使总本钱更小。线性规划问题建模求解实例分析八、其它 例1：某市场调查公司受某公司委托，调查消费者对某种新产品的了解和反响情况。该公司对调查公司提出如下要求：1共对500个家庭进展调查；2在被调查家庭中，至少有200个是没有孩子的家庭，

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

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

27、x Z=300 x1+500 x2 x14 2x212 3x1+2x218 x1、x20S.tMin W=4y1+12y2+18y3 y1+3y3300 2y2+2y3500 y1、 y2 、y30S.t线性规划问题的影子价钱及灵敏度分析影子价钱：经济学的一个重要概念，又称预测价钱。指某种产品或资源添加一个单位所带来的总收益的添加量反映一种资源在最优方案条件下单位资源提供的目的函数值的增量。是一种资源成效价值的估价。对偶问题的第i个对偶变量就是原问题第i个约束条件的影子价钱。如前例：x*=( 2,6)；y*=( 0,150,100)。车间2的总工时由12变为13时，可使所获总利润添加150元。

28、实践意义：当思索经过添加资源以添加收益，应选择影子价钱最大的资源；当某种资源的影子价钱高于或低于该资源的市场价钱时，公司应思索对该种资源进展购买或出卖、租；影子价钱协助管理人员判别某种产品能否值得消费或制定新产品价钱；线性规划问题的影子价钱及灵敏度分析灵敏度分析： 在用线性规划方法处理实践问题时，把cj、aij、bi均当成确定的常量系数是不符合实践的。因此所得出的最优解和最优值也不是一尘不变的。其缘由：这些数据是经过统计、预测或阅历得出；受政策要素、市场条件、科技提高、资源供应情况等要素影响。 因此，线性规划还需思索：当上述系数中的一个或几个要素发生变化，原来的最优解能否发生变化？这些系数在什

29、么范围内变化，原来的最优解或最优值不变？假设系数发生变化引起最优解发生变化，新的最优解和最优值如何得到？线性规划问题的影子价钱及灵敏度分析 线性规划问题的灵敏度分析是在求出最优解的根底上，进一步讨论当cj、bi、aij发生变化时，对最优解的影响。 判别某一系数发生变化，原最优解能否发生变化？ 怎样得出使原最优解不变的系数变化范围。 当最优解发生变化时，怎样求出新的最优解。线性规划问题的影子价钱及灵敏度分析1、单个cj变动例：假设门的单位利润由原来的300元提升到500元，最优解能否会改动？对总利润会产生怎样的影响？方法1：运用电子表格进展分析 改动电子表格模型中相应的参数，再运转EXCEL规划

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

31、性规划问题的影子价钱及灵敏度分析方法2：运用敏感性报告及百分之百法那么进展分析 对原电子表格模型，运转EXCEL规划求解功能，得出“规划求解结果对话框，选择右端“敏感性报告选项，得出相应结果。运用百分之百法那么进展判别。百分之一百法那么： 对于一切变化的目的函数决策变量系数或约束条件右边常数，当其一切允许添加百分比和允许减少百分比之和不超越百分之一百时，最优解不变。线性规划问题的影子价钱及灵敏度分析允许添加量百分比= 实践添加量上限-如今值/允许添加量允许减少量百分比= 实践减少量如今值-下限/允许减少量例：门300450；窗500400例：门300600；窗500300假设超越100%，用电

32、子表格模型重新求解思索：当结果刚好为100%时，最优解变吗？线性规划问题的影子价钱及灵敏度分析运用规那么：当允许添加量减少量为无穷大时，那么对于任一个添加量减少量，其允许添加或减少的百分比都看成零。百分之一百法那么是判别最优解变与不变的充分条件，但不是必要条件。不能运用于目的函数决策变量系数和约束条件右端常数同时变化的情况。线性规划问题的影子价钱及灵敏度分析3、单个bi变动例：假设车间2的可用工时由12小时添加到13小时，原来的最优解和最优值能否发生变化？方法1：运用电子表格进展分析 改动电子表格模型中相应的参数，再运转EXCEL规划求解功能，得出结果，看其能否对原最优解、最优值有影响。 分析：2101820的不同结果？线性规划问题的影子价钱及灵敏度分析方法2：运用敏感性报告寻觅允许变化范围 对原电子表格模型运转EXCEL规划求解功能，得出“规划求解结果对话框，选择右端“敏感性报告选项，得出相应结果。线性规划问题的影子价钱及灵敏度分析4、多个bi变动例：假设车间2的可用工时由12小时添加到13小时，车间3的可用工时由18小时减少到17小时，原来的最优解和最优值能否发生变化？方法1：运用电子表格进展分析 改动电子表格模型中相应的参数，