运筹学培训教材

运筹学基础付秀慧----行政中心一个早晨的事件时间如下表所示

请计算完成这些事件最短的时间

（如果事件C的时间是15分）？工序A(穿衣服）B（烧开水）C（烧稀饭）D（涮牙）E（洗脸）F（上厕所）G（吃早饭）H（听外语）I（冲开水）紧前工序--A、IA、IC、D、EB作业时间37202255202运筹学的名称英文名称：OperationalReseach(英国），OperationsReseach(美国）中国取自于古语“夫运筹帷幄之中，决胜千里之外”比较好的反映了它的本质：谋划、计划，以策略到胜。运筹学的定义运筹学是一门研究如何有效组织和管理人机系统的科学。运筹学是为决策机构对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。莫斯（P.M.Morse）和金博尔（G.E.Kimball）运筹学是运用科学的方法、技术和工具来处理一个系统运行中的问题，使系统的控制得到最优的解决方案。（Cherchman)运筹学所研究的问题通常是在要求分配有限的资源下，科学的决定如何最好的设计和运营人机系统。（美国运筹学会）运筹学是运用分析、试验、量化的方法对经济管理系统中人力、财力、物力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。（中国管理百科全书）运筹学作用和意义大幅度的节约成本，提高系统效率。运筹学的应用领域市场营销，生产计划，库存管理，运输问题，财政和会计，人事管理，设备维修、更新和可靠性、项目选择和评价，工程的优化设计，计算机和信息系统，城市管理

配料问题

某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表格。该厂应如何安排生产，使利润收入为最大?

产品计划问题

某厂生产I，II，III三种产品，都分别经A，B两道工序加工。设A工序可分别在设备A1或A2上完成，B工序可在B1，B2，B3三种设备上完成。已知产品I可在A，B任何一种设备上加工；产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工，产品III只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如表格所示，试安排最优生产计划，使该厂获利最大。网络计划第1节网络计划图

第2节网络计划图的时间参数计算。

第3节时标网络计划图

第4节网络计划的优化

第5节网络计划软件

第1节

网络计划图网络计划图的基本思想是：首先应用网络计划图来表示工程项目中计划要完成的各项工作，完成各项工作必然存在先后顺序及其相互依赖的逻辑关系；这些关系用节点、箭线来构成网络图。网络图是由左向右绘制，表示工作进程。并标注工作名称、代号和工作持续时间等必要信息。通过对网络计划图进行时间参数的计算，找出计划中的关键工作和关键线路；通过不断改进网络计划，寻求最优方案，以求在计划执行过程中对计划进行有效的控制与监督，保证合理地使用人力、物力和财力，以最小的消耗取得最大的经济效果。基本术语网络计划图是在网络图上标注时标和时间参数的进度计划图，实质上是有时序的有向赋权图。

⑴节点，箭线是网络计划图的基本组成元素。节点用“○”或“□”表示箭线之间的连接点。箭线是一带箭头实射线,虚射线，用“→”,“”表示。

⑵工作（曾称工序、活动、作业）将整个项目按需要粗细程度分解成若干需要耗费时间或需要耗费其他资源的子项目或单元。它们是网络计划图的基本组成部分。第1节网络计划图(3)双代号网络计划图在双代号网络计划图中，用箭线表示工作，箭尾的节点表示工作的开始点，箭头的节点表示工作的完成点。用(i–j)两个代号及箭线表示一项工作。在箭线上标记必须的信息，如

(4)单代号网络计划图用节点表示工作，箭线表示工作之间的先完成与后完成的关系为逻辑关系。在节点中标记必需的信息，如以下主要介绍双代号网络计划图1.2双代号网络计划图例1开发一个新产品，需要完成的工作和先后关系，各项工作需要的时间汇总在逻辑关系表中，见下页表。要求编制这项目的网络计划图和计算有关参数。序号工作名称工作代号工作持续时间（天）紧后工作1产品设计和工艺设计A60B,C,D,E2外购配套件B45L3锻件准备C10F4工装制造1D20G,H5铸件E40H6机械加工1F18L7工装制造2G30K8机械加工2H15L9机械加工3K25L10装配与调试L35/根据表中数据，绘制以下网络图。正确绘制网络计划图，应遵循以下规则1.网络计划图的方向、时序和节点编号网络计划图是有向、有序的赋权图，按项目的工作流程自左向右地绘制。在时序上反映完成各项工作的先后顺序。节点编号必须按箭尾节点的编号小于箭头节点的编号来标记。在网络图中只能有一个起始节点，表示工程项目的开始。一个终点节点，表示工程项目的完成。2.紧前工作和紧后工作紧前工作是指紧排在本工作之前的工作；紧前工作完成后，才能开始本工作。紧后工作是指紧排在本工作之后的工作；本工作完成后，才能开始紧后工作。如图11-3中，只有工作A完成后工作B,C,D,E才能开始，工作A是B,C,D,E的紧前工作；而工作B,C,D,E则是工作A的紧后工作。3.虚工作在双代号网络计划图中，虚工作只表示相邻工作之间的逻辑关系，不占用时间和不消耗人力，资金等的虚设的工作。虚工作用虚箭线表示。4.相邻两节点之间只能有一条箭线连接的规则。

否则将造成逻辑上的混乱。下图中左图是错误画法，为了使两节点之间只有一条箭线，可增加一个节点②′，增加一项虚工作②′②。右图是正确的画法应改正为5.网络计划图中不能有缺口和回路。在网络计划图中严禁出现从一个节点出发，顺箭线方向又回到原出发节点，形成回路。回路将表示这工作永远不能完成。网络计划图中不能出现缺口，表示某些工作永远达不到终点，项目无法完成。7.起始节点与终点节点。在网络计划图中只能有一个起始节点和一个终点节点。当工程开始或完成时存在几个平行工作时，可以用虚工作将它们与起始节点或终点节点连接起来。12s6.平行工作

可与本工作同时进行的工作

交叉工作

两件或两件以上的工作交叉进行8.线路：网络图中从起点节点沿箭线方向顺序通过一系列箭线与节点，最后到达终点节点的通路。本例中有五条线路。并可以计算出各线路的持续时间如下表线路线路的组成各工作的持续时间之和（天）1①→②→⑦→⑧60＋45＋35=1402①→②→③→⑦→⑧60＋10＋18＋35=1233①→②→④→⑥→⑦→⑧60＋20＋30＋25＋35=1704①→②→④→⑤→⑦→⑧60＋20＋15＋35=1305①→②→⑤→⑦→⑧60＋40＋15＋35=150关键路线网络图中持续时间最长线路是关键路线。关键路线上的各工作为关键工作。其持续时间就决定了整个项目的工期。第2节网络计划图的时间参数计算网络计划的时间参数计算：双代号网络计划有工作计算法和节点计算法；单代号网络计划有节点计算法。仅介绍双代号网络图的工作计算法。

网络图中工作的时间参数：工作持续时间(D)；工作最早开始时间（ES）；工作最早完成时间（EF）；工作最迟开始时间（LS）；工作最迟完成时间（LF）；工作总时差（TF）；工作自由时差（FF）。第3节时标网络计划图

时间坐标，简称时标。在网络计划图的上方或下方，加表示工程进度时间的坐标轴。根据需要规定时间单位为：小时、天、周、月或季。标注有时间坐标的网络计划图称为：时标网络计划图。在该图中箭线的长度就表示工作持续时间的长度。并且在图中可以用实粗箭线或实红色的箭线表示关键工作和关键线路。并且可用不同的线型表示出工作的总时差和自由时差。例1的时标网络计划图如图所示。图第4节网络计划的优化

绘制网络计划图，计算时间参数和确定关键线路，仅得到一个初始计划方案。然后根据上级要求和实际资源的配置，需要对初始方案进行调整和完善。即进行网络计划优化。目标是综合考虑进度，合理利用资源，降低费用等。包括：4.1工期优化。

4.2资源优化4.3时间－费用优化4.1工期优化若网络计划图的计算工期大于上级要求的工期时。必须根据要求计划的进度，缩短工程项目的完工工期。主要从：采取技术措施，提高工效，缩短关键工作的持续时间，使关键线路的时间缩短。采取组织措施，充分利用非关键工作的总时差，合理调配人力、物力和资金等资源。增加对关键工作的投入，以便缩短关键工作的持续时间，实现工期缩短。4.2资源优化

在编制初始网络计划图后，需要进一步考虑尽量利用现有资源的问题。即在项目的工期不变的条件下，均衡地利用资源。实际工程项目包括工作繁多，需要投入资源种类很多，均衡地利用资源是很麻烦的事，要用计算机来完成。为了简化计算，具体操作可以：⑴优先安排关键工作所需要的资源。⑵利用非关键工作的总时差，错开各工作的开始时间，避开在同一时区内集中使用同一资源，以免出现高峰。⑶在确实受到资源制约，或在考虑综合经济效益的条件下，在许可时，也可以适当地推迟工程的工期。实现错开高峰的目的。

下面通过例1的例子说明平衡人力资源的方法。假设在例1中，现有机械加工工人数65人，要完成工作D,F,G,H,K。各工作需要工人人数列于表11-4

表

由于机械加工工人数的限制若上述工作若都按最早开始时间安排，在完成各关键工作的75天工期中，每天需要机械加工工人人数如图11-9所示。图11-9

有10天需要80人，另10天需要81人。超过了现有机械工人人数的约束必须进行调整。以……线表示的非关键路线上非关键工作F,H有机动时间，若将工作F延迟10天开工，就可以解决第70－80天的超负荷问题；将工作H推迟10天开工，可以解决第100－110天的超负荷问题。于是新的负荷图（见图11-10）能满足机械工人的人数65人约束条件。图11-10以上人力资源平衡是利用非关键工作的总时差，可以错开资源负荷的高峰。也可以采用将非关键工作分段作业或采用技术措施减少所需要资源。也可以根据计划规定适当延长项目的工期。

4.3时间－费用优化

编制网络计划时，要研究如何使完成项目的工期尽可能缩短，费用尽可能少；或在保证既定项目完成时间条件下，所需要的费用最少；或在费用限制的条件下，项目完工的时间最短。这就是时间－费用优化要解决的问题。完成一项目的费用可以分为两大类：1.

直接费用2.

间接费用。

1.

直接费用

直接与项目的规模有关的费用。包括材料费用，直接生产工人工资等。为了缩短工作的持续时间和工期，就需要增加投入，即增加直接费用。

2.

间接费用包括管理费等。一般按项目工期长度进行分摊。工期愈短，分摊的间接费用就愈少。一般项目的总费用与直接费用和间接费用与项目工期之间存在一定关系，可以用图11-11表示T1—

最短工期，项目总费用最高；T2—

最经济的工期；T3—

正常的工期当总费用最少工期短于要求工期时，这就是最佳工期。以下通过例1说明已知项目的每天间接费用为400元，利用表11-6中的已知资料，按图11-7安排进度，项目正常工期为170天。表11-6170天方案对应的项目直接费用为68900元，间接费用为170×400=68000元，项目总费用为136900元。这是在正常条件下进行的方案，称为170天方案。若要缩短这方案的工期，首先从缩短关键路线上直接费用率最小的工作的持续时间，在170天方案中关键工作K,G的直接费用率是最低。从表中可见这两项工作的持续时间都只能缩短10天。由此总工期可以缩短到170－10－10=150天。按150天工期计算，这时总直接费用增加到68900＋（290×10＋350×10）=75300元。由于缩短