线性规划和整数规划.ppt

《线性规划和整数规划.ppt》由会员分享，可在线阅读，更多相关《线性规划和整数规划.ppt（93页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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%，并将本金收回，但该项投资

3、不得超过2万元；第种是在第二年的年初投资，第三年的年底可获利65%，并将本金收回，但该项投资不得超过1.5万元；第种是在第三年的年初投资，年底收回本金，且可获利35%，但该项投资不得超过1万元。现在本公司准备拿出3万元来投资，问如何计划可使到第三年年未本利和最大？解：问题分析。该问题的实际投资背景如下表所示：（1）确定决策变量：设xij表示第i年对第j个方案的投资额,i=1,2,3;j=1,2,3,4年份一二三四x111.15x11x121.45x12x211.15x21x231.65x23x311.15x31x341.35x34（2）确定目标函数：第三年年未的本利和为maxz=1.65x23

4、+1.15x31+1.35x34（3）确定约束条件：每一年的投资额应等于当年公司拥有的资金数：x11+x12=3x21+x23=1.15x11x31+x34=1.45x12+1.15x21每个方案投资额的限制：x122x231.5非负约束：xij0,i=1,2,3;j=1,2,3,4x341案例案例2 债券投资问题债券投资问题 国家农业银行国家农业银行(National Agricultural Bank,NAB)希望为十五名希望为十五名要提前退休的员工制定一项提前退休计划。这些员工将要在从明年要提前退休的员工制定一项提前退休计划。这些员工将要在从明年开始的七年内逐渐退休完。为了给这个提前退休

5、计划筹集资金，此开始的七年内逐渐退休完。为了给这个提前退休计划筹集资金，此银行决定在这七年期间进行债券投资。下表给出了每年应向这些提银行决定在这七年期间进行债券投资。下表给出了每年应向这些提早退休的员工支付的金额，这些金额必须在每年年初支付。早退休的员工支付的金额，这些金额必须在每年年初支付。年年1234567金额（千欧元）金额（千欧元）10006006404807601020950表：每年要求金额表：每年要求金额 此银行计划购买三种不同的债券，即此银行计划购买三种不同的债券，即SNCF公司（法国国营铁路公司（法国国营铁路公司）的债券，公司）的债券，Fujutsu（富士通）公司债券，以及国债。

6、未投资于富士通）公司债券，以及国债。未投资于这些债券的资金将作为储蓄保存，储蓄的利率为这些债券的资金将作为储蓄保存，储蓄的利率为3.2%,下表列出了下表列出了各个债券的收益各个债券的收益,时间长度时间长度,以及价格等信息以及价格等信息.这些债券只能按整数这些债券只能按整数数目进行购买数目进行购买,并且一旦购买之后在债券期限内即无法更改投资金并且一旦购买之后在债券期限内即无法更改投资金额额.每年只返回投资的利息每年只返回投资的利息.此退休计划的负责人决定只在第一年年此退休计划的负责人决定只在第一年年初初购买债券购买债券,而在此后的几年内不再购买而在此后的几年内不再购买,应该如何分配在各个债券应该

7、如何分配在各个债券的投资金额才能使得只需要花费最少的资金就能够满足此退休计划的投资金额才能使得只需要花费最少的资金就能够满足此退休计划的要求的要求?债券债券价值价值(千欧元千欧元)利率利率期限期限SNCFFujitsu国债国债1.00.80.57.0%7.0%6.5%5年年4年年6年年表表:债券信息债券信息分析：分析：决策变量：初始投资决策变量：初始投资y，债券购买量债券购买量xi，每年的储蓄量每年的储蓄量StP债券价格，债券价格，Dt每年资金需求，每年资金需求，ri-债券利率债券利率第第1年年第第24年年第第5，6年年第第7年年例题例题3：养老金管理问题：养老金管理问题 华信金融公司管理的金

8、融产品中有一只很受赞誉的养老基金，这些养老基金是很多公司用来为其雇员提供养老金的，华信公司希望能够进行合理的投资来保证养老金的供应。现在是2007年的12月了，在接下去的10年中需要支付的总的养老金如表所示：表：表：未来十年的养老金需求未来十年的养老金需求年份年份需要支付的养老金（万美元）需要支付的养老金（万美元）2008800200912002010130020111400201216002013170020142000201521002015220020162400为了使养老基金的提供有安全保证，华信公司希望投资在能够与未来10年中的养老金支付相匹配的项目。养老基金管理中心授权华信公司的投

9、资项目只能是资本市场基金和债券。资本市场基金获得每年固定的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日的利息支付获得正好

10、能够用来冲抵当年养老金的支付，所有多余的利息收入将存入资本市场基金。为金融计划的保守起见，华信公司假定所有的养老金支付在每年的年初，正好在利息收入(包括资本市场基金的利息收入)获得之后，债券的面值也将在到期日获得。既然当前的债券价格低于面值，真正的债权的收益比利息率要高。如债券3是一个零利息率的债券，所以每年得到的利息为0，但是到到期日获得的面值要远大于当年债券的购得价格。华信公司希望在2008年1月1日用最小可能的投资(包括市场基金的存款)来应付到2016年为止的所有所需的养老金的支付，请对此问题进行分析，并求出最优投资方案。例题例题4：定额投资问题：定额投资问题 通用公司的董事会正在考虑几

11、个大型的投资项目，每个项目只能投资一次，且各项目所需要的投资金额与能够产生的预期收益是不同的，如表所示：表：投资额及预期收益表：投资额及预期收益 投投资项资项目目预预期收益（百万美元）期收益（百万美元）所需所需资资金（百万美元）金（百万美元）117432102831534419485717613327923假设公司现有的总投资金额为1亿美元，其中投资项目1和项目2是互斥的，项目3与项目4也是互斥的。此外，如果不选择项目1或是项目2的话，就不能选择项目3、4。投资项目5、6、7上没有附加约束。问题的目标是通过组合各种投资，使得估计的预期收益最大。解：解：例例题题5（合理下料问题）要用一批长度为7

12、.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）确定目标函数：问题要求所

13、用原料最省，所用原料为：minz=x1+x2+x3+x4+x5+x6+x7+x8（3）确定约束条件：2.9米园钢的数量限制x1+x2+x3+2x41002.1米园钢的数量限制2x1+x3+x5+2x6+3x71001.5米园钢的数量限制3x2+x3+x4+3x5+2x6+4x3100非负限制xj0，且为整数，j=1,2,8建立线性规划模型的一般步骤：（1）确定决策变量；（2）确定目标函数；（3）确定约束条件。例题例题6一个木材储运公司有很大的仓库用以储运出售木材。由于一个木材储运公司有很大的仓库用以储运出售木材。由于木材季度价格的变化，该公司于每季度初购进木材，一部分于本季木材季度价格的变化，

14、该公司于每季度初购进木材，一部分于本季度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存度内出售，一部分储存起来以后出售。已知该公司仓库的最大储存量为量为2000万米万米3，储存费用为（，储存费用为（70+100u）千元千元/万米万米3，u为存储时间为存储时间（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。（季度数）。已知每季度的买进卖出价及预计的销售量如下表所示。季度季度买进价（万元买进价（万元/万米万米3）卖出价（万元卖出价（万元/万米万米3）预计销售量（万米预计销售量（万米3）冬冬4104251000春春4304401400夏夏4604652000秋秋45045516

15、00由于木材不宜久贮，所有库存木材应于每年秋末售完。为由于木材不宜久贮，所有库存木材应于每年秋末售完。为使售后利润最大，试建立这个问题的线性规划模型。使售后利润最大，试建立这个问题的线性规划模型。设设yi分别表示冬、春、夏、秋四个季度采购的木材数，分别表示冬、春、夏、秋四个季度采购的木材数，xij代代表第表第i季度采购的用于第季度采购的用于第j季度销售的木材数。季度销售的木材数。季季度度买进价买进价（万元（万元/万万米米3）卖出价卖出价（万元（万元/万万米米3）预计销售预计销售量（万米量（万米3）冬冬4104251000春春4304401400夏夏4604652000秋秋4504551600例

16、题例题7 自行车生产规划问题自行车生产规划问题有有一家公司生产儿童自行车。在下表中给出了明年预期的销售量一家公司生产儿童自行车。在下表中给出了明年预期的销售量（以千辆为单位计）。此公司的生产能力为每个月（以千辆为单位计）。此公司的生产能力为每个月30000辆自行车。辆自行车。通过工人加班，可以将产量提高通过工人加班，可以将产量提高50%，但会将每辆自行车的生产成，但会将每辆自行车的生产成本从本从30欧元提高到欧元提高到40欧元。欧元。表：表：明年的销售预期（千辆）明年的销售预期（千辆）1月月2月月3月月4月月5月月6月月7月月8月月9月月10月月11月月12月月3015152533404545

17、26142530当前自行车的库存量为当前自行车的库存量为2000辆，对于库存中的每辆自行车，在每个辆，对于库存中的每辆自行车，在每个月月底都需要支出月月底都需要支出5欧元的存储费用。我们假定此公司的库存能力欧元的存储费用。我们假定此公司的库存能力是无限的。现在是一月一日，在下面的十二个月里面每个月应生产是无限的。现在是一月一日，在下面的十二个月里面每个月应生产和存储多少辆自行车才能满足此销售预期，并最小化总成本？和存储多少辆自行车才能满足此销售预期，并最小化总成本？分析：分析：决策变量：设决策变量：设t时间内的正常工作时间内和加班时间内生产的自时间内的正常工作时间内和加班时间内生产的自行车数量

18、分别为行车数量分别为xt，yt,每个月月底时库存的自行车数量为每个月月底时库存的自行车数量为St 目标：生产成本与库存成本和最小目标：生产成本与库存成本和最小约束：约束：第一个月第一个月其它月份其它月份生产能力限制生产能力限制最优最优方案如下：方案如下：例题例题8 8：计算机生产问题计算机生产问题案例概述：案例概述：SytechSytech 国国际际公公司司是是一一家家在在同同行行业业中中处处于于领领先先地地位位的的计计算算机机和和外外围围设设备备的的制制造造商商。公公司司的的主主导导产产品品分分类类如如下下：大大型型计计算算机机（MFRAMESMFRAMES）、小小型型计计算算机机（MINI

19、SMINIS）、个个人人计计算算机机（PCSPCS）、和和打打印机（印机（PRINTERSPRINTERS）。）。公司的两个主要市场是北美和欧洲。公司的两个主要市场是北美和欧洲。公司一直按季度作出公司最初的重要决策。公司必须按照营销公司一直按季度作出公司最初的重要决策。公司必须按照营销部门的需求预测来对分布在全球的三个工厂调整产量，公司下一季部门的需求预测来对分布在全球的三个工厂调整产量，公司下一季度需求预测如下：度需求预测如下：而公司的三个工厂的生产能力限度又使得其不能随心所欲地在任而公司的三个工厂的生产能力限度又使得其不能随心所欲地在任一工厂进行生产，限制主要是各工厂规模及劳动力约束。一工

20、厂进行生产，限制主要是各工厂规模及劳动力约束。最终分析所要求的数据由会计部门提供，下表所显示的数据表示单最终分析所要求的数据由会计部门提供，下表所显示的数据表示单位利润贡献（税后）：位利润贡献（税后）：根据以上信息，为根据以上信息，为SYTECHSYTECH公司建立了一个线性优化模型，帮助其进公司建立了一个线性优化模型，帮助其进行生产决策。行生产决策。解：解：例题例题9：蔗糖生产计划蔗糖生产计划 在澳大利亚甘蔗的收割已经实现了高度机械化。甘蔗在砍下之后将马上通过运行于小型铁路网上的货车运送到蔗糖厂。一辆货车的运量、能够生产的蔗糖取决于甘蔗收购的地点以及甘蔗成熟的程度。在收割之后，甘蔗中的含糖量

21、将由于发酵而迅速下降，在一段时间之后，所含糖份将完全流失。现在有11辆货车到达了蔗糖厂，每辆货车运载的甘蔗量都相同。已经对每辆货车每小时的损失量以及剩余时间进行了测算，具体数据如表所示。表表 每车甘蔗属性每车甘蔗属性货车编货车编号号1234567891011损损失率（千克失率（千克/小小时时）4326372813546249192830剩余剩余时间时间88284888888在制糖厂内有三条生产线，每辆货车都可以选择在哪条生产线上进行加工。一车甘蔗的加工时间为两个小时。必须在这车甘蔗的质量寿命结束之前完成加工。制糖厂的经理希望找出一个生产计划，使总的蔗糖损失降到最低。货车编货车编号号123456

22、7891011损损失率（千克失率（千克/小小时时）4326372813546249192830剩余剩余时间时间88284888888表表 每车甘蔗属性每车甘蔗属性解：解：例题例题10：石油精炼问题石油精炼问题 石油精炼厂将使用两种原油生产出丁烷(butane)，汽油(petrol)，柴油(dieseloil)，以及民用燃料油(heating oil)。为生产出这些产品，需要四道工序：分离、转化、提纯、混合。在分离工序中将把原材料进行分馏，使其分离为丁烷(butane)、石脑油(naphtha)、轻柴油(gasoil)、以及残渣。残渣然后将进行催化裂解以获得较轻的产品。从分馏工序得到的各种产品将

23、进行提纯(脱硫)，或通过重整工艺增加其辛烷值。最终，为获得可以出售的最终产品，精炼厂需要将若干种中间产物进行混合，以满足商业产品所要求的各种属性。下图中是对此精炼厂的生产过程的简单的示意图。石油精炼流程图石油精炼流程图 在分馏之后，原油1能够得到3%的丁烷，15%的石脑油，40%的轻柴油，以及15%的残渣。原油2能够得到5%的丁烷，20%的石脑油，25%的轻柴油，以及10%的残渣。对石脑油进行重整能够得到5%的丁烷和85%的重整油(重整石脑油)。对残渣的催化裂解可以生成45%的裂解石脑油和35%的裂解轻柴油(注意，由于在此工艺中也将生成15%的气体和5%的石油焦以及其他另一种无法计入我们的问题

24、中的残余物，因此这两个百分比之和不等于1)。汽油由三种成分混合而成：重组石脑油(重组油)，丁烷，以及裂解石脑油。柴油可以通过将脱硫轻柴油，裂解轻柴油，以及裂解石脑油混合得到。民用燃料油由轻柴油及裂解石脑油组成，对其成分含量没有要求。法律规定了一些汽油和柴油的规格指标。对于汽油有三项重要指标：辛烷值，蒸汽压，以及挥发性。辛烷值是对汽油的抗爆能力的度量。蒸汽压能够反映出汽油储存过程中发生爆炸的风险，尤其在炎热气候条件下。挥发性能够决定在寒冷气候条件下发动机是否能够容易启动。空气污染法规对柴油的含硫量进行了规定。表2-19中列出了最终产品的规格指标和中间产品的成分组成。如果对某一项没有限制，则对应在

25、域保留为空。我们假定所有这些成分都将按照质量线性混合(实际上只有含硫量才如此)。表表 中间产物和最终产品规格属性中间产物和最终产品规格属性规规格格丁丁烷烷重整油重整油裂解石裂解石脑脑油油裂解裂解轻轻柴柴油油去硫去硫轻轻柴柴油油汽油汽油柴油柴油辛辛烷值烷值12010074=94蒸气蒸气压压602.64.1=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吨

26、，裂解工艺每月加工能力为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案例

27、案例11、有一艘货轮，分前、中、后三个舱位，它们的容积与最大有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表允许载重量如表1所示。现有三种货物待运，已知有关数据列于表所示。现有三种货物待运，已知有关数据列于表2。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱。为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载最大允许载重量的比例关系，具体要求前、后舱分别与中舱之间载重量比例上偏差不超过重量比例上偏差不超过15%，前、后舱之间不超过，前、后舱之间不超过10%。问该货轮。问该货轮应装载应装载A，B，C各多少件

28、，运费收入为最大？试建立这个问题的线各多少件，运费收入为最大？试建立这个问题的线性规划模型。性规划模型。前舱前舱中舱中舱后舱后舱最大允许载重量（吨）最大允许载重量（吨）200030001500容积（立方米）容积（立方米）400054001500表1商品商品数量（件）数量（件）每件每件体积（立方米体积（立方米/件）件）每件每件重量（吨重量（吨/件）件）运运价（元价（元/件）件）A6001081000B100056700C80075600设设表示表示xij装于第装于第j(j=1,2,3)舱位的第舱位的第i(i=1,2,3)种商品的数量种商品的数量舱位载重限制舱位体积限制商品数量限制平衡条件前舱前舱

29、 中舱中舱 后舱后舱重重量量200030001500容容积积400054001500商商品品数量数量 体体积积重重量量运运价价A6001081000B100056700C80075600案例案例12.(仓库租用问题仓库租用问题)捷运公司拟在下一年度的捷运公司拟在下一年度的1-4月的月的4个月内个月内需租用仓库堆放物资需租用仓库堆放物资.已知各月份所需仓库面积数列于表已知各月份所需仓库面积数列于表1.仓库租借仓库租借费用随合同期而定费用随合同期而定,期限越长期限越长,折扣越大折扣越大,具体数字见表具体数字见表2.租借仓库的租借仓库的合同每月初都可办理合同每月初都可办理,每份合同具体规定租用面积数

30、和期限每份合同具体规定租用面积数和期限.因此该因此该厂可根据需要厂可根据需要,在任何一个月初办理租借合同在任何一个月初办理租借合同.每次办理时可签一份每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同也可签若干份租用面积和租借期限不同的合同,试确定该公司签订试确定该公司签订租借合同的最优决策租借合同的最优决策,目的是使所付租借费用最小目的是使所付租借费用最小.月份1234所需仓库面积(100m2)15102012表表1合同租借期限1个月2个月3个月 4个月仓库借费用(元/100m2)2800450060007300表表2解解:1)设决策变量设决策变量xij表示捷运公司在第表示捷运公司

31、在第i(I=1,2,3,4)个月初签个月初签订的租借期为订的租借期为j(j=1,2,3,4)个月的仓库面积的合同个月的仓库面积的合同(单位为单位为100m2).因因5月份起该公司不需要租借仓库月份起该公司不需要租借仓库,故故x24,x33,x34,x42,x43,x44均为零均为零2)目标函数目标函数:使总的租借费用最小使总的租借费用最小3)约束条件约束条件:每个月份所需仓库面积的限制每个月份所需仓库面积的限制二、二、整数规划模型整数规划模型案例案例1 某单位有某单位有5个拟选择的投资项目，其所需投资额与期望收益个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，如下表

32、。由于各项目之间有一定联系，A、C、E之间必须选择一之间必须选择一项且仅需选择一项；项且仅需选择一项；B和和D之间需选择也仅需选择一项；又由于之间需选择也仅需选择一项；又由于C和和D两项目密切相关，两项目密切相关，C的实施必须以的实施必须以D的实施为前提条件，该单的实施为前提条件，该单位共筹集资金位共筹集资金15万元，问应该选择哪些项目投资，使期望收益最万元，问应该选择哪些项目投资，使期望收益最大？大？项目所需投资额（万元）期望收益（万元）A610B48C27D46E59解：决策变量：设目标函数：期望收益最大约束条件：投资额限制条件6x1+4x2+2x3+4x4+5x515项目A、C、E之间必

33、须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：案例案例2 某服务部门各时段（每某服务部门各时段（每2小时为一时段）需要的服务员人数小时为一时段）需要的服务员人数如下表，按规定，服务员连续工作如下表，按规定，服务员连续工作8小时（即四个时段）为一班，小时（即四个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。现要求安排服务员的工作时间，使服务部门服务员总数最小。时段时段12345678服务员最少数目服务员最少数目10891113853解：设在第解：设在第j时段开始时

34、上班的时段开始时上班的服务员人数为服务员人数为xj，由于第由于第j时段时段开始时上班的服务员将在第开始时上班的服务员将在第(j+3)时段结束时下班，故决策时段结束时下班，故决策变量只需考虑变量只需考虑x1,x2,x3,x4,x5，此此问题的数学模型为：问题的数学模型为：案例案例3：护士工作时间调度问题护士工作时间调度问题 Mr.Schedule 先生受人之托要为先生受人之托要为 St.Joseph医院的心脑血管部门医院的心脑血管部门制定护士的工作时间表。在心脑血管部门中一个工作日分为制定护士的工作时间表。在心脑血管部门中一个工作日分为12个两个两小时长的时段，每个时段的人员要求都不同。例如，在

35、夜间只要求小时长的时段，每个时段的人员要求都不同。例如，在夜间只要求有很少的几个护士就足够了，但是在早晨为了给病人提供特殊服务，有很少的几个护士就足够了，但是在早晨为了给病人提供特殊服务，需要很多护士。下表列出了每个时段的人员需求量。需要很多护士。下表列出了每个时段的人员需求量。编号编号时段时段需要护士人数需要护士人数0123456789101100am-02am02am-04am04am-06am06am-08am08am-10am10am-12pm12pm-02pm02pm-04pm04pm-06pm06pm-08pm08pm-10pm10pm-12am151515354040403031

36、353020问题问题1：请计算出为满足需求最少需要多少护士，假定已知护：请计算出为满足需求最少需要多少护士，假定已知护士每天工作士每天工作8小时，且在工作四小时后需要休息两小时。小时，且在工作四小时后需要休息两小时。问题问题2：此部门目前只有：此部门目前只有80名护士，这个数目不足以满足给定名护士，这个数目不足以满足给定的需求。因此的需求。因此Schedule先生建议每天安排部分人加班。每天加先生建议每天安排部分人加班。每天加班时间为班时间为2小时，且紧随在后一个四小时工作时段之后，中间小时，且紧随在后一个四小时工作时段之后，中间没有休息。请给出护士工作时间安排方案，以使需要加班的护没有休息。

37、请给出护士工作时间安排方案，以使需要加班的护士数目最少。士数目最少。分析：设分析：设xt为为时段时段t开始工作的护士数目开始工作的护士数目问题问题1模型模型最优最优方案方案 由此我们看到，第由此我们看到，第1问题求出的最优解为至少需要问题求出的最优解为至少需要100名护士，名护士，然而目前只有然而目前只有80名，这就需要安排一部分人加班。名，这就需要安排一部分人加班。设变量设变量yt表示表示t时段开始工作并且需要加班时段开始工作并且需要加班2小时的护士人数小时的护士人数,问问题需要求的是满足服务需要，最小需要加班的人数，因此模型变为：题需要求的是满足服务需要，最小需要加班的人数，因此模型变为：

38、t时段加班人数时段加班人数小于开始工作小于开始工作人数人数总人数限制总人数限制各时段需求各时段需求人数限制人数限制最优方案如下表，表中列示了各时段开始工作的人数及保时段需最优方案如下表，表中列示了各时段开始工作的人数及保时段需要加班的人数，最少需要加班人数为要加班的人数，最少需要加班人数为40人。人。案例案例4 （固定费用问题）有三种资源被用于生产三种产品，资源量、（固定费用问题）有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单件耗量及组成三种产品生产的固定产品单件可变费用售价、资源单件耗量及组成三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。费用见下表。要

39、求制定一个生产计划，使总收益最大。产产品品 单件耗量单件耗量资源资源123资源量资源量A248500B234300C123100单件单件可变费用可变费用456固定费用固定费用100150200单件单件售价售价81012解：总收益等于销售收入减去生产上述产品的固定费用和解：总收益等于销售收入减去生产上述产品的固定费用和可变费用之和。建模碰到的困难主要是事先不能确切知道可变费用之和。建模碰到的困难主要是事先不能确切知道某种产品是否生产，因而不能确定相应的固定费用是否发某种产品是否生产，因而不能确定相应的固定费用是否发生。下面借助生。下面借助0-1变量解决这个困难变量解决这个困难设设xj是第是第j种

40、产品的产量，种产品的产量，j=1,2,3,再设再设则问题的整数规划模型为：则问题的整数规划模型为：M为很大为很大的正数的正数案例案例5 （工件排序问题）用（工件排序问题）用4台机床加工台机床加工3件产品。各产品的机床加件产品。各产品的机床加工顺序，以及产品工顺序，以及产品i在机床在机床j上的加工工时上的加工工时aij如下表。由于某种原因，如下表。由于某种原因，产品产品2的加工总时间不得超过的加工总时间不得超过d，现要求确定各件产品在机床上的加现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。工方案，使在最短的时间内加工完全部产品。产品产品1a11 a13 a14 机床机床1

41、 机床机床3 机床机床4 产品产品2a21 a22 a24机床机床1 机床机床2 机床机床4产品产品3 a32 a33 机床机床2 机床机床3解：设解：设xij表示产品表示产品i在机床在机床j上开始加工的时间上开始加工的时间(i=1,2,3;j=1,2,3,4)下面将逐步列出问题的整数规划模型下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时间不得早于在对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间，故应有：上一台机床上加工的约束时间，故应有：产品产品1：及及

42、产品产品2：及及产品产品3：2、每一台机床对不同产品的加工顺序约束、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，则不能一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床开始另一件产品的加工。对于机床1，有两种加工顺序。或，有两种加工顺序。或先加工产品先加工产品1，后加工产品，后加工产品2；或反之。对于其它；或反之。对于其它3台机床，台机床，情况也类似。为了容纳两种相互排斥的约束条件，对于每情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入台机床，分别引入0-1变量变量各各yj的意义是明显的。如当的意义是明显的。如当

43、yj=0时，表示机床时，表示机床1先加工产品先加工产品1，后加工产品，后加工产品2，当，当yj=1时，表示机床时，表示机床1先加工产品先加工产品2，后加，后加工产品工产品1。机床机床1：及及机床机床2：及及机床机床3：及及机床机床4：及及那么，每台机床上的加工产品的顺序可用下列四组约束条件来保那么，每台机床上的加工产品的顺序可用下列四组约束条件来保证证3、产品、产品2的加工时间约束的加工时间约束产品产品2的开始加工时间是的开始加工时间是x21，结束加工时间是结束加工时间是x24+a24，故应有：故应有：4、目标函数的建立、目标函数的建立设全部产品加工完毕的结束时间为设全部产品加工完毕的结束时间

44、为W，由于三件产品的加工结束时由于三件产品的加工结束时间分别为间分别为x14+a14，x24+a24，x33+a33，故故全部产品的实际加工结束时间全部产品的实际加工结束时间为：为：转化为线性表达式：转化为线性表达式：0-1规划特别适合用在选址问题中规划特别适合用在选址问题中 某某个个公公司司准准备备投投资资一一项项大大型型的的房房地地产产开开发发项项目目，该该项项目目是是建建造造一一个个占占地地数数平平方方英英里里的的住住宅宅小小区区。由由于于地地球球变变暖暖的的趋趋势势越越来来越越严严重重，小小区区如如何何预预防防火火灾灾变变得得越越来来越越重重要要。因因此此，公公司司需需要要解解决决的的

45、一一个个重重要要问问题题之之一一是是如如何何布布置置两两个个消消防防站站。为为便便于于规规划划，整整个个小小区区分分为为5个个区区域域，每每个个区区域域最最多多只只能能设设一一个个消消防防站站。每每个个消消防防站站必必须须负负责责处处理理所所处处区区域域以以及及分分配配给给该该站站的的其其他他区区域域发发生生的的火火灾灾。这这样样，要要作作出出的的决决策策就就包包括括：（1）消消防防站站设设在在哪哪个个区区域域？（2）将将其其他他区区域域分分配配给给某某一一个个消消防防站站。问问题题的的目目标是发生火灾之后平均的反应时间最短。标是发生火灾之后平均的反应时间最短。下表给出的是将消防站建在各区域（

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

47、，表中最后一行给出是各区域每天估计会发对火灾反应的平均时间，表中最后一行给出是各区域每天估计会发生火灾的平均次数。生火灾的平均次数。消防站所在区域消防站所在区域各区发生火灾后的反应时间各区发生火灾后的反应时间(分分)1234515123020152204151025315206151242515254105102515125每年平均发生火灾次每年平均发生火灾次数数21313 有一家大公司希望开设一些新的仓库，以向销售中心供货。每开有一家大公司希望开设一些新的仓库，以向销售中心供货。每开设一个新仓库都有一些固定费用。货物将从仓库运输到附近的销售设一个新仓库都有一些固定费用。货物将从仓库运输到附近

48、的销售中心。每次运输的运费取决于运输的距离。这两种类型的费用非常中心。每次运输的运费取决于运输的距离。这两种类型的费用非常不同：仓库开设费用属于投资支出，通常在若干年后将勾销，而运不同：仓库开设费用属于投资支出，通常在若干年后将勾销，而运输费用属于运营成本。我们假定这两种费用可比，为此可能需要以输费用属于运营成本。我们假定这两种费用可比，为此可能需要以年为单位计算运营费用。年为单位计算运营费用。有有12个可以建造新仓库的位置，并且需要从这些仓库向个可以建造新仓库的位置，并且需要从这些仓库向12个个销售中心供货。下表给出了每个仓库完全满足每个客户（销售中心）销售中心供货。下表给出了每个仓库完全满

49、足每个客户（销售中心）需求所需的总成本（千欧元，不是单位成本）。因此，例如从仓库需求所需的总成本（千欧元，不是单位成本）。因此，例如从仓库1向客户向客户9（根据表（根据表3可以看到此客户总需求量为可以看到此客户总需求量为30吨）供货的单位吨）供货的单位成本为成本为60000欧元欧元/30吨，即吨，即2000欧元欧元/吨。吨。如果无法进行送货，则对应的成本标记为无穷大如果无法进行送货，则对应的成本标记为无穷大。仓库位置设置问题仓库位置设置问题案例案例7：客户客户仓库仓库 1 2 3 4 5 6 7 8 9 10 11 12 1 100 80 50 50 60 100 120 90 60 70 6

50、5 110 2 120 90 60 70 65 110 140 110 80 80 75 130 3 140 110 80 80 75 130 160 125 100 100 80 150 4 160 125 100 100 80 150 190 150 130 5 190 150 130 200 180 50 6 200 180 150 100 80 50 50 60 100 7 100 80 50 50 60 100 120 90 60 70 65 110 8 120 90 60 70 65 110 140 110 80 80 75 130 9 140 110 80 80 75 130 1