数学模型与数学建模5.1 线性规划ppt课件.ppt

《数学模型与数学建模5.1 线性规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学模型与数学建模5.1 线性规划ppt课件.ppt（55页珍藏版）》请在三一办公上搜索。

1、数学模型,安徽大学数学科学学院,第5章 数学规划模型,5.1 线性规划5.2 非线性规划 5.3 整数规划 5.4 多目标规划,5.1线性规划5.1.1 线性规划问题的数学模型及其标准形式例5.1.1 某工厂在计划期内要安排生产A、B两种产品，已知生产单位产品所需设备台时及对甲、乙两种原材料的消耗，有关数据如表5.1.1。问：应如何安排生产计划，使工厂获利最大？,表5.1.1 资源配置问题的数据,解 设 为生产A、B两种产品的数量，则由表5.1.1知利润函数为 。同时所需设备台时和对甲、乙两种原料的消耗分别不超过8台时、16公斤和12公斤， 因此建立线性规划问题的数学模型为： （5.1.1）,

2、例5.1.2 某公司饲养实验用的动物以供出售，已知这些动物的生长对饲料中3种营养成分（蛋白质、矿物质和维生素）特别敏感，每个动物每周至少需要蛋白质60g，矿物质3g，维生素8mg，该公司能买到5种不同的饲料，每种饲料1kg所含各种营养成分和成本如表5.1.2所示，求既能满足动物生长需要，又使总成本最低的饲料配方。,表5.1.2 饲料营养成分表,解 设 分别表示每周每个动物需要饲料 、 、 、 、 的数量，则成本函数为 。根据营养的需求，要求蛋白质、矿物质和维生素分别不低于60g、3g和8mg， 因此，可建立如下的数学模型： （5.1.2）,通过以上两个举例可以看出，上述问题的数学模型主要包括以

3、下三个基本要素：（1）决策变量：问题中有待确定的未知变量；（2）约束条件：问题的一些资源等限制条件，且用决策变量的一线性等式或线性不等式来表达；（3）目标函数：问题的目标，按问题的要求，求其最大值或最小值，并用决策变量的线性函数来表达；,若建立的数学模型的目标函数是决策变量的线性函数、约束条件是决策变量的线性等式或线性不等式，则称此数学模型为线性规划（Linear Programming，简记为LP）模型。一般地，线性规划问题的数学模型具有形式： （5.1.3）,从（5.1.3）式可以看出，线性规划问题的目标函数有的是求最大值，有的是求最小值；约束条件有的是等式约束，有的是不等式约束，因此有必

4、要给出线性规划问题的标准形式。线性规划问题的标准形满足：（1）求目标函数的最大值；（2）所有约束条件都是等式约束，且,约束条件右端的常数项满足非负性；（3）所有变量均为非负限制。则LP问题的标准形可表示为： （5.1.4）如果所给的线性规划问题不符合标准形的要求，可从以下几个方面将其适当变换化成标准形：,（1）目标函数最小值化为求最大值：若求 ，令 ，则有 。（2）不等式约束化为等式约束：若约束条件为 ，引进非负松弛变量 ，则有：,若约束条件为 ，增加非负剩余变量 ，则有： （3）决策变量无非负限制化为非负限制：若变量 无非负限制，引进 ，则有： 且 。,（4）若某个约束条件右端的常数项小于零

5、，则用 （ ）乘以该式两端即可。若令 则可将线性规划问题（5.1.4）表示成矩阵形式： （5.1.5）,我们称满足约束条件 且 的 为线性规划问题的可行解；使目标函数取到最大值的可行解称为线性规划问题的最优解。,5.1.2 线性规划问题的LINGO软件和MATLAB软件求解例5.1.3 用LINGO求解例5.1.1。解 例5.1.1建立的线性规划数学模型见（5.1. 1）。在LINGO的MODEL窗口内输入如下模型：model:max=2*x1+3*x2; x1+2*x2=8; 4*x1=16;4*x2=12;end,求解结果如下：运行5步找到全局最优解，目标函数值为14，变量值分别为 。“R

6、educed Cost”的含义是需缩减成本系数或需增加利润系数（最优解中取值非零的决策变量的Reduced Cost值等于零）。“Row”是输入模型中的行号，目标函数是第一行；“Slack or Surplus”的意思是松弛或剩余，即约束条件左,边与右边的差值，对于“ ”的不等式，右边减左边的差值为Slack（松弛），对于“ ”的不等式，左边减的右边差值为Surplus（剩余），当约束条件两边相等时，松弛或剩余的值等于零。“Dual Price”的意思是对偶价格，上述报告中Row2的松弛值为0，表明生产甲产品4单位、乙产品2单位，所需,设备8台时已经饱和，对偶价格5.1的含义是：如果设备增加1

7、台时，能使目标函数值增加5.1。报告中Row4的松弛值为4，表明生产甲产品4单位、乙产品2单位，所需原材料乙8公斤还剩余4公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为0。,例5.1.4 用LINGO求解例5.1.2配料问题。解 例5.1.2配料问题的数学模型为（5.1.2），在LINGO的MODEL窗口内输入如下模型：Min=0.2*x1+0.7*x2+0.4*x3+0.3*x4+0.5*x5;0.3*x1+2*x2+x3+0.6*x4+1.8*x560; 0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x53;0.05*x1+0.1*x2+0.02*x3+

8、0.2*x4+0.08*x58; x1+x2+x3+x4+x552;,求解输出结果如下:,因此,每周每个动物的配料为饲料 、 、 分别为12 、30 和10 ，合计为52 ，可使得饲养成本达到最小，最小成本为22.4元；不选用饲料 和 的原因是因为这两种饲料的价格太高了，没有竞争力。“Reduced Cost”分别等于0.7和0.617，说明当这两种饲料的价格分别降低0.7元和0.62元以上时，不仅选用这两种饲料而且使得饲养成本降低。从,“Slack or Surplus”可以看出，蛋白质和维生素刚达到最低标准，矿物质超过最低标准4.1 ；从“Dual Price”可以得到降低标准蛋白质1单位

9、可使饲养成本降低0.583元，降低标准维生素1单位可使饲养成本降低4.167元，但降低矿物质的标准不会降低饲养成本，如果动物的进食量减少，就必须选取精一些的饲料但要增加成本，大约进食量降低1 可使得饲养成本增加0.88元。,我们也可以用MATLAB的优化工具箱求解线性规划问题。一般线性规划问题的数学模型为 (5.1.6)其中 是目标函数的系数行向量（常数）， 是 维决策向量， 是常数矩阵， 是常数向量， 是 维列向量分别表示决策变量 的下界与上界.,在Matlab优化工具箱（Optimization Toolbox）中，求解(5.1.1)的程序如下：x，fval，exitflag，output

10、，lambda = linprog (c，A，b，Aeq，beq，lb，ub，x0，options)其中linprog是求解线性规划问题所调用的函数，它的各种参数的意义如下：(1)A是不等式约束的系数矩阵，b是相应的常数列向量，若没有不等式约束，则均用代替；,(2) Aeq是等式约束的系数矩阵，beq是相应的常数列向量，若没有等式约束，则均用代替；(3)如果某个变量无下界，则用-inf表示；如果某个变量无上界，则用inf表示，若决策变量 无下界和上界，则lb和ub均用代替；(4) x0是线性规划的初始解，这种设计仅对中规模算法有效，通常可以缺省；(5) 输出 是最优解，fval是最优值；,(6

11、) 输出exitflag描述了程序的运行情况，若其值大于零，表示程序收敛到最优解 ；若其值等于零，表示计算达到了最大次数；若其值小于零，表示问题无可行解，或程序运行失败；(7)输出output表示程序运行的某些信息，如迭代次数(iterations)、所用算法(algorithm)、共轭梯度(cgiterations)等；(8)lambda表示解 处的拉格朗日乘子。,例5.1.5 用MATLAB解线性规划问题 （5.1.7）,解 Matlab程序如下:c=-2,-1,1; A=1,4,-1;2,-2,1; b=4;12; eq=1,1,2; beq=6;lb=0,0,-inf; ub=inf,

12、inf,5; x,z=linprog(c,A,b,Aeq,beq,lb,ub)运行后得到输出Optimization terminated successfully.x= 4.6667 0.0000 0.6667; z= -8.6667,5.1.3线性规划应用案例用线性规划解决实际生活中的优化问题，首先要建立线性规划的数学模型来刻画实际问题问题中的变量之间的数量关系，因此建模的过程是一项技巧性很强的创造性工作，然后通过计算机软件进行求解，并对求解结果进行分析。,例5.1.6 一种汽油的特性可用两个指标描述：其点火性用“辛烷数”描述，其挥发性用“蒸汽压力”描述。某炼油厂有四种标准汽油，其标号分别

13、为1，2，3，4，其特性及库存量列于表5.1.3中，将上述标准汽油适量混合，可得两种飞机汽油，某标号为1，2，这两种飞机汽油的性能指标及产量需求列于表5.1.4中。问应如何根据库存情况适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又最高。,表5.1.3 各种标号的标准汽油的特性与存量,表5.1.4 两种飞机汽油的性能指标及产量需求,解 设标准汽油1，2，3，4用于混合飞机汽油1的数量分别为 ；用于混合飞机汽油2的数量分别为 ，则可建立线性规划问题数学模型：,整理以后就是线性规划模型。用LINGO求解的输入模型：max=x1+x2+x3+x4; x5+x6+x7+x8=250000;

14、x1+x5=0; 7.5*x5-7.0*x6-13.0*x7+8.0*x8=0; 2.85*x1-1.42*x2+4.27*x3-18.49*x4=0; 2.85*x5-1.42*x6+4.27*x7-18.49*x8=0;,求解得最优解：因此生产飞机汽油1的数量为933400 ，生产飞机汽油2的数量为250000 。,例5.1.7 某投资公司拟制定今后5年的投资计划，初步考虑下面四个投资项目：项目A：从第1年到第4年每年年初可以投资，于次年年末收回成本，并可获利润15%；项目B：第3年年初可以投资，到第5年年末可以收回成本，并获得利润25%，但为了保证足够的资金流动，规定该项目的投资金额上限

15、为不超过总金额的40%,项目C：第2年年初可以投资，到第5年年末可以收回成本，并获得利润40%，但公司规定该项目的最大投资金额不超过总金额的30%；项目D：5年内每年年初可以购买公债，于当年年末可以归还本金，并获利息6%。该公司现有投资金额100万元，请帮助该公司制定这些项目每年的投资计划，使公司到第5年年末核算这5年投资的收益率达到最大。,解 虽然这是一个连续投资问题，但可以把5年的投资计划一并考虑。用决策变量 分别表示第 年年初为项目A，B，C，D的投资额，根据问题的要求各个变量对应的关系见5.1.5，表中的空白处表示当年不能为该项目投资，也可以认为投资额等于0。,表5.1.5 连续投资问

16、题各变量的对应关系,首先注意到，项目D每年都可以投资，并且当年末就能收回本息，所以公司每年都应该把全部资金投出去。因此投资方案应满足以下条件：第1年：将100万元资金全部用项目A和D的投资，即 第2年：第2年初可投资项目A、C、D的资金是第1年项目D投资收回的本息之和,第3年：第3年初可投资项目A、B、D的资金是第1年项目A投资和第2年项目D投资收回的本息之和 ， 第4年：第4年初可投资项目A、D的资金是第2年项目A投资和第3年项目D投资收回的本息之和,第5年：第5年初投资于项目D的资金是第3年项目A投资和第4年项目D投资收回的本息之和 问题的目标是第5年年末公司收回四个项目全部总和最大，即,

17、于是我们所建立线性规划问题的数学模型为：,用LINGO求解程序如下：max=1.15*x41+1.25*x32+1.4*x23+1.06*x54;x11+x14=1000000; x21+x23+x24-1.06*x14=0; x31+x32+x34-1.15*x11-1.06*x24=0;x41+x44-1.15*x21-1.06*x34=0; x54-1.15*x31-1.06*x44=0;x32=400000;x23=300000;,得最优解：,即连续投资方案为：第1年用于投资项目A的金额为716981.1元，项目D的金额为283018.9元；第2年用于项目C的投资金额为300000元（

18、这部分资金是第1年投资项目D收回的本息之和）；第3年用于项目A的投资金额为424528.3元，用于项目B的投资金额为400000元（这两部分资金是第1年投资项目A收回的本息之和）；,第4年不投资；第5年用于项目D的金额为488207.5元（这部分资金是第3年投资项目A收回的本息之和），可使该公司到第五年末核算收益率最大。到第5年年末该公司拥有总资金1437500元，五年期间的收益率43.75%。,例5.1.8 设有四个化肥厂供应四个地区的农用化肥，假定等量的化肥在这些地区使用效果相同。已知各化肥厂年产量（单位：吨）、各地区年需要量以及从各化肥厂到各地区单位化肥的运价如表5.1.6所示（表中运价

19、中“”表示不适合）。试决定总的运费最节省的化肥调运方案。,表5.1.6 化肥供应的平衡表与运价表,解 设 表示化肥厂 供应地区 的化肥的数量为 ， 为了体现运价表中的不适合，可以不设 三个变量，或者说让他们自动取值为0；为了能解决一般的运输问题，便于用软件计算，我们可以把化肥厂3到地区和化肥厂4到地区、的运价用充分大的整数 来代替，以阻止供应。如果用软件求解，本题赋值 。,建立线性规划问题的数学模型：,可以按照一般解线性规划的方法用LINGO求解。此处由于运输问题的特殊性，下面给出用LINGO求解运输问题的程序：MODEL:SETS:WAREHOUSE / WH1.WH4/ : CAPACIT

20、Y;CUSTOMER / C1.C4/ : DEMAND;LINKS( WAREHOUSE, CUSTOMER) : COST, VOLUME;ENDSETSMIN = SUM( LINKS: COST * VOLUME);FOR(CUSTOMER( J): SUM(WAREHOUSE( I): VOLUME( I, J) =DEMAND( J);FOR( WAREHOUSE( I): SUM( CUSTOMER( J): VOLUME( I, J) =CAPACITY( I);DATA:CAPACITY=50,60,50,50;DEMAND=50,70,30,60;COST=16,13,22,17,14,13,19,15,19,20,23,1000,12,1000,10,1000;ENDDATAEND,求解结果： ，其余都等于0， 。即化肥厂1生产的50吨化肥全部供应地区，化肥厂2生产的60吨化肥全部供应地区，化肥厂3生产的50吨化肥供应30吨给地区、20吨给地区，化肥厂4生产的50吨化肥供应20吨给地区、30吨给地区，可使得总运费达到最小，最小运费为3060元。,