非线性规划LING.ppt

非 线 性 规 划,非现性规划的基本概念 定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记:,非 线 性 规 划,定义1 把满足问题（1）中条件的解 称为可行解（或可行点），所有可行点的集合称为可行集（或可行域）记为D即 问题(1)可简记为 ,非 线 性 规 划,定义2 对于问题(1)，设 ，若存在 ,使得对一切 ，且 ，都有 ，则称X*是f(X)在D上的局部极小值点（局部最优解）特别地当 时，若 ，则称X*是f(X)在D上的严格局部极小值点（严格局部最优解）,非 线 性 规 划,定义3 对于问题(1),设 ,对任意的 ,都有 则称X*是f(X)在D上的全局极小值点（全局最优解）特别地当 时，若 ，则称X*是f(X)在D上的严格全局极小值点（严格全局最优解）,非 线 性 规 划,如何用LINGO软件求解非线性规划问题？,非 线 性 规 划,例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20,非 线 性 规 划,Lingo 程序 MIN=-2*X1-6*X2+X1*X1-2*X1*X2+2*X1*X1; X1+X2=2; -X1+2*X2=2;,非 线 性 规 划,计算结果 Objective value: -9.777778 X1 = 0.6666667 X2 = 1.333333,非 线 性 规 划,练习题1,2x1+3x2 6 s.t x1+4x2 5 x1,x2 0,非 线 性 规 划,例2,x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x1x2 10 0,非 线 性 规 划,Lingo程序 min=exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1); x1+x2=0; 1.5+x1*x2-x1-x2=0; -x1*x2-10=0; free(x1); free(x2);,非 线 性 规 划,计算结果 Objective value: 5.276848 X1 = 1.224745 X2 = -1.224745,选 址 问 题,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米 ）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,Lingo 使用外部数据,方法一 Copy Paste 方法 方法二 FILE 输入数据、TEXT输出数据（文本文件） 方法三OLE函数与电子表格软件EXCEL连接 方法四 ODBC函数与数据库连接,FILE和TEXT：文本文件输入输出,使用格式 File(“filename”) 文件filename 是文本文件 每行以 结束 一次File(“filename”) 读取一行纪录,FILE和TEXT：文本文件输入输出,data: a=file(example3_3.ldt); b=file(example3_3.ldt); d=file(example3_3.ldt); e=file(example3_3.ldt); enddata init: x,y=file(example3_3.ldt); endinit,1.25,8.75,0.5,5.75,3,7.25 1.25,0.75,4.75,5,6.5,7.75 3,5,4,7,6,11 20,20 5,1,2,7,Example3_3.ldt的格式,FILE和TEXT：文本文件输入输出,比较,a=1.25,8.75,0.5,5.75,3,7.25; b=1.25,0.75,4.75,5,6.5,7.75; d=3,5,4,7,6,11; e=20,20; x,y=5,1,2,7;,OLE ：与EXCEL连接,使用格式 OLE(“filename” ，range_name_list) filename 为电子表 文件名 , range_name_list 为数据的单元范围。,OLE 的使用例子 Excel文件example3_4.xls 的内容,注意 要将表格中的数据进行命名 :选中数据,选菜单 “插入|名称|定义” 在这里分别命名为 a,b,d,e,x,y,result,OLE 的使用例子 Lingo文件example3_4.lg4 的内容,data: a,b,d,e=OLE(“d:数学建模EXAMPLE3_4.XLS“); enddata init: x,y=Ole(“d:数学建模Example3_4.xls“); endinit,OLE 的使用例子 如果在Lingo文件example3_4.lg4 加上以下内容 其他不变,data: ole(“d:数学建模EXAMPLE3_4.XLS“,“result“)=c; ole(“d:数学建模EXAMPLE3_4.XLS“,“x“)=x; ole(“d:数学建模EXAMPLE3_4.XLS“,“y“)=y; enddata,OLE 的使用例子,则example3_4.xls 变为,注意其中x,y ,result 的变化,钢管订购和运输(2000年B题 ）,要铺设一条 的输送天然气的主管道, 如图一所示. 经筛选后可以生产这种主管道钢管的钢厂有 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。,为方便计，1km主管道钢管称为1单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：,1单位钢管的铁路运价如下表：,1000km以上每增加1至100km运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。 钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。,问题： （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,问 题 分 析,这是一个优化问题，要找到一个钢管订购运输计划，使得总费用最小。 而总费用=钢厂到各枢纽点的运输费用+铺设费用,问 题 分 析,运输费用的计算 记1单位钢管从钢厂i运到结点j的最少总费用为： (包含钢管采购费用) 若运输点j向钢厂i订购 单位钢管，则钢管从钢厂i运到运输点j所需的费用为 。那么所有钢管从各钢厂运到各运输点上的总费用为：,问 题 分 析,铺设费用的计算 若运输点j向(j,j-1)路段铺设 ，运输点j向(j,j+1)路段铺设的总费用为： ，于是运输点j巷两边铺设的费用为： 从而铺设总费用为：,问 题 一模 型,其中si为第i个钢厂的最大产量， Bj为Aj,Aj+1两节点的距离。,问 题 求 解,一、求钢厂Si到Aj的单位钢管最小费用Aij,由于钢管从钢厂运到运输点要通过铁路和公路运输， 而铁路运输费用是分段函数，与全程运输总距离有关, 因此不能直接使用图论中的Dijkstra算法或Floyd算 法.,问 题 求 解,一、求钢厂Si到Aj的单位钢管最小费用Aij,分别在铁路网和公路网上计算最短路径, 换算成费用 在整个网络上以相应的运费为权, 再求一次最短路.,问 题 求 解,二、模型求解,.,为了能够处理约束,我们增加0-1变量Ui, Ui=0表示不使用Si, 此时上述约束变为:,问 题 求 解,三、Lingo 程序,.,Moel: Title 钢管运输计划问题一; Sets: Supply/S1S7/:s,U; Need/A1A15/:B,Y,Z; Matrix(Supply,Need):A,X; EndSets,问 题 求 解,三、Lingo 程序,.,Data: S=800 800 1000 2000 2000 2000 3000; B=104 301 750 606 194 205 201 680 480 300 220 210 420 500; A=Text(“cost.txt”); Enddata;,问 题 求 解,三、Lingo 程序,.,Min=sum(Matrix(i,j):A(i,j)*X(i,j)+0.05*sum (Need(j):Y(j)2+Y(j)+Z(j)2+Z(j); for(Supply(i):sum(Need(j):X(i,j)=500*U(i); for(Need(j):sum(supply(i):X(i,j)=Y(j)+Z(j); for(Need(j)|j#NE#15:Y(j)+Z(j+1)=B(j); Z(1)=0;Y(15)=0; for(Supply:bin(U); for(Need:gin(Y); End,问 题 求 解,三、Lingo 程序,.,运行结果 Objective value: 1278632.,其 它 合 理 模 型,将待铺设的管道全线，按照1公里作为一个单位分割成 5170个点Pj。以Aij 记一个单位钢管从Si到Pj的最小费用. Xij为运量(0-1变量),则问题一的模型为:.,