1. PERT计划评审技术三点估算法这是一道非常典型的软件工程项目管理题目主要考查PERT三点估算法和关键路径法CPM的综合应用。1.1.计算作业 C 的期望完成时间题目给出了作业 C 的三个估算值我们需要使用 PERT 期望时间公式进行计算乐观时间 (to​) 5 天最可能时间 (tm​) 14 天保守时间 (tp​) 17 天期望时间 (te​) 公式te​(to​4×tm​tp​)/6 代入数据te​(54×1417)/6(55617)/678/613天1.2. 找出项目的所有路径并确定关键路径我们需要列出从项目开始到结束的所有可能路径并计算它们的总工期路径 1Start→ A →B → D → E → G 工期5(A)7(B)8(D)3(E)4(G)27路径 2Start → A → C → E → G 工期5(A)13(C)3(E)4(G)25路径 3Start → F → G 工期20(F)4(G)24关键路径是耗时最长的路径即路径 127 天。1.3. 计算作业 C 的总时差浮动时间作业 C 所在的路径是“路径 2”25 天而关键路径是“路径 1”27 天。总时差 (Total Float) 关键路径总工期 - 包含该作业的路径工期对于作业 C27−252天这意味着作业 C 拥有2 天的缓冲时间时差。只要它的延迟不超过 2 天就不会影响项目的总工期27 天。1.4 核心技巧总结看到“乐观、最可能、保守”立刻用 (o4mp)/6 算期望值。求“能不能拖延”先找最长的路径关键路径再看包含该任务的路径比关键路径短多少差值就是能拖延的时间。注意紧前关系比如 E 必须等 C 和 D 都完成如果 C 花了 15 天132它还是在 20 天结束AC不影响 E 开工因为 D 要到第 20 天才结束ABD。这就是时差的本质。2. 项目时间与成本优化网络图赶工某工程包括A、B、C、D四个作业其衔接关系、正常进度下所需天数和所需直接费用、赶工进度下所需的最少天数和每天需要增加的直接费用见下表。该工程的间接费用为每天5万元。据此可以估算出完成该工程最少需要费用万元以此最低费用完成该工程需要天。2.1 第一步定基准最差情况最长路径A-C-D12天(A - B 是 10天。初始成本直接费(55) 间接费(12 *560) 115万。2.2 第二步疯狂赚差价贪心压缩核心公式净赚 5万 - 赶工费。只要净赚 0就干第一刀单线压缩当前只有A-C-D是关键路径。上面最便宜的是 D2万。压 D 压 2天为了和 AB 的 10天平齐。赚差价(5 - 2) *2天 6万。第二刀双线压缩现在两条线都是 10天了。找公共节点 A4万。压 A 压到极限最少1天所以能压 2天。赚差价(5 - 4) *2天 2万}。第三刀双线压缩两条线都是 8天了。A 压干了只能各挑一个便宜的B(2万) D(2万) 4万。压 B 和 D压 1天因为 D 之前压了2天只剩最后1天额度了。赚差价(5 - 4) *1天 1万。第四刀尝试两条线都是 7天。A、D 都干了只能压 B(2) C(4) 6万。6万 5万亏本立刻停手。2.3 第三步算总账总共赚了省下6 2 1 9万最低费用初始 115 - 省下 9 106 万最短天数初始 12 - (压2压2压1) 7 天考场避坑指南只要出现多条关键路径长度一样时千万记得要减一起减必须找公共节点或者各选一个节点同时花钱否则单压一条路径总工期是不会变的钱却白花了做这种题不要一上来就算每个任务的极限成本严格按照这个“贪心算法”跑先画图找最长关键路径算出初始总价基准线。只在关键路径上找最便宜的捏。一旦捏出多条关键路径一样长必须同时捏成本相加一旦相加的成本 小于5万立刻停手3. 投资收益最大化某公司有4百万元资金用于甲、乙、丙三厂追加投资。各厂获得不同投资款后的效益见下表。适当分配投资以百万元为单位可以获得的最大的总效益为百万元。既然我们的目标是“好钢用在刀刃上”我们只需要看每多投 1 百万能多赚多少钱边际收益。挑那个增长最猛的投我们在草稿纸上快速算出每个厂每增加 1 百万投资带来的“差价增量*甲厂增量0.3 (投1) - 0.7 (投2) -1.2 (投3)- 0.6 (投4)乙厂增量0.2 (投1) - 0.8 (投2) - 1.0 (投3) - 0.6 (投4)丙厂增量1.6 (投1)- 0.4 (投2) - 1.0 (投3) - 0 (投4)开始像大老板一样分钱总共 4 百万第一笔巨款给谁看一眼增量丙厂投第 1 个百万时收益暴增1.6这笔买卖太划算了必须给丙投 1 百万。剩余资金3 百万剩下的 3 百万怎么分我们继续看谁的增量大。甲厂在投第 3 个百万时有一个高达1.2的收益突变。为了吃到这 1.2 的暴利我们必须给甲连续投 3 百万增量合计0.3 0.7 1.2 2.2。对比一下如果这 3 百万给乙增量 0.2 0.8 1.0 2.0显然不如给甲划算。敲定方案丙投 1 百万甲投 3 百万乙不投0 百万。核算总收益甲投 36.0乙投 04.0丙投 16.4合计6.0 4.0 6.4 16.44. 指派问题甲、乙、丙、丁4人加工A、B、C、D四种工件所需工时如下表所示。指派每人加工一种工件四人加工四种工件其总工时最短的最优方案中工件B应由加工。4.1 原理分析这正是解决指派问题的数学基石也是著名的匈牙利算法的核心原理。为什么这个思路是对的数学原理在一个指派矩阵中如果你对某一行或某一列的所有元素同时减去一个常数 k那么由于任何一个合法的指派方案都必须且只能从这一行中选出一个元素所以所有可能方案的总和都会刚好减少 k结论 既然所有方案都同时变小了它们之间的“相对大小关系”没有改变那么原本最小的方案在减完之后依然是最小的。为什么要把元素变成 0我们的最终目标是在矩阵中找到一组位于不同行、不同列的 0。如果矩阵中所有元素都 ≥0而你找到了一组互相独立的 0总和为 0那么这组指派一定是绝对最优解因为总和不可能比 0 更小了。通过行列减法创造出的 0实际上代表了在该行或该列中相对效率最高的选择。4.2 具体算法对该矩阵并不存在全0指派。位于(13)、(21)、(34)、(42)的元素之和为1是最小的。因此分配甲、乙、丙、丁分别加工C、A、D、B能达到最少的总工时28129。更进一步再在第三行上都加1在第2、4列上都减1可得到更多的0元素本题也可用试验法解决但比较烦琐需要仔细不要遗漏。5.流水车间调度问题题目有 3 道工序设计、制造、检验原版的约翰逊法则只适用于 2 道工序。我们要做的第一步就是“降维打击”把 3 道工序捏合成 2 道虚拟工序。第一步合并出两道“虚拟工序”虚拟工序 A 第一道工序设计 第二道工序制造虚拟工序 B 第二道工序制造 第三道工序检验我们把表格里的数据加一下甲A 1315 28 B 1520 35乙A 1020 30 B 2018 38丙A 2016 36 B 1610 26丁A 810 18 B 1015 25第二步应用法则排序核心口诀谁小排谁A小排前B小排后在刚才算出的所有 A 和 B 的数值中找最小值进行排位全场最小值是18它属于丁的工序A。因为是在 A前半段所以把丁尽可能往前排。丁排第 1。排除丁剩下的数值中最小的是26它属于丙的工序B。因为是在 B后半段所以把丙尽可能往后排。丙排倒数第 1第 4。现在只剩下甲和乙它们中最小的数字是28属于甲的工序A。在前半段尽可能往前排。甲排第 2。最后只剩下乙自动填入空位。乙排第 3。得出最优生产顺序丁 、 甲 、乙 、丙。第三步画线推演计算总时间确定了顺序丁-甲-乙-丙我们来模拟一下这 3 个部门的流水线注意下一个部门必须等上一个部门干完且自己部门空闲才能开工。先做丁设计第 0 天开始第8天完工。制造第 8 天开始第18天完工。检验第 18 天开始第33天完工。接着做甲设计丁第 8 天设计完就空出来了甲直接上。8 13 第21天完工。制造甲 21 天设计完此时制造部门18天就搞定丁了闲着直接上。21 15 第36天完工。检验甲 36 天制造完检验部门33天搞定丁了闲着直接上。36 20 第56天完工。接着做乙设计甲 21 天走人乙直接上。21 10 第31天完工。制造乙 31 天设计完但制造部门还在干甲要干到36天乙必须等等到第 36 天开干。36 20 第56天完工。检验乙 56 天制造完正好检验部门也刚干完甲56天无缝衔接。56 18 第74天完工。最后做丙设计乙 31 天走人丙直接上。31 20 第51天完工。制造丙 51 天设计完制造部门在干乙到56天丙必须等等到第 56 天开干。56 16 第72天完工。检验丙 72 天制造完检验部门在干乙到74天丙必须等等到第 74 天开干。74 10 最终第 84 天完工为了直观感受到这种“互相等待”的流水线时间消耗制作了一个可交互的甘特图模拟器6.概率统计题1路和2路公交车都将在10分钟内均匀随机地到达同一车站则它们相隔4分钟内到达该站的概率为。第一步画出“总地盘”样本空间x 可以取 0 到 10y 也可以取 0 到 10。这就构成了一个边长为 10 的大正方形。总面积 10 *10 100。第二步画出“目标地盘”符合条件的区域题目要求两车相隔 4 分钟以内到达翻译成数学语言就是|x - y| 4。把绝对值拆开就是两条线之间的区域y x 4y x - 4在刚才的正方形里画出这两条线你会发现它们截出了中间的一条“斜向上的宽带子”。第三步反向算面积抓小头算中间那条不规则带子的面积有点麻烦我们直接算正方形左上角和右下角被切掉的那两个空白直角三角形的面积。左上角三角形的两个直角边因为从 4 开始截断边长是 $10 - 4 6$。面积 ( 6* 6) / 2 18。右下角三角形同样如此边长也是 6。面积 (6 *6) / 2 18。不符合条件的面积两个空白三角形 18 18 36。第四步得出概率符合条件的面积中间的带子 总面积 100 - 空白面积 36 64。概率 符合条件的面积 / 总面积 64 / 100 0.64。