利用LINGO软件优化数学模型.ppt

《利用LINGO软件优化数学模型.ppt》由会员分享，可在线阅读，更多相关《利用LINGO软件优化数学模型.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、利用利用LINGO软件优化数学模型软件优化数学模型邓邓 磊磊西南大学西南大学 数学与统计学院数学与统计学院20112011年年4 4月月1515日日1提 纲n n问题问题1 合建水厂问题的优化合建水厂问题的优化n n问题问题2 选址问题的优化选址问题的优化 2问题1 合建水厂问题的优化合建水厂问题的优化 在河边（X轴）有两座城市A、B,其坐标分别是A(1,5),B(6,4),现要合建一个自来水厂,向它们供水.试设计自来水厂的位置以及铺设水管的方法,使所铺设的水管总长度为最短.这个问题实际上也是一个选址问题,通过对几种选址方案的比较而得出最佳方案.31.特殊点法建模特殊点法建模图1 特殊点法4

2、首先考虑在几个特殊位置建立水厂，如图1，(1)在离A最近的河边A1处建水厂,水管从A1分别铺设到A、B,得出水管总长度11.40;(2)在离B最近的B1处建水厂,水管从B1分别铺设到A、B,得出水管总长度11.07;(3)仍在离A最近的A1处建水厂,但B厂的水管经过A,得出水管总长度10.40;(4)仍在离B最近的B1处建水厂,但到A厂的水管经过B,得出水管总长度9.10.上述四个模型中，水管总长度每后一个比前一个小,同时表明水管总长与水厂位置及水管铺设方法均有关.52.对称点连线法建模对称点连线法建模 如果水管必须分别从水厂铺设,则1中的(3)、(4)不合要求,但(1)、(2)中的铺设方法也

3、不是最佳的.图2 对称点法6 利用光行最速原理求解：如图2，先作点B关于X轴的对称点B(6,-4),再作线段AB交X轴于点W,以点W为自来水厂的位置,水管按折线AWB铺设成V型,所用水管总长为10.30,该结果优于(1)、(2)、(3)方法.但还不如(4)中方法好.应该说，许多中学数学教师认为，2中的模型已经是最优了，未参加过数学建模培训的大学生基本上都是给出这个答案.73.利用费尔马点建模利用费尔马点建模 在2中W点建立水厂,改进水管铺设方法.8图图3 3 费尔马点法费尔马点法9 当然,也可在W点取水,而在N点建立水厂进行净化处理后再分别输送到A、B,水管总长度不变.如图3，取ABW的费尔马

4、点N,在W处建厂,先铺设总水管至N再分别铺设到A、B,这时的水管总长度为8.85,比前几种方案都更优.104.改进费尔马点建模改进费尔马点建模 即便是参加过数学建模培训的大学生，通常也会认为3中的解就是最优解了.但只要注意到NW并不与x轴垂直就会想到还可通过改变水厂位置进一步优化.移动W点使NW与x轴垂直,则水管总长还会变小,但随着W点的移动，相应地N又不是新位置的ABW的费尔马点了,进一步改变N点的位置,又改变W点的位置,如此下去,何时才是最优解呢？11 如图如图4,4,设水厂的位置建在点设水厂的位置建在点MM处处,显然显然MM应在应在A1A1与与B1B1之间之间,设设N(x,yN(x,y)

5、为为ABMABM的费尔马点的费尔马点,则只则只有当有当MNMNX X轴时轴时,才可能使才可能使AN+BN+MNAN+BN+MN达到最短达到最短,于是设点于是设点MM的坐标为的坐标为M(x,0).M(x,0).过点过点N N作直线作直线PQPQX X轴轴交交AA1AA1于于P P、交、交BB1BB1于于Q.Q.图图4 4 改进费尔马点法改进费尔马点法12 由费尔马点性质可知由费尔马点性质可知,ANM=,ANM=BNM=120BNM=120度度,从而从而ANP=ANP=BNQ=30BNQ=30度度,由由 列出方程组得列出方程组得 求解得求解得 由此得由此得N(4.37,3.06),M(4.36,0

6、),N(4.37,3.06),M(4.36,0),这时的水管这时的水管总长度为总长度为8.83.8.83.135.利用利用Lingo求解求解 利用Lingo建模求解,设N(x,y),M(m,0),则只需求x,y,m使NA+NB+NM最小,将AB的坐标代入,得如下程序.MODEL:MIN=SQRT(x-1)2+(y-5)2)+SQRT(x-6)2+(y-4)2)+SQRT(x-m)2+(y-0)2);END 运行得出的结果与4一致,表明4中的结果已经是优化到最佳状态了.146.优化效果比较优化效果比较设计方设计方案编号案编号1 12 23 35 54 46 67 7水管总水管总长度长度11.41

7、1.411.0711.0710.410.410.310.39.19.18.858.858.838.83每次优每次优化比例化比例 2.89%2.89%6.05%6.05%0.96%0.96%11.65%11.65%2.75%2.75%0.23%0.23%与最长与最长水管比水管比2.89%2.89%8.77%8.77%9.65%9.65%20.18%20.18%22.37%22.37%22.54%22.54%15123456A1.258.750.505.753.007.25B1.250.754.755.006.507.75D3547611 某公司有某公司有6 6个建筑工地要开工，每个工地的位个建筑

8、工地要开工，每个工地的位置置(用平面坐标表示用平面坐标表示,距离单位：距离单位：km)km)及水泥日用量及水泥日用量(单位：单位：t)t)如下表，而在如下表，而在P(5,1)P(5,1)及及Q(2,7)Q(2,7)处有两个临处有两个临时料场时料场,日储量各有日储量各有20t,20t,如何安排运输如何安排运输,可使总的可使总的吨公里数最小吨公里数最小?问题2 选址问题的优化选址问题的优化161.料场位置确定时的最少运量料场位置确定时的最少运量 设第i个工地的坐标为(ai,bi),水泥用量为di,第j个两个临时料场的坐标为(xj,yj),水泥日储量为ej,从第j个料场运到第i个工地的水泥为c(i,

9、j),则有如下数学模型 17目标函数：需求约束：非负约束：供应约束：18 c c(i i,j j)为决策变量为决策变量,可编制如下程序：可编制如下程序：MODEL:MODEL:SETS:SETS:demand/1.6/:a,b,d;demand/1.6/:a,b,d;supply/1.2/:x,y,e;supply/1.2/:x,y,e;link(demand,supply):clink(demand,supply):c;ENDSETSENDSETSDATA:DATA:a=1.25,8.75,0.5,5.75,3,7.25;!a=1.25,8.75,0.5,5.75,3,7.25;!需求点的位

10、置需求点的位置;b=1.25,0.75,4.75,5,6.5,7.75;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;!d=3,5,4,7,6,11;e=20,20;!供需量及日储量供需量及日储量;x,yx,y=5,1,2,7;=5,1,2,7;ENDDATAENDDATA19OBJ MIN=SUM(link(i,j):c(i,j)*SQRT(x(j)-a(i)2+(y(j)-b(i)2);FOR(demand(i):DEMAND_CON SUM(supply(j):c(i,j)=d(i););!需求约束;FOR(supply(j):SU

11、PPLY_CON SUM(demand(i):c(i,j)=e(j););!供应约束;FOR(supply:BND(0.5,X,8.75);BND(0.75,Y,7.75););END 运行结果,最小运量为136.2275.202.自动选择新自动选择新料场的最少运量的最少运量 在1中，设工地及水泥用量不变,料场选在何处可使总运量最少？能节约多少吨公里数？模型同1,但从已知数据中去掉xi及yi而把c(i,j)及xj,yj均当成决策变量.其程序只需从第一个程序中去掉x,y=5,1,2,7;并添加for(supply:free(x);free(Y);即可.运行结果,新料场坐标为(3.25,7.25)

12、,(5.65,7.75),最小运量为85.26604,节约的吨公里数为50.9615.213.水泥日储量也自动选择时水泥日储量也自动选择时的最少运量的最少运量 在1中，设工地及水泥用量不变,料场选在何处,每处的水泥日储量各多少时总运量最少？能节约多少吨公里数？模型同1,但从已知数据中去掉xi、yi、ej而把c(i,j),xj,yj,ej均当成决策变量.其程序只需从第二个程序中去掉e=20,20即可.运行结果,新料场坐标为(7.25,7.75),(4.74,4.78),最小运量为82.19366,还可节约3.07238.224.料场增加到三个时的最少运量料场增加到三个时的最少运量 在3的基础上,

13、设料场由两个增加到三个,这时只需把第三个原程序中的supply/1.2/:x,y,e;改成supply/1.3/:x,y,e;经运行得最小运量为50.00684,又节约了32.1868.235.料场个数分别为料场个数分别为16个时的个时的最少运量最少运量 料场个数123456最小运量117.855482.1936650.0068428.0794010.738370 自动选择料场的水泥日储量时分别建立16个料场,运行结果所得各种情况下的最小运量汇总如下 24相应地新料场地址如下列：相应地新料场地址如下列：1 1个料场个料场:A(5.73,5.04);:A(5.73,5.04);2 2个料场个料场

14、:A(7.25,7.75):A(7.25,7.75)、B(4.74,4.78)B(4.74,4.78)；3 3个料场个料场:A(8.75,0.75):A(8.75,0.75)、B(1.76,5.21)B(1.76,5.21)、C(7.25,7.75)C(7.25,7.75)；4 4个料场个料场:A(7.25,7.75):A(7.25,7.75)、B(1.76,5.21)B(1.76,5.21)、C(5.75,5.00)C(5.75,5.00)、D(8.75,0.75)D(8.75,0.75)；5 5个料场个料场:A(7.25,7.75):A(7.25,7.75)、B(0.50,4.75)B(0

15、.50,4.75)、C(3.00,6.50)C(3.00,6.50)、D(5.75,5.00)D(5.75,5.00)、E(8.75,0.75)E(8.75,0.75)；6 6个料场时正好将新料场建在各个工地上个料场时正好将新料场建在各个工地上.25比较发现如下规律：比较发现如下规律：(1)(1)当建立的料场数至少两个时当建立的料场数至少两个时,在水泥需求量最多的在水泥需求量最多的6 6号号工地总要建立一个料场工地总要建立一个料场.(2)(2)当建立当建立6 6个料场时个料场时,算出的各料场水泥存量与各工地的需算出的各料场水泥存量与各工地的需求量一致求量一致,且料场地址与工地地址也一致且料场地

16、址与工地地址也一致,运量为零运量为零,即即6 6个料场分别建在个料场分别建在6 6个工地上个工地上.对于这种特殊情况对于这种特殊情况,人工安人工安排也容易想到排也容易想到.(3)(3)实际应用中实际应用中,由于料场的建立成本及管理成本由于料场的建立成本及管理成本,一般不一般不会使料场个数太多会使料场个数太多,如果把这个因素也考虑进去如果把这个因素也考虑进去,必定能必定能求出一个最佳料场个数及相应的水泥日储量及运量求出一个最佳料场个数及相应的水泥日储量及运量.(4)(4)当分别在当分别在(5,1),(2,7)(5,1),(2,7)各设置一个料场时最小运量为各设置一个料场时最小运量为136.227

17、5,136.2275,经比较发现经比较发现,由于人工选址的盲目性由于人工选址的盲目性,两个料两个料场情况下的最小运量比自动选址情况下的一个料场的运场情况下的最小运量比自动选址情况下的一个料场的运量还大量还大,再考虑到多建料场的成本就知道选好料场地址再考虑到多建料场的成本就知道选好料场地址的重要性的重要性!(5)(5)没有出现某一工地从两个料场运水泥的情况没有出现某一工地从两个料场运水泥的情况!,!,此结果可此结果可以说明：把料场的建立及管理费用按需求量比例分摊到以说明：把料场的建立及管理费用按需求量比例分摊到只需从此运料场水泥的工地是合理的只需从此运料场水泥的工地是合理的.2611莫忠息莫忠息

18、.求最短路径树的一个新算法求最短路径树的一个新算法J.J.数学杂志数学杂志 ,1995,15(1):57-621995,15(1):57-6222王绍恒王绍恒,贾振声贾振声,冯天祥冯天祥,一类树图的最短路算法一类树图的最短路算法J.J.数学杂志数学杂志,2009,29(3):354-358,2009,29(3):354-35833林健良林健良 关于费尔马点的几点注解关于费尔马点的几点注解J.J.华南理工大学学华南理工大学学报报.2004,32(1):93-95.2004,32(1):93-9544堵丁柱堵丁柱.谈谈斯坦纳树谈谈斯坦纳树J.J.数学通报数学通报.1995(1):25-31.1995(1):25-31 32(1):93-9532(1):93-9555毋波毋波,刘扬刘扬,李成侠李成侠,陈立祥陈立祥.与运输路线有关的货物装与运输路线有关的货物装载模型与算法载模型与算法J.J.数学杂志数学杂志,2003,23,(1):49-53,2003,23,(1):49-5366谢金星谢金星,薛毅薛毅.优化建模与优化建模与LINDO/LINGOLINDO/LINGO软件软件M.M.清华清华大学出版社大学出版社,2005.,2005.参考文献参考文献27Thank you!28