画网络计划图的技巧运筹学
网络计划图是一种用于表示和管理项目进度的工具，它可以帮助项目经理有效地安排任务、确定关键路径和进行资源分配。以下是一些绘制网络计划图的技巧，运筹学是其中一种方法：
1. 制定项目目标和工作分解结构：在绘制网络计划图之前，首先需要确定项目的整体目标，并将其细分为可管理的工作包或任务。这可以通过编制工作分解结构（Work Breakdown Structure，简称WBS）来完成。
2. 识别任务间的依赖关系：在绘制网络计划图时，需要确定每个任务之间的依赖关系。任务可以是紧前（必须在另一个任务之前完成）、紧后（必须在另一个任务完成之后开始）或并行（可以同时进行）关系。这可以通过绘制箭头来表示任务之间的关系。
3. 评估任务时间：每个任务都需要估计完成所需的时间。这通常可以通过历史数据、专家判断或其他项目类似任务的经验来确定。确保合理地估计任务时间可以帮助避免项目延迟。
4. 使用关键路径方法：关键路径是指在网络计划图中，其上的每个任务都没有缓冲时间，即任何一个任务的延迟都会导致整个项目的延迟。找到关键路径是网络计划图中的关键步骤之一。运筹学方法可以帮助找到最长路径和关键路径。
5. 确定并管理资源：网络计划图还可以用于资源分配和管理。通过标识每个任务所需的资源，项目经理可以更好地规划并分配资源，以确保项目按计划执行。
6. 监测和更新：一旦绘制了网络计划图，项目经理需要不断监测项目的进展，并根据实际情况及时更新计划。这可以通过比较实际进展与计划进展来完成，并根据需要调整任务时间或重新安排任务。
总之，网络计划图是一个强大的工具，可以帮助项目经理有效地管理项目进度和资源。了解运筹学技巧和其他相关技巧可以帮助项目经理更好地使用网络计划图来完成项目。
第 1 页 共 29 页 《运筹学》复习参考资料
资料加工、整理人——杨峰（函授总站高级讲师）
要求掌握的各部分知识点
第一部分 线性规划问题的求解（相当于教材的第一章）
——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法
第二部分 动态规划问题的求解（相当于教材的第三章）
——重要算法：图上标号法
第三部分 网络分析问题的求解（相当于教材的第四章）
——重要算法：破圈法、TP标号法、寻求网络最大流的标号法
第四部分 存储论简介（相当于教材的第七章）
※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。
非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。
定义：达到目标的可行解为最优解。
㈡图解法：
图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；
2、确定可行解域；
3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；
注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。
4、确定最优解及目标函数值。
㈢参考例题：（只要求下面这些有唯一最优解的类型）
例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：
10.1已知下表所列资料
工序 紧前工序 工序时间（天数） 工序 紧前工序 工序时间（天数）a － 3 f c 8
b a 4 g c 4
c a 5 h d,e 2
d b,c 7 i g 3
e b,c 7 j j,h,i 2
要求：（1）绘制网络图；（2）计算各结点的最早时间与最迟时
间；（3）计算各工序的最早开工、最早完工、最迟开工及最迟完工时
间；（4）计算各工序的总时差（总机动时间）；（5）确定关键路线。
10.2 已知建设一个汽车库及引道的作业明细表如下表所示。要求：
（1）计算该项工程从施工开始到全部结束的最短周期；
（2）若工序l拖期10天，对整个工程进度有何影响；
（3）若工序j的时间由12天缩短到8天，对整个工程进度有何影
响；
（4）为保证整个工程进度在最短周期内完成，工序i最迟必须在哪
天开工；
（5）若要求整个工程在75天完工，要不要采取措施？若要的话，
应从哪些方面采取措施？
工序代号 工序名称 工序时间（天） 紧前工序
a 清理场地开工 10 －
b 备 料 8 －
c 车库地面施工 6 a,b
d 预制墙及房顶 16 b
e 车库地面保养 24 c
f 立墙架 4 d,e
g 立房顶架 4 f
h 装窗及边墙 10 f
i 装 门 4 f
j 装天花板 12 g
k 油 漆 16 h,i,j
l 引道施工 8 c
m 引道保养 24 l
n 交工验收 4 k,m
10.3 已知下表所列资料：
工序代正常时最短时紧前工正常完成的
直接费用费用斜率
（百元/号间间序（百元）天）
A43—205
B86—304
C64B153
D32A52
E53A184
F75A407
G43B、D103
H32E、F、G156
合 计153
工程的间接费用5（百元/天）
求出该项工程总费用最低的最优工期（最低成本日程）。
10.4 已知某工程的网络图如下图所示，设该项工程开工时间为零，
合同规定该项工程的完工时间为25天。
2 6
c
6-9-12
a 7-8-9 3-4-8 j
1. 简答题
（1） 运筹学的工作步骤
提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；
建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；
求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。复杂模型的求解需用计算机，解得精度要求可有决策者提出；
解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；
解的控制：通过控制解的变化过程决定对解是否做一定的改变；
解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
（2） 退化产生原因及解决办法
单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
勃兰特规则：
1.选取cj-zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜cj-zj＞0)
2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。
（3）对偶问题的经济解释
• 这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。
• 对偶变量 yi在经济上表示原问题第i种资源的边际价值。
• 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。 njmiiijjybxcZ11iiybZ若原问题的价值系数Cj表示单位产值，则yi 称为影子价格；
若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。
影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。
（4）分枝定界法步骤
a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解，
b) 若求得的最优解符合整数要求，则是原IP的最优解；
c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
