3分派与装载.ppt

2 16 2020 1 3分派与装载 2 16 2020 2 生活和工作中经常碰到任务分派问题 如由5个人承担5项任务 由于各人的专长不同 他们完成各项任务的时间 或代价 不同 那么派谁去完成哪项任务使总的效率最高呢 类似的问题很多 例4车间有n项加工任务 分派给n个工人完成 已知每个人完成各项任务的时间 其中有若干人不能完成某几项任务 问如何进行任务分派 使所需总时间最少 解 将工人编号为i 1 2 n 任务编号为j 1 2 n 第i人完成第j项任务的时间记为cij 若第i人不能完成任务j 则记cij M M是充分大的正数 任务分派用如下的0 1变量表述 2 16 2020 3 问题的目标函数 总时间为 1 约束条件为 2 3 4 其中 2 说明第i人只能完成一项任务 3 说明任务j只能由一人完成 2 16 2020 4 其中 2 说明第i人只能完成一项任务 3 说明任务j只能由一人完成 这里决策变量xij只能取值0和1 称为0 1规划 满足 2 4 的可行解xij可表为矩阵形式 其中每一行和每一列都必须有且只能有一个1 其余元素均为0 引入0 1变量解决任务分配问题还可以有其他方式 如例5工厂用k种不同工艺生产n种产品 每种产品的利润已知 在各种工艺条件下每种产品所消耗的资源 如原料 是确定的 并且工厂的总资源有一定的限制 问应选择哪种工艺 每种产品各生产多少 使总利润最高 2 16 2020 5 解 用A1 A2 Ak表示k种工艺 B1 B2 Bn表示n种产品 已知单件Bi的利润为Pi i 1 2 n 设在工艺Aj下 j 1 2 k 单件Bi的资源消耗为cij 资源限制为Qj 显然 Bi的产量是决策变量 记为xi 目标函数 总利润为 1 在任一种工艺Aj下 资源限制都可以表为 2 2 16 2020 6 为确定工艺的选择 引入0 1变量为了使 2 式k个条件中只有被选中的某一个起作用 2 式代之以 3 4 5 6 其中M是一个充分大的正数 2 16 2020 7 这样 y1 y2 yk中有k 1个取值1 这些yj对 3 是多余的 只有取值0的那个在 3 式中起作用 它就相应于被选中的工艺 于是问题归结为条件 3 6 下求 1 式的Z最大 这是混合0 1规划模型 最优装载也是日常生活中经常碰到的问题 如空运若干种物资 每种物资的价值与装载上飞机的数量有关 而装载的总量受到飞机对重量 体积等条件的限制 问每种物资装载多少使空运的总价值最大 这类问题具有类似的模型 试看下例 2 16 2020 8 例6 要把7种规格的包装箱装到两辆铁路平板车上去 箱子宽 高相同 而厚度和重量不同 下表给出了它们的厚度 重量和数量 每辆平板车有10 2米长的地方用于装箱 像面包片那样 载重40吨 由于货运限制 对c5 c6 c7三种包装箱的装载有如下特殊约束 它们所占的空间 厚度 不得超过302 7厘米 试把包装箱装到平板车上 使浪费的空间最小 2 16 2020 9 解 容易算出所有包装箱的厚度为27 495米 而两辆车共有20 4米长的地方 所以不可能全装上 记表中所给第i种箱子ci的厚道度 重量和数量分别为ti wi ni i 1 2 7 问题的决策变量是装载到两辆车上的数量 记ci装到1 2辆车上的数量为xi1 xi2 问题要求使浪费空间最小 等价于装载所占的空间最大 故目标函数可表为 1 约束条件包括