第一讲--线性规划和整数规划

第一部分：优化模型1、线性规划模型（算法：单纯形法）2、整数规划模型（算法：分枝定界法）3、非线性规划模型（化为线性规划求解）4、动态规划模型（算法：递归算法）5、多目标规划模型（化为线性规划求解）一、线性规划模型线性规划主要解决两个方面的问题：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？用线性规划方法解决问题一般按下列步骤进行第一步：建立线性规划模型；第二步：用单纯形算法进行求解；第三步：对求解结果进行检验；第四步：将求解结果形成优化方案，付诸实施；线性规划模型一般包括三个要素：（1）决策变量（2）目标函数（3）约束条件线性规划的一般形式为：max(或min)z=c1x1+c2x2+…+cnxn0,,,),(),(),(.2122212222222111212211nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats（1.1)（1.2)（1.3)或矩阵形式0Xb),(AXt.scxzmin)max(或其中c=(c1,c2,…,cn)，称为价值系数向量；aaaaaaaaamn2m1mn22221n11211A称为技术系数矩阵(也称消耗系数矩阵)m21bbbb称为资源限制向量,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.45x12x211.15x21x231.65x23x311.15x31x341.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年3111iiiypxSD第2…4年3111.032iiitttipxrSSD第5，6年33311,2(1)1.032iiitttipxrpxrSSD第7年3331(1)1.032ttpxrSD例题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季度销售的木材数。1600xxxx0xy2000yxxx2000xxx0xxy2000yxxxx1400xx0xxxy2000yxxx1000x0xxxxy2000y)y450x455()y460x438x465()y430x428x448x440()y410x438x423x425(max443424144444342414332313343333242314132212242322221413121114131211114443343322423221131211季度买进价（万元/万米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目标：生产成本与库存成本和最小121212111min30405ttttttZxyS约束：第一个月11112000xydS其它月份1tttttxySdS3000015000ttxy生产能力限制自行车生产规划正常正常生产加班加班生产可提供需求月份生产量能力生产量能力库存量总量总量预期销售量1月28,000=30,0000=15,000030,000=30,00030,0002月15,000=30,0000=15,000015,000=15,00015,0003月15,000=30,0000=15,000015,000=15,00015,0004月28,000=30,0000=15,0003,00028,000=28,00025,0005月30,000=30,0000=15,000033,000=33,00033,0006月