第4讲优化模型的Lingo实现1

1、数学建模课程综合设计数学建模课程综合设计 王 丹 2016 例1 设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品，根据机车性能和以前的生产情况，得知生产每单位产品所需各车间的工作时数、每个车间在一个季度工作时数的上限以及产品的价格，如下表所示。问：每种产品每季度各应生产多少，才能使这个工厂每季度生产总值达到最大？ 第第4讲讲 优化模型的优化模型的Lingo实现实现3. 产品产品车间车间A AB BC CD DE EF F 每个车间每季度每个车间每季度 工作时数上限工作时数上限 甲甲乙乙丙丙丁丁0.010.010.02 0.02 0.010.010.02 0.02 0.01

2、0.010.03 0.03 0.030.030.050.050.030.030.05 0.05 0.030.030.08 0.08 850850700700100100900 900 单价（元）单价（元）0.40 0.40 0.280.280.32 0.32 0.72 0.72 0.64 0.64 0.600.60第第4讲讲 优化模型的优化模型的Lingo实现实现 解 以 x1 x6 分别表示每季度生产产品A、B、C、D、E、F的单位数，于是它们需满足目标函数为1234560.01 0.01 0.01 0.03 0.03 0.038500.020.057000.020.051000.030.0

3、8900 xxxxxx126,0,ixxxxZ123456max0.400.280.320.720.640.60fxxxxxx第第4讲讲 优化模型的优化模型的Lingo实现实现LINGO实现实现第第4讲讲 优化模型的优化模型的Lingo实现实现123456max0.400.280.320.720.640.60fxxxxxx模型：Max = 0.4*x1+0.28*x2+0.32*x3+0.72*x4+0.64*x5+0.6*x6代码：方法1：直接转换第第4讲讲 优化模型的优化模型的Lingo实现实现1234560.01 0.01 0.01 0.03 0.03 0.038500.020.0570

4、00.020.051000.030.08900 xxxxxx约束：126,0,ixxxxZ代码：第第4讲讲 优化模型的优化模型的Lingo实现实现目标函数约束条件整数约束第第4讲讲 优化模型的优化模型的Lingo实现实现方法2：使用集合变量（1）车间集合：Factory/1.4/: ftotal;（2）产品集合：Productor/A.F/: pvalue,x;车间工时数产品价值待求变量（3）加工时数矩阵：Pro_Fact(Factory, Productor): pf;0.010.010.010.030.030.030.020.050.020.050.030.08数据段：数据段： 第第4讲讲

5、 优化模型的优化模型的Lingo实现实现123456max0.400.280.320.720.640.60fxxxxxx模型：Min = -sum(Productor(i):pvalue(i)*x(i);代码：约束代码：for(Factory(i):sum(Productor(j):pf(i,j)*x(j) ftotal(i););for(Factory(i): gin(x(i););第第4讲讲 优化模型的优化模型的Lingo实现实现集合段目标函数约束条件 例2 （MCM-88B）要把七种不同规格的包装箱装到两辆铁路平板车上去，各包装箱宽、高均相同，但厚度（厘米）与重量（公斤）不同。下表给出各

6、包装箱的厚度、重量及数量。 每辆平板车有10.2米长的地方可用来装包装箱，载重40吨。由于当地货运限制，对C5 , C6 , C7 类包装箱总数有一个特别限制：该类箱子总厚度不超过302.7（厘米）。试把包装箱装到平板车上去使得浪费空间最小。 第第4讲讲 优化模型的优化模型的Lingo实现实现12.C1C2C3C4C5C6C7厚度厚度t t 48.7 48.7 52.0 52.0 61.3 61.3 72.0 72.0 48.7 48.7 52.0 52.0 64.0 64.0 重量重量w w 2000 2000 3000 3000 1000 1000 500 500 4000 4000 20

7、00 2000 1000 1000 件数件数n n8 87 79 96 66 64 48 8 1. 问题分析 题中所有的包装箱共重89吨，而两辆平板车只能载80吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。 第第4讲讲 优化模型的优化模型的Lingo实现实现 2. 模型建立 设xij =第i 辆车装 Cj 类箱子的个数，i =1,2 j =1, ,7自然约束：箱数约束：重量约束：厚度约束：特别约束： ijxZ12,1,2,7jjjxxnj1234567230.54240,1,2iiiiiiixxxxxxxi12345670.4870.5200.6130.7200.4870.5200.6

8、4010.2,1,2iiiiiiixxxxxxxi5670.4870.5200.643.0271,2iiixxxi第第4讲讲 优化模型的优化模型的Lingo实现实现 目标函数 212345671max0.4870.5200.6130.7200.4870.5200.640iiiiiiiizxxxxxxx第第4讲讲 优化模型的优化模型的Lingo实现实现 约束条件：约束条件： 1234567230.54240,1,2iiiiiiixxxxxxxi12345670.4870.5200.6130.7200.4870.5200.64010.2,1,2iiiiiiixxxxxxxi5670.4870.52

9、00.643.0271,2iiixxxiijxZ12,1,2,7jjjxxnj定义集合段：第第4讲讲 优化模型的优化模型的Lingo实现实现板车集合箱子集合派生集合：分配变量集合段第第4讲讲 优化模型的优化模型的Lingo实现实现模型：212345671max0.4870.5200.6130.7200.4870.5200.640iiiiiiiizxxxxxxxMAX = sum(Car(i):sum(Box(j):hd(j)/100*x(i,j);代码：1234567230.54240,1,2iiiiiiixxxxxxxi约束：代码：for(Car(i):sum(Box(j):zl(j)/10

10、00*x(i,j)=40;);第第4讲讲 优化模型的优化模型的Lingo实现实现for(Car(i):sum(Box(j):hd(j)/100*x(i,j)=10.2;);代码：代码：for(Car(i):sum(Box(j)|j#GE#5:hd(j)/100*x(i,j)=3.027;);约束：12345670.4870.5200.6130.7200.4870.5200.64010.2,1,2iiiiiiixxxxxxxi约束：5670.4870.5200.643.0271,2iiixxxi第第4讲讲 优化模型的优化模型的Lingo实现实现for(Box(j):x(1,j)+x(2,j)=0

11、;);约束：12,1,2,7jjjxxnj约束：ijxZ第第4讲讲 优化模型的优化模型的Lingo实现实现 例3 （MCM-89B）机场通常按“先来先走”的原则分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道队伍。假设控制中心可以从快速联机数据库中得到每架飞机的如下信息：（1）预定离开登机口的时间；（2）实际离开登机口的时间；（3）机上乘客人数；（4）预定在下一站转机的人数和时间；（5）到达下一站的预定时间。 又设飞机有7种型号，载客量从100人起以50人递增，乘客最多400人。设计一种能使乘客和航空公司双方满意的数学模型。第第4讲讲 优化模型的优化模型的Ling

12、o实现实现假设机场只有一条跑道供起飞使用，且每架飞机起飞占用的跑道时间为d，则n架飞机起飞时间可分为时间窗口：乘客不满意主要由飞机晚点而耽误行程，而航空公司不满意主要由于飞机晚点而受到大的损失，定义 为第i架飞机在第j个时间窗口起飞而导致的乘客和航空公司损失费用之和0,), 2),(1),dddnd ndijc第第4讲讲 优化模型的优化模型的Lingo实现实现定义定义目标函数 ：约束条件：（1）一个时间窗口只能有一架飞机起飞11,1, 2,nijixjn1,0,ijx第i架飞机在第(j-1)d，jd)窗口起飞其他11minnnijijjizc x 第第4讲讲 优化模型的优化模型的Lingo实现

13、实现（2）一架飞机只选择一个时间窗口起飞（3）下面来讨论损失费用损失费用由三部分构成：晚点导致的燃油附加费+转乘乘客由于误机的赔偿+乘客的不满意度11,1, 2,nijjxin0,1, ,1, 2,ijxijnijc第第4讲讲 优化模型的优化模型的Lingo实现实现晚点导致的燃油附加费：转乘乘客由于误机的赔偿：乘客的不满意度：总的费用即为：0,0,0,iiiiiitFk ttkt( )()iiiRtwQ H t(1)()tiiiiDa ePbQ H t( )( )( )ijiiicFtRtDt第第4讲讲 优化模型的优化模型的Lingo实现实现赔偿费转机人数0-1函数飞机人数折算系数 假设早上6

14、点有三架飞机同时起飞，其型号相同，飞行距离相同，到达终点时间均为7:20，三架飞机上乘客数为350,100,400，每架飞机上有100人要求转机，设起飞时间窗口长度为1分钟，同时为简单起见，将上述费用中用到的参数均设为1，可得到费用矩阵：相应的0-1规划问题最优解为：05.898911.896601.69733.422806.739213.5914C010001100第第4讲讲 优化模型的优化模型的Lingo实现实现第第4讲讲 优化模型的优化模型的Lingo实现实现26飞机集合派生集合：飞机与起飞窗口构成的二维矩阵费用矩阵一个时间窗口只能安排一架飞机一架飞机只能在一个时间窗口起飞0-1变量第第

15、4讲讲 优化模型的优化模型的Lingo实现实现第第4讲讲 优化模型的优化模型的Lingo实现实现由钢管厂订购钢管，经铁路、公路运输，铺设一条钢管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km)（

16、沿管道建有公路）例4：第第4讲讲 优化模型的优化模型的Lingo实现实现钢 厂 i1234567产 量 上 限 is80080010002000200020003000销 价ip（ 万 元 ）160155155160155150160钢厂的产量和销价（1单位钢管=1km管道钢管）钢厂产量的下限：500单位钢管里程(km)300301350351400401450451500运价(万元)2023262932里程(km)5016006017007018008019009011000运价(万元)37445055601单位钢管的铁路运价1000km以上每增加1至100km运价增加5万元1单位钢管的公路

17、运价：0.1万元/km（不足整公里部分按整公里计）第第4讲讲 优化模型的优化模型的Lingo实现实现（1）制定钢管的订购和运输计划，使总费用最小.A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7基本模型：总费用最小的优化问题总费用：订购，运输（由各厂Si经铁路、公路

18、至各点Aj, i=1,7; j=1, 15 ），铺设管道Aj Aj+1 （j=1, 14)由Si至Aj的最小购运费用路线及最小费用cij 由Si至Aj的最优运量xij由Aj向Aj Aj-1段铺设的长度yj及向Aj Aj+1段铺设的长度zj最优购运计划约束条件钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj 加yj； zj与 yj+1之和等于Aj Aj+1段的长度ljyj zjAj-1 Aj Aj+1第第4讲讲 优化模型的优化模型的Lingo实现实现由Aj向Aj Aj-1段铺设的运量为 1+ +yj= yj( yj+1)/2由Aj向Aj Aj+1段铺设的运量为 1+ +z

19、j= zj( zj+1)/2)6(0, 0) 5(15, 2 , 1, 7 , 2 , 10, 0, 0)4(14, 2 , 1) 3(15, 2 , 1)2(7 , 2 , 1,5000. .) 1 ()1() 1(21 . 0min15117115171151151zyjiyzxjlyzjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij第第4讲讲 优化模型的优化模型的Lingo实现实现的处理约束条件)7 , 2 , 1(,5000151isxijij问问题题求求解解。，分分解解为为上上述述形形式式的的子子的的那那些些求求解解，再再对对解解中中满满足足先先松

20、松弛弛为为ixisxbjijijij5000)7, 1(0)151151 个个子子问问题题共共和和分分解解为为71511512)7, 1(5000) isxxaijijjij第第4讲讲 优化模型的优化模型的Lingo实现实现fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量 引入0-1变量. 7,.,1, 1 , 0, 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifsxftszzyyxcpMinijjjjjiijiijijijjjjjjiijijiyj zjAj第第4讲讲 优化模型的优化模型的Lingo实现实现第第4讲讲 优化模型的优化模型的Lingo实现实现定义集合段：生产上限