数学建模算法与应用-线性规划.ppt

1、第2章 线性规划,数学建模算法与应用,应用场景_成功的优化例子,“最优人员安排”为美国航空每年节约两千万美元.,“改进的出货流程”每年为Yellow Freight 公司节约一千七百多万美元.,应用场景_成功的优化例子,“改进的卡车分派”为 Reynolds 公司每年节约七百万美元 .,应用场景_成功的优化例子,“最优全局供应链”为数字设备行业节约超过三亿美元.,应用场景_成功的优化例子,大阪Hanshin高速的 “最优交通控制”每年节约一千七百万小时 ,为他们带来三亿二千万美圆的收益.,应用场景_成功的优化例子,数学规划,线性规划(LP)二次规划(QP)非线性规划(NLP),纯整数规划(PI

2、P)混合整数规划(MIP),整数规划(IP),0-1整数规划一般整数规划,连续规划,如何利用现有资源安排生产，以取得最大经济效益的问题数学规划,实际问题中的优化模型,x是决策变量,f(x)是目标函数,gi(x)0是约束条件,优化模型的分类,其中：,1.1.1 线性规划的实例与定义,1.1 线性规划问题,目标函数及约束条件均为线性函数，故被称为线性规划问题(Linear Programming,LP)。线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。,一般研究的问题：（1）给定了一定的人力、物力、财力，如何应用这些资源获得最大的经济效益；（2）给定了一项任务，如果统筹

3、安排才能以最小的资源去完成它。,方法：图解法或单纯形法,线性规划的组成要素：目标函数 Max F 或 Min F约束条件 s.t. (subject to) 满足于决策变量 用符号来表示可控制的因素建模步骤1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（ x1 ，x2 ， ，xn ），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。,1.1.2 线性规划问题的标准型,模 型 转 换,目标转换,变量转换,（1）等式变不等式,约束转换,（2）不 等 式 变 等 式,松弛变量,

4、剩余变量,（3）不等式变不等式,把问题转化为标准形式,1.1.3 线性规划的Matlab标准形式及软件求解,1.1.4 可以转化为线性规划问题的模型,例1.4 数学规划问题： 式中： ；A和b 为相应维数的矩阵和向量。,例1.5 求解下列数学规划问题：,计算的MATLAB程序如下：,clc, clear c=1:4;c=c,c；%构造价值列向量a=1 -1 -1 1;1 -1 1 -3;1 -1 -2 3；a=a,-a；%构造变换后新的系数矩阵b=-2 -1 -1/2；y,z=linprog(c,a,b,zeros(8,1)%这里没有等式约束，对应的矩阵为空矩阵x=y(1:4)-y(5:end

5、)%变换到原问题的解，x=u-v,运价表（元/T）,表1,例1.6 现有A1，A2，A3三个产粮区，可供应 粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表1所示. 问如何安排一个运输计划，使总的运输费用最少。,解：设 xij (i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，则运输费用为：,从产粮区运出去的量,运给需求地的量,这样得到下列运输问题的数学模型：,运输问题的一般数学模型,设有m个产地（记作A1，A2，A3,Am），生产某种物资，其产量分别为a1,a2，am；

6、有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即 。从第i个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设 xij (i=1,2,，m；j=1,2,n)为第i个产地到第j个销地的运量，则数学模型为：,1,产销平衡,2.当产大于销时,数学模型为,即,2.当销大于产时,即,数学模型为,1.2 投资的收益和风险,1.2.1 问题提出,1.2.2 符号规定和基本假设,1.2.3 模型的分析与建立,1.2.4 模型一的求解,1.2.5 结果分析,第3章 整数规划,数学建模算法与应用,2.1 概论,1. 整数规划的定义数学规

7、划中的变量（部分或全部）限制为整数时，称为整数规划。,若在线性规划模型中，变量限制为整数，则称为整数线性规划。,2.整数规划的分类,如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：（1）变量全限制为整数时，称纯（完全）整数规划；（2）变量部分限制为整数的，称混合整数规划。,5.用MATLAB求整数线性规划,MATLAB求解混合整数线性规划的命令为:x,fval=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub),对应数学模型：,其中，f,x,intcon,b,beq,lb,ub为列向量；A，Aeq为矩阵。,例2.3 （套裁下料问题）,某工厂要做

8、100套钢架，每套要用长为2.9m，2.1m和1.5m的圆钢各一根。已知原料每根长7.4m。问如何下料可使所用原料的根数最少？,解：,问题分析：,模型建立：,模型求解：,MATLAB程序：clc,clearf=1 1 1 1 1; intcon=1:5;%整数变量的地址， x1 x5 A=1 2 0 1 0;0 0 3 2 1;3 1 2 0 3;b=100 100 100;lb=zeros(5)x=intlinprog(f,intcon,-A,b,lb),例2.4 （背包问题）,有 n 个物品，编号为1, 2, , n，第 i 件物品重ai,千克，价值为 ci 元，现有一个载重量不超过a千,，应如何装载这些物品？,克的背包，为了使装入背包的物品总价值最大，,用变量 xi 表示物品 i 是否装包，i =1, 2, , n，,并令：,解,可得到背包问题的规划模型为：,例2.5 （指派问题）,有n 项任务，由 n 个人来完成，每个人只能做一,件， 第 i 个人完成第 j 项任务要 cij 小时，如何合,理安排时间才能使总用时最小？,引入状态变量 xij ，并令：,解,则总用时表达式为：,可得到指派问题的规划模型为：,2.2.1 相互排斥的约束条件,2.2.2 关于固定费用的问题（Fixed Cost Problem）,2.2.3 指派问题的数学模型,2.4 指派问题的计算机求解,