《运筹学》第一次课内实验题目

第一次课内实验题目1生产筹划问题已知某工厂筹划生产I，II，III三种产品，多种产品需要在A，B，C三种设备上加工生产，具体有关数据如表，试研究下列问题：（1）如何充足发挥已有设备的能力，使生产赚钱最大？（2）如果为了增长产量，可租用其他厂家设备B，每月可租用60台时，租金为1.8万元，试问租用设备B与否合算？（3）如果该厂家拟增长生产两种新产品IV和V，其中产品IV需用A设备12台时，B设备5台时，C设备10台时，单位产品赚钱2100元；产品V需用A设备4台时，B设备4台时，C设备12台时，单位产品赚钱1870元。假设A，B，C三种设备台时不增长，试分别考虑这两种新产品的投产在经济上与否合算？（4）如果工厂对产品工艺进行重新设计改造，使改造后生产每件产品I需用A设备9台时，B设备12台时，C设备4台时，单位产品赚钱4500元，试问这种改造方案对原筹划有何影响？ 生产筹划的有关数据设备 产品IIIIII设备有效台时/每月ABC8102251310810300400420单位产品利润/元300029002快餐店用工问题某快餐店坐落在远离都市的风景区，平时游客较少，而每到双休日游客数量猛增，快餐店重要是为游客提供快餐服务，该快餐店雇用了两名正式员工，重要负责管理工作，每天需要工作8h，其他的工作都由临时工担任，临时工每天要工作4h。双休日的营业时间为11:00到22:00，根据游客的就餐状况，在双休日的每天营业小时所需的职工数（涉及正式工和临时工）如表所示。 营业时间与所需职工数量营业时间所需职工数量/人营业时间所需职工数量/人11:00-12:0012:00-13:0013:00-14:0014:00-15:0015:00-16:0016:00-17:0099933317:00-18:0018:00-19:0019:00-20:0020:00-21:0021:00-22:006121277 已知一名正式职工11：00开始上班，工作4h后休息1h，而后再工作4h；另一名正式职工13：00开始上班，工作4h后休息1h，而后再工作4h。又临时工每小时工资为4元。（1）在满足对职工需求的条件下，如何安排临时工的班次，使得使用临时工的成本最小？（2）如果临时工每班工作时间可觉得3h，也可觉得4h，如何安排临时工的班次，使得使用临时工的成本最小？这样比方案(1)能节省多少费用？此时需要安排多少临时工班次？3轰炸方案问题某战略轰炸机群奉命摧毁敌人军事目的，已知该目的有四个要害部位，只要摧毁其中之一即可达到目的。为完毕此项轰炸任务的汽油消耗量限制为48000L，重型炸弹48枚，轻型炸弹32枚，飞机携带重型炸弹时每升汽油可飞行2km，带轻型炸弹时每升汽油可飞行3km，空载时每升汽油可飞行4km，又知每架飞机每次只能装载一枚炸弹，每起飞轰炸一次除来回路途汽油消耗外，起飞和降落每次各消耗100L汽油，其她有关数据如表所示。为了保证以最大的也许性摧毁敌方军事目的，应当如何拟定飞机的轰炸方案。轰炸方案问题的有关数据敌要害部位距机场的距离/km摧毁目的的也许性每枚重型炸弹每枚轻型炸弹12344504805406000.100.200.150.250.080.160.120.204食品加工问题某食品公司下设3个工厂，分别生产熟食品、罐头食品和冷冻食品。由于市场销售状况的变化影响产品价格波动，该公司需要不断修正多种产品的产量，以便充足运用其生产能力来获得最大利润。3个工厂一共生产8种产品，消耗10种原材料。其中有两种原材料是3个工厂都要用到的，由于市场供应短缺，公司不得不从外地进货，其他8种原材料每个工厂分别用其中若干种，互不影响。下面分别给出3个工厂生产的有关数据。问题是公司如何制定原材料的供应筹划使公司获利最大？ 熟食品厂的有关数据 单位：t原材料 产品I II III 原材料每天供应量ABC 2 4 3 10 7 3 6 15 5 0 3 12单位产品的利润/万元 8 5 6 罐头厂的有关数据 单位：t原材料 产品IV V VI 原材料每天供应量DE 3 1 2 7 2 4 3 9 单位产品的利润/万元 8 5 6 冷冻品厂的有关数据 单位：t原材料 产品 VII VIII 原材料每天供应量FGH 8 5 25 7 9 30 6 4 20单位产品的利润/万元 6 5 3个厂都用的原材料数据 单位：t原材料 产品I II III IV V VI VII VIII 原材料每天供应量JK 5 3 0 2 0 3 4 6 30 2 0 4 3 7 0 1 0 205木材的存储问题某木材储运公司有一种很大的仓库用以储运发售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分用于本季度内发售，一部分储存起来后来发售。 已知该公司仓库的最大储存量为20万m3 。储存费用为元/万m3,其中，为存储时间（季度数），已知每季度买进卖出价及估计的销售量如表所示。由于木材不适宜久贮，所有库存木材应于每年秋末售完，试问该公司应采用什么存储方略使之能获最大利润。每季度的买进卖出价与销售量数据季 度买进价(万元/万m3)卖出价(万元/万m3)估计销售量/万m3冬春夏秋4104304604504254404654551001402001606生产、储存与设备维修筹划问题某机械加工工厂有2台车床、1台钻床、1台磨床，承当4种产品的生产任务。已知生产多种产品所需的设备台时及生产单位产品的售价如表所示。 设备台时和产品售价 单位：台时设备 产品I II III IV车床钻床磨床 0.5 0.7 0.5 0.1 0.2 0.6 0.2 0.2 0.6售价/(元/件) 80 60 50 40 对各产品此后三个月的市场最大需求(当不不小于最大需求量时觉得可所有销售出)及各产品在此后三个月的生产成本分别如表所示。市场的最大需求量 单位：件月份 产品I II III IV123 200 300 200 200 300 200 0 300 300 100 400 0 产品成本 单位：元/件月份 产品I II III IV123 50 46 40 28 55 45 38 32 58 47 42 36上述设备在13月内需要进行一次维修，具体安排为2台车床于2月份、3月份各维修一台，钻床安排在2月份维修，磨床安排在3月份维修，各设备每月工作22天，每天2班，每班8h，每次维修占用半个月时间。又生产出的产品当月销售不出去(超过最大需求量)时，可以在后来各月销售，但需要付每件月存储费5元。但规定每月底多种产品存储量均不超过100件。1月初各产品无库存，规定3月底各产品均库存50件。问题是该如何安排生产、存储和维修筹划，可使总的利润最大。7生产筹划问题设某制造公司根据合同规定，从当年起持续三年在年末各提供三套型号规格相似的大型设备。已知该厂此后三年的生产能力及生产成本如表所示。生产能力与生产成本年 度正常生产时完毕的设备数量/套加班生产时完毕的设备数量/套正常生产时完毕每套设备的成本费/万元第一年次年第三年241323500600550已知在加班生产的状况下，每套设备成本比正常生产时要高出70万元。又知所制造出的设备如果当年不能交货，每套设备每积压一年将增长维修保养等费用40万元。在签订合同步，该厂现库存两套该种设备，该厂但愿在第三年末完毕合同任务后能储存一套该设备留作备用。问该厂应如何安排生产筹划，使在满足上述规定的条件下，总的支出费用最小。8用煤的运送问题某校有A，B，C三个校区，每年冬天分别需要取暖用煤3000t，t，1000t，根据实际状况，拟从甲地和乙地两处煤矿调运用煤，已知两处煤矿煤质量相似，售价也相似，两处煤矿可以供应的数量分别为4000t和1500t，其单位运价如表所示。由于供应不不小于需求，经学校研究决定A校区供应量可以减少0300t，B校区供应量不少于1500t，C校区按需求供应。试给出该学校总运费最低的取暖用煤调运方案。调运价格表 校区供应地 运价/(百元/t)A B C甲乙 1.80 1.55 1.70 1.60 1.75 1.509生产资料的调拨问题设有甲、乙、丙三家工厂负责供应A，B，C，D四个地区的农用生产资料，等量的生产资料在这些地区所起的作用相似。各工厂的年产量、各地区的年需求量和单位运价如表所示。试求出总的运费至少的生产资料调拨方案。调运价格表 地区供应地 运价/(百元/t)A B C D产量/万t甲乙丙 16 13 22 17 14 13 19 15 19 20 23 506050最低需求/万t 30 70 0 10最高需求/万t 50 70 30 不限10采购问题某公司拟去外地采购A，B，C，D四种规格的商品，数量分别为1500个，个，3000个，3500个。既有甲、乙、丙三个都市的供应商可以供应这些商品，供应数量分别为2500个，2500个，5000个。由于这三个供应商的商品质量、运价不同，使销售状况有差别，估计发售后的利润(元/个)也不同，详见表所示。请协助该公司制定一种预期赚钱最大的采购方案。估计销售利润表 商品供应商 利润/(元/个)A B C D甲乙丙 10 5 6 7 8 2 7 6 9 3 4 811生产与存储方案问题某机械制造厂按合同规定需要于当年每个季度末分别提供10,15,25,20台型号的拖拉机，已知该厂各季度的生产能力及生产每台拖拉机的成本费用如表所示。生产能力与成本费用季 度 生产能力/台 单位成本/万元季 度 生产能力/台 单位成本/万元 1 25 10.8 2 35 11.1 3 30 11.0 4 10 11.3又如果生产出来的拖拉机当季不交货，每台每积压一种季度需储存和维护保养等费用0.15万元。规定在完毕合同的状况下，做出使该厂全年生产(涉及储存、维护)费用为最小的决策方案。12生产、运送、存储方案问题某工厂是生产某种电子仪器的专业厂家，该厂是以销售来拟定产量的。16月份各个月生产能力、合同销售和单台仪器平均生产费用如表所示。生产、销售、成本费用表月 份 正常生产能力/台 加班生产能力/台 销售/台 单台生产费用/万元 1 60 10 104 15 2 50 10 75 14 3 90 20 115 13.5 4 100 40 160 13 5 100 40 103 13 6 80 40 70 13.5 又知上年末积压库存103台该仪器没售出。如果生产出的仪器当月不交货，则需要运到分厂库房储存，每台仪器需增长运送成本0.1万元，每台仪器每月的平均仓储费、维护费0.2万元。在78月份销售淡季，全厂停产1个月，因此在6月份完毕销售合同后还要留出库存80台。加班生产仪器每台增长成本1万元。试问应当如何安排16月份的生产，使总的生产成本(涉及运送、仓储和维护)费用至少？13港口运送问题某国际港口航运公司承当六个港口都市A，B，C，D，E，F之间的四条固定航线的货运任务，已知各条航线的起点、终点及每天航班数如表所示，假设各航线使用相似型号的船只运送，各港口间航程天数如表所示，又知每条船只在港口装卸货的时间各需1天，为维修等所需要备用船只数占总船只数的20%，问该航运公司至少应配备多少条船，才干满足所有航线的货运规定？起、终点的航班数航线 起点都市 终点都市 每天航班数航线 起点都市 终点都市 每天航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1 各港口间的航程天数 月份 起点 终点B C D E FABCDE 1 2 14 7 7 3 13 8 8 15 5 517 20 314棋子问题有一种木匠作坊制作两种不同大小的黄杨木棋子。小型棋子一套需要车床加工3小时，大型棋子一套需要2小时。木匠作坊内有4个车床和4名纯熟操作员，每人每周工作40小时，因此每周车床总工时数为160小时。小型棋子一套需要1公斤黄杨木，大型棋子一套需要3公斤黄杨木。很不幸的是，黄杨木目前很稀缺，每周只能得到200公斤。如果售出，每套大型棋子可以得到20元利润，每套小型棋子可以得到5元利润。 问题是：每周应分别加工每种棋子多少套才干得到最多的利润。15合金制造问题有一家钢铁公司收到一份500吨造船用钢的订单。对这些造船用钢有如下规定(品质)：造船钢品质规定化学元素 最低含量 最高含量 碳(C) 2 3铜(Cu) 0.4 0.6锰(Mn) 1.2 1.65 此公司储存有七种不同的原材料，都可以用于制造这种钢。下表列出了这些原材料的品质，可用库存量，以及价格。原材料品质，可用库存量，价格原材料 C% Cu% Mn% 可用库存(吨) 单价(欧元/吨) 铁合金1 2.5 0 1.3 400 200铁合金2 3 0 0.8 300 250铁合金3 0 0.3 0 600 150铜合金1 0 90 0 500 220铜合金2 0 96 4 200 240铝合金1 0 0.4 1.2 300 100铝合金2 0 0.6 0 250 165我们的目的是求出多种原材料各取多少才干使生产成本最低。16动物饲料制造问题有一家牛饲料公司要生产两种类型的动物饲料：粉状饲料和颗粒饲料。生产这些饲料所需的原料有：燕麦，玉米和糖渣。一方面需要将这些原料(糖渣除外)磨碎，然后将所有原料混合形成饲料产品。在最后一种生产工序中，需要将半成品制成颗粒状或粉末状，从而得到最后产品。磨 碎混 合结 粒筛 粉燕麦玉米糖渣颗粒饲料饲料粉状饲料饲料动物饲料生产流程 每周饲料产品都需要满足某些营养成分需求。下表列出了原料具有的和最后产品规定的蛋白质，脂肪和纤维含量比例。营养成分含量比例原料 蛋白质 脂肪 纤维素 燕麦 13.6 7.1 7 玉米 4.1 2.4 3.7 糖渣 5 0.3 25 规定含量 =9.5 =2 =6 多种原料的可用量也有限制。下表列出了每天多种原料的可用量以及相应的价格。原材料可用量与价格原料 可用量(公斤) 价格(欧元/公斤) 燕麦 11900 0.13 玉米 23500 0.17 糖渣 750 0.12下表列出各道工序的成本。加工成本(欧元/公斤)磨碎 混合 结粒 筛粉0.25 0.05 0.42 0.17如果每天需求量为9吨颗粒饲料，12吨粉状饲料，则多种原材料应分别使用多少，并应如何进行混合才可以使总成本最低？17蔗糖生产问题在澳大利亚甘蔗的收割已经实现了高度机械化。甘蔗在砍下之后将立即通过运营于小型铁路网上的货车运送到蔗糖厂。一辆货车的运量可以生产的蔗糖量取决于甘蔗收购的地点以及甘蔗成熟限度。在收割之后，甘蔗中的含糖量将由于发酵而迅速下降，在一段时间之后，所含糖份将完全流失。目前有11辆货车达到了蔗糖厂，每辆货车运载的甘蔗量都相似。已经对每辆货车每小时的损失量以及剩余时间进行了测算，具体数据如下表所示。每车甘蔗属性货车编号 1 2 3 4 5 6 7 8 9 10 11损失率(公斤/小时) 43 26 37 28 13 54 62 49 19 28 30剩余时间 8 8 2 8 4 8 8 8 8 8 8在制糖厂内有三条生产线，每辆货车都可以选择在哪条生产线上进行加工。一车甘蔗的加工时间为两个小时。必须在这车甘蔗的质量寿命结束之前完毕加工。制糖厂的经理但愿找出一种生产筹划，使总的蔗糖损失降到最低。18电力生产调度问题为满足每日电力需求(单位为兆瓦)，可以选用四种不同类型的发电机。每日电力需求如下表所示。每日用力需求(单位为兆瓦)时段 0am-6am 6am-9am 9am-12pm 12pm-2pm 2pm-6pm 6pm-10pm 10pm-12am需求 1 3 25000 36000 25000 30000 18000每种发电机均有一种最大发电能力，当接入电网时，其输出功率不应低于某一最小输出功率。所有发电机都存在一种启动成本，以及工作于最小功率状态时的固定的每小时成本，并且如果功率高于最小功率，则超过部分的功率每兆瓦每小时还存在一种成本，即边际成本。这些数据均列于下表中。发电机描述 可用数量 最小输出功率 最大输出功率 固定成本 每兆瓦边际成本 启动成本 (MW) (MW) (欧元/小时) (欧元/小时)型号1 10 750 1750 2250 2.7 5000型号2 4 1000 1500 1800 2.2 1600型号3 8 1200 3750 1.8 2400型号4 3 1800 3500 4800 3.8 1200只有在每个时段开始时才容许启动或关闭发电机。与启动发电机不同，关闭发电机不需要付出任何代价。在任意时刻，正在工作的发电机组必须留出20%的发电能力余量，以防用电量忽然上升。问题是：在每个时段应分别使用哪些发电机才可以使每天的总成本最小？19自行车生产规划问题有一家公司生产小朋友自行车。在下表中给出来年预期的销售量(以千辆为单位计)。此公司的生产能力为每月30000辆自行车，通过工人加班，可以将产量提高50%，但是会将每辆自行车的生产成本从30欧元提高到40欧元。来年的销售预期(千辆) 1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月 30 15 15 25 33 40 45 45 26 14 25 30目前自行车的库存量为辆。对于库存中的每辆自行车，在每月月底都需要支出5欧元的存储费用。我们假定此公司的库存能力是无限的。目前是一月一日，在下面的十二个月里面每月应生产和存储多少辆自行车才可以满足此销售预期，并最小化总成本？20玻璃杯生产筹划问题在法国北部有一家公司重要生产饮水用玻璃杯。目前此公司销售六种不同类型的玻璃杯(V1到V6)，这些杯子按照1000个为一批进行生产，此公司但愿为下面12个星期的生产做出规划。可以生产小数数目批(局限性1000个)。下表列出了将来12个星期预期每种类型的杯子的需求量。规划期间内需求量(以1000个杯子为一批计) 星期 1 2 3 4 5 6 7 8 9 10 11 12 V1 20 22 18 35 17 19 23 22 29 30 28 32V2 17 19 23 20 11 10 12 34 21 23 30 12V3 18 35 17 10 9 21 23 15 10 0 13 17V4 31 45 24 38 41 20 19 37 28 12 30 37V5 23 20 23 15 19 22 18 30 28 7 15 10V6 22 18 20 19 18 35 0 28 12 30 21 23已知每种类型杯子的初始库存量以及最后规定保存的库存量(以1000个杯子为单位)。已知每种杯子的每一批的生产成本和库存成本(单位为欧元)，以及需要的工人和机器工作时间(小时)以及需要的储存空间(单位为货箱数)。限制工人每周的总工时不能超过390小时，机器每周的总工时不能超过850小时。库存空间足够保存1000个货箱。那么在每个时期内每种类型的杯子应各生产多少个才可以使生产和库存成本最小化？六种类型杯子的数据 生产成本 库存成本 初始库存 最后库存 工人工时 机器工时 储存空间V1 100 25 50 10 3 2 4V2 80 28 20 10 3 1 5V3 110 25 0 10 3 4 5V4 90 27 15 10 2 8 6V5 200 10 0 10 4 11 4V6 140 20 10 10 4 9 921物料需求规划问题M公司生产两种大型小朋友玩具车：蓝色集装箱卡车和红色油罐卡车。每种类型的玩具车都由13个部件组装而成。下图列出了这些部件的分解成果，下表列出了多种组件的价格。组件价格 轮子 棒材 保险杠 底盘 驾驶室 车门窗 0.30欧元 1欧元 0.20欧元 0.80欧元 2.75欧元 0.10欧元 风挡 蓝色集装箱 红色油罐 蓝色发动机 红色发动机 车头灯 0.29欧元 2.60欧元 3欧元 1.65欧元 1.65欧元 0.15欧元蓝色/红色货车1组装好的底盘1蓝色集装箱(或红色油罐)1组装好的驾驶室1蓝色发动机(或红色发动机)2车头灯1风挡2车门窗1驾驶室1底盘2轮轴2保险杠1棒材2轮子组件分解其中轮轴，底盘，蓝色和红色驾驶室可以由此公司自己组装，也可以转包给别的公司。下面列出了自己组装和转包这些组件的成本以及此公司的产能。在组装成本中未计入购买原料的费用。转包和组装成本，组装产能轮轴 组装好的底盘 组装好的驾驶室 蓝色卡车 红色油罐车转包 30欧元 6欧元 自己组装 6.80欧元 3.55欧元 3.20欧元 2.20欧元 2.60欧元产能 600 4000 3000 4000 5000 下个月M公司预期这两种玩具车的需求量均为3000辆。目前库存量为0。那么M公司购买或转包这些组件的数量各为多少才可以在满足规定的同步又可以最小化生产成本？22电子元件生产规划问题为增长利润，一家小公司但愿提高其最畅销产品的产量。这家公司的重要业务之一是生产IC卡和电子徽章。这家公司也生产这些卡和徽章的各个元件。因此对这些元件的生产进行良好的规划就成了此工厂获得成功的决定因素。在这个例子中对这些元件的需求都来源于此公司内部，因此很容易对其进行预测。在将来的半年内，筹划生产四种元件，型号分别为X43-M1，X43-M2，Y54-N1，Y54-N2。这些元件的产量受到产能变化的影响，并且每次产能变化后都需要重新进行控制和调节，因此会带来不可忽视的费用。因此公司但愿最小化这些变化带来的费用，以及生产和库存成本。在下表中列出了每种产品每个时期内的需求量，生产和库存成本，初始库存量，以及最后但愿保存的库存量。当产量发生变化时，需要对机器和控制系统进行重新调节。由此带来的费用与产量较前一种月的变化量(提高或上升)成正比。产量每提高一种产品单位，则需要支出1欧元；产量每减少一种产品单位，只需要支出0.50欧元。四种产品的数据产品需求 成本 库存量 月 1 2 3 4 5 6 生产 储存 初始 最后X43-M1 1500 3000 4000 2500 20 0.4 10 50X43-M2 1300 800 800 1000 1100 900 25 0.5 0 10Y54-N1 2200 1500 2900 1800 1200 2100 10 0.3 0 10Y54-N2 1400 1600 1500 1000 1100 1200 15 0.3 0 10为最小化由于产量变化引起的费用，以及生产和库存成本，应采用何种生产方案？23玻璃纤维生产规划有一家公司生产玻璃纤维，产量以立方米为单位计算。这家公司但愿对将来六个星期的生产进行规划。产能有一定上限，且在每个时期产能的上限都不同。规划所覆盖的整个期间的每周需求量都已知。不同步期的生产和存储的费用也不相似。下表中列出了这些数据。每周各项数据星期 产能(m3) 需求(m3) 生产成本(欧元/m3) 储存成本(欧元/m3) 1 140 100 5 0.22 100 120 8 0.33 110 100 6 0.24 100 90 6 0.255 120 120 7 0.36 100 110 6 0.4应采用如何的生产方案才可以最小化生产和存储的总成本？24汽车租赁问题有一家小型汽车租赁公司，此公司有94辆可供出租的汽车，分布于10个代理点中。每个代理点的位置都将以地理坐标X和Y的形式给出，单位为千米。我们假定两个代理点之间的距离约为她们之间欧氏距离(即最短距离)的1.3倍。下表给出了各个代理点的位置坐标，以及第二天上午汽车租赁的需求量和前一天晚上各个代理点拥有的汽车数。车辆租赁代理点信息 代理点 1 2 3 4 5 6 7 8 9 19 X坐标 0 20 18 30 35 33 5 5 11 2Y坐标 0 20 10 12 0 25 27 10 0 15汽车需求量 10 6 8 11 9 7 15 7 9 12目前拥有量 8 13 4 8 12 2 14 11 15 7假定汽车转运的成本为每辆车每千米0.50欧元，请找出如何在各个代理点之间调度分派汽车才可以满足各处的需求，并且使转运成本最低。25选择运送方式问题在法国西南部有一家公司，这家公司需要将180吨寄存于仓库D1到D4中的化学产品运送到3个回收中心C1，C2和C3。仓库D1到D4分别储存有50，40，35和65吨化学产品，总计为190吨。可以选用两种运送方式：公路运送和铁路运送。仓库D1只能通过公路向回收中心C1和C2进行运送，运费分别为12欧元/吨和14欧元/吨。仓库D2只能向回收中心C2运送，可以选择通过铁路或公路，运费分别为12欧元/吨和14欧元/吨。仓库D3可以通过公路向回收中心C2运送(9欧元/吨)，或通过铁路或公路向回收中心C3运送，运费分别为4欧元/吨和5欧元/吨。仓库D4通过铁路或公路向回收中心C2运送，运费分别为11欧元/吨和14欧元/吨，或通过铁路或公路向回收中心C3运送，运费分别为10欧元/吨和14欧元/吨。 此公司与铁路公司签订的化学物品运送合同规定，每次运送量至少应为10吨，最多为50吨。除了原则的安全规章之外，对公路运送不存在其她特殊的限制。那么此公司应如何运送这180吨化学物品才可以使总运费最低？26燃油运送问题有一种运送商需要将某些燃油从位于Donges的炼油厂运送到法国西部的某些客户那里。这些客户分别位于B，C，G，H，M和P。下表列出了每个地方的需求量升数。客户需求量(升)B C G H M P 14000 3000 6000 16000 15000 5000下面这个表中列出了炼油厂与客户之间的距离。距离矩阵(千米)Donges B C G H M PDonges 0 148 55 32 70 140 73B 148 0 93 180 99 12 72C 55 93 0 85 20 83 28G 32 180 85 0 100 174 99H 70 99 20 100 0 85 49M 140 12 83 174 85 0 73P 73 72 28 99 49 73 0 此运送公司使用容量为39000升的油罐车进行运送。请选择运送路线，使向所有客户运送的总里程数至少。