数学规划

下回停一、引言二、线性规划模型三、整数规划模型数学建模专题----规划理论及模型四、0-1规划模型五、几种常用的线性规划模型六、非线性规划模型七、多目标规划模型八、LINGO入门一、引言我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.它在数学建模中处于中心的地位.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.在数模竞赛过程中，规划模型是最常见的一类数学模型.从92-08年全国大学生数模竞赛试题越多的人所重视.随着计算机的逐渐普及，它越的解题方法统计结果来看，规划模型共出现了16次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解.二、线性规划模型线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有n种食物，各含m种营养素，第j种食物中第i种营养素的含量为aij,n种食物价格分别为c1,c2,…,cn，请确定食谱中n种食物的数量x1,x2,…,xn，要求在食谱中m种营养素简单的一种.2.1线性规划模型的基本形式的含量分别不低于b1,b2,…,bm的情况下，使得总总的费用最低.首先根据食物数量及价格可写出食谱费用为其次食谱中第i种营养素的含量为因此上述问题可表述为：1122,nncxcxcx1122.iiinnaxaxax11221111221121122222112212min..0,0,0nnnnnnmmmnnmncxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx解上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，线性规划的数学模型•maxz=nnxcxcxc22110,,,2122112211111212111nmnmnjmjmmininjijiinnjjxxxbxaxaxaxabxaxaxaxabxaxaxaxaS.T线性规划、线性规划的可行解，最优解的概念线性规划一般可写作min(ormax)f=s.t.nnxcxcxc2211,2211ininiibxaxaxami,,2,1njxj,,2,1,0线性规划问题还可以用矩阵表示minf=xcTs.tAx≥b,x≥0其中f被称作目标函数，目标函数下的等式或不等式被称作约束条件，Tnxxx),,,(21Tnccc),,,(21mnmmnnaaaaaaaaa212222111211A=mbbb21,b=一组满足约束条件的变量的值称为一组可行解。可行解的集合称为可行解域，或可行解空间。线性规划问题也就是在可行解域上寻找使目标函数取得极小（或极大）值的可行解，称之为最优解。nxxx,,,21针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算单纯形方法是线性规划问题的最为基础、也法——单纯形方法及其相应的变化形式（两阶段2.2线性规划模型的求解法，对偶单纯形法等）.是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见相关文献.然而在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有LINGO、LINDO和MATLAB。MATLAB中有关求解线性规划问题的指令•X=linprog(f,A,b,Aeq,beq)•X=linprog(f,A,b,Aeq,beq,lb,ub)•X=linprog(f,A,b,Aeq,beq,lb,ub,x0)•X=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)•[x,fval,exitflag,output]=linprog(…)2020/4/1514用MATLAB优化工具箱解线性规划minz=cXbAXts..1、模型：命令：x=linprog（c，A，b）2、模型：minz=cXbAXts..beqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].bAX2020/4/15153、模型：minz=cXbAXts..beqXAeqVLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点beqXAeq4、命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.2020/4/1516解编写M文件如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)例1max6543216.064.072.032.028.04.0xxxxxxz85003.003.003.001.001.001.0..654321xxxxxxts70005.002.041xx10005.002.052xx90008.003.063xx6,2,10jxj2020/4/1517解:编写M文件如下：c=[-7-5];A=[32;46;07];b=[90;200;210];Aeq=[];beq=[];vlb=[0,0];vub=[inf,inf];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)21)57(minxxz2100xx21020090706423..21xxts2157maxxxz0,02107200649023..2122121xxxxxxxts问题2解答线性规划中的特殊形式----运输问题例2.设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.已知每吨运费如表1.1所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨计划？1572521甲15375151乙DCBA表1.1销地运费产地乙11x12x13x14x21x22x23x24x2000411jix1100412jix1700211iix1100212iix200213iix100214iix甲DCBA2423222114131211153751511572521minxxxxxxxxf)4,3,2,1;2,1(0jixij解1112131421222324min212571551513715fxxxxxxxxs.t.11121314212223241121122213231424..20001100170011002001000,1,2;1,2,3,4ijstxxxxxxxxxxxxxxxxxij一般的运输问题可以表述如下：要把某种物资从m个发点miAi,,2,1,，调运给需要这种物资的n个收点njBj,,2,1,.已知nijmiiba11，从iA运一个单位的产品到jB的运价为ijc.现在需要确定一个调运方案，即确定由iA到jB的运输量njmixij,,2,1;,,2,1,，在满足供需要求的条件下，使总运输费用最省.数学模型：njmixnjbxmiaxtsxczijmijijnjiijminjijij,,2,1;,,2,1,0,,2,1,,,2,1,..min1111若其中各产地的总产量等于各销地的总销量，即类似与将一般的线性规划问题转化为其标准nijmiiba11否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题.总产量总销量和总产量总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题.从而，我们的重点就是解决平衡运输问题的求解.显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解.但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解.关于运输问题及其解法的进一步介绍可参考相关文献.对于线性规划问题，如果要求其决策变量取整数值，则称该问题为整数线性规划问题.平面法和分枝支定界法是两种常用的求解整数线性对于整数线性规划问题的求解，其难度和运算量远大于同规模的线性规划问题.Gomory割规划问题的方法(参见相关文献).此外，同线性规划模型一样，我们也可以运用LINGO和LINDO软件包来求解整数线性规划模型.三、整数线性规划模型以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包如何求解整数线性规划模型。例3.有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以cm计）及重量（w，以kg计）是不同的.表1给出了每种包装箱的厚度、重量以及数量。每节平板车有10.2m长的地方可用来装包装箱（像面包片那样），载重为40t.由于当地货运的限制，对于C5,C6,C7类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm.试把包装箱装到平板车上，使得浪费的空间最小.种类C1C2C3C4C5C6C7t/cm48.753.061.372.048.752.064.0w/kg200030001000500400020001000n/件8796648为在第节车上装载第件包装箱的,ijxji解令数量（1,2,7;1,2ij）；in为第i种包装箱需要装的件数；iw为第i种包装箱的重量；it为第i种包装箱的厚度；jcl为第j节车的长度（1020jcl）；jcw为第j节车的载重量；s为特殊限制（302.7s）。下面我们建立该问题的整数线性规划模型。1)约束条件两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：12,1,2,,7iiixxni71,1,2iijjitxclj每节车可装的重量不超过车能够承受的重量：71,1,2iijjiwxcwj对于C5,C6,C7类包装箱的总数的特别限制：2)目标函数7125()iiiitxxs浪费的空间最小，即包装箱的总厚度最大：7121max()()iiiifxtxx