线规划建模与求解.ppt

线性规划 建模与求解,目录,线性规划问题对偶规划问题运输问题指派问题线性规划应用之一：DEA分析线性规划应用值二：零和对策混合策略附录,一、线性规划问题,问题提出 某食品公司雇佣了一家广告公司来帮助设计 全国性的促销活动，计划最多支付广告公司 服务酬金100万元，广告费用400万元。根 据该食品公司产品状况，广告公司确定了最 有效的三种广告媒体。媒体1：星期六上午儿童节目的电视广告媒体2：食品与家庭导向的杂志广告媒体3：主要报纸星期天增刊上的广告,现在要解决的问题是如何确定各种广告活动的水平（levels）以取得最有效的广告组合（advertising mix）。相关数据如下：,问题分析与建模 本问题是一个典型的线性规划问题。食品公司的最终目标是利润最大化，在本题中用单位贡献表示单位利润。有目标函数为：Max z=130TV+60M+50SS 其中，TV、M、SS分别表示电视上的广告时段数、杂志上的广告数目和星期天增刊上的广告数目。,约束条件有三个：（1）广告总费用400万；（2）计划总成本100万；（3）总的电视广告时段数目5。表示为：300TV+150M+100SS 4000 90 TV+30 M+40 SS1000 TV 5,数学模型为：Max z=130TV+60M+50SS s.t.300TV+150M+100SS 4000 90 TV+30 M+40 SS1000 TV 5,任务：（1）EXCEL求解；（2）录制一个规划求解的宏；（3）制作一个用于规划求解的命令按钮；（4）加入一个用于规划求解的新菜单。,二、对偶规划问题,问题提出 某玻璃制品公司生产高质量的玻璃制 品，包括具有手艺和最精细工艺特性 的床和玻璃门。公司有三个工厂共同 生产窗和玻璃门，其中 工厂1：生产铝框和硬制件 工厂2：生产木框 工厂3：生产玻璃和组装窗和门,已知相关数据如下：,任务：（1）列出问题数学模型，求取总利润最大时的两种产品产量，并练习制作命令按钮；（2）当门和窗的单位利润分别在什么范围内变动时，公司的最优生产计划不变？（3）如果改变一个工厂可用于生产新产品的生产时间，结果将如何？（4）学会看灵敏度分析报告。,数学模型为：,Max z=300D+500W 2W 12s.t.3D+2W 18其中，D、W分别表示生产的门和窗的个数。,运算结果报告解释,列出目标单元格和可变单元格以及它们的初始值、最终结果、约束条件和有关约束条件的信息。其中，目标单元格和可变单元格是用其行和列命名的，约束单元格是用其列命名的。初值和终值分别指单元格在本次求解前的数值和求解后的数值。,敏感性报告解释,提供关于求解结果对“目标单元格”编辑框中所指定的公式的微小变化，以及约束条件的微小变化的敏感性信息。含有整数约束条件的模型不能生成本报告。对于非线性模型，此报告提供缩减梯度和拉格朗日乘数；对于线性模型，此报告中将包含递减成本、影子价格（机会成本）、目标系数(允许有小量增减额)以及右侧约束区域。,1）可变单元格一栏：当门和窗的单位利润分别在(300-300，300+450)和(500-300，+)之间变动时，最优解保持不变。注意：最优解不变，但最优目标函数值可能发生变化；分别变动而不是同时变动，即固定其中一个，另一个可在适当范围内变动。,2）约束单元格一栏：阴影价格即运筹学中的影子价格，它是指资源每增加一个单位时目标函数的增量，即：工厂1每周可用时间在4-2，+之间发生变化时，影子价格恒为0，对目标函数值无影响；工厂2每周可用时间在12-6，12+6之间发生变化时，影子价格恒为150，即每增加一个单位可用时间，目标函数值就增加150，工厂3每周可用时间在18-6，18+6之间发生变化时，影子价格恒为100，即每增加一个单位可用时间，目标函数值就增加100。注意：此处也是分别变动，而不是同时变动。,极限值报告解释,列出目标单元格和可变单元格以及它们的数值、上下限和目标值。含有整数约束条件的模型不能生成本报告。其中，下限是在满足约束条件和保持其它可变单元格数值不变的情况下，某个可变单元格可以取到的最小值。上限是在这种情况下可以取到的最大值。,延伸,下面对目标式系数同时变动以及约束限制值同时变动的情况分别作以延伸。（1）目标式系数同时变动的百分之百法则（The 100 percent rule of simultaneous changes in objective function coefficients）：如果目标函数系数同时变动，计算出每一系 数变动量占该系数同方向可容许变动范围的 百分比，而后将各个系数的变动百分比相加，如果所得的和不超过百分之一百，最优解 不会改变；如果超过百分之一百，则不能确 定最优解是否改变。,（2）约束限制值同时变动的百分之百法则（The 100 percent rule of simultaneous changes in right-hand sides）：同时改变几个或所有函数约束的约束右端值，如果这些变动的幅度不大，那么可以用影 子价格预测变动产生的影响。为了判别这些 变动的幅度是否允许，计算每一变动占同方 向可容许变动范围的百分比，如果所有的百 分比之和不超过百分之一百，那么影子价格 还是有效的；如果所有的百分比之和超过百 分之一百，那就无法确定影子价格是否有效。,三、运输问题,（一）供需平衡 某食品公司有三个罐头加工厂A1、A2、A3，四个仓库B1、B2、B3、B4。已知相关数据如下：,任务：求总的运输费用最小的运输策略。建模求解。,数学模型为：,x11+x12+x13+x14=75 x21+x22+x23+x24=125 x31+x32+x33+x34=100 x11+x21+x31=80 x12+x22+x32=65 x13+x23+x33=70 x14+x24+x34=85xij0 i=1，2，3；j=1，2，3，4,Min z=464x11+513x12+654x13+867x14+352x21+416x22+690 x23+791x24+995x31+416x32+690 x33+791x34,（二）供大于需 某水管站主管着广阔地域的水资源分配机构。由于该地域十分干燥，需要从外地引水。已知引入的水来自R1、R2、R3三条河流，主要供应客户为D1、D2、D3、D4四个城市的供水部门。除了R3的水不能供应D4之外，所有的河流均可供应这四个城市。运输表格如下：,x11+x12+x13+x14 5 x21+x22+x23+x24 6 x31+x32+x33+x34 1.5 x11+x21+x31=2 x12+x22+x32=5 x13+x23+x33=4 x14+x24+x34=1.5xij0 i=1，2，3；j=1，2，3，4,数学模型为：,Min z=160 x11+130 x12+220 x13+170 x14+140 x21+130 x22+190 x23+150 x24+190 x31+200 x32+230 x33+Mx34,无穷大,（三）转运或转载问题,数学模型格式,4,1,四、指派问题,某公司营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好的安排这次会议，他雇佣了四个临时人员张三、李四、王五、宋六，每一个人负责完成下面的一项任务：1.书面陈述的文字处理；2.制作口头和书面陈述的电脑图；3.会议材料准备，包括书面材料的抄写和组织；4.处理与会者的提前和当场注册报名。,现在他需要确定将哪一项任务指派给哪一个人。相关数据如下：,五、线性规划应用之一 DEA分析,数据包络分析是一种基于线性规划，用于评价同类型组织绩效相对有效性的工具手段。这类组织例如学校、医院、银行分支机构、超市的各营业部等。注意：各组织具有相同的投入、产出项目，对应单位也应相同。有某个银行的4个分理处数据如下：,试对四个分理处进行DEA有效性分析，包括规模有效分析即C2R，和技术有效分析即C2GS2。,（一）规模有效性分析 数学模型（D）：,对DMU1：Min 15 1+20 2+21 3+20 4=1800 200 1+350 2+450 3+420 4=2001600 1+1000 2+1300 3+1500 4=1600 i=0，i=1，2，3，4；=0,=1，说明为弱DEA有效（C2R）；=1，且松弛变量或人工变量均为0，说明为DEA有效（C2R）；DEA有效性分析（C2R）反映的是规模有效。,练习：分理处2、3、4的规模有效性分析。借助运算结果报告。,（二）技术有效性分析 数学模型（D），以对DMU2为例。,Min 15 1+20 2+21 3+20 4=1000 200 1+350 2+450 3+420 4=3501600 1+1000 2+1300 3+1500 4=1000 1+2+3+4=1 i=0，i=1，2，3，4；=0,=1，说明为弱DEA有效（C2GS2）；=1，且松弛变量或人工变量均为0，说明为DEA有效（C2GS2）；DEA有效性分析（C2GS2）反映的是技术有效。,练习：分理处1、2、4的技术有效性分析。借助运算结果报告。,六、线性规划应用之二 零和对策混合策略均衡,两个人互相独立的各自从1、2、3三个数字中任意选写一个数字。如果二人所写数字之和为偶数，则局中人2付给局中人1以数量为此和数的报酬；如果二人所写数字之和为奇数，则局中人1付给局中人2以数量为此和数的报酬，求此对策的解。支付矩阵（赢得矩阵）为：,为方便求解，每项加5化为非负矩阵。,原数学模型为：,Min v,Max w,Min w=x1+x2+x37x1+2x2+9x3=12x1+9x2=19x1+11x3=1x1,x2,x3=0,Max v=y1+y2+y37y1+2y2+9y3=0,对偶规划模型：,X*=1/w*X,Y*=1/v*Y,七、网络优化,某工程项目的网络计划如图所示，工程,事项的最早开始时间：,事项的最迟开始时间：,工作的最早可能开始时间和最早可能完工时间：,工作的最迟必须开工时间和工作的最迟必须完工时间：,目标式系数同时变动的百分之百法则证明,目标式系数同时变动的百分之百法则证明,目标式系数同时变动的百分之百法则证明,目标式系数同时变动的百分之百法则证明,约束限制值同时变动的百分之百法则证明,约束限制值同时变动的百分之百法则证明,约束限制值同时变动的百分之百法则证明,约束限制值同时变动的百分之百法则证明,