下下下下回回回回停停停停一、引言一、引言二、线性规划模型二、线性规划模型三、整数规划模型三、整数规划模型数学建模专题数学建模专题-规划理论及模规划理论及模型型四、四、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 2.1 线性规划模型的根本形式线性规划模型的根本形式 的含量分别不低于的含量分别不低于b1, b2, , bm 的情况下，使得总的情况下，使得总总的费用最低总的费用最低.首先根据食物数量及价格可写出食谱费用为首先根据食物数量及价格可写出食谱费用为其次食谱中第其次食谱中第i 种营养素的含量为种营养素的含量为因此上述问题可表述为：因此上述问题可表述为：解解上述食谱问题就是一个典型的线性规划问题，上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大小值为目标的数学模寻求以线性函数的最大小值为目标的数学模型型.它是指在一组线性的等式或不等式的约束条件下，它是指在一组线性的等式或不等式的约束条件下，线性规划的数学模型线性规划的数学模型max z = max z = 线性性规划、划、线性性规划的可行解，最划的可行解，最优解的概念解的概念线性规划一般可写作线性规划一般可写作min(or max) f=min(or max) f=s.t. s.t. 线性规划问题还可以用矩阵表示线性规划问题还可以用矩阵表示 min f= min f= s.t Ax b, x0其中f被称作目标函数，目标函数下的等式或不等式被称作约束条件， A=,b= 一组满足约束条件的变量 的值称为一组可行解。 可行解的集合称为可行解域，或可行解空间。 线性规划问题也就是在可行解域上寻找使目标函数取得极小或极大值的可行解，称之为最优解。针对标准形式的线性规划问题，其解的理论针对标准形式的线性规划问题，其解的理论分析已经很完备，在此根底上也提出了很好的算分析已经很完备，在此根底上也提出了很好的算单纯形方法是线性规划问题的最为根底、也单纯形方法是线性规划问题的最为根底、也法法单纯形方法及其相应的变化形式两阶段单纯形方法及其相应的变化形式两阶段2.2 2.2 线性规划模型的求解线性规划模型的求解法，对偶单纯形法等法，对偶单纯形法等.是最核心的算法。它是一个迭代算法，先从一个是最核心的算法。它是一个迭代算法，先从一个特殊的可行解极点出发，通过判别条件去判特殊的可行解极点出发，通过判别条件去判断该可行解是否为最优解或问题无界，假设不断该可行解是否为最优解或问题无界，假设不是最优解，那么根据相应规那么，迭代到下一个是最优解，那么根据相应规那么，迭代到下一个更好的可行解极点，直到最优解或问题无更好的可行解极点，直到最优解或问题无界界.关于线性规划问题解的理论和单纯形法具体关于线性规划问题解的理论和单纯形法具体的求解过程可参见相关文献的求解过程可参见相关文献.然而在实际应用中，特别是数学建模过程中，然而在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划有的软件进行求解，此时通常并不要求线性规划问题是标准形式问题是标准形式.比较常用的求解线性规划模型比较常用的求解线性规划模型的软件包有的软件包有LINGO、LINDO和和MATLAB。MATLABMATLAB中有关求解线性规划问题的指令中有关求解线性规划问题的指令X=linprog(f,A,b,Aeq,beq) 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)X=linprog(f,A,b,Aeq,beq,lb,ub,x0)X=linprog(f,A,b,Aeq,beq,lb,ub,x0)X=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)X=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)x,fval,exitflag,output= linprog()x,fval,exitflag,output= linprog()用用MATLAB优化工具箱解线性规划优化工具箱解线性规划min z=cX 1、模型：命令：x=linprogc，A，b 2、模型：min z=cX 命令：x=linprogc，A，b，Aeq,beq注意：若没有不等式： 存在，则令A= ，b= .9/20/2024143、模型：min z=cX VLBXVUB命令：1 x=linprogc，A，b，Aeq,beq, VLB，VUB 2 x=linprogc，A，b，Aeq,beq, VLB，VUB, X0 注意：1 若没有等式约束: , 则令Aeq= , beq= . 2其中X0表示初始点 4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.9/20/202415解解 编写编写M文件如下：文件如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.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)9/20/202416解解: 编写编写M文件如下：文件如下： c=-7 -5; A=3 2; 4 6; 0 7; b=90;200;210; Aeq=; beq=; vlb=0,0; vub=inf,inf; x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)问题问题2解答解答9/20/202417线性规划中的特殊形式线性规划中的特殊形式-运输问题运输问题例例2.2. 设要从甲地调出物资设要从甲地调出物资2000吨，从乙地调出物吨，从乙地调出物 资资1100吨，分别供给吨，分别供给A地地1700吨、吨、B地地1100吨、吨、C假定运费与运量成正比假定运费与运量成正比.在这种情况下，采用不在这种情况下，采用不地地200吨、吨、D地地100吨吨.每吨运费如表所示每吨运费如表所示.同的调拨方案，运费就可能不一样同的调拨方案，运费就可能不一样.现在问：怎现在问：怎样才能找出一个运费最省的调拨方案？样才能找出一个运费最省的调拨方案？1572521甲甲15375151乙乙DCBA表表 1.1销销地地运运费费产产地地乙乙甲甲DCBA解解一般的运输问题可以表述如下：一般的运输问题可以表述如下：数学模型：数学模型： 假设其中各产地的总产量等于各销地的总销量，假设其中各产地的总产量等于各销地的总销量，即即类似与将一般的线性规划问题转化为其标准类似与将一般的线性规划问题转化为其标准否那么，称为不平衡的运输问题，包括：否那么，称为不平衡的运输问题，包括：，那么称该问题为平衡的运输问题，那么称该问题为平衡的运输问题.总产量总产量总销量和总产量总销量和总产量0，要受惩罚SUTMSUTM外点法外点法9/20/202492 罚函数法的缺点缺点是：每个近似最优解Xk往往不是容许解，而只能近似满足约束，在实际问题中这种结果可能不能使用；在解一系列无约束问题中，计算量太大，特别是随着Mk的增大，可能导致错误1、任意给定初始点X0，取M11，给定允许误差 ，令k=1；2、求无约束极值问题 的最优解，设为Xk=X(Mk)，即 ；3、假设存在 ，使 ，那么取MkM( )令k=k+1返回2，否那么，停止迭代得最优解 .计算时也可将收敛性判别准那么 改为 . SUTMSUTM外点法外点法(罚函数法)的迭代步骤迭代步骤9/20/202493SUTMSUTM内点法障碍函数法内点法障碍函数法9/20/202494 内点法的迭代步骤内点法的迭代步骤9/20/202495 近似规划法的根本思想：将问题中的目标函数 和约束条件 近似为线性函数，并对变量的取值范围加以限制，从而得到一个近似线性规划问题,再用单纯形法求解之，把其符合原始条件的最优解作为原问题的解的近似近似规划法近似规划法每得到一个近似解后，都从这点出发，重复以上步骤 这样，通过求解一系列线性规划问题，产生一个由线性规划最优解组成的序列，经验说明，这样的序列往往收敛于非线性规划问题的解。9/20/202496 近似规划法的算法步骤如下近似规划法的算法步骤如下9/20/2024979/20/202498用MATLAB软件求解,其输入格式输入格式如下: 1. x=quadprog(H,C,A,b); 2. x=quadprog(H,C,A,b,Aeq,beq); 3. x=quadprog(H,C,A,b,Aeq,beq,VLB,VUB); 4. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0); 5. x=quadprog(H,C,A,b, Aeq,beq ,VLB,VUB,X0,options); 6. x,fval=quaprog(.); 7. x,fval,exitflag=quaprog(.); 8. x,fval,exitflag,output=quaprog(.);1.二次规划二次规划9/20/202499例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 1、写成标准形式写成标准形式： 2、 输入命令输入命令： H=1 -1; -1 2; c=-2 ;-6;A=1 1; -1 2;b=2;2; Aeq=;beq=; VLB=0;0;VUB=; x,z=quadprog(H,c,A,b,Aeq,beq,VLB,VUB)3、运算结果运算结果为： s.t.9/20/2024100 1. 首先建立M文件fun.m,定义目标函数FX:function f=fun(X);f=F(X); 其中X为n维变元向量，G(X)与Ceq(X)均为非线性函数组成的向量，其它变量的含义与线性规划、二次规划中相同.用Matlab求解上述问题，根本步骤分三步：2. 一般有约束一般有约束非线性规划非线性规划9/20/20241013. 建立主程序.非线性规划求解的函数是fmincon,命令的根本格式如下： (1) x=fmincon(fun,X0,A,b) (2) x=fmincon(fun,X0,A,b,Aeq,beq) (3) x=fmincon(fun,X0,A,b, Aeq,beq,VLB,VUB) (4) x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon)(5)x=fmincon(fun,X0,A,b,Aeq,beq,VLB,VUB,nonlcon,options) (6) x,fval= fmincon(.) (7) x,fval,exitflag= fmincon(.) (8)x,fval,exitflag,output= fmincon(.)输出极值点M文件迭代的初值参数说明变量上下限9/20/2024102注意：注意：1 fmincon函数提供了大型优化算函数提供了大型优化算法和中型优化算法。默认时，假设在法和中型优化算法。默认时，假设在fun函数中提供了梯度函数中提供了梯度options参参数的数的GradObj设置为设置为on，并且只，并且只有上下界存在或只有等式约束，有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既函数将选择大型算法。当既有等式约束又有梯度约束时，使用中有等式约束又有梯度约束时，使用中型算法。型算法。2 fmincon函数的中型算法使用的函数的中型算法使用的是序列二次规划法。在每一步迭代中是序列二次规划法。在每一步迭代中求解二次规划子问题，并用求解二次规划子问题，并用BFGS法更法更新拉格朗日新拉格朗日Hessian矩阵。矩阵。3 fmincon函数可能会给出局部最函数可能会给出局部最优解，这与初值优解，这与初值X0的选取有关。的选取有关。9/20/20241031、写成标准形式写成标准形式： s.t. 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0例例29/20/20241042、先建立先建立M-文件文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)2+(1/2)*x(2)23、再建立主程序youh2.m： x0=1;1; A=2 3 ;1 4; b=6;5; Aeq=;beq=; VLB=0;0; VUB=; x,fval=fmincon(fun3,x0,A,b,Aeq,beq,VLB,VUB)4、运算结果为：运算结果为：9/20/20241051先建立先建立M文件文件 fun4.m,定义目标函数定义目标函数: function f=fun4(x); f=exp(x(1) *(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1); x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0例例32再建立再建立M文件文件mycon.m定义非线性约束：定义非线性约束： function g,ceq=mycon(x) g=x(1)+x(2);1.5+x(1)*x(2)-x(1)-x(2);-x(1)*x(2)-10;9/20/20241063主程序主程序youh3.m为为:x0=-1;1;A=;b=;Aeq=1 1;beq=0;vlb=;vub=;x,fval=fmincon(fun4,x0,A,b,Aeq,beq,vlb,vub,mycon)3. 运算结果为运算结果为： 9/20/2024107 例4 1先建立先建立M-文件文件fun.m定义目标函数定义目标函数: function f=fun(x); f=-2*x(1)-x(2);2再建立再建立M文件文件mycon2.m定义非线性约束：定义非线性约束： function g,ceq=mycon2(x) g=x(1)2+x(2)2-25;x(1)2-x(2)2-7;9/20/2024108为为: x0=3;2.5; VLB=0 0;VUB=5 10; x,fval,exitflag,output =fmincon(fun,x0,VLB,VUB,mycon2)9/20/20241094. 运算结果为运算结果为: x =exitflag = 1output = iterations: 4 funcCount: 17 stepsize: 1 algorithm: 1x44 char firstorderopt: cgiterations: 9/20/2024110非线性规划建模实例非线性规划建模实例(一一)： 供给与选供给与选址址 某公司有6个建筑工地要开工，每个工地的位置用平面坐标系a，b表示，距离单位：千米 及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 1试制定每天的供给方案，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 2为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？9/20/2024111一、建立模型一、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。9/20/2024112二使用临时料场的情形二使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：设X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 9/20/2024113计算结果为：计算结果为：x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.00009/20/2024114三改建两个新料场的情形三改建两个新料场的情形 改建两个新料场,要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小.这是非线性规划问题。非线性规划模型为：9/20/2024115设 X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12 x1=X13, y1=X14, x2=X15, y2=X16 1先编写M文件liaoch.m定义目标函数。(2) 取初值为线性规划的计算结果及临时料场的坐标: x0=3 5 0 7 0 1 0 0 4 0 6 10 5 1 2 7;编写主程序gying2.m.9/20/2024116(3) 计算结果为： 10.0707 6.3875 4.3943 5.7511 7.1867exitflag = 19/20/2024117(4) 假设修改主程序gying2.m, 取初值为上面的计算结果:x0= 3.0000 5.0000 0.0707 7.0000 0 0.9293 0 0 3.9293 0 6.0000 10.0707 6.3875 4.3943 5.7511 7.1867得结果为:x=3.0000 5.0000 0.3094 7.0000 0.0108 0.6798 0 0 3.6906 0 5.9892 10.3202 5.5369 4.9194 5.8291 7.2852exitflag = 1总的吨千米数比上面结果略优. (5) 假设再取刚得出的结果为初值, 却计算不出最优解.9/20/2024118(6) 假设取初值为: x0=3 5 4 7 1 0 0 0 0 0 5 11 5.6348 4.8687 7.2479 7.7499, 那么计算结果为:x=3.0000 5.0000 4.0000 7.0000 1.0000 0 0 0 0 0 5.0000 11.0000 5.6959 4.9285 7.2500 7.7500exitflag = 1总的吨千米数89.8835比上面结果更好. 通过此例可看出fmincon函数在选取初值上的重要性.9/20/2024119非线性规划建模实例非线性规划建模实例(二二)高速公路问题高速公路问题9/20/20249/20/2024120120A城和城和B城之间准备建一条高速公路，城之间准备建一条高速公路，B城位于城位于A城正南城正南20公里和正东公里和正东30公里交汇处，它们之间有东西走向连绵起伏公里交汇处，它们之间有东西走向连绵起伏的山脉。公路造价与地形特点有关，以下图给出了整个地的山脉。公路造价与地形特点有关，以下图给出了整个地区的大致地貌情况，显示可分为三条沿东西方向的地形带。区的大致地貌情况，显示可分为三条沿东西方向的地形带。你的任务是建立一个数学模型，在给定三种地形上每公里你的任务是建立一个数学模型，在给定三种地形上每公里的建造费用的情况下，确定最廉价的路线。图中直线的建造费用的情况下，确定最廉价的路线。图中直线AB显显然是路径最短的，但不一定最廉价。而路径然是路径最短的，但不一定最廉价。而路径ARSB过山地过山地的路段最短，但是否是最好的路径呢？你怎样使你的模型的路段最短，但是否是最好的路径呢？你怎样使你的模型适合于下面两个限制条件的情况呢？适合于下面两个限制条件的情况呢？1.当道路转弯是，角度至少为当道路转弯是，角度至少为1400。2.道路必须通过一个地点如道路必须通过一个地点如P。9/20/20249/20/20241211219/20/20249/20/2024122122问题分析问题分析 在在建建设设高高速速公公路路时时，总总是是希希望望建建造造费费用用最最小小。如如果果要要建建造造的的起起点点、终终点点在在同同一一地地貌貌中中，那那么么最最正正确确路路线线那那么么是是两两点点间间连连接接的的线线段段，这这样样费费用用那那么么最最省省。因因此此本本问问题题是是一一个个典典型型的的最最优优化化问问题题，以以建建造造费费用用最最小小为为目目标标，需需要要做做出出的的决决策策那那么是确定在各个地貌交界处的集合点。么是确定在各个地貌交界处的集合点。9/20/20249/20/2024123123变量说明变量说明 xi：在在第第i个个集集合合点点上上的的横横坐坐标标以以左左下下角角为直角坐标原点，为直角坐标原点，i1，2，4；x530指目的地指目的地B点的横坐标点的横坐标li：第第i段段南南北北方方向向的的长长度度i1，5Si：在在第第i段段上上地地所所建建公公路路的的长长度度i1，2，5。由问题分析可知，由问题分析可知，9/20/20249/20/2024124124C1：平原每公里的造价单位：万元：平原每公里的造价单位：万元/公里公里C2：高地每公里的造价单位：万元：高地每公里的造价单位：万元/公里公里C3：高山每公里的造价单位：万元：高山每公里的造价单位：万元/公里公里 9/20/20249/20/2024125125模型假设模型假设1、假设在相同地貌中修改高速公路，建、假设在相同地貌中修改高速公路，建造费用与公路长度成正比；造费用与公路长度成正比；2、假设在相同地貌中修改高速为直线。、假设在相同地貌中修改高速为直线。在理论上，可以使得建造费用最少，当在理论上，可以使得建造费用最少，当然实际中一般达不到。然实际中一般达不到。9/20/20249/20/2024126126模型建立模型建立 在在A城城与与B城城之之间间建建造造一一条条高高速速公公路路的的问问题题可可以以转转化化为为下下面面的的非非线线性性规规划划模模型型。优优化化目目标标是是在在A城城与与B城城之之间间建建造造高高速速公公路路的费用。的费用。9/20/20249/20/2024127127模型求解模型求解 这里采用这里采用Matlab编程求解。编程求解。模型求解时，分别取模型求解时，分别取Ci如下。如下。平原每公里的造价平原每公里的造价C1400万元万元/公里；公里；高地每公里的造价高地每公里的造价C2800万元万元/公里；公里；高山每公里的造价高山每公里的造价C31200万元万元/公里。公里。注注意意：实实际际建建模模时时必必须须查查找找资资料料来来确确定参数或者题目给定有数据定参数或者题目给定有数据9/20/20249/20/2024128128模型结果及分析模型结果及分析 通过求解可知，为了使得建造费用最小。通过求解可知，为了使得建造费用最小。建造地点的选择宜采取以下结果。建造地点的选择宜采取以下结果。 建造总费用为亿元。建造总费用为亿元。总长度为公里。总长度为公里。 9/20/20249/20/2024129129求解模型的主程序文件求解模型的主程序文件model_p97 function x=model_p97clear allglobal C LC=400 800 1200;L=4 4 4 4 4;x=fmincon(objfun_97,1,1,1,1,zeros(1,4),ones(1,4)*30,mycon_p97);optans=objfun_97(x)C=ones(3,1);len = objfun_97(x) 9/20/20249/20/2024130130模型中描述目标函数的模型中描述目标函数的Matlab程序程序 function obj=objfun_97(x)global C Lobj= C(1)*sqrt(L(1)2+x(1)2) + C(2)*sqrt(L(2)2+(x(2)-x(1)2) + . C(3)*sqrt(L(3)2+(x(3)-x(2)2) + C(2)*sqrt(L(4)2+(x(4)-x(3)2)+. C(1)*sqrt(L(5)2+(30-x(4)2); 9/20/20249/20/2024131131描述约束条件的描述约束条件的Matlab函数函数 function c,ceq=mycon_p97(x)c(1)=x(1)-x(2);c(2)=x(2)-x(3);c(3)=x(3)-x(4);c(4)=x(4)-30;ceq=;9/20/20249/20/2024132132主程序运行结果主程序运行结果model_p97optans=2.2584e+004len=ans= 9/20/20249/20/2024133133七、多目标规划模型七、多目标规划模型 在许多实际问题中，衡量一个方案的好坏标在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高最远，又要燃料最省，还要精度最高. 这一类问这一类问题统称为多目标最优化问题或多目标规划问题题统称为多目标最优化问题或多目标规划问题. 我们先来看一个生产方案的例子我们先来看一个生产方案的例子.我们希望购置我们希望购置DVDDVD的总数量最小，即的总数量最小，即 : :由此，可以得到问题三的双目标整数线性规划模型由此，可以得到问题三的双目标整数线性规划模型如下：如下： 表表6 6 当当 时最小购置量的时最小购置量的 值值DVDDVD编号号D0D01 1D0D02 2D0D03 3D0D04 4D0D05 5D0D06 6D0D07 7D0D08 8D0D09 9D1D10 0最少最少购买量量1414212117172424121217171919212122221414DVDDVD编号号D1D11 1D1D12 2D1D13 3D1D14 4D1D15 5D1D16 6D1D17 7D1D18 8D1D19 9D2D20 0最少最少购买量量1818181817171717171724241818161618182323DVDDVD编号号D2D21 1D2D22 2D2D23 3D2D24 4D2D25 5D2D26 6D2D27 7D2D28 8D2D29 9D3D30 0最少最少购买量量2020181822221414181817171515121216162424DVDDVD编号号D3D31 1D3D32 2D3D33 3D3D34 4D3D35 5D3D36 6D3D37 7D3D38 8D3D39 9D4D40 0最少最少购买量量1919222220201919222222221313171717171717DVDDVD编号号D4D41 1D4D42 2D4D43 3D4D44 4D4D45 5D4D46 6D4D47 7D4D48 8D4D49 9D5D50 0最少最少购买量量3232202016162121222216162020151520202020续上表DVDDVD编号号D5D51 1D5D52 2D5D53 3D5D54 4D5D55 5D5D56 6D5D57 7D5D58 8D5D59 9D6D60 0最少最少购买量量2424171719191717191918181919171720202121DVDDVD编号号D6D61 1D6D62 2D6D63 3D6D64 4D6D65 5D6D66 6D6D67 7D6D68 8D6D69 9D7D70 0最少最少购买量量1616191919192020171719191717212120201919DVDDVD编号号D7D71 1D7D72 2D7D73 3D7D74 4D7D75 5D7D76 6D7D77 7D7D78 8D7D79 9D8D80 0最少最少购买量量2121222215152020151514141212171719191717DVDDVD编号号D8D81 1D8D82 2D8D83 3D8D84 4D8D85 5D8D86 6D8D87 7D8D88 8D8D89 9D9D90 0最少最少购买量量1818101014141212212113132222151513131717DVDDVD编号号D9D91 1D9D92 2D9D93 3D9D94 4D9D95 5D9D96 6D9D97 7D9D98 8D9D99 9D1D10 00 0最少最少购买量量2424171715151414252515152222202011112222 我们利用规划模型求得每种DVD的购置量后，需要对其进行可行性校验，测试此结果是否可以满足一个月内比例为95%的会员得到他想看的DVD，且具有尽可能大的总体满意度.校验方法：校验方法： 一根据订单和求得的DVD购置数量，利用问题二的规划模型进行第一次分配，对分配情况：租赁的会员，DVD的分配情况，剩余的各种DVD数量作记录；同时将已租赁的会员在满意指数矩阵的指数全变为0，即不考虑对其进行第二次分配. 二随机从第一次得到DVD的会员中抽取60%，将这局部人所还回的DVD与第一次分配余下的DVD合在一起，作为第二次分配时各种DVD的现有量.然后，利用问题二的0-1线性规划模型对第一次未分配到DVD的会员进行第二次分配； 三统计出经过两次分配后，得到三统计出经过两次分配后，得到DVD的的会员的比例，假设大于会员的比例，假设大于95%，那么此次分配成功，那么此次分配成功.利用这种算法进行屡次随机模拟，假设大多数情利用这种算法进行屡次随机模拟，假设大多数情况下可以使得到况下可以使得到DVD的会员大于的会员大于95%，那么认为，那么认为模型三是合理的模型三是合理的.校验结果：校验结果： 因为每次检验需时约因为每次检验需时约1小时，我们只对问题三求得的小时，我们只对问题三求得的结果进行了结果进行了7次模拟，其中次模拟，其中6次符合要求观看比例大于次符合要求观看比例大于95%.下面给出下面给出7次模拟得到的观看比例表次模拟得到的观看比例表7： 表表7 77 7次模拟结果每次的观看比例列表次模拟结果每次的观看比例列表验证次数次数1 12 23 34 45 56 67 7观看比例看比例95.895.896.696.693.493.495.395.395.995.996.196.195.795.7八、Lingo 入门9/20/20249/20/20241611611 在Lingo中使用Lindo模型n nLindo与Lingo都是LINDO系统公司开发的专门用于求解最优化问题的软件包。与Lindo相比，Lingo软件主要具有两大优点：n n1除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题。n n2LINGO包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定格式保存在独立的文件中。 9/20/20249/20/20241621621 在Lingo中使用Lindo模型n n完全支持Lindo模型程序的书写格式。在模型窗口中选择菜单命令“File|Open (F3) n n注意 在以前的版本中如， “File|Import LINDO File (F12)命令可以将Lindo模型文件转化成Lingo模型。这个菜单命令的意思是“导入Lindo文件在中已无必要，所以该命令已经被取消了。 9/20/20249/20/2024163163n n 后缀后缀“ldt“ldt表示表示LINGOLINGO数据文件；数据文件；n n 后缀后缀“ltf“ltf表示表示LINGOLINGO命令脚本文件；命令脚本文件；n n 后缀后缀“lgr“lgr表示表示LINGOLINGO报告文件；报告文件；n n 后缀后缀“mps“mps表示表示MPSMPS数学规划系统格式的模型数学规划系统格式的模型文件；文件；n n“*.*“*.*表示所有文件。表示所有文件。 后缀“lg4表示LINGO格式的模型文件，是一种特殊的二进制格式文件，保存了我们在模型窗口中能够看到的所有文件和其他对象及其格式信息，只有LINGO能读出它，用其他系统翻开这种文件时会出现乱码； 后缀“lng表示文本格式的模型文件，并且以这个格式保存模型时LINGO将给出警告，因为模型中的格式信息如字体、颜色、嵌入对象等将会丧失；LINDO格式的模型文件 9/20/20249/20/20241641642用用Lingo求解求解二次规划二次规划QP模型模型n n例例例例2.1 2.1 某厂生产的一种产品有甲、乙两个牌号，讨论在产销某厂生产的一种产品有甲、乙两个牌号，讨论在产销某厂生产的一种产品有甲、乙两个牌号，讨论在产销某厂生产的一种产品有甲、乙两个牌号，讨论在产销平衡的情况下如何确定各自的产量，使总的利润最大。所谓平衡的情况下如何确定各自的产量，使总的利润最大。所谓平衡的情况下如何确定各自的产量，使总的利润最大。所谓平衡的情况下如何确定各自的产量，使总的利润最大。所谓产销平衡指工厂的产量等于市场上的销量，没有卖不出去的产销平衡指工厂的产量等于市场上的销量，没有卖不出去的产销平衡指工厂的产量等于市场上的销量，没有卖不出去的产销平衡指工厂的产量等于市场上的销量，没有卖不出去的产品的情况。显然，销售总利润既取决于两种牌号产品的销产品的情况。显然，销售总利润既取决于两种牌号产品的销产品的情况。显然，销售总利润既取决于两种牌号产品的销产品的情况。显然，销售总利润既取决于两种牌号产品的销量和单件价格，也依赖于产量和单件本钱，按照市量和单件价格，也依赖于产量和单件本钱，按照市量和单件价格，也依赖于产量和单件本钱，按照市量和单件价格，也依赖于产量和单件本钱，按照市场经济规律，甲的价格场经济规律，甲的价格场经济规律，甲的价格场经济规律，甲的价格p1p1固然会随其销量固然会随其销量固然会随其销量固然会随其销量x1x1的增长而降低，的增长而降低，的增长而降低，的增长而降低，同时乙的销量同时乙的销量同时乙的销量同时乙的销量x2x2的增长也会使甲的价格有稍微的下降，可以的增长也会使甲的价格有稍微的下降，可以的增长也会使甲的价格有稍微的下降，可以的增长也会使甲的价格有稍微的下降，可以简单地假设价格与销量成线性关系，即简单地假设价格与销量成线性关系，即简单地假设价格与销量成线性关系，即简单地假设价格与销量成线性关系，即p1=b1p1=b1a11x1a11x1a12x2a12x2，b1,a11,a120b1,a11,a120，a11a12a11a12；类似地，乙的价；类似地，乙的价；类似地，乙的价；类似地，乙的价格格格格p2p2遵循同样的规律，即有遵循同样的规律，即有遵循同样的规律，即有遵循同样的规律，即有p2=b2p2=b2a21x1a21x1a22x2a22x2，b2,a21,a220b2,a21,a220，a22a21.a22a21.例如，假定实际中例如，假定实际中例如，假定实际中例如，假定实际中b1=100b1=100，a11=1a11=1，a12a12，b2=280b2=280；a21a21，a22=2a22=2。此外，假设工厂的生产能力有限，两种牌号产品的产量之和此外，假设工厂的生产能力有限，两种牌号产品的产量之和此外，假设工厂的生产能力有限，两种牌号产品的产量之和此外，假设工厂的生产能力有限，两种牌号产品的产量之和不可能超过不可能超过不可能超过不可能超过100100件，且甲的产量不可能超过乙的产量的两倍，件，且甲的产量不可能超过乙的产量的两倍，件，且甲的产量不可能超过乙的产量的两倍，件，且甲的产量不可能超过乙的产量的两倍，甲乙的单件生产本钱分别是甲乙的单件生产本钱分别是甲乙的单件生产本钱分别是甲乙的单件生产本钱分别是q1=2q1=2和和和和q2=3(q2=3(假定为常数假定为常数假定为常数假定为常数) )。求甲、乙两个牌号的产量求甲、乙两个牌号的产量求甲、乙两个牌号的产量求甲、乙两个牌号的产量 x1 x1，x2x2使总利润最大。使总利润最大。使总利润最大。使总利润最大。 9/20/20249/20/2024165165优化模型优化模型 n n决策变量：决策变量就是甲、乙两个牌号的产量也是销量决策变量：决策变量就是甲、乙两个牌号的产量也是销量决策变量：决策变量就是甲、乙两个牌号的产量也是销量决策变量：决策变量就是甲、乙两个牌号的产量也是销量x1x1，x2x2n n目标函数：显然，目标函数就是总利润目标函数：显然，目标函数就是总利润目标函数：显然，目标函数就是总利润目标函数：显然，目标函数就是总利润z(x1z(x1，x2)x2)，即，即，即，即n nz(x1z(x1，x2)x2)p1p1q1q1x1x1p2p2q2q2x2x2n n 100100x1x12 2x1x12802801 1 2x22x23 3x2x2n n 98 x198 x1277 x2277 x2x12x120.3 x1 x20.3 x1 x22x222x22n n约束条件：题中假设工厂的生产能力有限，两种产品的产量约束条件：题中假设工厂的生产能力有限，两种产品的产量约束条件：题中假设工厂的生产能力有限，两种产品的产量约束条件：题中假设工厂的生产能力有限，两种产品的产量之和不可能超过之和不可能超过之和不可能超过之和不可能超过100100件，且产品甲的产量不可能超过乙的产件，且产品甲的产量不可能超过乙的产件，且产品甲的产量不可能超过乙的产件，且产品甲的产量不可能超过乙的产量的两倍。写成数学表达式，就是量的两倍。写成数学表达式，就是量的两倍。写成数学表达式，就是量的两倍。写成数学表达式，就是n nx1x1x2100, x12x2x2100, x12x29/20/20249/20/2024166166综上所述综上所述 max 98 x1277 x2x120.3 x1 x22x22 st x1x2100 x12x2 x1，x2 9/20/20249/20/2024167167n nLINGOLINGO中的变量中的变量名由字母和数字名由字母和数字组成，但必须以组成，但必须以字母开头，长度字母开头，长度不能超过不能超过3232个字个字符只能是英文符只能是英文字符，不能含有字符，不能含有中文字符中文字符n n行号、行号、“TITLE“TITLE语句和注释语句语句和注释语句是是LINGOLINGO中唯一中唯一可以使用汉字字可以使用汉字字符的地方行号必符的地方行号必须以字母或下划须以字母或下划线开头；线开头； n nLINGOLINGO中不区分中不区分大小写字母大小写字母n nLINGOLINGO中已假定中已假定所有变量非负所有变量非负 9/20/20249/20/2024168168n n通过通过“LINGO | Generate | Display Model “LINGO | Generate | Display Model (Ctrl +G)(Ctrl +G)命令可以看到完整的模型以及每命令可以看到完整的模型以及每行语句对应的行号了。行语句对应的行号了。9/20/20249/20/2024169169n n可使用可使用“ LINGO | “ LINGO | Picture Picture 命令检查模命令检查模型中的简单错误，该命型中的简单错误，该命令将目标函数和约束表令将目标函数和约束表达式中的非零系数通过达式中的非零系数通过列表或图形显示出列表或图形显示出来。来。9/20/20249/20/2024170170n n用用“LINGO | Solve “LINGO | Solve Ctrl +SCtrl +S命令来运命令来运行这个程序。行这个程序。n n如果想要了解运行状如果想要了解运行状态窗口中各项的含义，态窗口中各项的含义，可先点击工具栏上的图可先点击工具栏上的图标标 ，再点击运行状，再点击运行状态窗口，屏幕上自动弹态窗口，屏幕上自动弹出运行状态窗口的帮助出运行状态窗口的帮助信息。信息。9/20/20249/20/2024171171求解结果报告窗口9/20/20249/20/20241721723 敏感性分析n n敏感性分析的作用是给出“Ranges in which the basis is unchanged，即研究当目标函数的系数和约束右端项在什么范围变化此时假定其他系数保持不变时，最优基矩阵保持不变。n n注意：这里LINGO不询问是否进行敏感性分析。如果需要进行敏感性分析，必须用“LINGO |Options命令翻开系统选项对话框，在“General Solver标签下的“Dual Computations下拉列表中选中“Prices & Range，再按下“OK按钮激活敏感性分析功能。修改了系统选项后，以后只需调用“LINGO |Range命令即可进行敏感性分析了。 9/20/20249/20/2024173173修改运行时的内存限制激活敏感性分析9/20/20249/20/2024174174例例例例3.1 3.1 一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1A1，A2A2两种奶制品，两种奶制品，两种奶制品，两种奶制品，1 1桶牛奶可以在甲车间用桶牛奶可以在甲车间用桶牛奶可以在甲车间用桶牛奶可以在甲车间用12h12h加工成加工成加工成加工成3kgA13kgA1，或者在乙，或者在乙，或者在乙，或者在乙车间用车间用车间用车间用8h8h加工成加工成加工成加工成4kg A24kg A2。根据市场需求，生产出的。根据市场需求，生产出的。根据市场需求，生产出的。根据市场需求，生产出的A1A1，A2A2全部能售出，且每千克全部能售出，且每千克全部能售出，且每千克全部能售出，且每千克A1A1获利获利获利获利2424元，每千克元，每千克元，每千克元，每千克A2A2获获获获利利利利1616元。现在加工厂每天能得到元。现在加工厂每天能得到元。现在加工厂每天能得到元。现在加工厂每天能得到5050桶牛奶的供给，每天桶牛奶的供给，每天桶牛奶的供给，每天桶牛奶的供给，每天正式工人总的劳动时间为正式工人总的劳动时间为正式工人总的劳动时间为正式工人总的劳动时间为480h480h，并且甲车间的设备每天，并且甲车间的设备每天，并且甲车间的设备每天，并且甲车间的设备每天至多能加工至多能加工至多能加工至多能加工100kg A1100kg A1，乙车间的设备的加工能力可以，乙车间的设备的加工能力可以，乙车间的设备的加工能力可以，乙车间的设备的加工能力可以认为没有上限限制即加工能力足够大。试为该厂制定认为没有上限限制即加工能力足够大。试为该厂制定认为没有上限限制即加工能力足够大。试为该厂制定认为没有上限限制即加工能力足够大。试为该厂制定一个生产方案，使每天获利最大，并进一步讨论以下一个生产方案，使每天获利最大，并进一步讨论以下一个生产方案，使每天获利最大，并进一步讨论以下一个生产方案，使每天获利最大，并进一步讨论以下3 3个个个个附加问题：附加问题：附加问题：附加问题：1 1假设用假设用假设用假设用3535元可以买到元可以买到元可以买到元可以买到1 1桶牛奶，是否作这项投资？桶牛奶，是否作这项投资？桶牛奶，是否作这项投资？桶牛奶，是否作这项投资？假设投资，每天最多购置多少桶牛奶？假设投资，每天最多购置多少桶牛奶？假设投资，每天最多购置多少桶牛奶？假设投资，每天最多购置多少桶牛奶？2 2假设可以聘用临时工人以增加劳动时间，付给临时假设可以聘用临时工人以增加劳动时间，付给临时假设可以聘用临时工人以增加劳动时间，付给临时假设可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？工人的工资最多是每小时几元？工人的工资最多是每小时几元？工人的工资最多是每小时几元？ 3 3由于市场需求变化，每千克由于市场需求变化，每千克由于市场需求变化，每千克由于市场需求变化，每千克A1A1的获利增加到的获利增加到的获利增加到的获利增加到3030元，元，元，元，是否应该改变生产方案？是否应该改变生产方案？是否应该改变生产方案？是否应该改变生产方案？ 9/20/20249/20/2024175175优化模型优化模型n n决策变量：决策变量：决策变量：决策变量：n n设每天用设每天用设每天用设每天用x1x1桶牛奶生产桶牛奶生产桶牛奶生产桶牛奶生产A1A1，用，用，用，用x2x2桶牛奶生产桶牛奶生产桶牛奶生产桶牛奶生产A2A2n n目标函数：目标函数：目标函数：目标函数：n n设每天获利为设每天获利为设每天获利为设每天获利为z z元，元，元，元，x1x1桶牛奶生产桶牛奶生产桶牛奶生产桶牛奶生产3x1(kg)A13x1(kg)A1，获利，获利，获利，获利243x1243x1，x2x2桶牛奶生产桶牛奶生产桶牛奶生产桶牛奶生产4x2(kg) 4x2(kg) A2A2，获利，获利，获利，获利164x1164x1，故，故，故，故z=72x1+64x2.z=72x1+64x2.n n约束条件：约束条件：约束条件：约束条件：n n原料供给：生产原料供给：生产原料供给：生产原料供给：生产A1A1，A2A2的原料牛奶总量不得超的原料牛奶总量不得超的原料牛奶总量不得超的原料牛奶总量不得超过每过每过每过每天的供给，即天的供给，即天的供给，即天的供给，即x1+x250x1+x250桶；桶；桶；桶；n n劳动时间：生产劳动时间：生产劳动时间：生产劳动时间：生产A1A1，A2A2的总加工时间不得超过每天的总加工时间不得超过每天的总加工时间不得超过每天的总加工时间不得超过每天正式正式正式正式工人总的劳动时间，即工人总的劳动时间，即工人总的劳动时间，即工人总的劳动时间，即 12x1+8x2480 12x1+8x2480h h；n n设备能力：设备能力：设备能力：设备能力：A1A1的产量不得超过甲车间设备每天的加工的产量不得超过甲车间设备每天的加工的产量不得超过甲车间设备每天的加工的产量不得超过甲车间设备每天的加工能力，即能力，即能力，即能力，即3x11003x1100；n n非负约束：非负约束：非负约束：非负约束：x1x1，x2x2均不能为负值。均不能为负值。均不能为负值。均不能为负值。9/20/20249/20/2024176176综上所述Max z=72x1+64x2；s. t. x1+x250， 12x1+8x2480， 3x1100， x1，x20 线性规划模型LP9/20/20249/20/2024177177模型分析与假设模型分析与假设 比比例例性性 可可加加性性 连续性连续性 xi对目标函数的对目标函数的“奉献与奉献与xi取值成取值成正比正比 xi对约束条件的对约束条件的“奉献与奉献与xi取值成取值成正比正比 xi对目标函数的对目标函数的“奉献与奉献与xj取值无取值无关关 xi对约束条件的对约束条件的“奉献与奉献与xj取值无取值无关关 xi取值连续取值连续 A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与各自产量无关的常数时间是与各自产量无关的常数A1,A2每公斤的获利是与相每公斤的获利是与相互产量无关的常数互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与相互产量无关的常数时间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数 线性规划模型线性规划模型9/20/20249/20/2024178178模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600z=c (常数常数) 等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。 9/20/20249/20/2024179179Lingo优化模型这是一个连这是一个连 续线性规划续线性规划LPLP问题问题 9/20/20249/20/2024180180“LINGO| Solve“LINGO| Solve求解结果报求解结果报告告1 1假设用假设用3535元可以买到元可以买到1 1桶牛奶，是否作这项投资？假设投资，每天最多购桶牛奶，是否作这项投资？假设投资，每天最多购置多少桶牛奶？置多少桶牛奶？2 2假设可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小假设可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？时几元？3 3由于市场需求变化，每千克由于市场需求变化，每千克A1A1的获利增加到的获利增加到3030元，是否应该改变生产方元，是否应该改变生产方案？案？“LINGO| Range“LINGO| Range敏感性分敏感性分析析9/20/20249/20/2024181181结 论n n应该批准用35元买1桶牛奶的投资，但每天最多购置10桶牛奶。 n n可以用低于2元/h的工资聘用临时工人以增加劳动时间，但最多增加。n n假设每千克A1的获利增加到30元，那么x1系数变为303=90，在允许的范围内，所以不应改变生产方案，但最优值变为9020+6430=3720。 9/20/20249/20/2024182182例例 SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元，假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？ 4 在LINGO中使用集合 9/20/20249/20/2024183183 DEMDEM需求量，需求量，RPRP正常生产的产量，正常生产的产量，OPOP加班加班生产的产量，生产的产量，INVINV库存量库存量目标函数目标函数： 约束条件： 能力限制RP(I)40，I=1，2，3，4 产品数量的平衡方程 INVIINVI1RPIOPIDEMI ， INV10； 变量的非负约束9/20/20249/20/2024184184Lingo优化模型集合属性集合的属性相当于以集合的元素为下标的数组9/20/20249/20/2024185185Lingo模型的根本要素1集合段SETS2目标与约束段3数据段DATA：作用在于对集合的属性数 组输入必要的常数数据。格式为： attribute(属性)=value _list(常数列表);常数列表value _list中数据之间可以用逗号“,分开，也可以用空格分开回车的作用也等价于一个空格 “变量名=?; 运行时赋值4初始段INIT赋初值5计算段CALC预处理9/20/20249/20/2024186186n n例例4.2 4.2 建筑工地的位置用平面坐标建筑工地的位置用平面坐标a a，b b表示，表示，距离单位：距离单位：kmkm及水泥日用量及水泥日用量d d单位：单位：t t由由下表给出。目前有两个临时料场位于下表给出。目前有两个临时料场位于P P5 5，1 1，QQ2 2，7 7，日储量各有，日储量各有20t20t，求从，求从A A，B B两料场两料场分别向各工地运送多少吨水泥，使总的吨公里数分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里最小。两个新的料场应建在何处，节省的吨公里数有多大？数有多大？n n 1 12 23 34 45 56 6a a1.251.258.758.750.50.55.755.753 37.257.25b b1.251.250.750.754.754.755 56.56.57.757.75d d3 35 54 47 76 61111工地的位置a，b及水泥日用量d9/20/20249/20/2024187187优化模型记工地的位置为记工地的位置为ai ai，bibi，水泥日用量为，水泥日用量为didi，i=1,2,6i=1,2,6；料场位置为；料场位置为xjxj，yjyj，日储量为，日储量为ej ej，j=1,2j=1,2；从料场；从料场j j向工地向工地i i的运送量为的运送量为cijcij。决策变量：决策变量：在问题在问题1 1中，决策变量就是料场中，决策变量就是料场j j向工地向工地i i的的运送量运送量cijcij，该问题是个，该问题是个LPLP问题；在问题问题；在问题2 2中，中，决策变量除了料场决策变量除了料场j j向工地向工地i i的运送量的运送量cijcij，新建料场，新建料场位置位置xjxj，yjyj也是决策变量，该问题是个也是决策变量，该问题是个NLPNLP问问题。题。目标函数：目标函数：f f是总吨公里数运量乘以运输距离是总吨公里数运量乘以运输距离9/20/20249/20/2024188188n n约束条件：约束条件：n n各工地的日用量必须满足，所以各工地的日用量必须满足，所以n n各料场的运送量不能超过日储量，所以各料场的运送量不能超过日储量，所以n nC Cij ij非负非负9/20/20249/20/2024189189综上所述n n该问题的数学规划模型是：该问题的数学规划模型是：9/20/20249/20/2024190190Lingo优化模型NLPdemand，supply：这种直接：这种直接把元素列举出来的集合，称为根把元素列举出来的集合，称为根本集合本集合link=(s, t)| s demand , t supply.这种基于其他集合派生出来这种基于其他集合派生出来的二维或多维集合称为的二维或多维集合称为派生派生集合集合。Demand ,supply称为称为link的的父集合父集合。初初始始段段按列赋值按列赋值9/20/20249/20/2024191191局部最优解局部最优解9/20/20249/20/2024192192全局最优解9/20/20249/20/2024193193Lingo优化模型LP9/20/20249/20/2024194194全局最优解9/20/20249/20/2024195195 总结： 集合的不同类型及其关系集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法9/20/20249/20/20241961965 运算符优先级优先级 运算符运算符Highest #NOT# - (negation)Highest #NOT# - (negation) * / * / + - + - #EQ# #NE# #GT# #GE# #LT# #LE# #EQ# #NE# #GT# #GE# #LT# #LE# #AND# #OR# #AND# #OR#LowestLowest = = = =算术运算符：算术运算符： * / + - * / + -逻辑运算符：逻辑运算符： a a#AND# #OR# #NOT# #AND# #OR# #NOT# 逻辑值之间逻辑值之间b b#EQ# #NE# #GT# #GE# #LT# #EQ# #NE# #GT# #GE# #LT# #LE#LE#数与数之间数与数之间a a、b b运算结果都是逻辑值运算结果都是逻辑值关系运算符：关系运算符： = = = =数与数之间，表示优化模型的数与数之间，表示优化模型的约束条件约束条件9/20/20249/20/2024197197函 数n n注意：与之前的版本相比，增加了很多新的内注意：与之前的版本相比，增加了很多新的内注意：与之前的版本相比，增加了很多新的内注意：与之前的版本相比，增加了很多新的内部函数。使用这些新函数的优化模型在之前的部函数。使用这些新函数的优化模型在之前的部函数。使用这些新函数的优化模型在之前的部函数。使用这些新函数的优化模型在之前的各种版本中无法执行。各种版本中无法执行。各种版本中无法执行。各种版本中无法执行。n n我们可以使用下拉菜单我们可以使用下拉菜单我们可以使用下拉菜单我们可以使用下拉菜单“Edit | Paste “Edit | Paste FunctionFunction在在在在LINGOLINGO的模型窗口下直接输入的模型窗口下直接输入的模型窗口下直接输入的模型窗口下直接输入所需的各种内部函数。所需的各种内部函数。所需的各种内部函数。所需的各种内部函数。n n此外，可先点击工具栏上的图标此外，可先点击工具栏上的图标此外，可先点击工具栏上的图标此外，可先点击工具栏上的图标 ，再点击，再点击，再点击，再点击“Edit | Paste Function“Edit | Paste Function下你所感兴趣的下你所感兴趣的下你所感兴趣的下你所感兴趣的函数，屏幕上将弹出该函数功能的帮助信息。函数，屏幕上将弹出该函数功能的帮助信息。函数，屏幕上将弹出该函数功能的帮助信息。函数，屏幕上将弹出该函数功能的帮助信息。 9/20/20249/20/2024198198“Edit | Paste Function菜单命令9/20/20249/20/20241991996 LINGO软件与外部文件的接口 1 1 通过通过WindowsWindows剪剪贴板传递数据：贴板传递数据：1 1“Edit |Paste “Edit |Paste (Ctrl +V)(Ctrl +V) 一般仅一般仅用于剪贴板中的内容用于剪贴板中的内容是文本包括多信息是文本包括多信息文本，即文本，即RTFRTF格式的格式的文本的情形。文本的情形。2 2“Edit |Paste “Edit |Paste Special (Ctrl +V)Special (Ctrl +V) 可以用于剪贴板中可以用于剪贴板中的内容不是文本的情的内容不是文本的情形，如可以嵌入插形，如可以嵌入插入其他应用程序中入其他应用程序中生成的对象生成的对象objectobject或对象的链接或对象的链接linklink。 9/20/20249/20/2024200200 2 2通过文本文件传递数据通过文本文件传递数据 1 1输入：输入： FILE FILE filenamefilename; ; 可以在集合段和数据段使用，但不允许嵌套使用，可以在集合段和数据段使用，但不允许嵌套使用，filenamefilename文件中记录之间必须文件中记录之间必须 用用“分开。分开。2 2输出：输出：TEXT( filename )TEXT( filename )；通常只在数据；通常只在数据段使用段使用 。9/20/20249/20/20242012013 通过Excel电子表格文件传递数据 OLE( xlsFile, range1, ., rangen) xlsFile是电子表格文件的名称，应当包括扩展名如 *.xls，还可以包含完整的路径名，只要字符数不超过64均可；range列表是指文件中包含数据的单元范围单元范围的格式与Excel中工作表的单元范围格式一致。9/20/20249/20/2024202202该函数只能在LINGO模型的集合段、数据段和初始段使用。集合段：OLE(.) 数据段：属性或变量=OLE(.) 初始段：OLE(.)=属性或变量 9/20/20249/20/202420320320052005高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛B B题：题： DVD DVD在线租赁在线租赁 随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的效劳。例如，音像制品的在线租赁就是一种可行的效劳。业化和便捷化的效劳。例如，音像制品的在线租赁就是一种可行的效劳。这项效劳充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消这项效劳充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感官性强、本钱相对低廉等，为顾客提供更为周费群、强烈的互动性、感官性强、本钱相对低廉等，为顾客提供更为周到的效劳。到的效劳。考虑如下的在线考虑如下的在线DVDDVD租赁问题。顾客缴纳一定数量的月费成为会员，租赁问题。顾客缴纳一定数量的月费成为会员，订购订购DVDDVD租赁效劳。会员对哪些租赁效劳。会员对哪些DVDDVD有兴趣，只要在线提交订单，网站有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张就会通过快递的方式尽可能满足要求。会员提交的订单包括多张DVDDVD，这些这些DVDDVD是基于其偏爱程度排序的。网站会根据手头现有的是基于其偏爱程度排序的。网站会根据手头现有的DVDDVD数量和数量和会员的订单进行分发。每个会员每个月租赁次数不得超过会员的订单进行分发。每个会员每个月租赁次数不得超过2 2次，每次获得次，每次获得3 3张张DVDDVD。会员看完。会员看完3 3张张DVDDVD之后，只需要将之后，只需要将DVDDVD放进网站提供的信封里放进网站提供的信封里寄回邮费由网站承担，就可以继续下次租赁。请考虑以下问题：寄回邮费由网站承担，就可以继续下次租赁。请考虑以下问题：表表2 2中列出了网站手上中列出了网站手上100100种种DVDDVD的现有张数和当前需要处理的的现有张数和当前需要处理的10001000位会员的在线订单表位会员的在线订单表2 2的数据格式例如如下表的数据格式例如如下表2 2，具体数据请从下，具体数据请从下载，如何对这些载，如何对这些DVDDVD进行分配，才能使会员获得最大的满意度？请具进行分配，才能使会员获得最大的满意度？请具体列出前体列出前3030位会员即位会员即C0001C0030C0001C0030分别获得哪些分别获得哪些DVDDVD。9/20/20249/20/2024204204解法一：解法一： BIP的优化模型19/20/20249/20/2024205205Lingo优化程序19/20/20249/20/2024206206解法二：BIP优化模型29/20/20249/20/20242072079/20/20249/20/2024208208Lingo优化程序29/20/20249/20/2024209209再见再见