数学模型与数学建模5.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）21,xx1223zxx12121212max2328;416..412;,0zxxxxxstxxx例5.1.2某公司饲养实验用的动物以供出售，已知这些动物的生长对饲料中3种营养成分（蛋白质、矿物质和维生素）特别敏感，每个动物每周至少需要蛋白质60g，矿物质3g，维生素8mg，该公司能买到5种不同的饲料，每种饲料1kg所含各种营养成分和成本如表5.1.2所示，求既能满足动物生长需要，又使总成本最低的饲料配方。表5.1.2饲料营养成分表解设分别表示每周每个动物需要饲料、、、、的数量，则成本函数为。根据营养的需求，要求蛋白质、矿物质和维生素分别不低于60g、3g和8mg，因此，可建立如下的数学模型：（5.1.2）54321,,,,xxxxx1A2A3A4A5A123450.20.70.40.30.5zxxxxx1234512345123451234512345min0.20.70.40.30.50.320.61.8600.10.050.020.20.053.0.050.10.020.20.088,,,,0zxxxxxxxxxxxxxxxstxxxxxxxxxx通过以上两个举例可以看出，上述问题的数学模型主要包括以下三个基本要素：（1）决策变量：问题中有待确定的未知变量；（2）约束条件：问题的一些资源等限制条件，且用决策变量的一线性等式或线性不等式来表达；（3）目标函数：问题的目标，按问题的要求，求其最大值或最小值，并用决策变量的线性函数来表达；若建立的数学模型的目标函数是决策变量的线性函数、约束条件是决策变量的线性等式或线性不等式，则称此数学模型为线性规划（LinearProgramming，简记为LP）模型。一般地，线性规划问题的数学模型具有形式：（5.1.3）11221122min(max)........(,),1,2,...,0,1,2,...,nniiinnijzcxcxcxstaxaxaxbimxjn从（5.1.3）式可以看出，线性规划问题的目标函数有的是求最大值，有的是求最小值；约束条件有的是等式约束，有的是不等式约束，因此有必要给出线性规划问题的标准形式。线性规划问题的标准形满足：（1）求目标函数的最大值；（2）所有约束条件都是等式约束，且约束条件右端的常数项满足非负性；（3）所有变量均为非负限制。则LP问题的标准形可表示为：（5.1.4）如果所给的线性规划问题不符合标准形的要求，可从以下几个方面将其适当变换化成标准形：1122112212max,1,2,,..01,2,,,0,0,,0nniiinnijmScxcxcxaxaxaxbimstxjnbbb（1）目标函数最小值化为求最大值：若求，令，则有。（2）不等式约束化为等式约束：若约束条件为，引进非负松弛变量，则有：1122minnnzcxcxcx'zz1122max'nnzzcxcxcxknknkkbxaxaxa2211nkx02211knkknnknkkxbxxaxaxa若约束条件为，增加非负剩余变量，则有：（3）决策变量无非负限制化为非负限制：若变量无非负限制，引进，则有：且。1122lllnnlaxaxaxbnlx0ln2211lnllnnllxbxxaxaxakx0,0kkxxkkkxxx0,0kkxx（4）若某个约束条件右端的常数项小于零，则用（）乘以该式两端即可。若令则可将线性规划问题（5.1.4）表示成矩阵形式：（5.1.5）1121212,,,,,,)TTijnmnmnaxxxbbbccc（AxbcmaxSs.t.cxAxbxo我们称满足约束条件{且}的为线性规划问题的可行解；使目标函数取到最大值的可行解称为线性规划问题的最优解。bAxoxxTnxxx),,,(21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，变量值分别为。“ReducedCost”的含义是需缩减成本系数或需增加利润系数（最优解中取值非零的决策变量的ReducedCost值等于零）。“Row”是输入模型中的行号，目标函数是第一行；“SlackorSurplus”的意思是松弛或剩余，即约束条件左124,2xx边与右边的差值，对于“”的不等式，右边减左边的差值为Slack（松弛），对于“”的不等式，左边减的右边差值为Surplus（剩余），当约束条件两边相等时，松弛或剩余的值等于零。“DualPrice”的意思是对偶价格，上述报告中Row2的松弛值为0，表明生产甲产品4单位、乙产品2单位，所需设备8台时已经饱和，对偶价格5.1的含义是：如果设备增加1台时，能使目标函数值增加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+0.2*x4+0.08*x58;x1+x2+x3+x4+x552;求解输出结果如下:因此,每周每个动物的配料为饲料、、分别为12、30和10，合计为52，可使得饲养成本达到最小，最小成本为22.4元；不选用饲料和的原因是因为这两种饲料的价格太高了，没有竞争力。“ReducedCost”分别等于0.7和0.617，说明当这两种饲料的价格分别降低0.7元和0.62元以上时，不仅选用这两种饲料而且使得饲养成本降低。从2A4A5Akgkgkgkg1A3A“SlackorSurplus”可以看出，蛋白质和维生素刚达到最低标准，矿物质超过最低标准4.1；从“DualPrice”可以得到降低标准蛋白质1单位可使饲养成本降低0.583元，降低标准维生素1单位可使饲养成本降低4.167元，但降低矿物质的标准不会降低饲养成本，如果动物的进食量减少，就必须选取精一些的饲料但要增加成本，大约进食量降低1可使得饲养成本增加0.88元。gkg我们也可以用MATLAB的优化工具箱求解线性规划问题。一般线性规划问题的数学模型为(5.1.6)其中是目标函数的系数行向量（常数），是维决策向量，是常数矩阵，是常数向量，是维列向量分别表示决策变量的下界与上界.11minSs.t.cxAxbAxblbxubcxn1,AA1,bb,lbubnx在Matlab优化工具箱（OptimizationToolbox）中，求解(5.1.1)的程序如下：[x，fval，exitflag，output，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是最优值；xx(6)输出exitflag描述了程序的运行情况，若其值大于零，表示程序收敛到最优解；若其值等于零，表示计算达到了最大次数；若其值小于零，表示问题无可行解，或程序运行失败；(7)输出output表示程序运行的某些信息，如迭代次数(iterations)、所用算法(algorithm)、共轭梯度(cgiterations)等；(8)lambda表示解处的拉格朗日乘子。x例5.1.5用MATLAB解线性规划问题（5.1.7）123123123123123226442212005minzxxxxxxxxxs.t.xxxx,x,x解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,inf,5];[x,z]=linprog(c,A,b,Aeq,beq,lb,ub)运行后得到输出Optimizationterminatedsuccessfully.x=[4.66670.00000.6667];z=-8.66675.1.3线性规划应用案例用线性规划解决实际生活中的优化问题，首先要建立线性规划的数学模型来刻画实际问题问题中的变量之间的数量关系，因此建模的过程是一项技巧性很强的创造性工作，然后通过计算机软件进行求解，并对求解结果进行分析。例5.1.6一种汽油的特性可用两个指标描述：其点火性用“辛烷数”描述，其挥发性用“蒸汽压力”描述。某炼油厂有四种标准汽油，其标号分别为1，2，3，4，其特性及库存量列于表5.1.3中，将上述标准汽油适量混合，可得两种飞机汽油，某标号为1，2，这两种飞机汽油的性能指标及产量需求列于表5.1.4中。问应如何根据库存情况适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又最高。表5.1.3各种标号的标准汽油的特性与存量Pacmg98/12表5.1.4两种飞机汽油的性能指标及产量需求解设标准汽油1，2，3，4用于混合飞机汽油1的数量分别为；用于混合飞机汽油2的数量分别为，则可建立线性规划问题数学模型：4321,,,xxxx8765,,,xxxx1234152637481234123456785678123412345max380000;262200408100;130100107.5938710891..107.593871081007.1111.385.6928.459.967.1111.Zxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxxxxxx6785678567812345678385.6928.459.96250000;,,,,,,,0xxxxxxxxxxxxxxxxxxx整理以后就是线性规划模型。用LINGO求解的输入模型：max=x1+x2+x3