《2022年第五章运筹学线性规划在管理中的应用案例》由会员分享,可在线阅读,更多相关《2022年第五章运筹学线性规划在管理中的应用案例(18页珍藏版)》请在金锄头文库上搜索。
1、第五章线性规划在管理中的应用5.1 某企业停止了生产一些已经不再获利的产品,这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品、的生产。 可用的机器设备是限制新产品产量的主要因素,具体数据如下表:机器设备类型每周可用机器台时数铣床500 车床350 磨床150 每生产一件各种新产品需要的机器台时数如下表:机器设备类型新产品新产品新产品铣床8 4 6 车床4 3 0 磨床3 0 1 三种新产品的单位利润分别为0.5 元、 0.2 元、 0.25 元。目标是要确定每种新产品的产量,使得公司的利润最大化。1、判别问题的线性规划数学模型类型。2、描述该问题要作出决策的目标、决策的限制条
2、件以及决策的总绩效测度。3、建立该问题的线性规划数学模型。4、用线性规划求解模型进行求解。5、对求得的结果进行灵敏度分析(分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析)。6、若销售部门表示,新产品、生产多少就能销售多少,而产品最少销售18 件,请重新完成本题的1-5。解:1、本问题是资源分配型的线性规划数学模型。2、该问题的决策目标是公司总的利润最大化,总利润为:0.5x1+ 0.2x2+ 0.25x3 决策的限制条件:8x1+ 4x2+ 6x3500 铣床限制条件4x1+ 3x2350 车床限制条件3x1+ x3150 磨床限制条件即总
3、绩效测试(目标函数)为:max z= 0.5x1+ 0.2x2+ 0.25x3 3、本问题的线性规划数学模型max z= 0.5x1+ 0.2x2+ 0.25x3 ST8x1+ 4x2+ 6x3500 4x1+ 3x2350 3x1+ x3150 x10、x20、x304、用 Excel 线性规划求解模板求解结果:最优解(50, 25,0) ,最优值: 30 元。5、灵敏度分析精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 18 页目标函数最优值为 : 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛
4、 / 剩余变量对偶价格 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 元 /件
5、。(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、若产
6、品最少销售18 件,修改后的的数学模型是:max z= 0.5x1+ 0.2x2+ 0.25x3 ST8x1+ 4x2+ 6x3500 4x1+ 3x2350 3x1+ x3150 x318 x10、x20、x30这是一个混合型的线性规划问题。代入求解模板得结果如下:最优解( 44, 10,18) ,最优值: 28.5 元。灵敏度报告:目标函数最优值为 : 28.5 变量最优解相差值 x1 44 0 x2 10 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 18 页 x3 18 0 约束松弛 / 剩余变量对偶价格 1 0 .05
7、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,表明铣床和磨床的可用工时已经用完,新产品的产量也刚好达到最低限制
8、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 件以内。 各自每增加一个工时
9、对总利润的贡献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+x10S.T. 3x1+2x2+2x3+x4+x5+x675 x2+2x4+x6+3x7+2x8+x950 x3+3x5+x6+2x8+3x9+4x1011
10、0 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 变量最优解相差值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 18 页 x1 18.333 0 x2 0 .056 x3 0 .111 x4 0 .111 x5 20 0 x6
11、 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
12、 3 50 110 275 这是一个统计型的线性规划问题,所以分析价值系数的取值范围和相差都没有意义。松弛 /剩余变量都为0,表示最优方案已达到三种规格薄铜板数量的最低限。三个约束条件的对偶价格-.333 、-.278 、-.222 分别表示三种规格薄铜板数量的最低限再增加一个,将增加原铜板.333cm、.278cm、.222cm。这个数字实际跟薄铜板长度规格相一致。常数项数范围表示三种规格薄铜板数量的最低限在这些范围内,每增一个限额所原原铜板.333cm、.278cm、.222cm 不变。这里需要特别指出的是,第一种规格的薄铜板32cm 宽,已使三块组合就能比较恰当地用完原铜板,所以这种规格
13、的薄铜板无论增加多少,都不改变用原铜板的比例。5.3 某医院对医生工作的安排为4 小时一个工作班次,每人要连续工作二个班次。各班次需要医生人数如下表:班次时间人数1 0:00-4:00 4 2 4:00-8:00 7 3 8:00-12:00 9 4 12:00-16:00 12 5 16:00-20:00 8 6 20:00-24:00 6 其中,第 6 班报到的医生要连续上班到第二天的第1 班。问在各班开始时应该分别有几位医精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页,共 18 页生报到。若参加1、2、6 班的医生需要支付夜班津贴,为
14、了使支付总的夜班津贴为最少,应如何安排各班开始时医生的报到人数。解:第一步:不考虑夜班津贴。线性规划数学模型为:min f=x1+x2+x3+x4+x5+x6S.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 约束松
15、弛 / 剩余变量对偶价格 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 1 x4 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 这是一统计型线性规划规划问题,所以相差值的价值系数的变化范围没有必要分析。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -
16、第 5 页,共 18 页班次时间所需人数本段安排人数上段安排人数本段实际人数多余人数1 0:00-4:00 4 7 0 7 3 2 4:00-8:00 7 0 7 7 0 3 8:00-12:00 9 10 0 10 1 4 12:00-16:00 12 2 10 12 0 5 16:00-20:00 8 6 2 8 0 6 20:00-24:00 6 0 6 6 0 合计46 25 50 4 松弛 /剩余变量一栏就是上表的“多余人数”一列是各时间段安排所剩余的人数。“对偶价格”一栏。第一个常数项由4 增加到 5,因为还剩下2 人,所以不会改变最优值;第二个常数项由7 增加到 8,因为再没有剩
17、余的人,所以本班必须再多安排一个人最优值解也必须增加1,因为是求最小化问题,所以对偶价格为1;第三个常数项由9 增加到 10,刚好将原来剩余的人用上,所以不会改变最优值;第四个、第六个常数项与第二个常数项一样;第五个常数项由2 增加到 3,因为再没有剩余的人,所以本班必须再多安排一个人,但下个班就可以再少安排一个人,所以不会改变最优值;本题的这种情况是每一个变量都会影响到两个时段的结果, 所以在进行灵敏度分析时也必定要考虑这个因素,这里第一个时段是特殊情况(有资源剩余),其余的时段分析时相邻两个是相互影响的。因此,第2 时段为 -1,第 3 时段为 0,后面的依次相反。若第2 时段为0,则第
18、3时段就为 -1。第二步:考虑夜班津贴。线性规划数学模型为:min f=x1+x2+x3+x5+x6S.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 约束松弛 / 剩余变量对
19、偶价格精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 18 页 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 无上限这是一统计型线性规划规划问题,所以相差值的价值系数的变化范围没有必要分析。班次时间所需人
20、数本段安排人数上段安排人数本段实际人数多余人数1 0:00-4:00 4 06 6 2 2 4:00-8:00 7 70 7 0 3 8:00-12:00 9 27 9 0 4 12:00-16:00 12 102 12 0 5 16:00-20:00 8 010 10 2 6 20:00-24:00 6 60 6 0 合计46 25 50 4 “对偶价格”一栏。第一个常数项由4 增加到 5,因为还剩下2 人,所以不会改变最优值;第二个常数项由7 增加到 8,由于上段时间已增一个人,这个人本班还上班,所以本也不需要增加人。第三个常数项由9 增加到 10,前面安排的人都已下班,本班刚好只朋9 人
21、,若需求再增加一人,就需要新安排一人所以对偶价格-1;第四个、第五个、第六个常数项与前三个常数项一样;5.4 某塑料厂要用四种化学配料生产一种塑料产品,这四种配料分别由A、B、C 三种化学原料配制,三种化学原料的配方及原料价格如下表:配料1 2 3 4 价格(元 /公斤)含原料 A(%)30 40 20 15 11 含原料 B(%)20 30 60 40 13 含原料 C(%)40 25 15 30 12 要配制的塑料产品中,要求含有20%的原料 A,不少于30%的材料 B 和不少于20%的原料C。由于技术原因,配料1 的用量不能超过30%,配料 2的用量不能少于40%。第一次配制的塑料产品不
22、能少于5 公斤。请设计一套配料方案,使总的成本为最低。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 18 页解:线性规划数学模型:min f =10.7 x1+11.3 x2+11.8 x3+9.45 x4S.T. 0.1x1+0.2 x2-0.05 x4=0 -0.1x1 +0.3 x3+0.1 x40 0.2 x1+0.05 x2-0.05 x3+0.1 x40 0.7x1-0.3x2-0.3x3-0.3x40 -0.4 x1+0.6x2-0.4x3-0.4x40 x1+x2+x3+x45 xi0(i=1 ,2, 3,4, )将模
23、型代入到线性规划求解模板,得结果:用配料 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
24、 -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 表示已达到产量要求。关五个约束的对偶价格
25、表示配料或者说原料不匹配时,对总费用的影响。 不为 0 的对偶价格表示配比每差一个单位都会使总费用的增加量。第五个对偶价格是每增加一公斤的产品,需要增加的费用值。在学数项取值范围栏:前五个约束在常数项在这个范围内,保持上述的对偶价格,而此时的上限都不高, 说明这个最优方案中的匹配关系失衡并不严重,若比例失衡将会导致费用的增加比例更大。对五个对偶价格实际上说明了该产品的绝对成本,在这个方案下, 生产多少的产品都是这个成本构成。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 18 页5.5 某工厂生产、四种产品,产品需经过A、B 两种机器加
26、工,产品需经过 A、C 两种机器加工,产品需经过B、C 两种机器加工,产品需经过A、B 两种机器加工。有关数据见下表所示:产品机器生产率(件/小时)原料成本(元/件)产品价格(元 /件)A B C 10 20 16 65 20 10 25 80 10 15 12 50 20 10 18 70 机器成本(元 /小时)200 150 225 每周可用机时数150 120 70 请为该厂制定一个最优生产计划。解:线性规划数学模型:max Z=21.5 x1+22.5 x2+8 x3+27 x4S.T. 2x1+x2+x43000 x1+2x3+2x424003x2+4x34200 xi0(i=1,2
27、,.4)用 Excel 线性规划求解模板求解得:最优生产方案:产品生产267 件;产品生产1400 件;产品不安排生产;产品生产1067 件。可获得的最高利润:66033.3 元。灵敏度分析报告:即:目标函数最优值为 : 66033.3495 变量最优解相差值 - - - x1 266.667 0 x2 1400 0 x3 0 30.8333 x4 1066.667 0 约束松弛 / 剩余变量对偶价格 - - - 1 0 5.333 2 0 10.833 3 0 5.722 目标函数系数范围 : 变量下限当前值上限 - - - - x1 13.5 21.5 45 x2 5.333 22.5 无
28、上限 x3 无下限 8 38.333 x4 10.75 27 43 常数项数范围 : 约束下限当前值上限 - - - - 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 18 页 1 2600 3000 6200 2 800 2400 3200 3 0 4200 5400 此模型的最优解中,四个变量有三个变量不为0,即需要安排生产,另一个为0 的变量表示产品由于成本高或价格低,使所获的利润太低,不值得生产。从相差值栏可见,该产品的单位利润需要再增加30.8333 元才值得生产。松弛 / 剩余变量栏中三个数据都为0,表示该决策中所提供三种
29、设备的机时都已全部利用,没有剩余; 从对偶价格栏还可以看到三种设备的机时虽然都已用尽,但此时对三种设备增加机时, 则设备 B所带来的总利润为最多。因此设备 B是瓶径。 从约束条件的取值范围也可以看到这一点,因为设备B的机时取值范围最小,因此该设备是关键。5.6 某企业生产、两种产品,市场两种产品的需求量为:产品在1-4 月份每月需1 万件, 5-9 月份每月需3 万件, 10-12 月份每月需10 万件;产品在3-9 月份每月需1.5万件,其他月份每月需5 万件。该企业生产这两种产品的成本为:产品在1-5 月份生产时每件 5 元,6-12 月份生产时每件4.5 元;产品在1-5 月份生产时每件
30、8元, 6-12 月份生产时每件 7 元;该企业每月生产两种产品的能力总和不超过12 万件。产品容积为每件0.2立方米,产品容积为每件0.4 立方米。该企业仓库容积为1.5 万立方米。要求:1、问该企业应如何安排生产,使总的生产加工储存费用为最少,建立线性规划数学模型并求解,若无解请说明原因。2、若该企业的仓库容积不足时,可从外厂租借。若占用本企业的仓库每月每立方米需1 万元的储存费,而租用外厂仓库时其储存费用为每月每立方米1.5 万元,试问在满足市场需求情况下,该企业又应如何安排生产,使总的生产加储存费用为最少。解:1、这是一个72 个变量、 60 个约束条件的线性规划问题,若不考虑外厂租借
31、仓库,则无法求解(无解) ,只有考虑外厂租借仓库才能解决本问题。分析及解决过程和结果可见下表:月份1 2 3 4 5 6 7 8 9 10 11 12 仓容外存产品销售量(千件)10 10 10 10 30 30 30 30 30 100 100 100 15000(m3)1 元/m3容量不限1.5 元/m3成本(元、件)5 5 5 5 5 4.5 4.5 4.5 4.5 4.5 4.5 4.5 产量(件)x1=10 x2=10 x3=10 x4=10 x5=30 x6=30 x7=30 x8=45 x9=105 x10=70 x11=70 x12=70 总容积(千m3) 0.2x1 0.2x
32、2 0.2x3 0.2x4 0.2x5 0.2x6 0.2x7 0.2x8 0.2x9 0.2x10 0.2x11 0.2x12 库存数x25=0 x26=0 x27=0 x28=0 x29=0 x30=0 x31=0 x32=15 x33=90 x34=60 x35=30 x36=0 产品销售量(千件)50 50 15 15 15 15 15 15 15 50 50 50 成本(元、件)8 8 8 8 8 7 7 7 7 7 7 7 产量(件)x13=50 x14=50 x15=15 x16=15 x17=15 x18=15 x19=15 x20=15 x21=15 x22=50 x23=5
33、0 x24=50 总容积(千m3) 0.4x13 0.4x14 0.4x15 0.4x16 0.4x17 0.4x18 0.4x19 0.4x20 0.4x21 0.4x22 0.4x23 0.4x24 库存数x37=0 x38=0 x39=0 x40=0 x41=0 x42=0 x43=0 x44=0 x45=0 x46=0 x47=0 x48=0 仓容本厂(千 m3)x49=0 x50=0 x51=0 x52=0 x53=0 x54=0 x55=0 x56=3 x57=15 x58=12 x59=6 x60=0 外借(千 m3)x61=0 x62=0 x63=0 x64=0 x65=0 x
34、66=0 x67=0 x68=0 x69=3 x70=0 x71=0 x72=0 产品总和(千件)120 120 120 120 120 120 120 120 120 120 120 120 总的生产加储存最少费用为4910500 元精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 18 页外借的库房,在9 月份用了3 千平方米的容量。本问题灵敏度详细分析太麻烦,从略。5.7 某快餐店坐落在一个远离市区的旅游点中,平时游客不多, 而在除冬季外每个双休日游客都比较多。该快餐店有两名正式职工,正式职工每天工作8 小时, 且每个时间段都至少
35、要有一个正式职工在上班,其余工作由临时工来承担,临时工每班工作4 小时。 在双休日每天上午10 时开始营业到下午10 时关门。 根据游客就餐情况,在双休日每个营业时间段所需职工数(包括正式工和临时工)如下表:时间段所需职工数10:00-11:00 9 11:00-12:00 10 12:00-13:00 10 13:00-14:00 9 14:00-15:00 3 15:00-16:00 3 16:00-17:00 3 17:00-18:00 6 18:00-19:00 12 19:00-20:00 12 20:00-21:00 7 21:00-22:00 7 已知一名正式职工10 点开始上班
36、, 工作 4 小时后休息1 小时, 而后再工作4 小时; 另一名正式职工13 点开始上班,工作4 小时后休息1 小时,而后再工作4 小时。临时工每小时的工资为4 元。1、在满足对职工需求的条件下,如何安排临时工的班次,使得使用临时工的成本为最小?2、 这时付给临时工的工资总额为多少?一共需要安排多少个班次的临时工?请用剩余量来说明如果安排一些每班工作3 小时的临时工班次,可使得总成本更小。3、如果临时工每班工作时间可以是3 小时, 也可以是4 小时, 那么应如何安排临时工的班次,使得使用临时工的总成本为最小?这样比第1 问的结果能节省多少费用?这时要安排多少临时工的班次?解: 1、线性规划数学
37、模型:min f 16x1+16x2+16x3+16x4+16x5+16x6+16x7+16x8+16x9+12x10+8x11+4x12s tx18 x1x2 9 x1x2x3 9 x1x2x3x47 x2x3x4x52 x3x4x5x6 1 x4x5x6x7 1 x5x6x7x8 5 x6 x7 x8 x910 x7x8x9x10 11 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 18 页x8x9x10x11 6 x9x10x11x12 6 x1, x2, x3, x4, x5,x6,x7,x8,x9,x10,x11, x12
38、 0将该模型代入到线性规划求解模板得结果:其解为:x18,x2 1,x31,x40,x50,x6 0,x71,x84,x95,x101,x110,x120 最优值为 332。在满足对职工需求的条件下,在10 时新安排临时工8个 ;11 时新安排临时工1个;12 时新安排临时工1个;16 时新安排临时工1个;17 时新安排临时工4个;18 时新安排临时工5个;19 时新安排临时工1个。全天共安排 21个临时工,其中18时以前安排的20人是连续上四小时班,19时安排的一人上 3小时班。可使临时工的总成本最小为332元。如下表所示:时间段所需临时工安排上班人数实际上班人数剩余人数10:00-11:0
39、0 88 8 8-8=0 11:00-12:00 91 9 9-9=0 12:00-13:00 91 10 10-9=1 13:00-14:00 70 10 10-7=3 14:00-15:00 20 2 2-2=0 15:00-16:00 10 1 1-1=0 16:00-17:00 11 1 1-1=0 17:00-18:00 54 5 5-5=0 18:00-19:00 105 10 10-10=0 19:00-20:00 111 11 11-11=0 20:00-21:00 60 10 10-6=4 21:00-22:00 60 6 6-6=0 合计75 21 83 8 灵敏度分析报告
40、:2、这时付给临时工的工资总额为332 元,一共需要安排83 个临时工的班次。根据剩余变量的数字分析可知,可以让10 时安排的 8 个人中留 3人工作 3 小时,就可以将 13-14时多余的 3个工时省下来;同时17 时安排的 4个人工作 3 小时,也可将 20时的 4个工时省下来使得总成本更小。这时只有 12-13时间段剩余 1人, 其它时间段都没有剩余的人员,所以总的班次只用76个,总费用将是764=304元。3、设在 10:00-11:00 这段时间内有 x1个班是 3 小时, x2个班是 4 小时;设在 11:00-12:00 这段时间内有 x3个班是 3 小时, x4个班是 4 小时
41、;其他时段也类似。得线性规划数学模型:min z =12x1+12x3+12x5+12x7+12x9+12x11+12x13+12x15+12x17+12x19+8x21+4x23+ 16x2+16x4+16x6+16x8+16x10+16x12+16x14+16x16+16x18+12x20+8x22+4x24ST x1x2 8 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页,共 18 页x1x2 x3x4 9 x1x2x3 x4x5x6 9 x2x3x4x5x6x7x87 x4x5x6x7x8 x9 x10 2 x6x7x8x9x10
42、x11 x12 1 x8x9x10x11 x12x13x14 1 x10x11x12x13x14x15x16 5 x12 x13x14x15x16x17x18 10 x14 x15x16x17x18x19x2011 x16 x17x18x19x20x21x22 6 x18x19 x20x21 x22x23x24 6 xi 0 i=1,2, ,24 将该模型代入到线性规划求解模板得结果:其解为:在满足对职工需求的条件下,10 时安排 8 个临时工,其中3个3小时的, 5个 4小时的;11 时新安排 1个4小时的临时工;13 时新安排 1个3小时的临时工;16 时新安排 1个4小时的临时工;17
43、时新安排 4个3小时的临时工;18 时新安排 5个4小时的临时工;19 时新安排 1个3小时临时工。全天共安排 21个临时工,可使临时工的总成本最小为300元。如下表所示:时间段所需临时工4 小时班人数3 小时班人数实际上班人数剩余人数10:00-11:00 853 8 0 11:00-12:00 910 9 0 12:00-13:00 900 9 0 13:00-14:00 701 7 0 14:00-15:00 200 2 0 15:00-16:00 100 1 0 16:00-17:00 110 1 0 17:00-18:00 504 5 0 18:00-19:00 1050 10 0
44、19:00-20:00 1101 11 0 20:00-21:00 600 6 0 21:00-22:00 600 6 0 合计75 12 9 75 0 这样能比第一种方案节省:332-300=32 元。灵敏度分析报告:5.8 某咨询公司受厂商的委托对新上市的产品进行消费反映调查。被调查对象分为上班族和休闲族, 而调查时间在周一至周五与双休日得到的结果大不相同。委托厂商与该公司签订的业务合同规定:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页,共 18 页(1)必须调查3000 个消费对象;(2)周一至周五与双休日被调查的总人数相等;(3
45、)至少要调查1200 个上班族对象;(4)至少要调查800 个休闲族对象。调查每个对象所需费用如下表:调查对象周一至周五调查双休日调查上班族35 40 休闲族25 28 1、请建立该问题的线性规划数学模型,以确定在不同时间调查各种对象的人数,使得总的调查费用为最少。2、求解该模型,并对结果进行灵敏度分析。解: 1、线性规划数学模型:min 35x1+40x2+25x3+28x4 S.T. x1+x2+x3+x4 3000 x1-x2+x3-x4=0 x1+x21200 x3+x4800 x1,x2,x3,x40代入线性规划求解模板得结果:其调查方案如下表:调查对象周一至周五调查双休日调查上班族
46、1200 0 休闲族300 1500 按此方案的调查费用为最少:91500 元。2、灵敏度分析报告:即:目标函数最优值为 : 91500 变量最优解相差值 x1 1200 0 x2 0 2 x3 300 0 x4 1500 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页,共 18 页约束松弛 / 剩余变量对偶价格 1 0 -26.5 2 0 1.5 3 0 -10 4 1000 0 目标函数系数范围 : 变量下限当前值上限 x1 25 35 37 x2 38 40 无上限 x3 23 25 35 x4 -25 28 30 常数项数范围
47、 : 约束下限当前值上限 1 2400 3000 无上限 2 -600 0 3000 3 0 1200 1500 4 无下限 800 1800 5.9 西兰物业公司承担了正大食品在全市92个零售点的肉类、 蛋品和蔬菜的运送业务。运送业务要求每天4 点钟开始从总部发货,送完货时间必须在7:30 前结束 (不考虑空车返回时间)。这 92 个零售点每天需要运送货物0.5 吨,其分布情况为:5 公里以内为A 区,有36 个点,从总部到该区的时间为20 分钟; 10 公里以内5 公里以上的为B 区,有 26 个点,从总部到该区的时间为40 分钟; 10 公里以上的为C 区,有 30 个点,从总部到该区的
48、时间为 60 分钟; A 区各点间运送时间5 分钟; B 区各点间运送时间10 分钟; C 区各点间运送时间 20 分钟;各区之间运送时间20 分钟。每点卸货、验收时间为30 分钟。本公司准备购买规格为 2 吨的运送车辆,每车购价5 万元。请用线性规划方法确定每天的运送方案,使投入的购买车辆总费用为最少。1、 解:本问题的目标是使投入的购买车辆总费用为最少,而实际上总的运输时间为最少时,也就确定了最少的车辆数量,本问题最少的运输时间为目标的得线性规划数学模型:min z =155 x1+170x2+170x3+175x4+185x5+185x6+190x7+200x8+180x9+190x10
49、+200x11+210x12S.T. 4x1+3x2+3x3+2x4+2x5+2x6+x7+x8+x9+0x10+0x11+0x1236 0x1+1x2+0x3+2x4+1x5+0x6+2x7+1x8+3x9+4x10+3x11+2x12260x1+0x2+1x3+0x4+1x5+2x6+ x7+2x8+0x9+0x10+ x11+2x1230 代入线性规划求解模板得结果:即整理如下表:路线1 2 3 4 5 6 7 8 9 10 11 12 结果0 0 0 0 0 15 0 0 6 2 0 0 A 4 3 3 2 2 2 1 1 1 0 0 0 B 0 1 0 2 1 0 2 1 3 4 3
50、 2 C 0 0 1 0 1 2 1 2 0 0 1 2 运送时间155 170 170 175 185 185 190 200 180 190 200 210 最少的运输时间4235 小时。需要车辆23 台,最小的购车费用23*5=115 万元。灵敏度分析报告:目标函数最优值为 : 4235 变量最优解相差值 x1 0 5 x2 0 10 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页,共 18 页 x3 0 2.5 x4 0 5 x5 0 7.5 x6 15 0 x7 0 2.5 x8 0 5 x9 6 0 x10 2 0 x11 0
51、 2.5 x12 0 5 约束松弛 / 剩余变量对偶价格 1 0 -37.5 2 0 -47.5 3 0 -55 目标函数系数范围 : 变量下限当前值上限 x1 150 155 无上限 x2 160 170 无上限 x3 167.5 170 无上限 x4 170 175 无上限 x5 177.5 185 无上限 x6 75 185 190 x7 187.5 190 无上限 x8 195 200 无上限 x9 177.5 180 181.25 x10 188.333 190 191.667 x11 197.5 200 无上限 x12 205 210 无上限常数项数范围 : 约束下限当前值上限 1
52、 30 36 38.667 2 18 26 无上限 3 27.333 30 36 这里从对偶价格可见,A 区每增加一个点,需要增加投入37.5 分钟; B 区每增加一个点,需要增加投入47.5 分钟; C 区每增加一个点,需要增加投入55 分钟。 这完全符合实际。若直接用购车数量最少做为目标可将线性规划数学模型改为:min z =x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12S.T. 4x1+3x2+3x3+2x4+2x5+2x6+x7+x8+x9+0x10+0x11+0x1236 0x1+1x2+0x3+2x4+1x5+0x6+2x7+1x8+3x9+4x10+
53、3x11+2x12260x1+0x2+1x3+0x4+1x5+2x6+ x7+2x8+0x9+0x10+ x11+2x1230 代入线性规划求解模板得结果:路线1 2 3 4 5 6 7 8 9 10 11 12 结果1.5 0 0 0 0 15 0 0 6.5 0 0 0 A 4 3 3 2 2 2 1 1 1 0 0 0 B 0 1 0 2 1 0 2 1 3 4 3 2 C 0 0 1 0 1 2 1 2 0 0 1 2 运送时间155 170 170 175 185 185 190 200 180 190 200 210 即需要车辆23 台,最小的购车费用23*5=115 万元。但车辆
54、台数为非整数,这是不合理的,但要去尾取整或四舍五入也都肯定不合理。所以对这类问题这种方法还是有局限性。好则线性规划有专门处理这类问题的方法-整数规划。若用整数规划得以下结果:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页,共 18 页路线1 2 3 4 5 6 7 8 9 10 11 12 结果2 0 0 0 0 14 0 0 0 6 0 1 A 4 3 3 2 2 2 1 1 1 0 0 0 B 0 1 0 2 1 0 2 1 3 4 3 2 C 0 0 1 0 1 2 1 2 0 0 1 2 运送时间155 170 170 175 1
55、85 185 190 200 180 190 200 210 即需要车辆23 台,最小的购车费用23*5=115 万元。5.10 某公司生产A、B、C、D 四种规格的电子产品,这四种产品可以分别在五个不同的生产车间单独制造,这五个车间单独制造一件产品所需要时间、各车间可提供的总可制造时间及每件产品的利润如下表:产品型号所需时间(分钟)单件利润(元)车间 1 车间 2 车间 3 车间 4 车间 5 A 5 6 4 2 3 20 B 8 3 - 3 4 18 C - 6 2 4 - 24 D 5 - 3 4 2 30 可提供的总时间20000 18000 16000 14000 15000 该公司
56、销售人员提供信息:(1)产品 A 的销售数量不会超过1500 件;(2)产品 B 的销售数量在500-900 件之间;(3)产品 C 销售数量不会超过6000 件;(4)产品 D 至少能销售800 件,在此基础,生产多少能销售多少。请制定一个生产方案,使得该公司的总利润为最大。解:线性规划数学模型:Max Z= 20 x1+18x2+24x3+30x45x1+8x2+5x4200006x1+3x2+6x3180004x1+2x3+3x4160002x1+3x2+4x3+4x414000 3x1+4x2+2x415000x11500 x2900 x2500 x36000 x4800 x1、x2、
57、x3、x4 0用求解模型板求得结果:即:安排产品A、B、C、D 的产量分别为1050、900、1500、800 件,使得最多的利润为 97200 元。灵敏度分析报告:目标函数最优值为 : 97200 变量最优解相差值 x1 1050 0 x2 900 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页,共 18 页 x3 1500 0 x4 800 0 约束松弛 / 剩余变量对偶价格 1 3550 0 2 0 2.667 3 6400 0 4 0 2 5 6650 0 6 450 0 7 0 4 8 400 0 9 4500 0 10 0
58、 22 目标函数系数范围 : 变量下限当前值上限 x1 12 20 24 x2 14 18 无上限 x3 20 24 28 x4 8 30 无上限常数项数范围 : 约束下限当前值上限 1 16450 20000 无上限 2 14850 18000 19350 3 9600 16000 无上限 4 13100 14000 16100 5 8350 15000 无上限 6 1050 1500 无上限 7 500 900 1238.095 8 无下限 500 900 9 1500 6000 无上限 10 275 800 1025 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页,共 18 页