第8章_整数规划(带答案)

1 第八章整数规划 运筹学 2 第八章整数规划 1整数规划的图解法 2整数规划的计算机求解 3整数规划的应用 4整数规划的分枝定界法 3 整数规划是一类要求变量取整数值的数学规划 可分成线性和非线性两类 求整数解的线性规划问题 应注意 不是用四舍五入法和去尾法对线性规划的非整数解加以处理就能解决的 整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的 根据变量的取值情况 整数线性规划又可以分为纯整数规划 所有变量取非负整数 混合整数规划 部分变量取非负整数 0 1整数规划 变量只取0或1 等 第八章整数规划 4 整数规划是数学规划中一个较弱的分支 目前有成熟的方法解线性整数规划问题 而非线性整数规划问题 还没有好的办法 整数线性规划 IntegerLinearProgramming 简记为ILP 问题研究的是要求变量取整数值时 在一组线性约束条件下一个线性函数最优问题 是应用非常广泛的运筹学的一个重要分支 第八章整数规划 5 1整数规划的图解法 例1 某公司拟用集装箱托运甲 乙两种货物 这两种货物每件的体积 重量 可获利润以及托运所受限制如表所示 甲种货物至多托运4件 问两种货物各托运多少件 可使获得的利润最大 6 解 设x1 x2分别为甲 乙两种货物托运的件数 建立模型 目标函数 Maxz 2x1 3x2约束条件 s t 195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0 为整数 如果去掉最后一个约束 就是一个线性规划问题 1整数规划的图解法 7 利用图解法 得到线性规划的最优解为x1 2 44 x2 3 26 目标函数值为14 66 由图表可看出 整数规划的最优解 黄色叉号 为x1 4 x2 2 目标函数值为14 Maxz 2x1 3x2 195x1 273x2 1365 4x1 40 x2 140 4 2 3 1 1 2 3 x2 x1 1整数规划的图解法 Maxz 2x1 3x2约束条件 s t 195x1 273x2 13654x1 40 x2 140 x1 4 8 由于相应的线性规划的可行域包含了其整数规划的可行点 则对于整数规划 易知有以下性质 性质1 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值 任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值 1整数规划的图解法 9 例2 Maxz 3x1 x2 3x3s t x1 2x2 x3 44x2 3x3 2x1 3x2 2x3 3x1 x2 x3 0 均为整数 用 管理运筹学 软件求解得 x1 5x2 2x3 2 2整数规划的计算机求解 纯整数规划问题 10 11 例3 Maxz 3x1 x2 3x3s t x1 2x2 x3 44x2 3x3 2x1 3x2 2x3 3x3 1x1 x2 x3 0 x1 x3为整数 x3为0 1变量 用 管理运筹学 软件求解得 z 16 25x1 4x2 1 25x3 1 12 3整数规划的应用 应用实例 投资场所的选择问题 背包问题 固定成本问题 指派问题 分布系统设计 投资问题 13 14 3整数规划的应用 一 投资场所的选择例4 京成畜产品公司计划在市区的东 西 南 北四区建立销售门市部 拟议中有10个位置Aj j 1 2 3 10 可供选择 考虑到各地区居民的消费水平及居民居住密集度 规定 在东区由A1 A2 A3三个点至多选择两个 在西区由A4 A5两个点中至少选一个 在南区由A6 A7两个点中至少选一个 在北区由A8 A9 A10三个点中至少选两个 Aj各点的设备投资及每年可获利润由于地点不同都是不一样的 预测情况见表所示 单位 万元 但投资总额不能超过720万元 问应选择哪几个销售点 可使年利润为最大 解 设 0 1变量xi 1 Ai点被选用 或0 Ai点没被选用 这样我们可建立如下的数学模型 Maxz 36x1 40 x2 50 x3 22x4 20 x5 30 x6 25x7 48x8 58x9 61x10s t 100 x1 120 x2 150 x3 80 x4 70 x5 90 x6 80 x7 140 x8 160 x9 180 x10 720 x1 x2 x3 2x4 x5 1x6 x7 1x8 x9 x10 2xi 0且xi为0 1变量 i 1 2 3 10 在东区由A1 A2 A3三个点至多选择两个 在西区由A4 A5两个点中至少选一个 在南区由A6 A7两个点中至少选一个 在北区由A8 A9 A10三个点中至少选两个 补充例 解决某市消防站的布点问题 该城市有6个区 每个区都可以建消防站 市政府希望设置的消防站最少 但必须满足在城市的任何地区发生火警时 消防车要在15分钟内赶到现场 据实地测定 各区之间消防车行驶的时间如下表所示 请帮助该市制定一个最省的计划 123456101016282720210024321710316240122721428321201525527172715014620102125140 设xi 1 0 1 i区建消防站 0 i区不建消防站 i 1 6minz x1 x2 x3 x4 x5 x6约束方程保证每个地区都有一个消防站在15分钟行程内 将6个地区的条件分别列出 s t x1 x2 1 x1 x2 x6 1x3 x4 1 x3 x4 x5 1x4 x5 x6 1 x2 x5 x6 1xi 0 1 i 1 6 123456101016282720210024321710316240122721428321201525527172715014620102125140 18 123456101016282720210024321710316240122721428321201525527172715014620102125140 第2个地区建一个 地区1 2 6都解决了 第4个地区建一个 地区3 4 5都解决了 二 背包问题 补充 背包可装入8单位重量 10单位体积物品 若背包中每件物品至多只能装一个 怎样才能使背包装的物品价值最高 解 xi为是否带第i种物品 MaxZ 20 x1 30 x2 10 x3 18x4 15x5 一般形式 整数 xi为是否携带第i种物品ai为i物品单位重量 b为最大负重ci为i物品重要性估价 22 3整数规划的应用 三 固定成本问题例5 高压容器公司制造小 中 大三种尺寸的金属容器 所用资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如表所示 不考虑固定费用 每种容器售出一只所得的利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人 月 机器有100台 月 此外不管每种容器制造的数量是多少 都要支付一笔固定的费用 小号是l00万元 中号为150万元 大号为200万元 现在要制定一个生产计划 使获得的利润为最大 23 解 这是一个整数规划的问题 设x1 x2 x3分别为小号容器 中号容器和大号容器的生产数量 各种容器的固定费用只有在生产该种容器时才投入 若不生产则没有这部分费用 为了说明固定费用的这种性质 设yi 1 当生产第i种容器 即xi 0时 或0 当不生产第i种容器即xi 0时 引入约束xi Myi i 1 2 3 M充分大 以保证当yi 0时 xi 0 3整数规划的应用 即 不投入固定费用 是不能投入生产的 24 这样我们可建立如下的数学模型 Maxz 4x1 5x2 6x3 100y1 150y2 200y3s t 2x1 4x2 8x3 5002x1 3x2 4x3 300 x1 2x2 3x3 100 xi Myi i 1 2 3 M充分大xj 0yj为0 1变量 i 1 2 3 3整数规划的应用 没有固定投入 就不生产 yi 0 则xi 0 xi是数量 M为一个充分大的数 一个容器至少需要2个劳动力 共有300个劳动力 因此容器数量不会超过150 因此当yi 1时 M可取150 投入固定费用 生产小号容器 y1y2y3 25 三 指派问题有n项不同的任务 恰好n个人可分别承担这些任务 但由于每人特长不同 完成各项任务的效率等情况也不同 现假设必须指派每个人去完成一项任务 怎样把n项任务指派给n个人 使得完成n项任务的总的效率最高 这就是指派问题 3整数规划的应用 26 例6 有四个工人 要分别指派他们完成四项不同的工作 每人做各项工作所消耗的时间如下表所示 问应如何指派工作 才能使总的消耗时间为最少 3整数规划的应用 27 解 引入0 1变量xij 并令xij 1 当指派第i人去完成第j项工作时 或0 当不指派第i人去完成第j项工作时 这可以表示为一个0 1整数规划问题 Minz 15x11 18x12 21x13 24x14 19x21 23x22 22x23 18x24 26x31 17x32 16x33 19x34 19x41 21x42 23x43 17x44 3整数规划的应用 28 整数规划模型为 Minz 15x11 18x12 21x13 24x14 19x21 23x22 22x23 18x24 26x31 17x32 16x33 19x34 19x41 21x42 23x43 17x44s t x11 x12 x13 x14 1 甲只能干一项工作 x21 x22 x23 x24 1 乙只能干一项工作 x31 x32 x33 x34 1 丙只能干一项工作 x41 x42 x43 x44 1 丁只能干一项工作 x11 x21 x31 x41 1 A工作只能一人干 x12 x22 x32 x42 1 B工作只能一人干 x13 x23 x33 x43 1 C工作只能一人干 x14 x24 x34 x44 1 D工作只能一人干 xij为0 1变量 i j 1 2 3 4 3整数规划的应用 每人只能干一项工作 一项工作只能由一个人干 对于有m个人完成n项任务的一般指派问题 设 29 m不一定等于n 当m n时 有的人没有任务 第i个人完成的任务且最多承担一项 第j项工作正好有一人承担 注意 当m n时 可以设假想的n m个人 使得新的总人数等于工作数 再按照常规解法求解 不管m和n是什么关系 只要利用 指派 问题求解即可 输入 人数 工作数 每个人完成各项任务的成本 即可求得最优解 30 31 四 分布系统设计例7 某企业在A1地已有一个工厂 其产品的生产能力为30千箱 为了扩大生产 打算在A2 A3 A4 A5地中再选择几个地方建厂 已知在A2 A3 A4 A5地建厂的固定成本分别为175千元 300千元 375千元 500千元 另外 A1产量及A2 A3 A4 A5建成厂的产量 销地的销量以及产地到销地的单位运价 每千箱运费 如下表所示 a 问应该在哪几个地方建厂 在满足销量的前提下 使得其总的固定成本和总的运输费用之和最小 b 如果由于政策要求必须在A2 A3地建一个厂 应在哪几个地方建厂 3整数规划的应用 32 3整数规划的应用 33 解 a 设xij为从工厂Ai运往销地Bj的运输量 单位千箱 yk 1 当Ak被选中时 或0 当Ak没被选中时 k 2 3 4 5 这可以表示为一个整数规划问题 Minz 175y2 300y3 375y4 500y5 8x11 4x12 3x13 5x21 2x22 3x23 4x31 3x32 4x33 9x41 7x42 5x43 10 x51 4x52 2x53其中前4项为固定投资额 后面的项为运输费用 3整数规划的应用 s t x11 x12 x13 30 A1厂的产量限制 x21 x22 x23 10 A2厂的产量限制 x31 x32 x33 20 A3厂的产量限制 x41 x42 x43 30 A4厂的产量限制 x51 x52 x53 40 A5厂的产量限制 x11 x21 x31 x41 x51 30 B1销地的限制 x12 x22 x32 x42 x52 20 B2销地的限制 x13 x23 x33 x43 x53 20 B3销地的限制 xij 0 i 1 2 3 4 5 j 1 2 3 yk为0 1变量 k 2 3 4 5 A1厂已经建了 y2 y3 y4 y5 y2y3y4y5 A1厂运到B1的量A5厂运到B2和B3的量 2 再加一个约束条件y2 y3 1即可 35 36 五 投资问题例8 某公司在今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利115 但要求第一年投资最低金额为4万元 第二 三 四年不限 项目B 第三年初需要投资 到第五年末能回收本利128 但规定最低投资金额为3万元 最高金额为5万元 项目C 第二年初需要投资 到第五年末能回收本利140 但规定其投资额或为2万元或为4万元或为6万元或为8万元 项目D 五年内每年初可购买公债 于当年末归还 并加利息6 此项投资金额不限 该部门现有资金10万元 问它应如何确定给这些项目的每年投资额 使到第五年末拥有的资金本利总额为最大 3整数规划的应用 解 1 设xiA xiB xiC xiD i 1 2 3 4 5 分别表示第i年年初给项目A B C D的投资额 这样我们建立如下的决策变量 第1年第2年第3年第4年第5年Ax1Ax2Ax3Ax4ABx3BCx2C 20000y2CDx1Dx2Dx3Dx4Dx5D 规定其投资额或为2万元或为4万元或为6万元或为8万元 38 2 约束条件 第一年 年初有100000元 D项目在年末可收回投资 故第一年年初应把全部资金投出去 于是x1A x1D 100000 第二年 A的投资第二年末才可收回 第一年年末只有D项目可收回 故第二年年初的资金为1 06x1D 于是x2A x2C x2D 1 06x1D 第三年 年初的资金为1 15x1A 1 06x2D 于是x3A x3B x3D 1 15x1A 1 06x2D 第四年 年初的资金为1 15x2A 1 06x3D 于是x4A x4D 1 15x2A 1 06x3D 第五年 年初的资金为1 15x3A 1 06x4D 于是x5D 1 15x3A 1 06x4D 3整数规划的应用 39 关于项目A B C的投资额度的约束 项目A第一年年初投资最低金额为4万元 项目B第三年年初投资最低金额为3万元 最高金额为5万元 项目C第二年年初投资额度或为2 4 6 8万元 这些年份可以给相应项目投资 也可以不投资 如果投资的话就要遵守上述约定 因此 设0 1变量 yiA yiB yiC是第i年年初给项目A B C投资的情况 1为投资 0为不投资 对应上述约定 应该分别设为y1A y3B y2C y2C只用0 1不能详尽表述 则对y2C重新规定 第2年投资C项目8万元时 取值为4 第2年投资C项目6万元时 取值3 第2年投资C项目4万元时 取值2 第2年投资C项目2万元时 取值1 第2年不投资C时 取值0 x2C 20000y2C 40 关于项目A的投资额规定 x1A 40000y1A x1A My1A M是足够大的数 取200000 保证当y1A 0时 x1A 0 当y1A 1时 x1A 40000 关于项目B的投资额规定 x3B 30000y3B x3B 50000y3B 保证当y3B 0时 x3B 0 当y3B 1时 50000 x3B 30000 关于项目C的投资额规定 x2C 20000y2C y2C 0 1 2 3 4 3整数规划的应用 3 目标函数及模型 Maxz 1 15x4A 1 40 x2C 1 28x3B 1 06x5Ds t x1A x1D 100000 x2A x2C x2D 1 06x1D x3A x3B x3D 1 15x1A 1 06x2D x4A x4D 1 15x2A 1 06x3D x5D 1 15x3A 1 06x4D x1A 40000y1A x1A 200000y1A x3B 30000y3B x3B 50000y3B x2C 20000y2C y1A y3B 0或1y2C 0 1 2 3 4xiA xiB xiC xiD 0 i 1 2 3 4 5 4整数规划的分枝定界法 分枝定界法既能求解纯整数规划问题 又能求解混合整数规划问题 分枝定界法是先求解整数规划相应的线性规划问题 若其最优解不符合整数条件 则求出整数规划的上下界用增加约束条件的方法 把相应的线性规划的可行域分成子区域 分枝 再求解上述子区域的线性规划问题 不断缩小整数规划的上下界的距离 最终求得整数规划的最优解 42 用分枝定界法求解整数线性规划问题 例9 maxz 2x1 3x2s t 195x1 273x2 1365 4x1 40 x2 140 x1 4x1 x2 0 且为整数解 1 先求出相应LP问题的解 即maxz 2x1 3x2s t 195x1 273x2 1365 4x1 40 x2 140 x1 4 x1 x2 0 43 线性规划1 z1 14 66 x1 2 44 x2 3 26 2 确定整数规划的最优目标函数值Z的初始上界和下界 上界不超过14 66 性质1 下界 观察法求出一个整数规划的可行解 求得目标函数值 作为最优目标函数值的下界 约束方程的变量系数都大于等于0 不等号都为小于等于 因此 将LP问题的解去尾取整 都变小了 一定是整数规划问题的可行解 则 x1 2 x2 3 2x1 3x2 13 下界 44 x1 2 44 x2 3 26 3 将一个线性规划问题分为两枝 求解 怎么分枝 将线性规划1中的最优解的两个非整数变量x1 2 44 x2 3 26中挑选一个离整数最远的变量x1 若x1取整数值 则x1可由x1 2或x2 3范围内取得 在线性规划1中加入两个上述约束条件 将其分枝为线性规划2和线性规划3 45 46 max2x1 3x2s t 195x1 273x2 1365 4x1 40 x2 140 x1 4x1 3x1 x2 0 max2x1 3x2s t 195x1 273x2 1365 4x1 40 x2 140 x1 4x1 2x1 x2 0 线性规划2 线性规划3 z2 13 9 x1 2 x2 3 30 z2 14 58 x1 3 x2 2 86 4 修改整数线性规划的最优目标函数值的上 下界上界 线性规划2中 增加x1 2 整数规划的最优目标函数值不超过13 90 性质1 线性规划3中 增加x1 3 整数规划的最优目标函数值不超过14 58 性质1 因此 上界修改为14 58 取大者 下界 线性规划2中 一定有整数规划可行解x1 2 x2 3 目标函数值为13线性规划3中 一定有整数规划可行解x1 3 x2 2 目标函数值为12因此 下界修改为13 取大者 47 相比原来的上界14 66 变小了 相比原来的下界 恰好没变 为了求出最优整数解 不断缩小其最优目标函数值的上下界的距离 通过分枝使得上界越来越小 下界越来越大 才有可能使得上下界重合 找到最终的整数最优解 x1 2 x2 3 30 x1 3 x2 2 86 5 在线性规划2和线性规划3中选择一个上界最大线性规划进行分枝 本题取线性规划3分枝 怎么分枝 线性规划3的最优解为x1 3 x2 2 86 x2与整数距离最远 将其分成x2 2和x2 3两种情况 分别作为约束条件加在线性规划3中 因此 线性规划3分枝成线性规划4和线性规划5 48 49 max2x1 3x2s t 195x1 273x2 1365 4x1 40 x2 140 x1 4x1 3x2 3x1 x2 0 max2x1 3x2s t 195x1 273x2 1365 4x1 40 x2 140 x1 4x1 3x2 2x1 x2 0 线性规划4 线性规划5 z2 14 x1 4 x2 2 无可行解 6 进一步修改整数规划最优目标函数值的上下界上界 目标函数值对应的最优值分别为13 90 14和无解 因此上界14 取大者 下界 线性规划2存在整数可行解x1 2 x2 3 目标函数值为13线性规划4存在整数可行解x1 4 x2 2 目标函数值为14线性规划5无解下界改为14 取大者 50 考察线性规划2 4 5 上下界重合 1 2 3 4 5 x1 2 x2 3 30 x1 4 x2 2 性质2当整数规划的最优目标函数值的上界等于其下界时 该整数规划的最优解已被求出 这个整数规划的最优解即为其目标函数值取此下界的对应线性规划的整数可行解 本题即取线性规划4的解为最优解 x1 4 x2 2 51 例 分枝定界法的求解思路图 线性规划1Z1 14 66X1 2 44X2 3 26 线性规划2Z2 13 90X1 2X2 3 30 X1 2 X1 3 X2 2 X2 3 z 14 14 线性规划4Z4 14 00X1 4X2 2 线性规划5无可行解 线性规划3Z3 14 58X1 3X2 2 86 利用观察法取得X1 2 X2 3求出下界 则下 上界分别为 x1 2 x2 3求出目标函数值13作为下界 x1 3 x2 2求出目标函数值12作为下界 x1 4 x2 2求出目标函数值14 53 4整数规划的分支定界法 分枝定界法步骤 总结 第一步 求解与IP 整数规划 问题A 相应的LP 线性规划 问题B 问题 可能会出现下面几种情况 若B所得的最优解的各变量恰好取整数 则这个解也是原整数规划的最优解 计算结束 若B无可行解 则原整数规划问题也无可行解 计算结束 若B有最优解 但其各分量不全是整数 则这个解不是原整数规划的最优解 记录其目标函数Z1值 第二步 确定A的最优目标函数值的Z 上下界 上界即为刚才记录的Z1 下界利用观察法找到A的一个整数可行解 将其目标函数值作为Z 的下界z第三步 判断是否等于z 若不等 继续 第四步 在B的不满足整数条件的最优解中选一个最远离整数的变量如xl 进行分枝 构造两个约束条件xl xl xl xl 1 把这两个约束条件分别加进原问题B中 形成两个互不相容的子问题Bl B2 分枝 第五步 求解分枝Bl B2 修改问题A的最优目标函数值的上下界 取分枝Bl B2的最优目标函数值中最大的值作为新的上界 用观察法取分枝Bl B2的各自的整数可行解 选择其中一个较大的目标函数值作为新的下界 第六步 各个分枝的最优目标函数中小于目前的上界 则剪掉该分枝 若大于 但不符合整数条件 则重复第三步至第六步 直到上下界相等 55 56 本章结束 作业 3 7 第八章整数规划 第3题 设Xi为第i项工程 i 1 2 3 4 5 Xi为0 1变量 Xi为0时 表明该项目没有被选中Xi为1时 表明该项目被选中三年后总收入最大的目标函数为 MAXZ 20X1 40X2 20X3 15X4 30X5S T 5X1 4X2 3X3 7X4 8X5 25X1 7X2 9X3 4X4 6X5 258X1 10X2 2X3 X4 10X5 25X1 X2 X3 X4 X5 0 且为0 1变量 57 第4题 设X1 X2 X3分别为利用A B C设备生产的产品的件数 成本包括生产准备费 生产成本两部分 生产准备费为固定费用 只有利用该设备时才发生这部分费用 因此设一个0 1变量yi 设yi 1时 当利用第i种设备生产时 此时相应的Xi 0yi 0时 当不利用第i种设备生产时 此时相应的Xi 0目标函数为 MinZ 7x1 2x2 5x3 100y1 300y2 200y3 58 1 约束条件X1 800 X2 1200 X3 1400 X1 X2 X3 2000 改大于等于结果相同 0 5X1 1 8X2 1 0X3 2000还得保证Yi 0时 Xi 0 没有准备费就不启用该设备 引入一个很大的MXi MYi i 1 2 3 Xi 0 i 1 2 3 Yi i 1 2 3 是0 1变量 59 2 约束条件改为0 5X1 1 8X2 1 0X3 2500 60 3 约束条件改为0 5X1 1 8X2 1 0X3 2800 61 4 去掉电量的约束条件 62 第5题 63 64 yi是0 1变量 yi 0 相当于该库房不存在 需求量 上海y2 武汉y40 10 01 1 最多2个库房 武汉和广州不能同时建 i 1 2 3 4 北京上海广州武汉 华北华中华南 2 第6题 指派问题 1 引入0 1变量xij 并令xij 1 当指派第i人去完成第j项工作时 0 当不指派第i人去完成第j项工作时 目标函数MinZ 20 x11 19x12 20 x13 28x14 18x21 24x22 27x23 20 x24 26x31 16x32 15x33 18x34 17x41 20 x42 24x43 19x44 65 x11 x12 x13 x14 1 甲只能干一项工作 x21 x22 x23 x24 1 乙只能干一项工作 x31 x32 x33 x34 1 丙只能干一项工作 x41 x42 x43 x44 1 丁只能干一项工作 x11 x21 x31 x41 1 A工作只能一人干 x12 x22 x32 x42 1 B工作只能一人干 x13 x23 x33 x43 1 C工作只能一人干 x14 x24 x34 x44 1 D工作只能一人干 66 2 把目标函数改为求最大值即可 即 MaxZ 20 x11 19x12 20 x13 28x14 18x21 24x22 27x23 20 x24 26x31 16x32 15x33 18x34 17x41 20 x42 24x43 19x44约束条件不变 67 3 增加了一项工作E 问应指派四个人干哪四项工作 共有五项工作 则结果中肯定有一项工作无人做 m n 人数少于任务数 此时 添加虚拟人数n m 1个 该人是虚拟的 因此完成各项工作所需的时间都设为0 此时变为5个人完成5项工作的问题了 MinZ 20 x11 19x12 20 x13 28x14 17x15 18x21 24x22 27x23 20 x24 20 x25 26x31 16x32 15x33 18x34 15x35 17x41 20 x42 24x43 19x44 16x45 0 x51 0 x52 0 x53 0 x54 0 x55 68 甲乙丙丁每个人做第5项工作的时间 约束条件x11 x12 x13 x14 x15 1x21 x22 x23 x24 x25 1x31 x32 x33 x34 x35 1x41 x42 x43 x44 x45 1x51 x52 x53 x54 x55 1x11 x21 x31 x41 x51 1x12 x22 x32 x42 x52 1x13 x23 x33 x43 x53 1x14 x24 x34 x44 x54 1x15 x25 x35 x45 x55 1 69 结果中安排第5个虚拟人去做哪项工作 表明实际中该项工作无人做 70 方法二 x11 x12 x13 x14 x15 1 甲只能干一项工作 x21 x22 x23 x24 x25 1 乙只能干一项工作 x31 x32 x33 x34 x35 1 丙只能干一项工作 x41 x42 x43 x44 x45 1 丁只能干一项工作 x11 x21 x31 x41 1 A工作 x12 x22 x32 x42 1 B工作 x13 x23 x33 x43 1 C工作 x14 x24 x34 x44 1 D工作 x15