第五章运筹学 线性规划在管理中的应用案例

第五章线性规划在管理中的应用5.1某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管 理层考虑将这些剩余生产力用于新产品I、11、III的生产。可用的机器设备是限制新产品产 量的主要因素，具体数据如下表：机器设备类型每周可用机器台时数铣床500车床350磨床150每生产一件各种新产品需要的机器台时数如下表:机器设备类型新产品I新产品II新产品I铣床846车床430磨床301三种新产品的单位利润分别为0.5元、0.2元、0.25元。目标是要确定每种新产品的产 量，使得公司的利润最大化。1、判别问题的线性规划数学模型类型。2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。3、建立该问题的线性规划数学模型。4、用线性规划求解模型进行求解。5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰剩余量、对 偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。6、若销售部门表示，新产品I、II生产多少就能销售多少，而产品I最少销售18件， 请重新完成本题的1-5。解：1、本问题是资源分配型的线性规划数学模型。2、该问题的决策目标是公司总的利润最大化，总利润为：0.5气+ 0.2x2+ 0.25x3 决策的限制条件：8X+ 4x2+ 6x3 500铣床限制条件4x1+ 3x2350车床限制条件3x1+ x3150磨床限制条件即总绩效测试（目标函数）为：max z= 0.5x1+ 0.2x2+ 0.25x33、本问题的线性规划数学模型max z= 0.5x1+ 0.2x2+ 0.25x3S. T.8x1+ 4x2+ 6x35004x1+ 3x2 350 3x1 + x3150130、x230、x3304、用Excel线性规划求解模板求解结果：最优解（50，25, 0），最优值：30元。5、灵敏度分析目标函数最优值为:30变量最优解相差值X1500x2250x30.083约束松弛/剩余变量对偶价格10.05275030.033目标函数系数范围:变量下限当前值上限X1.4.5无上限x2.1.2.25x3无下限.25.333常数项数范围：约束下限当前值上限14005006002275350无上限337.5150187.5(1)最优生产方案：新产品I生产50件、新产品II生产25件、新产品m不安排。最大利润值为30J元o(2) x3的相差值是0.083意味着，目前新产品m不安排生产，是因为新产品m的利润 太低，若要使新产品m值得生产，需要将当前新产品m利润0.25元/件，提高到0.333元/件。(3) 三个约束的松弛/剩余变量0, 75, 0,表明铣床和磨床的可用工时已经用完，而 车床的可用工时还剩余75个工时；三个对偶价格0.05，0，0.033表明三种机床每增加一个工时可使公司增加的总利润 额。(4) 目标函数系数范围表明新产品I的利润在0.4元/件以上，新产品II的利润在0.1到0.25之间，新产 品m的利润在0.333以下，上述的最佳方案不变。(5) 常数项范围表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、 磨铣床的可用条件在37.5到187.5工时之间。各自每增加一个工时对总利润的贡献0.05元， 0元，0.033元不变。6、若产品m最少销售18件，修改后的的数学模型是：max z= 0.5气+ 0.2x2+ 0.25x3S. T.8X+ 4x2+ 6x35004X+ 3x2W3503x1+ x3W150x318130、x230、x30 这是一个混合型的线性规划问题。代入求解模板得结果如下：最优解(44，10，18)，最优值：28.5元。灵敏度报告：目标函数最优值为: 28.5变量最优解相差值X1440x2100x3180约束松弛/剩余变量对偶价格10.052144030.03340-.083目标函数系数范围：变量下限当前值上限X1.4.5无上限x2.1.2.25x3无下限.25.333常数项数范围：约束下限当前值上限14605006922206350无上限318150165401830(1) 最优生产方案：新产品I生产44件、新产品II生产10件、新产品III生产18件。最大利润值为28.5元。(2) 因为最优解的三个变量都不为0,所以三个相关值都为0。(3) 四个约束的松弛/剩余变量0, 144, 0, 0,表明铣床和磨床的可用工时已经用完， 新产品I的产量也刚好达到最低限制18件，而车床的可用工时还剩余144个工时；四个对偶价格0.05, 0, 0.033, -0.083表明三种机床每增加一个工时可使公司增加的总 利润额，第四个对偶价格-0.083表明新产品I的产量最低限再多规定一件，总的利润将减少 0.083 元。(4) 目标函数系数范围表明新产品I的利润在0.4元/件以上，新产品II的利润在0.1到0.25之间，新产品I 的利润在0.333以下，上述的最佳方案不变。(5) 常数项范围表明铣床的可用条件在460到692工时之间、车铣床的可用条件在206工时以上、磨 铣床的可用条件在18至到 165工时之间、新产品I产量限制在30件以内。各自每增加一个工 时对总利润的贡献0.05元，0元，0.033元，-.083元不变。5.2某铜厂轧制的薄铜板每卷宽度为100cm,现在要在宽度上进行切割以完成以下订货 任务：32cm的75卷，28cm的50卷，22cm的110卷，其长度都是一样的。问应如何切割 可使所用的原铜板为最少？解：本问题是一个套材下料问题，用穷举法找到所有可能切割的方式并建立数学模型:min f=x, +X +x+xA +xc+&+x=+x +x+x 12345678910S.T. 3x1+2x2+2x3+x4+x5+x675x2+2x4+x6+3x7+2x8+x9 350x3+3x5+x6+2x8+3x9+4x10 3110x30 (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变量最优解相差值X118.3330x20.056x30.111x40.111x5200x60.167x70.167x8250x90.056x100.111约束松弛/剩余变量对偶价格10-.33320-.27830-.222目标函数系数范围：变量下限当前值上限x1.7511.071x2.9441无上限x3.8891无上限x4.8891无上限x5.83311.083x6.8331无上限x7.8331无上限x8.44411.111x9.9441无上限x10.8891无上限常数项数范围:约束下限当前值上限12075无上限2050110350110275这是一个统计型的线性规划问题，所以分析价值系数的取值范围和相差都没有意义。松弛/剩余变量都为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 /=-x1+-x2+-x3+X4+x5+x6S.T.x6+X34%+%习x2+x39x3+x412x4+x58%+疽%30 (i=1, 2, 3, 4, 5, 6)用Excel线性规划求解模板求解得：第一班安排7人，第三班安排10人，第四班安排2人，第五班安排6人，第二、第六 班不安排人。总人数为25人。灵敏度分析报告：目标函数最优值为：25变量最优解相差值X170x200x3100x420x560x600约束松弛/剩余变量对偶价格13.020-131.040-150.060-1目标函数系数范围：变量下限当前值上限X10.11x211无上限.x30.11x41.12x5011x611无上限常数项数范围：约束下限当前值上限1无下限47247无上限3无下限91041112无上限56896568这是一统计型线性规划规划问题，所以相差值的价值系数的变化范围没有必要分析。班次时间所需人数本段安排人数上段安排人数本段实际人数多余人数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 仁x, +x +x +x+x,12356S.T.x6+X34x1+x27x2+x39x3+x412x4+x58%+疽xi0 （i=1，2，3，4，5，6）用Excel线性规划求解模板求解得：即：总人数还是25人，但每班安排人数有所调整：第一班不安排人，第二班安排7人，第三班安排2人，第四班安排10人，第五班安排 0人，第六班安排6人。灵敏度分析报告：目标函数最优值为：15变量最优解相差值X101x270x320x4100x500x660约束松弛/剩余变量对偶价格12020030-140052060-1目标函数系数范围：变量下限当前值上限X101无上限x2112x3011x4001x511无上限x6011常数项数范围：约束下限当前值上限1无下限4625793791141012无上限5无下限810646无上限这是一统计型线性规划规划问题，所以相差值的价值系数的变化范围没彳有必要分析。班次时间所需人数本段安排人数上段安排人数本段实际人数多余人数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公斤。请设计一套配料方案，使总的成本为最低。解：线性规划数学模型：minf =10.7x1+11.3%+11.8%+9.45劣4S.T.0.1%+0.2x2-0.05x4=0-0.1x1+0.3x3+0.1x400.2x+0.05x2-0.05x3+0.1x4300.7x-0.3x2-0.3x3-0.3x430-0.4X+0.6x2-0.4x3-0.4x4W0x1+x2+x3+x45xi0 (i=1, 2, 3, 4,)将模型代入到线性规划求解模板，得结果：用配料1, 1.5公斤；用配料2, 0.1公斤；用配料3, 0公斤；用配料4, 3.4公斤；花 费总的最低成本49.31元。灵敏度分析报告：变量下限当前值上限X110.5610.7无上限x2-481.811.311.533x39.8211.8无上限x4-5.0539.459.8常数项数范围：约束下限当前值上限1-.0250.4752无下限0.193无下限0.6454-1.50.1675-1.90无上限605无上限目标函数系数范围：目标函数最优值为：49.31变量最优解相差值X11.50x2.10x301.98x43.40约束松弛/剩余变量对偶价格10-7.42.1903.645040-.1451.9060-9.862本问题的相差值栏，x3的相差值为1.98,表示目前配料3的成本11.8太高，无法选用， 若该配料的成本再降低1.98元就可以选取用。松弛/剩余变量栏：前五个给条件都表示的是配料或原料的配比关系。松弛剩余变量为 0关系表示已完全按要求配比，不为0的表示没有达到配比要求。第五个约束是总产品的 产量最低限，松弛/剩余变量为0表示已达到产量要求。关五个约束的对偶价格表示配料或者说原料不匹配时，对总费用的影响。不为0的对偶 价格表示配比每差一个单位都会使总费用的增加量。第五个对偶价格是每增加一公斤的产 品，需要增加的费用值。在学数项取值范围栏：前五个约束在常数项在这个范围内，保持上述的对偶价格，而此 时的上限都不高，说明这个最优方案中的匹配关系失衡并不严重，若比例失衡将会导致费用 的增加比例更大。对五个对偶价格实际上说明了该产品的绝对成本，在这个方案下，生产多 少的产品都是这个成本构成。5.5某工厂生产I、II、m、W四种产品，产品I需经过A、B两种机器加工，产品II 需经过A、C两种机器加工，产品m需经过B、C两种机器加工，产品W需经过A、B两种 机器加工。有关数据见下表所示：产品机器生产率（件/小时）原料成本（元/件）产品价格（元/件）ABCI10201665II20102580m10151250W20101870机器成本（元/小时）200150225每周可用机时数15012070请为该厂制定一个最优生产计划。解：线性规划数学模型：max Z=21.5 %+225 %+8 %+27 气S.T. 2x1+x2+x4W3000x1+2x3+2x4W24003x +4x 0i=1,2,.,24将该模型代入到线性规划求解模板得结果：其解为：在满足对职工需求的条件下，10时安排8个临时工，其中3个3小时的，5个4小时的；11时新安排1个4小时的临时工；13时新安排1个3小时的临时工；16时新安排1个4小时的临时工；17 时新安排4个3小时的临时工；18 时新安排5个4小时的临时工；19时新安排1个3小时临时工。全天共安排21个临时工，可使临时工的总成本最小为300元。如下表所示:时间段所需临时工4小时班人数3小时班人数实际上班人数剩余人数10:00-11:008538011:00-12:009109012:00-13:009009013:00-14:007017014:00-15:002002015:00-16:001001016:00-17:001101017:00-18:005045018:00-19:00105010019:00-20:00110111020:00-21:006006021:00-22:0060060合计75129750这样能比第一种方案节省：332-300=32元。灵敏度分析报告:5.8某咨询公司受厂商的委托对新上市的产品进行消费反映调查。被调查对象分为上 班族和休闲族，而调查时间在周一至周五与双休日得到的结果大不相同。委托厂商与该公司 签订的业务合同规定：(1) 必须调查3000个消费对象；(2) 周一至周五与双休日被调查的总人数相等;(3) 至少要调查1200个上班族对象；(4) 至少要调查800个休闲族对象。调查每个对象所需费用如下表：调查对象周一至周五调查双休日调查上班族3540休闲族2528使得1、请建立该问题的线性规划数学模型，以确定在不同时间调查各种对象的人数， 总的调查费用为最少。2、求解该模型，并对结果进行灵敏度分析。解：1、线性规划数学模型：min 35x1+40x2+25x3+28x4S.T.X+x2+x3+x4 3 3000xx2+x3-x4=0x1+x231200X3+X43800气，x2，%，x430 代入线性规划求解模板得结果：其调查方案如下表:调查对象周一至周五调查双休日调查上班族12000休闲族3001500按此方案的调查费用为最少：91500元。2、灵敏度分析报告：即:目标函数最优值为:91500变量最优解相差值X112000x202x33000x415000约束松弛/剩余变量对偶价格10-26.5201.530-10410000目标函数系数范围：变量下限当前值上限X1253537x23840无上限x3232535x4-252830常数项数范围：约束下限当前值上限124003000无上限2-6000300030120015004无下限80018005.9西兰物业公司承担了正大食品在全市92个零售点的肉类、蛋品和蔬菜的运送业务。 运送业务要求每天4点钟开始从总部发货，送完货时间必须在7： 30前结束（不考虑空车返 回时间）。这92个零售点每天需要运送货物0.5吨，其分布情况为：5公里以内为A区，有 36个点，从总部到该区的时间为20分钟；10公里以内5公里以上的为B区，有26个点， 从总部到该区的时间为40分钟；10公里以上的为C区，有30个点，从总部到该区的时间 为60分钟；A区各点间运送时间5分钟；B区各点间运送时间10分钟；C区各点间运送时 间20分钟；各区之间运送时间20分钟。每点卸货、验收时间为30分钟。本公司准备购买 规格为2吨的运送车辆，每车购价5万元。请用线性规划方法确定每天的运送方案，使投入的购买车辆总费用为最少。1、解：本问题的目标是使投入的购买车辆总费用为最少，而实际上总的运输时间为最少时，也就确 定了最少的车辆数量，本问题最少的运输时间为目标的得线性规划数学模型：min z =155x1+170x2+170x3+175x4+185x5+185x6+190x7+200x8+180x9+190x10+200x11+210x12S.T.4x +3x+3x+2x,+2x=+2x,+x +x +x+0x +0x ,+0x”3361234567891011120x1+1x2+0x3+2x4+1x5+0x6+2x7+1x8+3x9+4x10+3x11+2x12 3260x, +0x +1x+0x,+1x+2x, + x=+2xo+0x+0x + x +2x, 330123456789101112代入线性规划求解模板得结果：即整理如下表：路线123456789101112结果0000015006200A433222111000B010210213432C001012120012运送时间155170170175185185190200180190200210最少的运输时间4235小时。灵敏度分析报告：目标函数最优值为：4235需要车辆23台，最小的购车费用23*5=115万元。变量最优解相差值X105x2010x302.5x405x507.5x6150x702.5x805x960x1020x1102.5x1205约束松弛/剩余变量对偶价格10-37.520-47.530-55目标函数系数范围：变量下限当前值上限x1150155无上限x2160170无上限x3167.5170无上限x4170175无上限x5177.5185无上限x675185190x7187.5190无上限x8195200无上限x9177.5180181.25x10188.333190191.667x11197.5200无上限x12205210无上限常数项数范围：约束下限当前值上限1303638.66721826无上限327.3333036这里从对偶价格可见，A区每增加一个点，需要增加投入37.5分钟；B区每增加一个 点，需要增加投入47.5分钟；C区每增加一个点，需要增加投入55分钟。这完全符合实际。若直接用购车数量最少做为目标可将线性规划数学模型改为：min z =x +x+x +x +x+x,+x+x+x+x +x +xiz,123456789101112S.T.4x +3x+3x+2x,+2x=+2x,+x +x +x+0x +0x ,+0x”3361234567891011120x1+1x2+0x3+2x4+1x5+0x6+2x7+1x8+3x9+4x10+3x11+2x12 326 0x, +0x +1x+0x+1x+2x, + 心+2x+0x+0x + x +2x, 330 123456789101112代入线性规划求解模板得结果:路线123456789101112结果1.5000015006.5000A433222111000B010210213432C001012120012运送时间155170170175185185190200180190200210即需要车辆23台，最小的购车费用23*5=115万元。但车辆台数为非整数，这是不合理的，但要去尾取整或四舍五入也都肯定不合理。所 以对这类问题这种方法还是有局限性。好则线性规划有专门处理这类问题的方V整数规划。若用整数规划得以下结果：路线123456789101112结果2000014000601A433222111000B010210213432C001012120012运送时间155170170175185185190200180190200210即需要车辆23台，最小的购车费用23*5=115万元。5.10某公司生产A、B、C、D四种规格的电子产品，这四种产品可以分别在五个不 同的生产车间单独制造，这五个车间单独制造一件产品所需要时间、各车间可提供的总可制 造时间及每件产品的利润如下表：产品型号所需时间（分钟）单件利润（元）车间1车间2车间3车间4车间5A5642320B83-3418C-624-24D5-34230可提供的总时间2000018000160001400015000该公司销售人员提供信息：（1）产品A的销售数量不会超过1500件；（2）产品B的销售数量在500-900件之间；（3）产品C销售数量不会超过6000件；（4）产品D至少能销售800件，在此基础，生产多少能销售多少。请制定一个生产方案，使得该公司的总利润为最大。解：线性规划数学模型：Max Z= 20x+18x+24xo+30x12345x+8x+5x W 200001246x +3x +6x W180001234x. +2x +3x W160001342x +3Xc+4xo+4xA W1400012343x +4Xc+2x W15000 124x1W1500x2W900 x?*00 x3W6000x*00x1、x2、x3、x430用求解模型板求得结果:即：安排产品A、B、C、D的产量分别为1050、900、1500、800件，使得最多的利润为97200元。灵敏度分析报告:目标函数最优值为：97200变量最优解相差值X110500x29000x315000x48000约束松弛/剩余变量对偶价格135500202.667364000402566500645007048400094500010022目标函数系数范围：变量下限当前值上限X1122024x21418无上限x3202428x4830无上限常数项数范围：约束下限当前值上限11645020000无上限21485018000193503960016000无上限41310014000161005835015000无上限610501500无上限75009001238.0958无下限500900915006000无上限102758001025