管理运筹学讲义 第2 章 线性规划讨论

OR:SM1第2章线性规划讨论Subtitle学习要点线性规划的目标函数和约束条件的表达技巧明确线性规划在生产计划制定中的应用层次了解企业管理中典型线性规划问题的数学模型理解灵敏度分析的基本原理和经济意义能够对价值系数和资源数量进行灵敏度分析OR:SM2计件工资体系，目标是企业利润最大化：第一节目标函数的描述技巧一、计件工资123max668970Zxxx产品甲：产品乙：产品丙：非负性约束140x280x340x123,,0xxx计件工资制薪酬体系下，工作时间不会完全受每天8小时工作时间约束，但有产品市场需求约束，如下：经Lindo软件求解，得到最优解为Z=12560，产品甲x1=40，产品乙x2=80，产品丙x3=40。OR:SM3第一节目标函数的描述技巧二、岗位工资岗位工资制薪酬体系，以计时工资制为基础，实行定岗定员。总收入=173x1+233x2+170x3，原料成本=65x1+95x2+65x3，营运费用=11000，则目标函数为maxZ=108x1+138x2+105x3-11000岗位工资制薪酬体系下，工作时间也不会完全受每天8小时工作时间约束，但有产品市场需求约束，如下：产品甲：产品乙：产品丙：非负性约束140x280x340x123,,0xxx经Lindo软件求解，得到最优解为Z=8560,x1=40,x2=80,x3=40。OR:SM4第一节目标函数的描述技巧三、计时工资目标函数为123max10813810511000Zxxx经Lindo软件求解，得到最优解为Z=5800,x1=40,x2=60,x3=40。123030152400xxx123102002400xxx1233121214800xxx1233113244800xxx设备E：设备F：设备G：设备H：140x280x340x产品甲：产品乙：产品丙：市场需求约束设备能力约束OR:SM5第二节线性规划的适用层次计划链的层次粗能力计划定单可行不可行CRP主生产计划MPS物料需求计划MRP能力需求计划车间作业计划销售计划可行否作业统计与控制物料清单库存管理外购计划供应商成品、在制品信息生产计划大纲预测当前条件经营计划•产值计划或利润计划•绝对数量或增长幅度•期限:年度单位:万元•大类产品销售收入或台套•产品品种和数量如何确定•期限:年度单位:万台•具体产品在具体时段的出产计划•合同订单和预测转换为生产任务•将产品出产计划转换成物料需求表•大类产品年度生产计划•确定产品的品种和数量•期限:年度单位:万台OR:SM6第三节线性规划的典型案例一、配送中心选择例：某企业存在两个供货源（产地）S1和S2，已知原有供货源S1每月的供货能力是5万台产品，新增供货源S2的生产能力可以满足产品的需求，且两个货源的价格相同。有三个区域目标市场（销地或销售商）R1,R2,R3，各销地每月的市场需求量为5万台、10万台、5万台。在分销渠道中，拟定在2个地点中选址设立分销中心W1,W2，执行产品的转运任务。各地之间的单位运输物流成本（由距离和运输方式决定）OR:SM7第三节线性规划的典型案例一、配送中心选择决策变量：设从供货源Si到分销中心Wj的运输量为，从分销中心Wj到需求市场Rk的运输量为。选址规划在于二者的实际取值。如果，则不设置分销中心W1；反之，则设置W1,其规模为如果，则不设置分销中心W2；反之，则设置W2，其规模为目标函数：各条路段上的实际运输量乘以物流运输的单位费用之总和最小，即存在供应能力约束、市场需求约束、配送中转约束，如下：11122122111213212223min2542345223Zxxxxyyyyyyijxjky11210xx1121xx12220xx1222xxOR:SM8第三节线性规划的典型案例一、配送中心选择供应能力平衡约束：市场需求平衡约束配送中心不存留产品所有变量大于等于零1112212250000150000xxxx1121122213235000010000050000yyyyyy11211112131222212223xxyyyxxyyy11122122111213212223,,,,,,,,,0xxxxyyyyyyOR:SM9第三节线性规划的典型案例二、污水处理问题例：有两个化工厂向同一河流中排放污水，如图所示。流经第一化工厂的河水流量为500万立方米/天，在两个工厂之间有一条支流进入，流量为200万立方米/天。第一化工厂排放污水2万立方米/天。第二化工厂排污1.4万立方米/天。一厂排出的污水流到二厂以前，有20％可以自然净化，根据环保要求，河水中污水含量不应大于2‰。这两个工厂需要各自处理一部分污水。一厂的污水处理成本是1000元/万立方米，二厂的污水处理成本是800元/万立方米，问各厂应各自处理多少污水，使两厂的污水处理费用总额为最低。OR:SM10第三节线性规划的典型案例二、污水处理问题设决策变量为一厂污水处理量，为二厂污水处理量。从一厂到二厂之间的河水中污水含量不得高于2‰‰二厂下游河水中污水含量也要低于2‰‰各厂污水处理量应小于其排放量1x2x122500x2200500)4.1()2(8.021xx21x21.4x0,4.126.18.01s.t.8001000min212121121xxxxxxxxxZOR:SM11第三节线性规划的典型案例三、合理下料问题例：某建筑公司要用铝型材作为构架，制作100个铝合金窗子，每个窗子需要2.8米的材料3根，1.8米的2根，1.17米的4根，0.6米的4根，原材料每根6米，怎样下料，才能使余料最少?123456789102.810000010101.811203001101.1712200223030.603010161124合计5.775.945.946.006.005.945.745.915.805.91余料0.230.060.06000.060.260.090.200.09下料的可能方案决策x1x2x3x4x5x6x7x8x9x10OR:SM12第三节线性规划的典型案例三、合理下料问题0,,,,,,40042610340033222220032300..6.017.18.18.209.02.009.026.006.00006.006.023.0min43211021410987654231087632129853211971432110987654321ssssxxxsxxxxxxxxsxxxxxxxsxxxxxxsxxxtssxssxxxxxxxxxxZ•这个问题的数学模型为：设长度为2.8米的材料多余根数为s1，1.8米多余s2，1.17米多余s3，0.6米多余s4。OR:SM13第三节线性规划的典型案例四、营养配餐问题例：假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择(当然可以扩充到n种食品)，它们每千克所含的热量和营养成分和市场价格见表2-3。问如何选择才能在满足营养的前提下使购买食品的费用最小？OR:SM14第三节线性规划的典型案例四、营养配餐问题建模：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：12341234123312341234min1463210008009002003005060201055s.t.400200300500800,,,0ZxxxxxxxxxxxxxxxxxxxxOR:SM15第四节线性规划灵敏度分析一、灵敏度分析的必要性线性规划研究的是一定条件下的最优化问题•资源环境和技术条件是可变的•基础数据往往是测算估计的数值•灵敏度分析的概念灵敏度分析又称敏感性分析或优化后分析•研究基础数据发生波动后对最优解的影响•最优解对数据变化的敏感程度•在多大的范围内波动才不影响最优基灵敏度分析解决的问题：•参数在什么范围变化而最优基不变•已知参数的变化范围，考察最优解(最优基)是否改变OR:SM16第四节线性规划灵敏度分析一、价值系数的变动分析非基变量Cj的变化范围•非基变量Cj变化，只影响它自己的检验数Cj35000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/203x14100-2/31/3检验数j000-1/2-1*jjC•参数Cj的变化范围：价值系数Cj变化影响检验数0'1jBjjjPBCCC*1jjjBjCPBCCOR:SM17第四节线性规划灵敏度分析一、价值系数的变动分析基变量CBl的变化范围CjC15000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/20C1x14100-2/31/3检验数j0002C1/3-5/2-C1/3415001cjOR:SM18第四节线性规划灵敏度分析二、右端常量的变动分析•参数bi的变化范围第r个约束的右端项为br，增量br，其它数据不变。新的基解为1'()BXBbbrmrrrrrbabababB**2*11**11**22**rrrmmrbababba1100rBbBb只要X'B≥0，则可保持最优基不变。***0iirrirbaba***0iirrirbaba}0|{min}0|{max******iririiriririiaabbaabOR:SM1912121212max35216210s.t.3432,0Zxxxxxxxx1234512312412512345max3500020160210..3432,,,,0ZxxxxxxxxxxxstxxxxxxxxCj35000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/203x14100-2/31/3检验数j000-1/2-1OR:SM20C2由5变为3，对最优解的影响Cj33000比值CBXBbx1x2x3x4x50x380014/3-2/33x250101/203x14100-2/31/3检验数j000？？454121=0(033())323221=0(0()303)133OR:SM21Cj33000比值CBXBbx1x2x3x4x50x380014/3-2/363x250101/20103x14100-2/31/3检验数j0001/2-1Cj33000比值CBXBbx1x2x3x4x50x4600¾1-1/23x2201-3/80¼3x1810½00检验数j00-3/80-3/4OR:SM22C1的变化范围Cjc15000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/20c1x14100-2/31/3检验数j0002/3c1-5/2-1/3c141512510,0323cc1115030.754ccOR:SM23b2的变化范围111'()BXBbbBbBb222242418333801150050224021204333bbbb266b