物流系统优化线性规划

线性规划模型“线性规划能做什么？线性规划的概念和研究的问题线性规划是在一定的限制条件下使其规划问题的某个整体指标达到最优的方法。线性规划在财贸金融、工农业生产、交通运输等领域的管理决策分析中均可帮助管理人员解决具体的实际问题。用线性规划解决的比较简单的问题：1、产品生产的组合安排2、原料搭配及下料3、物资运输4、投资问题等线性规划问题基本理论及方法例：某工厂生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。已知每扇门的利润为300元，每扇窗的利润为500元。根据市场调查得到的这两种新产品的市场需求状况可以确定，按当前的定价可确保所有的新产品均能销售出去。线性规划问题基本理论及方法车间单位产品的生产时间（小时）每周可获得的生产时间（小时）门窗11042021233218单位利润（元）300500问题：•该工厂如何安排这两种新产品的每周生产计划，才能使总利润最大？•如果要增加资源，首先应该增加哪种资源？•这些资源出租或出售，应如何定价？•如果产品市场价格发生变化、产品加工工艺发生改变，原生产方案是否需要调整？主要内容线性规划问题基本理论及方法应用EXCEL工具求解线性规划问题线性规划问题建模求解实例分析线性规划问题的影子价格及灵敏度分析线性规划问题基本理论及方法线性规划（LinearProgramming）:运筹学中理论最完善、方法最成熟、应用最广泛的一个分支。1939年，前苏联数学家康脱洛维奇（L.V.Kantorovich)提出，1947年，美国数学家丹捷格（G.B.Dantring)提出线性规划的求解方法—单纯形法。主要研究两类问题：现有资源有限，如何合理安排，使以最少的人力、物力完成任务？任务确定后，如何计划、安排，使在完成任务的前提下，资源消耗最低？可解决生产调度、合理下料、配料问题、产品配套问题、运输问题等问题。线性规划问题基本理论及方法数学模型：有三个要素组成：决策变量：一组定值代表所给问题的一个具体解决方案。一般要求其非负。约束条件：反映所给问题的客观限制及完成任务的具体要求，一般表示为一组决策变量的线性等式或不等式。目标函数：问题所要达到的目标。一般表示为决策变量的线性函数，取最大值或最小值。线性规划问题基本理论及方法建模步骤：确定决策变量：根据决策问题，确定x=(x1,x2,x3,…,xn)找出约束条件：找出所有的限制条件，写出其表达式。明确目标函数：写出目标函数的最大值（或最小值）。线性规划问题基本理论及方法xcxcxnn...)zminmax(2211cbxaxaxann11212111),(...bxaxaxann22222121),(...bxaxaxamnmnmm),(...22110,...,,,321xxxxn…S.t线性规划问题基本理论及方法假设：每周各生产门和窗x1、x2个。建立线性规划模型如下：MaxZ=300x1+500x2x1≤42x2≤123x1+2x2≤18x1、x2≥0S.t线性规划问题基本理论及方法例1：红星重型机械厂的产品组合问题：红星机械厂开发出产品甲与产品乙。管理层决定近期安排生产这两种产品。已知产品甲需要原料A，产品乙需要原料B。由于两种产品都在一个设备上生产，且设备工时有限，管理者必须合理安排两种产品的产量，使得在资源有限的条件下获得最大利润。甲乙资源限制原料A（吨）106原料B（吨）028设备（单位设备工时）2318单位利润（万元）43线性规划问题基本理论及方法例2：美克制造公司的劳动力分配问题：美克制造公司生产三种产品，每单位产品的利润分别为100元、90元和95元。每个产品都要经过4个车间加工。假定每个车间的工人总工时是给定的，每单位产品在各车间需要的工时见表。决定三种产品的生产数量。车间单位产品需要工时（小时）总可用工时（小时）产品1产品2产品311.00.81.2280020.30.40.4180030.91.20.6390040.80.40.32800单位利润（元）1009095线性规划问题基本理论及方法例3：新农饲料公司饲料配制问题：新农饲料公司希望用玉米和红薯两种原料配制一种混合饲料。由于玉米和红薯包含的营养成分和采购成本都不相同，公司管理层希望能够确定混合饲料中玉米和红薯的数量，使得饲料能够以最低的成本达到给定的营养要求。收集资料如下：营养成分每千克玉米每千克红薯最低要求量碳水化合物（克）8420蛋白质（克）3618维生素（克）1516采购成本（元）0.80.5线性规划问题基本理论及方法求解步骤：找出初始基本可行解（一般选择原点）；检验初始基本可行解是否为最优解；如果不是，寻找新的基本可行解；再次进行检验，直到找出最优解为止。对于两个变量的线性规划问题，可用图解法；对于两个以上变量问题，采用单纯形法求解。图解法、单纯形法例。线性规划问题基本理论及方法图解法求解步骤：建立x1Ox2平面直角坐标系。将所有约束条件的临界值（直线）标于坐标系中，得出可行域（所有可行解的集合）。给目标函数赋一值，在坐标系中划出相应直线，在可行域中移动，找出其极值方向的交点，即为该问题的最优解。线性规划问题基本理论及方法解的性质:线性规划问题的可行域都是凸多边形（可能无界）；可行域的顶点为基本可行解，若存在最优解，一定在顶点上达到；如果同时在两个顶点达到最优解，该直线上任意一点均为最优解，此时为无穷多最优解。求解原理：从可行域中的某一顶点开始，逐一进行比较，使目标函数最优的顶点即为最优解。线性规划问题基本理论及方法线性规划的基本原理（以例图解法说明）：解的类型：一定无解解的结果有可行域无可行域可行域有界可行域无界唯一解无穷解唯一解无穷解无解线性规划问题基本理论及方法单纯形法求解步骤：将线性规划模型转化为标准型（目标函数求极大、约束条件为等式、决策变量大于0）；找出初始基本可行解（即：m个约束条件中存在m个单位列向量，组成单位矩阵）；检验初始基本可行解是否为最优解？（若所有非基变量的检验数σj≤0，则基本可行解为最优解）；如果不是最优解，进行迭代，求出新的基本可行解。（根据最小比值原则选择出基变量和进基变量）单纯形法计算过程在单纯形表中具体实现。应用EXCEL工具求解线性规划问题一、在EXCEL电子表格中建立线性规划模型1、把相关数据输入到EXCEL电子表格中应用EXCEL工具求解线性规划问题2、主要求解结果■两种新产品x1、x2每周的产量；■两种新产品每周各实际使用的工时（不能超过计划工时）；■两种新产品的总利润z。应用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应用EXCEL工具求解线性规划问题（3）总利润计算：在G12单元格输入公式：=C4*C12+D4*D12或：=SUMPRODUCT（C4：D4，C12：D12）应用EXCEL工具求解线性规划问题收集问题数据；在EXCEL表格中输入数据（数据单元格）；确定决策变量单元格（可变单元格）；输入约束条件左边的公式（输出单元格）,使用SUMPRODUCT函数简化输入；输入目标函数公式（目标单元格）。使用SUMPRODUCT函数简化输入。在EXCEL中建立线性规划模型步骤总结应用EXCEL工具求解线性规划问题二、在EXCEL电子表格中求解线性规划模型1、求解参数设置：“工具”——”规划求解“，弹出“规划求解参数”对话框，设置求解相关参数。应用EXCEL工具求解线性规划问题2、约束的设置：单击“添加”，弹出“添加约束”，添加约束条件。应用EXCEL工具求解线性规划问题3、求解选项设置：单击“选项”，弹出“规划求解选项”对话框。选择“采用线性模型”和“假定非负”。应用EXCEL工具求解线性规划问题4、求解及结果单击“求解”，开始规划求解。弹出“规划求解结果”对话框。选择“保存规划求解结果”。应用EXCEL工具求解线性规划问题5、电子表格显示结果：单击“确定”，在电子表格的可变单元格、输出单元格及目标单元格出现求解结果。输入数据标识数据每个数据对应唯一单元格在电子表格中显示完整模型数据、公式分离保持简单化使用相对和绝对地址简化公式并复制使用边框、底色区分单元格类型例1-3建模求解要点回顾应用EXCEL工具求解线性规划问题四、线性规划问题解的表现EXCEL建模求解，其解的结果在“规划求解结果”对话框中提示：1、唯一最优解为”找到一个解“2、无穷多最优解为”满足条件有多个解“3、无解为”未找到可行解“线性规划问题建模求解实例分析一、生产计划问题例1：某工厂生产甲、乙、丙三种产品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可自行生产，但产品丙必须在本厂铸造才能保证质量。数据见表。问：公司为了获得最大利润，甲、乙、丙三种产品应各生产多少件？甲、乙两种产品的铸件应由本公司铸造和由外包协作各多少件?线性规划问题建模求解实例分析产品甲产品乙产品丙工时限制单件铸造工时（小时）51078000单件机加工工时（小时）64812000单件装配工时（小时）32210000自产铸件成本（元/件）354外协铸件成本（元/件）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每吨能赢利300元；当剩余的产品C报废时，每吨损失费为200元。经市场预测，在计划期内产品C的最大销售量为5吨。问：如何安排A、B两种产品的产量可使工厂总盈利最大？线性规划问题建模求解实例分析二、生产存储问题某公司根据订单生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用见表。已知公司每月的生产能力为100，每月仓库容量为50.问：如何确定产品未来半年内每月最佳生产量和存储量，才能使总费用最少？月份123456需求量504050455530单位生产费用825775850850775825单位存储费用403035204040线性规划问题建模求解实例分析三、项目投资问题1、某公司有100万元的资金可供投资,该公司有六个可选的投资项目,其各种数据见下表.该公司的目标:投资风险最小,每年红利至少6.5万元,最低平均增长率为12%,最低平均信用度为7.投资项目风险(%)红利(%)增长率(%)信用度11842242657103109122447810512615468886线性规划问题建模求解实例分析假设：xi为每种投资项目投资额。建立线性规划模型如下：MinZ=0.18x1+0.06x2+0.10x3+0.04x4+0.12x5+0.08x6x1+x2+x3+x4+x5+x6=1000.04x1+0.05x2+0.09x3+0.07x4+