第五章运筹学 线性规划在管理中的应用案例(18页).doc

-第五章 运筹学 线性规划在管理中的应用案例-第 18 页第五章 线性规划在管理中的应用5.1 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品、的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表：机器设备类型每周可用机器台时数铣床500车床350磨床150每生产一件各种新产品需要的机器台时数如下表：机器设备类型新产品新产品新产品铣床846车床430磨床301三种新产品的单位利润分别为0.5元、0.2元、0.25元。目标是要确定每种新产品的产量，使得公司的利润最大化。1、判别问题的线性规划数学模型类型。2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。3、建立该问题的线性规划数学模型。4、用线性规划求解模型进行求解。5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。6、若销售部门表示，新产品、生产多少就能销售多少，而产品最少销售18件，请重新完成本题的1-5。解：1、本问题是资源分配型的线性规划数学模型。2、该问题的决策目标是公司总的利润最大化，总利润为： 0.5x1+ 0.2x2+ 0.25x3 决策的限制条件： 8x1+ 4x2+ 6x3500 铣床限制条件4x1+ 3x2 350 车床限制条件3x1 + x3150 磨床限制条件 即总绩效测试（目标函数）为： max z= 0.5x1+ 0.2x2+ 0.25x33、本问题的线性规划数学模型 max z= 0.5x1+ 0.2x2+ 0.25x3 ST 8x1+ 4x2+ 6x3500 4x1+ 3x2 350 3x1 + x3150 x10、x20、x304、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。5、灵敏度分析目标函数最优值为 : 30 变量 最优解 相差值 x1 50 0 x2 25 0 x3 0 .083 约束 松弛/剩余变量 对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围 : 变量 下限 当前值 上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束 下限 当前值 上限 1 400 500 600 2 275 350 无上限 3 37.5 150 187.5（1） 最优生产方案： 新产品生产50件、新产品生产25件、新产品不安排。最大利润值为30元。（2）x3 的相差值是0.083意味着，目前新产品不安排生产，是因为新产品的利润太低，若要使新产品值得生产，需要将当前新产品利润0.25元/件，提高到0.333元/件。（3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格0.05，0，0.033表明三种机床每增加一个工时可使公司增加的总利润额。（4）目标函数系数范围 表明新产品的利润在0.4元/件以上，新产品的利润在0.1到0.25之间，新产品的利润在0.333以下，上述的最佳方案不变。（5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在37.5到187.5工时之间。各自每增加一个工时对总利润的贡献0.05元，0元，0.033元不变。6、若产品最少销售18件，修改后的的数学模型是：max z= 0.5x1+ 0.2x2+ 0.25x3 ST 8x1+ 4x2+ 6x3500 4x1+ 3x2 350 3x1 + x3150x318 x10、x20、x30这是一个混合型的线性规划问题。代入求解模板得结果如下：最优解（44，10，18），最优值：28.5元。灵敏度报告：目标函数最优值为 : 28.5 变量 最优解 相差值 x1 44 0 x2 10 0 x3 18 0 约束 松弛/剩余变量 对偶价格 1 0 .05 2 144 0 3 0 .033 4 0 -.083 目标函数系数范围 : 变量 下限 当前值 上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束 下限 当前值 上限 1 460 500 692 2 206 350 无上限 3 18 150 165 4 0 18 30（1） 最优生产方案：新产品生产44件、新产品生产10件、新产品生产18件。最大利润值为28.5元。（2）因为最优解的三个变量都不为0，所以三个相关值都为0。（3）四个约束的松弛/剩余变量0，144，0，0，表明铣床和磨床的可用工时已经用完，新产品的产量也刚好达到最低限制18件，而车床的可用工时还剩余144个工时；四个对偶价格0.05，0，0.033，-0.083表明三种机床每增加一个工时可使公司增加的总利润额，第四个对偶价格-0.083表明新产品的产量最低限再多规定一件，总的利润将减少0.083元。（4）目标函数系数范围表明新产品的利润在0.4元/件以上，新产品的利润在0.1到0.25之间，新产品的利润在0.333以下，上述的最佳方案不变。（5）常数项范围表明铣床的可用条件在460到692工时之间、车铣床的可用条件在206工时以上、磨铣床的可用条件在18到165工时之间、新产品产量限制在30件以内。各自每增加一个工时对总利润的贡献0.05元，0元，0.033元，-.083元不变。5.2 某铜厂轧制的薄铜板每卷宽度为100cm，现在要在宽度上进行切割以完成以下订货任务：32cm的75卷，28cm的50卷，22cm的110卷，其长度都是一样的。问应如何切割可使所用的原铜板为最少？解：本问题是一个套材下料问题，用穷举法找到所有可能切割的方式并建立数学模型：min f=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10 S.T. 3x1+2x2+2x3+x4+x5+x675 x2+2x4+x6+3x7+2x8+x950 x3+3x5+x6+2x8+3x9+4x10 110 xi0 （i=1，2.10） 用Excel线性规划求解模型板求解： 最优解：（18.33 ,0,0,0,20,0,0.25,0,0,0），最优值：63.3333 因为铜板切割时必须整卷切割所以需要做整数近似。即其结果为： 即最优解：（19 ,0,0,0,20,0,0.25,0,0,0），最优值：64灵敏度分析报告：目标函数最优值为 : 63.333 变量 最优解 相差值 x1 18.333 0 x2 0 .056 x3 0 .111 x4 0 .111 x5 20 0 x6 0 .167 x7 0 .167 x8 25 0 x9 0 .056 x10 0 .111 约束 松弛/剩余变量 对偶价格 1 0 -.333 2 0 -.278 3 0 -.222 目标函数系数范围 : 变量 下限 当前值 上限 x1 .75 1 1.071 x2 .944 1 无上限 x3 .889 1 无上限 x4 .889 1 无上限 x5 .833 1 1.083 x6 .833 1 无上限 x7 .833 1 无上限 x8 .444 1 1.111 x9 .944 1 无上限 x10 .889 1 无上限 常数项数范围 : 约束 下限 当前值 上限 1 20 75 无上限 2 0 50 110 3 50 110 275这是一个统计型的线性规划问题，所以分析价值系数的取值范围和相差都没有意义。松弛/剩余变量都为0，表示最优方案已达到三种规格薄铜板数量的最低限。三个约束条件的对偶价格-.333、-.278、-.222分别表示三种规格薄铜板数量的最低限再增加一个，将增加原铜板.333cm、.278cm、.222cm。这个数字实际跟薄铜板长度规格相一致。常数项数范围表示三种规格薄铜板数量的最低限在这些范围内，每增一个限额所原原铜板.333cm、.278cm、.222cm不变。这里需要特别指出的是，第一种规格的薄铜板32cm宽，已使三块组合就能比较恰当地用完原铜板，所以这种规格的薄铜板无论增加多少，都不改变用原铜板的比例。5.3 某医院对医生工作的安排为4小时一个工作班次，每人要连续工作二个班次。各班次需要医生人数如下表：班次时间人数10:00-4:00424:00-8:00738:00-12:009412:00-16:0012516:00-20:008620:00-24:006其中，第6班报到的医生要连续上班到第二天的第1班。问在各班开始时应该分别有几位医生报到。若参加1、2、6班的医生需要支付夜班津贴，为了使支付总的夜班津贴为最少，应如何安排各班开始时医生的报到人数。解：第一步：不考虑夜班津贴。线性规划数学模型为： min f=x1+x2+x3+x4+x5+x6 S.T. x6+x14 x1+x27 x2+x39 x3+x412 x4+x58 x5+x66 xi0（i=1，2，3，4，5，6）用Excel线性规划求解模板求解得：第一班安排7人，第三班安排10人，第四班安排2人，第五班安排6人，第二、第六班不安排人。总人数为25人。灵敏度分析报告：目标函数最优值为 : 25 变量 最优解 相差值 x1 7 0 x2 0 0 x3 10 0 x4 2 0 x5 6 0 x6 0 0 约束 松弛/剩余变量 对偶价格 1 3 .0 2 0 -1 3 1 .0 4 0 -1 5 0 . 0 6 0 -1 目标函数系数范围 : 变量 下限 当前值 上限 x1 0 .1 1 x2 1 1 无上限. x3 0 . 1 1x4 1 . 1 2 x5 0 1 1 x6 1 1 无上限 常数项数范围 : 约束 下限 当前值 上限 1 无下限 4 7 2 4 7 无上限 3 无下限 9 10 4 11 12 无上限5 6 8 9 6 5 6 8这是一统计型线性规划规划问题，所以相差值的价值系数的变化范围没有必要分析。班次时间所需人数本段安排人数上段安排人数本段实际人数多余人数10:00-4:004707324:00-8:007077038:00-12:009100101412:00-16:0012210120516:00-20:0086280620:00-24:0060660合计4625504松弛/剩余变量一栏就是上表的“多余人数”一列是各时间段安排所剩余的人数。“对偶价格”一栏。第一个常数项由4增加到5，因为还剩下2人，所以不会改变最优值；第二个常数项由7增加到8，因为再没有剩余的人，所以本班必须再多安排一个人最优值解也必须增加1，因为是求最小化问题，所以对偶价格为1；第三个常数项由9增加到10，刚好将原来剩余的人用上，所以不会改变最优值；第四个、第六个常数项与第二个常数项一样；第五个常数项由2增加到3，因为再没有剩余的人，所以本班必须再多安排一个人，但下个班就可以再少安排一个人，所以不会改变最优值；本题的这种情况是每一个变量都会影响到两个时段的结果，所以在进行灵敏度分析时也必定要考虑这个因素，这里第一个时段是特殊情况（有资源剩余），其余的时段分析时相邻两个是相互影响的。因此，第2时段为-1，第3时段为0，后面的依次相反。若第2时段为0，则第3时段就为-1。第二步：考虑夜班津贴。线性规划数学模型为：min f=x1+x2+x3+x5+x6 S.T. x6+x14 x1+x27 x2+x39 x3+x412 x4+x58 x5+x66 xi0（i=1，2，3，4，5，6）用Excel线性规划求解模板求解得：即：总人数还是25人，但每班安排人数有所调整：第一班不安排人，第二班安排7人，第三班安排2人，第四班安排10人，第五班安排0人，第六班安排6人。灵敏度分析报告：目标函数最优值为 : 15 变量 最优解 相差值 x1 0 1 x2 7 0 x3 2 0 x4 10 0 x5 0 0 x6 6 0 约束 松弛/剩余变量 对偶价格 1 2 0 2 0 0 3 0 -1 4 0 0 5 2 0 6 0 -1 目标函数系数范围 : 变量 下限 当前值 上限 x1 0 1 无上限 x2 1 1 2 x3 0 1 1 x4 0 0 1 x5 1 1 无上限 x6 0 1 1 常数项数范围 : 约束 下限 当前值 上限 1 无下限 4 6 2 5 7 9 3 7 9 11 4 10 12 无上限 5 无下限 8 10 6 4 6 无上限 这是一统计型线性规划规划问题，所以相差值的价值系数的变化范围没有必要分析。班次时间所需人数本段安排人数上段安排人数本段实际人数多余人数10:00-4:004066224:00-8:007707038:00-12:0092790412:00-16:0012102120516:00-20:008010102620:00-24:0066060合计4625504“对偶价格”一栏。第一个常数项由4增加到5，因为还剩下2人，所以不会改变最优值；第二个常数项由7增加到8，由于上段时间已增一个人，这个人本班还上班，所以本也不需要增加人。第三个常数项由9增加到10，前面安排的人都已下班，本班刚好只朋9人，若需求再增加一人，就需要新安排一人所以对偶价格-1；第四个、第五个、第六个常数项与前三个常数项一样；5.4 某塑料厂要用四种化学配料生产一种塑料产品，这四种配料分别由A、B、C三种化学原料配制，三种化学原料的配方及原料价格如下表：配料1234价格（元/公斤）含原料A（%）3040201511含原料B（%）2030604013含原料C（%）4025153012要配制的塑料产品中，要求含有20%的原料A，不少于30%的材料B和不少于20%的原料C。由于技术原因，配料1的用量不能超过30%，配料2的用量不能少于40%。第一次配制的塑料产品不能少于5公斤。请设计一套配料方案，使总的成本为最低。解：线性规划数学模型：min f =10.7x1+11.3x2+11.8x3+9.45x4S.T. 0.1x1+0.2x2 -0.05x4=0 -0.1x1 +0.3x3+0.1x40 0.2x1+0.05x2-0.05x3+0.1x40 0.7x1-0.3x2-0.3x3-0.3x40 -0.4x1+0.6x2-0.4x3-0.4x40 x1+x2+x3+x45 xi0（i=1，2，3，4，）将模型代入到线性规划求解模板，得结果：用配料1，1.5公斤；用配料2，0.1公斤；用配料3，0公斤；用配料4，3.4公斤； 花费总的最低成本49.31元。灵敏度分析报告：目标函数最优值为 : 49.31 变量 最优解 相差值 x1 1.5 0 x2 .1 0 x3 0 1.98 x4 3.4 0 约束 松弛/剩余变量 对偶价格 1 0 -7.4 2 .19 0 3 .645 0 4 0 -.14 5 1.9 0 6 0 -9.862 目标函数系数范围 : 变量 下限 当前值 上限 x1 10.56 10.7 无上限 x2 -481.8 11.3 11.533 x3 9.82 11.8 无上限 x4 -5.053 9.45 9.8 常数项数范围 : 约束 下限 当前值 上限 1 -.025 0 .475 2 无下限 0 .19 3 无下限 0 .645 4 -1.5 0 .167 5 -1.9 0 无上限 6 0 5 无上限本问题的相差值栏，x3的相差值为1.98，表示目前配料3的成本11.8太高，无法选用，若该配料的成本再降低1.98元就可以选取用。松弛/剩余变量栏：前五个给条件都表示的是配料或原料的配比关系。松弛/剩余变量为0 关系表示已完全按要求配比，不为0 的表示没有达到配比要求。第五个约束是总产品的产量最低限，松弛/剩余变量为0 表示已达到产量要求。关五个约束的对偶价格表示配料或者说原料不匹配时，对总费用的影响。不为0的对偶价格表示配比每差一个单位都会使总费用的增加量。第五个对偶价格是每增加一公斤的产品，需要增加的费用值。在学数项取值范围栏：前五个约束在常数项在这个范围内，保持上述的对偶价格，而此时的上限都不高，说明这个最优方案中的匹配关系失衡并不严重，若比例失衡将会导致费用的增加比例更大。对五个对偶价