线性规划和整数规划

第一部分：优化模型1、线性规划模型（算法：单纯形法）2、整数规划模型（算法：分枝定界法）3、非线性规划模型（化为线性规划求解）4、动态规划模型（算法：递归算法）5、多目标规划模型（化为线性规划求解）一、线性规划模型线性规划主要解决两个方面的问题：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？用线性规划方法解决问题一般按下列步骤进行第一步：建立线性规划模型；第二步：用单纯形算法进行求解；第三步：对求解结果进行检验；第四步：将求解结果形成优化方案，付诸实施；线性规划模型一般包括三个要素：（1）决策变量（2）目标函数（3）约束条件线性规划的一般形式为：

max(或min)z=c1x1+c2x2+…+cnxn

（1.1)（1.2)（1.3)或矩阵形式其中c=(c1,c2,…,cn)，称为价值系数向量；称为技术系数矩阵(也称消耗系数矩阵)

称为资源限制向量,

X=(x1,x2,…,xn)T称为决策变量向量下面我们来看几个实际例子。案例1(投资计划问题）某公司经调研分析知，在今后三年内有四种投资机会。第Ⅰ种方案是在三年内每年年初投资，年底可获利15%，并可将本金收回；第Ⅱ种是在第一年的年初投资，第二年的年底可获利45%，并将本金收回，但该项投资不得超过2万元；第Ⅲ种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第Ⅳ种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？

解：问题分析。该问题的实际投资背景如下表所示：（1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3;j=1,2,3,4年份一二三四x111.15x11x121.45x12

x211.15x21

x231.65x23

x311.15x31

x341.35x34（2）确定目标函数：第三年年未的本利和为maxz=1.65x23+1.15x31+1.35x34

（3）确定约束条件：每一年的投资额应等于当年公司拥有的资金数：x11+x12=3x21+x23=1.15x11x31+x34=1.45x12+1.15x21

每个方案投资额的限制：x12≤2x23≤1.5非负约束：xij≥0,i=1,2,3;j=1,2,3,4x34≤1案例2

债券投资问题国家农业银行(NationalAgriculturalBank,NAB)希望为十五名要提前退休的员工制定一项提前退休计划。这些员工将要在从明年开始的七年内逐渐退休完。为了给这个提前退休计划筹集资金，此银行决定在这七年期间进行债券投资。下表给出了每年应向这些提早退休的员工支付的金额，这些金额必须在每年年初支付。年1234567金额（千欧元）10006006404807601020950表：每年要求金额此银行计划购买三种不同的债券，即SNCF公司（法国国营铁路公司）的债券，Fujutsu（富士通）公司债券，以及国债。未投资于这些债券的资金将作为储蓄保存，储蓄的利率为3.2%,下表列出了各个债券的收益,时间长度,以及价格等信息.这些债券只能按整数数目进行购买,并且一旦购买之后在债券期限内即无法更改投资金额.每年只返回投资的利息.此退休计划的负责人决定只在第一年年初购买债券,而在此后的几年内不再购买,应该如何分配在各个债券的投资金额才能使得只需要花费最少的资金就能够满足此退休计划的要求?债券价值(千欧元)利率期限SNCFFujitsu国债1.00.80.57.0%7.0%6.5%5年4年6年表:债券信息分析：决策变量：初始投资y，债券购买量xi，每年的储蓄量StP—债券价格，Dt—每年资金需求，ri---债券利率第1年第2…4年第5，6年第7年例题3：养老金管理问题华信金融公司管理的金融产品中有一只很受赞誉的养老基金，这些养老基金是很多公司用来为其雇员提供养老金的，华信公司希望能够进行合理的投资来保证养老金的供应。现在是2007年的12月了，在接下去的10年中需要支付的总的养老金如表所示：表：未来十年的养老金需求年份需要支付的养老金（万美元）2008800200912002010130020111400201216002013170020142000201521002015220020162400为了使养老基金的提供有安全保证，华信公司希望投资在能够与未来10年中的养老金支付相匹配的项目。养老基金管理中心授权华信公司的投资项目只能是资本市场基金和债券。资本市场基金获得每年固定的5%的利息收入，公司所考虑投资的四只债券的特征如表3-7所示。表：四种债券的信息债券当前价格（美元）年利息率到期日面值（美元）债券19804%2009.1.11000债券29202%2011.1.11000债券37500%2013.1.11000债券48003%2016.1.11000所有的债券均可在2008年1月1日购买，可以购买任意数量单位。债券在每年的1月1日付息，支付期为购买后的第一年到到期日为止(包括到期日)。因此这些每年1月1日的利息支付获得正好能够用来冲抵当年养老金的支付，所有多余的利息收入将存入资本市场基金。为金融计划的保守起见，华信公司假定所有的养老金支付在每年的年初，正好在利息收入(包括资本市场基金的利息收入)获得之后，债券的面值也将在到期日获得。既然当前的债券价格低于面值，真正的债权的收益比利息率要高。如债券3是一个零利息率的债券，所以每年得到的利息为0，但是到到期日获得的面值要远大于当年债券的购得价格。华信公司希望在2008年1月1日用最小可能的投资(包括市场基金的存款)来应付到2016年为止的所有所需的养老金的支付，请对此问题进行分析，并求出最优投资方案。例题4：定额投资问题通用公司的董事会正在考虑几个大型的投资项目，每个项目只能投资一次，且各项目所需要的投资金额与能够产生的预期收益是不同的，如表所示：表：投资额及预期收益

投资项目预期收益（百万美元）所需资金（百万美元）117432102831534419485717613327923假设公司现有的总投资金额为1亿美元，其中投资项目1和项目2是互斥的，项目3与项目4也是互斥的。此外，如果不选择项目1或是项目2的话，就不能选择项目3、4。投资项目5、6、7上没有附加约束。问题的目标是通过组合各种投资，使得估计的预期收益最大。解：例题5（合理下料问题）要用一批长度为7.4米的园钢做100套钢架，每套钢架由2.9米、2.1米、1.5米的园钢各一根组成，问：应如何下料才能使所用的原料最省？解：问题分析：一根长度为7.4米的园钢，要裁出2.9米、2.1米、1.5米的料有多种裁法，如可裁出一根2.9米、二根2.1米，也可裁出三根2.1米的。这样我们把所有裁法列举出来，如下表所示：下料方案根数一二三四五六七八长度米2.9111200002.1201012301.503113204合计7.17.46.57.36.67.26.36料头（米）0.300.90.10.80.21.11.4（1）

确定决策变量：设xj表示按第j种方案所用的园钢的数量（2）

确定目标函数：问题要求所用原料最省，所用原料为：minz=x1+x2+x3+x4+x5+x6+x7+x8（3）

确定约束条件：2.9米园钢的数量限制x1+x2+x3+2x4≥1002.1米园钢的数量限制2x1+x3+x5+2x6+3x7≥1001.5米园钢的数量限制3x2+x3+x4+3x5+2x6+4x3≥100非负限制xj≥0，且为整数，j=1,2,…,8建立线性规划模型的一般步骤：（1）确定决策变量；（2）确定目标函数；（3）确定约束条件。例题6．一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为2000万米3，储存费用为（70+100u）千元/万米3，u为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。

季度买进价（万元/万米3）卖出价（万元/万米3）预计销售量（万米3）冬4104251000春4304401400夏4604652000秋4504551600由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。

设yi分别表示冬、春、夏、秋四个季度采购的木材数，xij代表第i季度采购的用于第j季度销售的木材数。季度买进价（万元/万米3）卖出价（万元/万米3）预计销售量（万米3）冬4104251000春4304401400夏4604652000秋4504551600例题7

自行车生产规划问题有一家公司生产儿童自行车。在下表中给出了明年预期的销售量（以千辆为单位计）。此公司的生产能力为每个月30000辆自行车。通过工人加班，可以将产量提高50%，但会将每辆自行车的生产成本从30欧元提高到40欧元。表：明年的销售预期（千辆）1月2月3月4月5月6月7月8月9月10月11月12月301515253340454526142530当前自行车的库存量为2000辆，对于库存中的每辆自行车，在每个月月底都需要支出5欧元的存储费用。我们假定此公司的库存能力是无限的。现在是一月一日，在下面的十二个月里面每个月应生产和存储多少辆自行车才能满足此销售预期，并最小化总成本？分析：决策变量：设t时间内的正常工作时间内和加班时间内生产的自行车数量分别为xt，yt,每个月月底时库存的自行车数量为St目标：生产成本与库存成本和最小约束：第一个月其它月份生产能力限制最优方案如下：例题8：计算机生产问题案例概述：Sytech国际公司是一家在同行业中处于领先地位的计算机和外围设备的制造商。公司的主导产品分类如下：大型计算机（MFRAMES）、小型计算机（MINIS）、个人计算机（PCS）、和打印机（PRINTERS）。公司的两个主要市场是北美和欧洲。公司一直按季度作出公司最初的重要决策。公司必须按照营销部门的需求预测来对分布在全球的三个工厂调整产量，公司下一季度需求预测如下：

而公司的三个工厂的生产能力限度又使得其不能随心所欲地在任一工厂进行生产，限制主要是各工厂规模及劳动力约束。

最终分析所要求的数据由会计部门提供，下表所显示的数据表示单位利润贡献（税后）：

根据以上信息，为SYTECH公司建立了一个线性优化模型，帮助其进行生产决策。

解：例题9：蔗糖生产计划

在澳大利亚甘蔗的收割已经实现了高度机械化。甘蔗在砍下之后将马上通过运行于小型铁路网上的货车运送到蔗糖厂。一辆货车的运量、能够生产的蔗糖取决于甘蔗收购的地点以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量将由于发酵而迅速下降，在一段时间之后，所含糖份将完全流失。现在有11辆货车到达了蔗糖厂，每辆货车运载的甘蔗量都相同。已经对每辆货车每小时的损失量以及剩余时间进行了测算，具体数据如表所示。表每车甘蔗属性货车编号1234567891011损失率（千克/小时）4326372813546249192830剩余时间88284888888在制糖厂内有三条生产线，每辆货车都可以选择在哪条生产线上进行加工。一车甘蔗的加工时间为两个小时。必须在这车甘蔗的质量寿命结束之前完成加工。制糖厂的经理希望找出一个生产计划，使总的蔗糖损失降到最低。货车编号1234567891011损失率（千克/小时）4326372813546249192830剩余时间88284888888表每车甘蔗属性解：例题10：石油精炼问题

石油精炼厂将使用两种原油生产出丁烷(butane)，汽油(petrol)，柴油(dieseloil)，以及民用燃料油(heatingoil)。为生产出这些产品，需要四道工序：分离、转化、提纯、混合。在分离工序中将把原材料进行分馏，使其分离为丁烷(butane)、石脑油(naphtha)、轻柴油(gasoil)、以及残渣。残渣然后将进行催化裂解以获得较轻的产品。从分馏工序得到的各种产品将进行提纯(脱硫)，或通过重整工艺增加其辛烷值。最终，为获得可以出售的最终产品，精炼厂需要将若干种中间产物进行混合，以满足商业产品所要求的各种属性。下图中是对此精炼厂的生产过程的简单的示意图。石油精炼流程图

在分馏之后，原油1能够得到3%的丁烷，15%的石脑油，40%的轻柴油，以及15%的残渣。原油2能够得到5%的丁烷，20%的石脑油，25%的轻柴油，以及10%的残渣。对石脑油进行重整能够得到5%的丁烷和85%的重整油(重整石脑油)。对残渣的催化裂解可以生成45%的裂解石脑油和35%的裂解轻柴油(注意，由于在此工艺中也将生成15%的气体和5%的石油焦以及其他另一种无法计入我们的问题中的残余物，因此这两个百分比之和不等于1)。汽油由三种成分混合而成：重组石脑油(重组油)，丁烷，以及裂解石脑油。柴油可以通过将脱硫轻柴油，裂解轻柴油，以及裂解石脑油混合得到。民用燃料油由轻柴油及裂解石脑油组成，对其成分含量没有要求。

法律规定了一些汽油和柴油的规格指标。对于汽油有三项重要指标：辛烷值，蒸汽压，以及挥发性。辛烷值是对汽油的抗爆能力的度量。蒸汽压能够反映出汽油储存过程中发生爆炸的风险，尤其在炎热气候条件下。挥发性能够决定在寒冷气候条件下发动机是否能够容易启动。空气污染法规对柴油的含硫量进行了规定。表2-19中列出了最终产品的规格指标和中间产品的成分组成。如果对某一项没有限制，则对应在域保留为空。我们假定所有这些成分都将按照质量线性混合(实际上只有含硫量才如此)。表中间产物和最终产品规格属性规格丁烷重整油裂解石脑油裂解轻柴油去硫轻柴油汽油柴油辛烷值12010074——>=94—蒸气压602.64.1——<=12.7—挥发性105312——>=17—含硫量（%）——0.120.760.03—<=0.05下个月此精炼厂需要生产20,000吨丁烷，40,000吨汽油，30,000吨柴油，42,000吨燃料油。可用原油分别为250,000吨原油1，300,000吨原油2。重整炉每月加工能力为70,000吨，脱硫工艺每月加工能力为80,000吨，裂解工艺每月加工能力为40,000吨。各个工艺的成本取决于其中使用的燃料和催化剂。整流，重整，脱硫，和裂解的成本分别为每吨2.10，4.18，2.04，0.60欧元。解：此案例的特点是信息多而且杂。首先进行适当的信息整理，列为表1和表2。

表1原油分馏可得到的产品及可用量

丁烷石脑油轻柴油残渣可用量原油13%15%40%15%250,000原油25%20%25%10%300,000表2各工序加工能力和单位加工成本工序单位成本（欧元/吨）加工能力（吨）整流2.10—重整4.1870000脱流2.0480000裂解0.6040000案例11、有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表1所示。现有三种货物待运，已知有关数据列于表2。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%。问该货轮应装载A，B，C各多少件，运费收入为最大？试建立这个问题的线性规划模型。

前舱中舱后舱最大允许载重量（吨）200030001500容积（立方米）400054001500表1商品数量（件）每件体积（立方米/件）每件重量（吨/件）运价（元/件）A6001081000B100056700C80075600设表示xij装于第j(j=1,2,3)舱位的第i(i=1,2,3)种商品的数量舱位载重限制舱位体积限制商品数量限制平衡条件前舱中舱后舱重量200030001500容积400054001500商品数量体积重量运价A6001081000B100056700C80075600案例12.(仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.月份1234所需仓库面积(100m2)15102012表1合同租借期限1个月2个月3个月4个月仓库借费用(元/100m2)2800450060007300表2解:1)设决策变量xij表示捷运公司在第i(I=1,2,3,4)个月初签订的租借期为j(j=1,2,3,4)个月的仓库面积的合同(单位为100m2).因5月份起该公司不需要租借仓库,故x24,x33,x34,x42,x43,x44均为零2)目标函数:使总的租借费用最小3)约束条件:每个月份所需仓库面积的限制二、整数规划模型案例1某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；B和D之间需选择也仅需选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件，该单位共筹集资金15万元，问应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E59解：决策变量：设目标函数：期望收益最大约束条件：投资额限制条件6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3

x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：案例2某服务部门各时段（每2小时为一时段）需要的服务员人数如下表，按规定，服务员连续工作8小时（即四个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。时段12345678服务员最少数目10891113853解：设在第j时段开始时上班的服务员人数为xj，由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班，故决策变量只需考虑x1,x2,x3,x4,x5，此问题的数学模型为：案例3：护士工作时间调度问题Mr.Schedule先生受人之托要为St.Joseph医院的心脑血管部门制定护士的工作时间表。在心脑血管部门中一个工作日分为12个两小时长的时段，每个时段的人员要求都不同。例如，在夜间只要求有很少的几个护士就足够了，但是在早晨为了给病人提供特殊服务，需要很多护士。下表列出了每个时段的人员需求量。编号时段需要护士人数0123456789101100am-02am02am-04am04am-06am06am-08am08am-10am10am-12pm12pm-02pm02pm-04pm04pm-06pm06pm-08pm08pm-10pm10pm-12am151515354040403031353020问题1：请计算出为满足需求最少需要多少护士，假定已知护士每天工作8小时，且在工作四小时后需要休息两小时。问题2：此部门目前只有80名护士，这个数目不足以满足给定的需求。因此Schedule先生建议每天安排部分人加班。每天加班时间为2小时，且紧随在后一个四小时工作时段之后，中间没有休息。请给出护士工作时间安排方案，以使需要加班的护士数目最少。分析：设xt为时段t开始工作的护士数目问题1模型最优方案由此我们看到，第1问题求出的最优解为至少需要100名护士，然而目前只有80名，这就需要安排一部分人加班。设变量yt表示t时段开始工作并且需要加班2小时的护士人数,问题需要求的是满足服务需要，最小需要加班的人数，因此模型变为：t时段加班人数小于开始工作人数总人数限制各时段需求人数限制最优方案如下表，表中列示了各时段开始工作的人数及保时段需要加班的人数，最少需要加班人数为40人。案例4（固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单件耗量及组成三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。产品单件耗量资源123资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助0-1变量解决这个困难设xj是第j种产品的产量，j=1,2,3,再设则问题的整数规划模型为：M为很大的正数案例5（工件排序问题）用4台机床加工3件产品。各产品的机床加工顺序，以及产品i在机床j上的加工工时aij如下表。由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。产品1a11a13a14机床1机床3机床4产品2a21a22a24机床1机床2机床4产品3a32a33机床2机床3解：设xij表示产品i在机床j上开始加工的时间(i=1,2,3;j=1,2,3,4)下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间，故应有：产品1：及产品2：及产品3：2、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床1，有两种加工顺序。或先加工产品1，后加工产品2；或反之。对于其它3台机床，情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入0-1变量各yj的意义是明显的。如当yj=0时，表示机床1先加工产品1，后加工产品2，当yj=1时，表示机床1先加工产品2，后加工产品1。机床1：及机床2：及机床3：及机床4：及那么，每台机床上的加工产品的顺序可用下列四组约束条件来保证3、产品2的加工时间约束产品2的开始加工时间是x21，结束加工时间是x24+a24，故应有：4、目标函数的建立设全部产品加工完毕的结束时间为W，由于三件产品的加工结束时间分别为x14+a14，x24+a24，x33+a33，故全部产品的实际加工结束时间为：转化为线性表达式：0-1规划特别适合用在选址问题中某个公司准备投资一项大型的房地产开发项目，该项目是建造一个占地数平方英里的住宅小区。由于地球变暖的趋势越来越严重，小区如何预防火灾变得越来越重要。因此，公司需要解决的一个重要问题之一是如何布置两个消防站。为便于规划，整个小区分为5个区域，每个区域最多只能设一个消防站。每个消防站必须负责处理所处区域以及分配给该站的其他区域发生的火灾。这样，要作出的决策就包括：（1）消防站设在哪个区域？（2）将其他区域分配给某一个消防站。问题的目标是发生火灾之后平均的反应时间最短。下表给出的是将消防站建在各区域（行）的情况下，每个区域对火灾反应的平均时间，表中最后一行给出是各区域每天估计会发生火灾的平均次数。

案例6：消防站位置设置问题问题：（1）消防站设在哪个区域？（2）将其他区域分配给某一个消防站。目标是发生火灾之后平均的反应时间最短。下表给出的是将消防站建在各区域（行）的情况下，每个区域对火灾反应的平均时间，表中最后一行给出是各区域每天估计会发生火灾的平均次数。

消防站所在区域各区发生火灾后的反应时间(分)1234515123020152204151025315206151242515254105102515125每年平均发生火灾次数21313有一家大公司希望开设一些新的仓库，以向销售中心供货。每开设一个新仓库都有一些固定费用。货物将从仓库运输到附近的销售中心。每次运输的运费取决于运输的距离。这两种类型的费用非常不同：仓库开设费用属于投资支出，通常在若干年后将勾销，而运输费用属于运营成本。我们假定这两种费用可比，为此可能需要以年为单位计算运营费用。有12个可以建造新仓库的位置，并且需要从这些仓库向12个销售中心供货。下表给出了每个仓库完全满足每个客户（销售中心）需求所需的总成本（千欧元，不是单位成本）。因此，例如从仓库1向客户9（根据表3可以看到此客户总需求量为30吨）供货的单位成本为60000欧元/30吨，即2000欧元/吨。如果无法进行送货，则对应的成本标记为无穷大∞。仓库位置设置问题案例7：客户仓库12345678910111211008050506010012090607065110212090607065110140110808075130314011080807513016012510010080150416012510010080150190150130∞∞∞5190150130∞∞∞20018050∞∞∞6200180150∞∞∞10080505060100710080505060100120906070651108120906070651101401108080751309140110808075130160125100100801501016012510010080150190150130∞∞∞11190150130∞∞∞200180150∞∞∞12200180150∞∞∞10080505060100表格1：满足客户需求所需的运输成本此外，对每个仓库，还有如下信息：仓库建设的固定费用（需要计入目标函数）和仓库的容量上限，这些信息都列于表2中。表格2：仓库建设费用和容量限制仓库123456789101112建设费用350090001000040003000900090003000400010000900035000容量上限300250100180275300200220270250230180表3列出了各个销售中心（客户）的需求量客户123456789101112需求量120807510011010090603015095120任何时候都要保证满足客户需求，可以从多个仓库向同一个客户送货。应在哪些位置开办仓库才能使总的建设成本以及运输成本最低，同时仍然能够满足所有客户需求？分析决策变量：12个仓库中需要决策选择哪些仓库，

每个被选中的仓库运输给每个客户的运输量xij

目标：总成本=建设成本+运输成本

约束：仓库容量上限约束客户需求量约束只有当某一位置建设了仓库才能向客户运输产品数据处理最优方案更深入的问题：一个客户只允许由一个仓库共货，但一个仓库可供多个客户。案例8：所得税交纳点选址问题所得税管理部门计划对某个地区的所得税交纳点网络进行重新设计。下图是对此地区内的城市和主要道路的示意图。城市这边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米。为覆盖各城市，所得税管理部门决定在三个城市中设置纳税点。应在哪三个城市中设置纳税点才能使居民与最近的纳税点之间平均距离最小？12357101149612815221812221219192120243025192215182415101218242019221651311121235710114961281522181222121919212024302519221518241510121824201922165131112分析：首先要根据图求出任意两点之间的最短距离矩阵其次：确定纳税点选址，与消防站点设置问题相似将每一个居民点乘以其人数，得人数加权距离矩阵决策变量：yi第i个居民点设置为纳税点，xij第j个居民点的人到第i个纳税点交税目标总距离最小：wij人数，dij距离约束：设置纳税点3个每个居民点只能到一个纳税点交税每个居民点只能到设置了纳税点的地方交税最优方案：案例9：移动电话网络设计下图是一个典型的移动电话网络的结构图。每个基本地理区域，也称为一个蜂窝（cell），将由一个称为中继站的收发器提供服务。从一个移动电话拨出的电话呼叫将首先通过这些中继站。每个中继站都通过缆线或微波连接到一个中间结点（枢纽，hub）。其中有一个枢纽将对此网络进行控制，此枢纽即为MTSO(移动电话交换局)。将使用高带宽光纤缆线在各个枢纽与MTSO之间建立十分可靠的环路连接。如果发生故障，则此环路可以自动重建连接（自修复环路），因此不需要对其全部替换。●中继站蜂窝12个连接●中继站蜂窝21个连接枢纽4枢纽1枢纽3枢纽2交换局环路在目前的技术条件下，中继站和交换局之间无法进行动态连接。在设计阶段即应固定这些连接，因此需要为每个中继站选择其连接到的环路结点。在蜂窝c和环路之间的连接数目称为蜂窝c的多径数，用CNCTc表示。为使系统更为可靠，多径数应大于1。这种类型的系统中的通信是完全数字化的，通信带宽可以表示为带宽为64kbps（千比特每秒）的双向回路数目。则此带宽数值即对应于在高峰期可并发的通信数。环路的带宽上限为CAP。从蜂窝c发出的通信量TRAFc可以平均分配到蜂窝与环路之间的各个连接上，每个连接分配到的通信量为TRAFc/CNTCc。此通信量将通过环路传输到交换局，在交换局中将把各个呼叫转移到另一个蜂窝或移动电话与固定电话之间的接口结点。由于交换局具有普通枢纽的所有功能，因此中继站也可以直接连接到交换局。我们考虑到一个有10个蜂窝和5个结点组成的环路的网络，此网络的总带宽为CAP=90路电话。交换局为结点5。下表6列出了每个蜂窝的通话量，要求连接数，以及每个连接的成本（单位为千元）。例如蜂窝1连接到结点1，连接成本为15,000元。蜂窝1的多径数为2，这表示它至少应连接到环路中的两个结点上。此蜂窝的通话量为22路电话。目标是找出蜂窝与环路之间的连接方案，以最小化总连接费用，同时仍然能够满足通话量限制，并满足连接数要求。表6：每个蜂窝的连接成本，通话量，以及连接数

分析：决策变量：设Ccn表示蜂窝c连接到结点n的成本，xcn表示蜂窝c是否连接到结点n，则目标：连接成本最小约束：每个蜂窝的连接数等于需要的连接数通话能力（带宽）限制案例10