第二章2 整数规划1精品.ppt

模型假设 卡车在一个班次中不应发生等待或熄火后再启动的情况； 在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论； 空载与重载的速度都是28km/h，耗油相差很大； 卡车可提前退出系统，等等。 如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略） 符号 xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨； cij ：从i号铲位到j号卸点的距离 公里； Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分； Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆； Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次； pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨 cki ：i号铲位的铁矿石储量 万吨 cyi ：i号铲位的岩石储量 万吨 fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。 (近似) 优化模型 （1）道路能力(卡车数)约束 （2）电铲能力约束 （3）卸点能力约束 （4）铲位储量约束 （5）产量任务约束 （6）铁含量约束 （7）电铲数量约束 （8）整数约束 . xij为非负整数 fi 为0-1整数 计算结果（LINGO软件） 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿漏 13 54 11 倒Ⅰ 42 43 岩场 70 15 岩漏 81 43 倒Ⅱ 13 2 70 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 0.867 1.862 0.314 倒场Ⅰ 1.077 1.162 岩场 1.892 0.326 岩石漏 1.841 1.229 倒场Ⅱ 0.684 0.1 1.489 cumcm2003b1.lg4 计算结果（派车） 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿石漏 1 (29) 倒场Ⅰ 1 (39) 1 (37) 岩场 1 (37) 岩石漏 1(44) 1 (35) 倒场Ⅱ 1 (47) 结论： 铲位1、2、3、4、8、9、10处各放置一台电铲。 一共使用了13辆卡车；总运量为85628.62吨公里； 岩石产量为32186吨；矿石产量为38192吨。 此外：6辆联合派车（方案略） 最大化产量 结论： （略） 目标函数变化 此外：车辆数量（20辆）限制（其实上面的模型也应该有） 排序问题指n 种零件经过不同设备加工是的顺序问题。其目的是使加工周期为最短。 1、n × 1 排序问题 即n 种零件经过1 种设备进行加工，如何安排？ 14 6 8 20 23 交货日期（d） 4 5 1 7 3 加工时间（t） 零件代号 例一、 七、排序问题 （1）平均通过设备的时间最小 按零件加工时间非负次序排列顺序，其时间最小。（即将加工时间由小到大排列即可） 零件加工顺序 工序时间 1 3 4 5 7 实际通过时间 1 4 8 13 20 交货时间 8 23 14 6 20 平均通过时间 延迟时间 = 13 – 6 = 7 （2）按时交货排列顺序 零件加工顺序 工序时间 1 3 4 5 7 实际通过时间 5 6 10 17 20 交货时间 8 23 14 6 20 平均通过时间 延迟时间 = 0 （3）既满足交货时间，又使平均通过时间最小 零件加工顺序 工序时间 1 3 4 5 7 实际通过时间 1 6 9 13 20 交货时间 8 23 14 6 20 延迟时间 = 0 平均通过时间 2、n × 2 排序问题 即n 种零件经过2 种设备进行加工，如何安排？ 例二、 4 9 5 2 3 B 5 3 7 8 6 A 零件 设备 A B T 经变换为 4 9 5 2 3 B 5 3 7 8 6 A 零件 设备 加工顺序