线性规划和非线性规划.ppt

第第4讲讲线性规划和非线性规划线性规划和非线性规划数学建模与数学实验数学建模与数学实验西南科技大学 理学院 杨学南Lingo优化软件的使用方法优化软件的使用方法Lingo安装完成，启动后，可以看到如下界面算术运算负号：+(加法）-（减法）*（乘法）/(除法）(乘幂）逻辑运算符号：#AND#(与)#OR#(或)#NOT#(非)#EQ#(等于)#NE#(不等于)#GT#(大于)#GE#(大于等于)#LT#(小于)#LE#(小于等于)逻辑运算的结果只有“真”（TRUE)和“假”（FALES)，Llingo用1表示True,其它的都是False。关系运算符号：(=)大于等于Lingo的运算符号的运算符号Lingo函数函数常见函数常见函数：abscosexpfloor(取整）lgm(自变量的gama函数的自然对数）smax(list)（返回列数的最大值）sminsintan集合循环函数集合循环函数function(setname(set_index_list)|condition：expression_list);其中，function是集合函数名，有for,max,min,sum四种；setname是集合名；set_index_list是集合索引列表；condition是逻辑表达式描述的条件；expresstoin_list是一个表达式，对for函数可以有一组表达式。for对集合setname的每个元素独立生成约束，约束由expression_list描述。max、min、sum依次返回集合setname上的表达式的最大值、最小值、和。例例1：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？一一、线性规划、线性规划解解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：解答在lingo下编程：model:min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6;x1+x4=400;x2+x5=600;x3+x6=500;0.4*x1+1.1*x2+x3800;0.5*x4+1.2*x5+1.3*x6900;endLINGO的基本用法的几点注意事项的基本用法的几点注意事项LINGO中不区分大小写字母；变量和行名可以超过8个字符，但不能超过32个字符，且必须以字母开头。用LINGO解优化模型时已假定所有变量非负(除非用限定变量取值范围的函数free或sub或slb另行说明)。变量可以放在约束条件的右端(同时数字也可放在约束条件的左端)。但为了提高LINGO求解时的效率，应尽可能采用线性表达式定义目标和约束(如果可能的话)。语句是组成LINGO模型的基本单位,每个语句都以分号结尾，编写程序时应注意模型的可读性。例如：一行只写一个语句，按照语句之间的嵌套关系对语句安排适当的缩进，增强层次感。以感叹号开始的是说明语句(说明语句也需要以分号结束)）。Globaloptimalsolutionfoundatiteration:2VariableValueReducedCostRowSlackorSurplusDualPrice设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3例例2 2、汽车厂生产计划、汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;289*x1+250*x2+400*x360000;lingolingo 下程序：Globaloptimalsolutionfoundatiteration:2VariableValueReducedCost3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。结果为小数，结果为小数，怎么办？怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值相差不大。最优值相差不大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通过比较可能得到更优的解。，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？IP可用可用Lingo直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)gin(x1)表示表示x1x1变量变量为整数为整数IP的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;289*x1+250*x2+400*x360;x1+x270;x2+x360;x3+x450;x4+x520;x5+x630;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);end丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步到57”5,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队?例例4混合泳接力队的选拔混合泳接力队的选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的名候选人的百米成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种。目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型规划模型 cij(秒秒)队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 +57.2x21+66x22+66.4x23+53x24SUBJECTTOx11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1x51+x52+x53+x54=1x11+x21+x31+x41+x51=1x12+x22+x32+x42+x52=1x13+x23+x33+x43+x53=1x14+x24+x34+x44+x54=1ENDINT20模型求解模型求解 输入输入LINDO求解求解exam0207exam0207 最优解：最优解：x14=x21=x32=x43=1,其它变量为其它变量为0;成绩为成绩为(秒秒)=413”2甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲自由泳、乙自由泳、乙蝶泳、丙蝶泳、丙仰泳、丁仰泳、丁蛙泳蛙泳.问题问题1.如何下料最节省如何下料最节省?例例5 5 钢管下料钢管下料 问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米8米米1根根8米米1根根钢管下料钢管下料 为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,7)约束约束满足需求满足需求 决策决策变量变量 目标目标1（总余量）（总余量）按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27。整数约束：整数约束：xi 为整数为整数当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。xi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米虽余料增加虽余料增加8米，但减少了米，但减少了2根根与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米”相比相比二、非线性规划二、非线性规划min=exp(x1)*(4*x12+2*x22+4*x1*x2+2*x2+1);x1*x2-x1-x2+1.50;-x1*x2-10lp(C,A,b)ans=0记所以生产计划为：A生产5t,B不生产，C生产3t,此时利润最大，为zmax=27.10/28/2022应用Lingo求解该问题的程序为：MODEL:max=3*x1+x2+4*x3;6*x1+3*x2+5*x3=45;3*x1+4*x2+5*x3=0;x2=0;x3=0;END求解结果为：Global optimal solution found.Objective value:Total solver iterations:2Variable Value Reduced Cost Row Slack or Surplus Dual Price 5 0.000000 四、无约束非线性规划1、无约束非线性规划的标准型下列形式称为无约束非线性规划的标准型：其中f是x的实值连续函数，通常还假设具有二阶连续偏导数。2、其它形式无约束非线性规划可化为标准型3、应用MatLab求解约束非线性规划问题，事实上就是求函数的极大极小问题。10/28/2022五、有约束非线性规划1、有约束非线性规划的标准型下列形式称为有约束非线性规划的标准型：其中f,gi,hj是x的实值连续函数，通常还假设具有二阶连续偏导数。10/28/20222、二次规划二次规划问题当属最简单的有约束非线性规划问题，即约束为线性的而目标函数是二次函数的最优化问题。其一般形式为其中假定m维向量b=0，H为n*n对称半正定矩阵。10/28/2022问题二求解二次规划将该二次规划写为矩阵形式，即10/28/2022应用MatLab命令qp求解，得x=qp(H,C,A,b)x=记算出相应的最优值为，再得源问题的最优值为zmax=11+9=20。10/28/2022应用Lingo求解该问题的程序为：MODEL:min=x12+x22+6*x1+9;2*x1+x2=4;x1=0;x2=0;END求解结果为：Local optimal solution found.Objective value:Variable Value Reduced Cost 3、其它有约束非线性规划问题三求解下述有约束非线性规划下面给出详细的求解过程。S1定义目标、约束函数：10/28/2022functionf,g=fun(x)f=exp(x(1)*(4*x(1)2+2*x(2)2+4*x(1)*x(2)+2*x(2)+1);g(1)=1.5+x(1)*x(2)-x(1)-x(2);g(2)=-x(1)*x(2)-10;S2调用优化程序x0=-1,1;%给定初值options=;%使用缺省参数x,options=constr(fun,x0,options);S3输出最优解x；输出最优值options(8)得ans=0.0236注在命令constr中参数options的意义如下：OPTIONS(8)-Functionvalue.OPTIONS(10)-NumberofFunctionandConstraintEvaluations.OPTIONS(13)-Numberofequalityconstraints.OPTIONS(14)-Maximumnumberoffunctionevaluations.应用Lingo求解该问题的程序为：MODEL:min=x12+x22+6*x1+9;2*x1+x2=4;x1=0;x2=0;END求解结果为：Local optimal solution found.Objective value:Variable Value Reduced Cost 然而应用Lingo求解该问题将会发生意外！程序一：min=exp(x1)*(4*x12+2*x22+4*x1*x2+2*x2+1);1.5+x1*x2-x1-x2=0;-x1*x2-10=0;相应求解结果为：Local optimal solution found.Objective value:Variable Value Reduced Cost 程序二：MODEL:min=exp(x1)*(4*x12+2*x22+4*x1*x2+2*x2+1);1.5+x1*x2-x1-x2=0;-x1*x2-10=0;END相应求解结果为：Local optimal solution found.Objective value:Variable Value Reduced Cost 此时我们相信谁呢？基于MatLab在计算方面的出色表现，当目标函数含有超越函数时，我们更相信MatLab的计算结果！问题四求解下述有约束非线性规划下面给出详细的求解过程。S1定义目标、约束函数：10/28/2022functionf,g=fun(x)f=(4-x(2)*(x(1)-3)2;g(1)=x(1)+x(2)-3;%必须把等式约束放在前面g(2)=x(1)2-4*x(1)*x(2)-2;vlb=0,0;%变量下界vub=2,2;%变量上界x0=1,2;%变量上界options(13)=1;%说明有一个等式约束S2调用优化程序x,options=constr(fun,x0,options,vlb,vub)即得最优解x输出最优值options(8)得ans六 对策论对策论(GameTheory)又称为博弈论，是研究带有竞争与对抗问题的理论与方法。它是运筹学的一个分支学科，在管理等领域有重要的应用。二、实验对策论问题五有三家公司A、B、C可以独立或合作某项工程，由于三家公司的基础与又是不同，因此采用独立或合作完成项目的利润也不同，详细利润如下表所示。试求完成该项目的最优方案。表完成项目的方法与得到的利润单位：万元完成项目的方法得到的利润A1.2B0C1AB4AC3BC4ABC7问题 有三家公司A、B、C可以独立或合作某项工程，由于三家公司的基础与又是不同，因此采用独立或合作完成项目的利润也不同，详细利润如下表所示。试求完成该项目的最优方案。表完成项目的方法与得到的利润 单位：万元上机实验2、钢管下料问题编程求解、钢管下料问题编程求解(Lingo)1、求整数规划：、求整数规划：3、混合泳问题（、混合泳问题（Lingo）4、问题 有三家公司A、B、C可以独立或合作某项工程，由于三家公司的基础是不同的，因此采用独立或合作完成项目的利润也不同，详细利润如下表所示。试求完成该项目的最优方案。表完成项目的方法与得到的利润 单位：万元完成项目的方法ABCABACBCABC得到的利润1.2014347