数学规划模型.doc

数 学 建 模 电 子 教 案第 1 教学周/星期五 /第 7、8 节/第 2 次课课 题 第二章 数学规划模型 2.1 线性规划模型 2.2 非线性规划模型教学内容1.线性规划模型的建立 2.线性规划模型的求解3. 非线性规划模型建立及求解教学目标1.使学生掌握基本的建立线性规划模型的方法2.能运用Matlab及Mathematica软件求解简单数学规划问题。教学重点 线性规划模型的实际应用教学难点 线性规划模型的理论讲解双语教学内容、安排Linear Programming 线性规划 subject to 约束Non-linear Programming 非线性规划教学手段、措施以板演为主,多媒体教学及课堂讨论为辅.作业、后记课后作业:43,1-2 教学过程及教学设计备注2.1 线性规划模型数学规划模型的一般表达式： 其中为目标函数，为约束函数，为可控变量，为已知参数，为随机参数。 数学规划分为线性规划、非线性规划、动态规划、整数规划等十几种。一线性规划的一般形式及其解的概念1.线性规划:通常把目标函数及约束都是线性表达式的规划问题称为线性规划，一般可表示为： ，则线性规划模型（1）可表示为矩阵的形式：2. 线性规划的可行解:满足约束条件的解；3.线性规划的最优解:使目标函数达到最优的可行解。二软件求解命令求解线性规划的软件很多，下面介绍Mathematica和MATLAB软件。（1）Mathematica命令可用于求解各种形式线性规划命令。 命令输入格式 c=c1x1+c2x2+cnxn；m=a11x1+a12x2+a1nxn=b1，am1x1+am2x2+amnxn=bm；ConstrainedMinc，m，x1,x2, ,xn （用于求极小）或Constrained-Maxc，m，x1,x2, ,xn（用于求极大）（2）MATLAB命令命令输入格式它用于求解线性规划模型：，x0是算法迭代的初始点可任意取，nEq表示等式约束的个数。三、模型示范 三 模型示范例1 、（ 生产组织与计划问题）某工厂计划生产甲、乙两种产品，主要材料有钢材3600kg、专用设备能力3000台时。材料与设备能力的消耗定额以及单位产品所获利润如下表所示，问如何安排生产，才能使该厂所获利润最大（只需建立数学模型）。单位产品消 产 甲（件） 乙（件） 现有材料与备 材料与设备 耗定额品 设备能力钢材（kg） 9 4 3600铜材（kg） 4 5 2000设备能力（台时） 3 10 3000单位产品的利润（元） 70 120建模过程： 设甲、乙两种产品计划生产量分别为，(件)，总的利润为(元)。求变量，的值为多少时，才能使总利润最大？建立数学模型： 例2、（营养配餐问题）每种蔬菜含有的营养素成份是不同的从医学上知道每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表61中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20千克，其它蔬菜的供应在一周内不多于40千克，每周共需供应140千克蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少千克？建模过程：设分别表示在下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，则费用的目标函数为：建立数学模型：0x140，0x240，0x340，0x420，0x540，0x640运用MATLAB程序求解得青豆40，胡罗卜40.0000，菜花0，白菜20.0000，甜菜0，土豆40，最小费用560.0000。 例3、（背包问题）有件物品，编号为。第件重为，价值为元。今一装包者欲将这些物品装入一包，其质量不能超过，问应装入哪几件价值最大？建模过程： 设， 建立模型： 例4、（投资场所的选定相互排斥的计划）某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）可供选择。规定 在东区，由三个点中至多选两个； 在西区，由两个点中至少选一个；在南区，由两个点中至少选一个。如选用点，设备投资估计为元，每年可获利润估计为元，但投资总额不能超过元。问应选择哪几个点可使年利润为最大？建模过程：引入变量，令 .建立模型： 2.2 非线性规划模型在数学规划问题中，当目标函数或约束函数中至少有一个是非线性函数时称这类问题为非线性规划。一、非线性规划的一般（标准）形式1.非线性规划：设均为上的实值函数，我们称为非线性规划的标准（一般）形式。2.可行域:如果令 称为可行域，则可（）写成简单形式3.无约束问题与约束问题：当时，称为无约束问题，否则称为约束问题。二模型示范例5、 某装饰材料公司欲以每桶2元的价钱购进一批彩漆。一般来说随着彩漆售价的提高，预期销售量将减少，并对此进行了估算，见表1。为了尽快收回资金并获得较多的赢利，装饰材料公司打算做广告，投入一定的广告费后，销售量将有一个增长，可由销售增长因子来表示。根据经验，广告费与销售增长因子关系见表2。现在的问题是装饰材料公司采取怎样的营销战略预期的利润最大？表1 表2建模过程：设x表示售价（单位：元），y表示预期销售量（单位：桶），z表示广告费（单位：元），k表示销售增长因子。投入广告费后，实际销售量记为s， 获得的利润记为P（单位：元）。由表1易见预期销售量y 随着售价x 的增加而单调下降，而销售增长因子k在开始时随着广告费z的增加而增加，在广告费z等于50000元时达到最大值，然后在广告费增加时反而有所回落，为此可用Mathematica画出散点图。运行之后，可显示图1，图2 图-1 图-2从图1和图2易见，售价与预期销售量近似于一条直线，广告费与销售增长因子k近似于一条二次曲线。为此可令： 系数是待定参数。建立模型： 模型求解： 首先利用Mathematica计算（1）（2）中的参数，并画出散点图和拟合曲线。文件名：ch622.ma f3=Fitd1,1,x,x f4=Plotf3,x,1,7Showf1,f4f5=Fitd2,1,x,x2,xf6=Plotf5,x,0,70000Showf2,f6运行之后，显示Out3= 50422.2-5133.33xOut5=1.01875+0.0000409226x-4.25595 10-10x2 图-3 图-4 及拟合曲线图-3和图-4。图-3 即： 其次用MATLAB求解优化模型，因MATLAB中仅能求极小值，为此将优化模型转化为且=5.9113，=33113，函数达到最大值16670。线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。线形规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。线性规划模型的求解方法目前仍以单纯形法为主要方法。对线性规划模型（1），求解结果有以下三种情况出现： 有最优解，即在可行解中能找到最优解。 有可行解，但无最优解。 无可行解，即不存在满足约束条件的解。背包问题看似简单，但应用很广，例如某些投资问题即可归入背包问题模型。当目标函数及约束函数是线性函数时，（）就变成（）。课 题 第二章 数学规划模型 2.3 多目标规划模型教学内容多目标模型的建立及求解。教学目标1.使学生掌握基本的建立多目标规划模型的方法。2.能运用Matlab及Mathematica软件求解简单非线性规划问题。教学重点多目标规划模型的实际应用教学难点多目标模型的理论讲解双语教学内容、安排Multiple objective Programming 多目标规划 subject to 约束教学手段、措施以板演为主,多媒体教学及课堂讨论为辅.作业、后记课后作业教学过程及教学设计备注2.3多目标规划模型一.多目标规划模型的一般形式为称之为多目标规划问题的数学模型。若记则上述模型可简记为二.模型示范 例1、投资收益和风险问题（这是全国大学生数学建模竞赛的A题）。市场上有种资产（股票、债券、） 供投资者选择，某公司有数额为的一笔相当大的资金可用作一个时间的投资。公司财务分析人员对种资产进行评估，估算在这一时期内购买有平均收益率为 ，并预测出购买的损失率为。考虑到投资分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的中的最大一个风险来度量。购买要付交易费，费率为,并且当购买额不超过给定值时，交易费按购买计算（不买当然无须付费）。另外，假定同期银行存款利率是,且既无交易费又无风险（）。 （1）已知时的相关数据如下：试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。（2）试就一般情况对以上问题进行讨论，利用以下数据进行计算。（%）（%）（%）（元）（元）9.6422.118118118.5543.240740749.4606.042842823.9421.55495498.11.27.627027014393.439739740.7685.617817831.233.433.122022033.653.32.747547536.8402.924824811.8315.119519595.55.732032035462.72672679.45.34.532832815237.6131131建模过程:1. 模型的假设及符号说明（1）模型的假设在一个时期内所给出的 保持不变。在一个时间内所购买的各种资产（如股票、证券等）不进行买卖交易，即在买入后不再卖出。每种投资是否收益是相互独立的。在投资过程中，无论盈利与否必须先付交易费。（2）符号说明（元）：公司现有投资总金额；（）：欲购买的第种资产种类（其中=0表示存入银行）；（）：（）:公司购买金额； （）：公司购买的平均收益率；()：公司购买的平均损失率；()：公司购买超过时所付交易费率。设购买的金额为，所付的交易费,令. 投资额相当大，所以总可以假定对每个的投资 ,这时（1）式可简化为 对投资的净收益 （3）对投资的风险 （4）对投资所需资金（投资金额与所需的手续费之和）即 (5)当购买的金额为（），投资组合的净收益总额 （6）整体风险： （7）资金约束： （8）2.数学模型为使净收益总额R（x）尽可能大，而整体风险Q（x）又尽可能小，则该问题的数学模型可归为多目标规划模型，即 （9） 假定投资者对风险收益的相对偏好参数为，则模型（9）可转化为： （10）将总收益与整体风险相比，则模型（9）可化为： (11)课 题 第二章 数学规划模型 2.4 动态规划模型教学内容动态规划模型的建立及求解 教学目标1.使学生掌握基本的建立动态规划模型的方法。2.能运用Matlab及Mathematica软件求解简单动态数学规划问题。教学重点 动态规划模型的实际应用教学难点 动态规划模型的理论讲解双语教学内容、安排 Dynamic Programming 动态规划 subject to 约束教学手段、措施以板演为主,多媒体教学及课堂讨论为辅.作业、后记课后作业:43,6-7 教学过程及教学设计备注2.4 动态规划模型 一最短路问题及其解法 如下图所示，称它为线路图（网络图）。B1B2C1C2C3C4D1D2D3EA53136876683533843221问题求一条从起点A到终点E的连通弧，使其总弧长最短最短路问题。2意义最短路问题的含义是很广泛的，如点代表加油站，弧代表管道，弧长代表铺设管道的费用。问题就变成让我们设计一条从起点A到终点E的管道，使其总费用最少。3特点 从A到E整个过程可分为从A到B（B有二种选择B1,B2）从B到C（C有四种选择C1，C2，C3，C4 ），从C到D（D有三种选择D1，D2，D3），在从D到E四个阶段，是一个多阶段决策问题。 每个阶段都有起点，用表示第K阶段的起点，并称为状态变量：每个阶段都有终点，前一段的终点就是后一段的起点。从每个起点出发（状态出发），都有若干选择（例如从B1出发有三种选择），用 表示从第K阶段的状态出发所作的选择并成为决策变量。决策变量全体成为决策集合（允许决策集合），即为。如果用表示从第K阶段的状态出发终点的最短弧长，或者用表示从起点到第K 阶段的状态的最短弧长，则问题就变成求或者求出。 4解法 逆序解法：从后向前逐步求出各阶段到终点E的最短路线与最短弧长，最后求出即从最后一个阶段K=4开始。逆序解法：求 K=3,有4个状态，每个状态又有两个决策可选取，所以有最短弧长为9，路径为 决策为 。类似地有K=2，有2个状态，每个状态又有3个决策可选，所以有 或 那么从A到E的最短弧长为14，路径为 。 决策为 上述解法的四个步骤可归纳为下述地推公式 其中。顺序解法：从前逐步求出从起点A到个阶段起点的最短弧长及其对应的路径。最后求出 。二动态规划的基本概念1. 多阶段决策问题，状态变量，允许决策变量，决策集合，最优函数 这些概念在前面的例中都已介绍过不再重复。需补充说明的是状态变量必须满足无后效性（即马尔科夫性）条件。即：给定某一阶段的状态，以后各阶段的行进不受以前个阶段状态的影响。 2. 阶段指标：用表示状态和状态间对应的指标，并称为阶段指标。 3. 策略：当每一阶段的策略都确定以后，由初始状态出发到终止状态每阶段的决策所构成的决策序列就成为一个整体策略，简称策略。记为 ，而 称为子策略。达到最优的策略成为最优策略。4.状态转移方程：把过程由一个状态变到另一个状态的变化叫做状态转移。它与状态有关，由与策略有关。逆序时，如