非线性规划LING课件

1、非线性规划LING 非非 线线 性性 规规 划划n非现性规划的基本概念非现性规划的基本概念定义定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf非线性规划LING 非非 线线 性性 规规 划划 定义定义1 1 把满足问题（1）中条件的解 称为可行解可行解（或可行（或可行点点），），所有可行点的集合

2、称为可行集可行集（或（或可行域可行域）记为D即 问题(1)可简记为 njiEXXhXgXD, 0, 0|)(nEX XfDXmin非线性规划LING 非非 线线 性性 规规 划划定义定义2 2 对于问题(1)，设 ，若存在 ,使得对一切 ，且 ，都有 ，则称X*是f(X)在D上的局部极小值点局部极小值点（局部最优解局部最优解）特别地当 时，若 ，则称X*是f(X)在D上的严格局部极小值点严格局部极小值点（严格局部最优解严格局部最优解）DX *0DX *XX*XX XfXf* XfXf*非线性规划LING 非非 线线 性性 规规 划划定义定义3 3 对于问题(1),设 ,对任意的 ,都有 则称X

3、*是f(X)在D上的全局极小值点全局极小值点（全局最优解全局最优解）特别地当 时，若 ，则称X*是f(X)在D上的严格全局极小值点严格全局极小值点（严格全局最优解严格全局最优解）DX *DX XfXf*XX XfXf*非线性规划LING 非非 线线 性性 规规 划划n如何用LINGO软件求解非线性规划问题？非线性规划LING 非非 线线 性性 规规 划划例例1 1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22 s.t. x1+x22 -x1+2x22 x10, x20 非线性规划LING 非非 线线 性性 规规 划划nLingo 程序nMIN=-2*X1-6*X2+

4、X1*X1-2*X1*X2+2*X1*X1;nX1+X2=2;n-X1+2*X2=2;非线性规划LING 非非 线线 性性 规规 划划n计算结果nObjective value: -9.777778nX1 = 0.6666667 X2 = 1.333333 非线性规划LING 非非 线线 性性 规规 划划n练习题122212121212minxxxxf 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0非线性规划LING 非非 线线 性性 规规 划划n例例2) 12424()(22122211xxxxxexfx x1+x2=0 s.t. 1.5+x1x2 - x1 - x2 0 -x

5、1x2 10 0非线性规划LING 非非 线线 性性 规规 划划nLingo程序nmin=exp(x1)*(4*x1*x1+2*x2*x2+4*x1*x2+2*x2+1);nx1+x2=0;n1.5+x1*x2-x1-x2=0;n-x1*x2-10=0;nfree(x1);nfree(x2);非线性规划LING 非非 线线 性性 规规 划划n计算结果nObjective value: 5.276848nX1 = 1.224745 nX2 = -1.224745 非线性规划LING 选 址 问 题某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米 ）及水泥日用量d

6、(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？非线性规划LINGLingo 使用外部数据使用外部数据方法一 Copy Paste 方法方法二 FILE 输入数据、TEXT输出数据（文本文件）方法三OLE函数与电子表格软件EXCEL连接方法四 ODBC函数与数据库连接 非线性规划LINGFILE和和TEXT

7、：文本文件输入输出文本文件输入输出使用格式File(“”) 文件 是文本文件 每行以 结束 一次File(“”) 读取一行纪录非线性规划LINGFILE和和TEXT：文本文件输入输出文本文件输入输出data:a=file(example3_3.ldt);b=file(example3_3.ldt);d=file(example3_3.ldt);e=file(example3_3.ldt);enddatainit:x,y=file(example3_3.ldt);endinit1.25,8.75,0.5,5.75,3,7.251.25,0.75,4.75,5,6.5,7.753,5,4,7,6,

8、1120,205,1,2,7Example3_3.ldt的格式格式非线性规划LINGFILE和和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;非线性规划LINGOLE ：与与EXCEL连接连接使用格式OLE(“” ，range_name_list) 为电子表 文件名 , range_name_list 为数据的单元范围。非线性规划LINGOLE 的使用例子Excel文件example3_4.xls 的内容abde

9、xyresult1.251.25320518.750.75520270.54.7545.755736.567.257.7511注意 要将表格中的数据进行命名 :选中数据,选菜单“插入|名称|定义” 在这里分别命名为 a,b,d,e,x,y,result 非线性规划LINGOLE 的使用例子Lingo文件example3_4.lg4 的内容data:a,b,d,e=OLE(d:数学建模EXAMPLE3_4.XLS);enddatainit:x,y=Ole(d:数学建模Example3_4.xls);endinit非线性规划LINGOLE 的使用例子如果在Lingo文件example3_4.lg4

10、 加上以下内容其他不变data:ole(d:数学建模EXAMPLE3_4.XLS,result)=c;ole(d:数学建模EXAMPLE3_4.XLS,x)=x;ole(d:数学建模EXAMPLE3_4.XLS,y)=y;enddata非线性规划LINGOLE 的使用例子则example3_4.xls 变为abdexyresult1.251.253205.69594 4.92852438.750.75520 7.2499977.7500.54.75455.7557036.5647.257.751107015011注意其中x,y ,result 的变化非线性规划LING钢管订购和运输钢管订购和运

11、输(2000(2000年年B B题题 ） 要铺设一条 的输送天然气的主管道, 如图一所示. 经筛选后可以生产这种主管道钢管的钢厂有 。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。1521AAA721,SSS非线性规划LINGA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306019520272069052017069046216032

12、0160110290115011001200A2A3A4A5A6A11A711A 11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一非线性规划LING为方便计，1km主管道钢管称为1单位钢管。一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表：ip123456780080010002000200020003000160155155160155150160非线性规划LING1单位钢管的铁路运价如下表：里程(km)3003013503514004014504515

13、00运价(万元)2023262932 里程(km)5016006017007018008019009011000运价(万元)3744505560 1000km以上每增加1至100km运价增加5万元。公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。非线性规划LING问题：问题：（1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。（2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。（3

14、）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。非线性规划LINGA13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003 0 60195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A1

15、7A18A20(A21)图二非线性规划LING 问问 题题 分分 析析这是一个优化问题，要找到一个钢管订购运输计划，使得总费用最小。而总费用=钢厂到各枢纽点的运输费用+铺设费用 非线性规划LING 问问 题题 分分 析析 运输费用的计算记1单位钢管从钢厂i运到结点j的最少总费用为： (包含钢管采购费用)若运输点j向钢厂i订购 单位钢管，则钢管从钢厂i运到运输点j所需的费用为 。那么所有钢管从各钢厂运到各运输点上的总费用为： ijAijXijijXA 15171jiijijAX非线性规划LING 问问 题题 分分 析析 铺设费用的计算铺设费用的计算若运输点j向(j,j-1)路段铺设 ，运输点j向

16、(j,j+1)路段铺设的总费用为： ，于是运输点j巷两边铺设的费用为： 从而铺设总费用为：jZjY2/1 . 0)1() 1(151jjjjjYYZZ2/ ) 1(1 . 02/ ) 1(1 . 0jjjjZZYY非线性规划LING 问问 题题 一模一模 型型 0, 0,15, 2, 7 , 1 0 ,5000,151,2,j . .1 . 0)2) 1(2) 1(min15111517115171151YZBYZjiXsXZYxtsAXZZYYfjjjijjiijijjijjiijijjjjjj其中si为第i个钢厂的最大产量， Bj为Aj,Aj+1两节点的距离。非线性规划LING问问 题题

17、求求 解解一、求钢厂Si到Aj的单位钢管最小费用Aij 由于钢管从钢厂运到运输点要通过铁路和公路运输，而铁路运输费用是分段函数，与全程运输总距离有关,因此不能直接使用图论中的Dijkstra算法或Floyd算法. 非线性规划LING问问 题题 求求 解解一、求钢厂Si到Aj的单位钢管最小费用Aij 分别在铁路网和公路网上计算最短路径,换算成费用在整个网络上以相应的运费为权, 再求一次最短路. 非线性规划LING问问 题题 求求 解解二、模型求解 . ,5000151jiijsX为了能够处理约束我们增加0-1变量Ui, Ui=0表示不使用Si, 此时上述约束变为: 500151jiiijisUX

18、U非线性规划LING问问 题题 求求 解解三、Lingo 程序 . Moel:Title 钢管运输计划问题一;Sets:Supply/S1.S7/:s,U;Need/A1.A15/:B,Y,Z;Matrix(Supply,Need):A,X;EndSets非线性规划LING问问 题题 求求 解解三、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;非线性规划LING问问 题题

19、 求求 解解三、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非线性规划LING问问 题题 求求 解解三、Lingo 程序 . 运行结果Objective value: 1278632.非线性规划LING 其 它 合 理 模 型将待铺设的管道全线，按照1