第七章整数规划模型.ppt

s．t． (平板车1的长度限制) (平板车2的长度限制 ) (平板车1的载重量限制) (平板车2的载重量限制 ) ( 类包装箱的件数限制 ) （对 、 、 三种型号包装箱长度的特别限制） 为整数 对上述整数线性规划问题，用分支定界法可以求得30个不同的解如下（没有利用的空间为0.6cm） 0 0 0 3 4 7 4 0 3 3 3 5 0 4 0 1 1 5 0 7 4 0 2 2 1 9 0 4 0 1 0 3 4 6 4 0 2 3 3 5 1 4 0 2 1 5 0 6 4 0 1 2 1 9 1 4 0 2 0 3 4 5 4 0 1 3 3 5 2 4 0 3 1 5 0 5 4 0 0 2 1 9 2 4 0 3 0 3 4 4 4 0 0 3 3 5 3 4 7 6 5 4 3 2 1 7 6 5 4 3 2 1 箱子类型 平板车2 平板车1 0 1 0 5 0 7 5 0 2 3 1 9 0 3 0 2 0 5 0 6 5 0 1 3 1 9 1 3 0 3 0 5 0 5 5 0 0 3 1 9 2 3 0 0 2 3 5 3 5 0 3 1 3 4 4 3 0 0 1 1 9 2 5 0 3 2 5 0 5 3 0 1 2 3 5 2 5 0 2 1 3 4 5 3 0 1 1 1 9 1 5 0 2 2 5 0 6 3 0 2 2 3 5 1 5 0 1 1 3 4 6 3 0 2 1 1 9 0 5 0 1 2 5 0 7 3 0 3 2 3 5 0 5 0 0 1 3 4 7 3 7 6 5 4 3 2 1 7 6 5 4 3 2 1 箱子类型 平板车2 平板车1 平板车2 平板车1 0 1 3 2 3 2 8 0 2 0 4 6 5 0 0 2 3 2 3 1 8 0 1 0 4 6 6 0 0 0 3 6 0 1 8 0 3 0 0 9 6 0 0 3 3 2 3 0 8 0 0 0 4 6 7 0 0 1 3 6 0 0 8 0 2 0 0 9 7 0 0 0 0 3 5 3 7 0 3 3 3 4 4 1 0 1 0 3 5 2 7 0 2 3 3 4 5 1 0 2 0 3 5 1 7 0 1 3 3 4 6 1 0 0 1 3 5 3 6 0 3 2 3 4 4 2 0 0 0 1 9 2 6 0 3 3 5 0 5 2 0 1 1 3 5 2 6 0 2 2 3 4 5 2 0 2 1 3 5 1 6 0 1 2 3 4 6 2 0 3 1 3 5 0 6 0 0 2 3 4 7 2 7 6 5 4 3 2 1 7 6 5 4 3 2 1 箱子类型 3.模型的分析 现在，我们分析求得的解是否是最优解？考虑 、 、 三种类型的箱子，它们有如下特别限制： 、 、 类箱子的件数限制为 （ ），记 ， ， ， 并把已知的 与 （ ）代入，我们有 为整数 这个问题的解共有315个，其中使 的最小值介于[292.2，302.7]的解有6个，列表如下： 292.2cm 0 0 6 292.7cm 3 1 1 295.5cm 0 1 5 296.0cm 3 2 0 298.8cm 0 2 4 302.1cm 0 3 3 可以看出对类型为 、 、 三种类型的包装箱，在所占空间（厚度）不能超过320.7cm的限制下，两辆平板车只能装运302.1cm宽度的包装箱。此时 类型和 类型的包装箱各装3只，不装 类型的包装箱。由 两辆平板车装运 、 、 、 四种类型的包装箱的空间厚度为1737.3cm。从而总的装运空间的厚度最多为 302.1+1737.3=2039.4（cm） 因此，装运的剩余空间至少为 2040-2039.4=0.6（cm） 因此，我们求得的30个解均为最优解。 如果我们进一步要求这两辆车装运包装箱后，使得剩余空间相同，此