数学建模暑期集训2016-2003.ppt

(7)车辆数量约束 为各路线上运输量所需的实数卡车 数学模型为 计算结果（LINGO软件） 铲位1 铲位2 铲位3 铲位4 铲位5 铲位6 铲位7 铲位8 铲位9 铲位10 矿漏 13 54 11 倒Ⅰ 42 43 岩场 70 15 岩漏 81 43 倒Ⅱ 13 2 70 （二）对最佳物流进行派车——第二阶段规划 这是一个组合优化中的一维装箱模型 装箱问题 装箱问题（Bin Packing）是一个经典的组合优化 问题，有着广泛的应用，在日常生活中也屡见不鲜 . 装箱问题的描述 设有许多具有同样结构和负荷的箱子 B1，B2，… 其数量足够供所达到目的之用 . 每个箱子的负荷（可为 长度、重量 etc.）为 C ,今有 n 个负荷为 wj，0 wj C j = 1，2，…，n 的物品 J1，J2，…，Jn 需要装入箱内. 装箱问题： 是指寻找一种方法，使得能以最小数量的箱子数将 J1，J2，…，Jn 全部装入箱内. 由于 wi C，所以 BP 的最优解的箱子数不超过 n . 设 箱子 Bi 被使用 否则 物品 Jj 放入箱子 Bi 中 否则 则装箱问题的整数线性规划模型为： 约束条件（1）表示：一旦箱子 Bi 被使用，放入 Bi 的物品总负荷不超过 C ； 约束条件（2）表示：每个物品恰好放入一个箱子中 . 上述装箱问题是这类问题最早被研究的，也是提 法上最简单的问题，称为一维装箱问题 . 但 装箱问题的其他一些提法： 1、在装箱时，不仅考虑长度，同时考虑重量或面积、 体积 etc . 即二维、三维、…装箱问题； 2、对每个箱子的负荷限制不是常数 C ; 而是 3、物品J1，J2，…，Jn 的负荷事先并不知道，来货是 随到随装；即 在线（On-Line）装箱问题； 2、对每个箱子的负荷限制不是常数 C ; 而是 BP 的应用举例： 1、下料问题 轧钢厂生产的线材一般为同一长度, 而用 户所需的线材则可能具有各种不同的尺寸, 如何根据用 户提出的要求，用最少的线材截出所需的定货； 2、 二维 BP 玻璃厂生产出长宽一定的大的平板玻璃, 但用户所需玻璃的长宽可能有许多差异，如何根据用 户提出的要求，用最少的平板玻璃截出所需的定货; 3、计算机的存贮问题 如要把大小不同的共 10 MB 的 文件拷贝到磁盘中去，而每张磁盘的容量为 1. 44 MB , 已知每个文件的字节数不超过 1.44 MB , 而且一个文件 不能分成几部分存贮，如何用最少的磁盘张数完成 . 装箱问题的近似算法 一、NF ( Next Fit ) 算法 设物品 J1，J2,…，Jn 的长度分别为 w1，w2,…，wn 箱子 B1，B2，…的长均为 C ，按物品给定的顺序装箱 . 先将 J1 放入 B1, 如果 则将 J2 放入 B1 … 如果 而 则 B1 已放入 J1，J2,…，Jj，将其关闭，将 Jj+1 放入 B2 . 同法进行，直到所有物品装完为止 . 特点： 1、按物品给定的顺序装箱； 2、关闭原则 . 对当前要装的物品 Ji 只关心具有最大下标的已使 用过的箱子 Bj 能否装得下？ 能. 则 Ji 放入 Bj ；否 . 关闭 Bj ，Ji 放入新箱子 Bj+1 . Example 1 物品 J1 J2 J3 J4 J5 J6 wj 6 7 4 2 8 3 I : C = 10 J1 J5 J6 J4 J3 J2 B1 B2 B3 B4 B5 J1 J2 J3 J4 J5 J6 Solution : 首先，将 J1 放入 B1; 由于 J2 在 B1 中放不下, 所 以关闭 B1 , 将 J2 放入 B2 , J3 在 B2 中放不下(不考虑 B1 是否能装), 所以关闭 B2 将 J3 放入 B3，… 解为: 其余为零 二、FF ( First Fit ) 算法 设物品 J1，J2,…，Jn 的长度分别为 w1，w2,…，wn 箱子 B1，B2，…的长均为 C ，按物品给定的顺序装箱 . 物品 J1 J2 J3 J4 J5 J6 wj 6 7 4 2 8 3 I : C = 10 用 NF 算法装 箱, 当放入 J3 时, 仅看 B2 是否能放入，因 B1 已关闭, 参见 EX .1 但事实上，B1 此时是能放得下 J3 的 . 如何修正 NF 算法 先将 J1 放入 B1，若