线性规划和整数规划.ppt

《线性规划和整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、决策变量（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万元；第Ⅲ种是在第二年的年

3、初投资，第三年的年底可获利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.15x3

4、1+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)希望为十五名要提前退休的员工制定一项提前退休计划。这些员工将要在从明年开始的七年内逐渐退休完。为了给这个提前退休计划筹集资金，此银行决定在这七年期间进行债券投资。下表给出了每年应向这些提早退休的员工支付的金

5、额，这些金额必须在每年年初支付。年1234567金额（千欧元）10006006404807601020950表：每年要求金额此银行计划购买三种不同的债券，即SNCF公司（法国国营铁路公司）的债券，Fujutsu（富士通）公司债券，以及国债。未投资于这些债券的资金将作为储蓄保存，储蓄的利率为3.2%,下表列出了各个债券的收益,时间长度,以及价格等信息.这些债券只能按整数数目进行购买,并且一旦购买之后在债券期限内即无法更改投资金额.每年只返回投资的利息.此退休计划的负责人决定只在第一年年初购买债券,而在此后的几年内不再购买,应该如何分配在各个债券的投资金额才能使得只需要花费最少的

6、资金就能够满足此退休计划的要求?债券价值(千欧元)利率期限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年中需要支付的总的养老金如表所示：表：未来十年的养老金需求年份需要支付的

7、养老金（万美元）2008800200912002010130020111400201216002013170020142000201521002015220020162400为了使养老基金的提供有安全保证，华信公司希望投资在能够与未来10年中的养老金支付相匹配的项目。养老基金管理中心授权华信公司的投资项目只能是资本市场基金和债券。资本市场基金获得每年固定的5%的利息收入，公司所考虑投资的四只债券的特征如表3-7所示。表：四种债券的信息债券当前价格（美元）年利息率到期日面值（美元）债券19804%2009