第4讲：优化模型的Lingo实现ppt课件

第4讲优化模型案例及Lingo实现,王丹理学院数学与系统科学系2016年夏季,例1设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品，根据机车性能和以前的生产情况，得知生产每单位产品所需各车间的工作时数、每个车间在一个季度工作时数的上限以及产品的价格，如下表所示。问：每种产品每季度各应生产多少，才能使这个工厂每季度生产总值达到最大？,第4讲优化模型的Lingo实现,3,.,第4讲优化模型的Lingo实现,解以x1x6分别表示每季度生产产品A、B、C、D、E、F的单位数，于是它们需满足目标函数为,第4讲优化模型的Lingo实现,LINGO实现,第4讲优化模型的Lingo实现,模型：,方法1：直接转换,第4讲优化模型的Lingo实现,约束：,代码：,第4讲优化模型的Lingo实现,目标函数,约束条件,整数约束,第4讲优化模型的Lingo实现,方法2：使用集合变量,（1）车间集合：Factory/1.4/:ftotal;,（2）产品集合：Productor/A.F/:pvalue,x;,车间工时数,产品价值,待求变量,（3）加工时数矩阵：Pro_Fact(Factory,Productor):pf;,数据段：,第4讲优化模型的Lingo实现,模型：,第4讲优化模型的Lingo实现,集合段,目标函数,约束条件,例2（MCM-88B）要把七种不同规格的包装箱装到两辆铁路平板车上去，各包装箱宽、高均相同，但厚度（厘米）与重量（公斤）不同。下表给出各包装箱的厚度、重量及数量。每辆平板车有10.2米长的地方可用来装包装箱，载重40吨。由于当地货运限制，对C5,C6,C7类包装箱总数有一个特别限制：该类箱子总厚度不超过302.7（厘米）。试把包装箱装到平板车上去使得浪费空间最小。,第4讲优化模型的Lingo实现,12,.,1.问题分析题中所有的包装箱共重89吨，而两辆平板车只能载80吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。,第4讲优化模型的Lingo实现,2.模型建立设xij=第i辆车装Cj类箱子的个数，i=1,2j=1,7自然约束：箱数约束：重量约束：厚度约束：特别约束：,第4讲优化模型的Lingo实现,目标函数,第4讲优化模型的Lingo实现,约束条件：,定义集合段：,第4讲优化模型的Lingo实现,板车集合,箱子集合,派生集合：分配变量,集合段,第4讲优化模型的Lingo实现,模型：,约束：,第4讲优化模型的Lingo实现,约束：,约束：,第4讲优化模型的Lingo实现,约束：,约束：,第4讲优化模型的Lingo实现,例3（MCM-89B）机场通常按“先来先走”的原则分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道队伍。假设控制中心可以从快速联机数据库中得到每架飞机的如下信息：（1）预定离开登机口的时间；（2）实际离开登机口的时间；（3）机上乘客人数；（4）预定在下一站转机的人数和时间；（5）到达下一站的预定时间。又设飞机有7种型号，载客量从100人起以50人递增，乘客最多400人。设计一种能使乘客和航空公司双方满意的数学模型。,第4讲优化模型的Lingo实现,假设机场只有一条跑道供起飞使用，且每架飞机起飞占用的跑道时间为d，则n架飞机起飞时间可分为时间窗口：乘客不满意主要由飞机晚点而耽误行程，而航空公司不满意主要由于飞机晚点而受到大的损失，定义为第i架飞机在第j个时间窗口起飞而导致的乘客和航空公司损失费用之和,第4讲优化模型的Lingo实现,定义定义目标函数：约束条件：（1）一个时间窗口只能有一架飞机起飞,第i架飞机在第(j-1)d，jd)窗口起飞,其他,第4讲优化模型的Lingo实现,（2）一架飞机只选择一个时间窗口起飞（3）下面来讨论损失费用损失费用由三部分构成：晚点导致的燃油附加费+转乘乘客由于误机的赔偿+乘客的不满意度,第4讲优化模型的Lingo实现,晚点导致的燃油附加费：转乘乘客由于误机的赔偿：乘客的不满意度：总的费用即为：,第4讲优化模型的Lingo实现,赔偿费,转机人数,飞机人数,假设早上6点有三架飞机同时起飞，其型号相同，飞行距离相同，到达终点时间均为7:20，三架飞机上乘客数为350,100,400，每架飞机上有100人要求转机，设起飞时间窗口长度为1分钟，同时为简单起见，将上述费用中用到的参数均设为1，可得到费用矩阵：相应的0-1规划问题最优解为：,第4讲优化模型的Lingo实现,第4讲优化模型的Lingo实现,26,飞机集合,派生集合：飞机与起飞窗口构成的二维矩阵,费用矩阵,一个时间窗口只能安排一架飞机,一架飞机只能在一个时间窗口起飞,0-1变量,第4讲优化模型的Lingo实现,第4讲优化模型的Lingo实现,例4：,第4讲优化模型的Lingo实现,钢厂的产量和销价（1单位钢管=1km管道钢管）,钢厂产量的下限：500单位钢管,1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）,第4讲优化模型的Lingo实现,（1）制定钢管的订购和运输计划，使总费用最小.,基本模型：,总费用最小的优化问题,总费用：订购，运输（由各厂Si经铁路、公路至各点Aj,i=1,7;j=1,15），铺设管道AjAj+1（j=1,14),由Si至Aj的最小购运费用路线及最小费用cij由Si至Aj的最优运量xij由Aj向AjAj-1段铺设的长度yj及向AjAj+1段铺设的长度zj,最优购运计划,约束条件,钢厂产量约束：上限和下限（如果生产的话）运量约束：xij对i求和等于zj加yj；zj与yj+1之和等于AjAj+1段的长度lj,yjzj,Aj-1AjAj+1,第4讲优化模型的Lingo实现,由Aj向AjAj-1段铺设的运量为1+yj=yj(yj+1)/2由Aj向AjAj+1段铺设的运量为1+zj=zj(zj+1)/2,第4讲优化模型的Lingo实现,第4讲优化模型的Lingo实现,fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量,引入0-1变量,yjzj,Aj,第4讲优化模型的Lingo实现,第4讲优化模型的Lingo实现,定义集合段：,生产上限,单价,是否参与输