复习2运筹学课件胡运权第四版复习要点.ppt

指派问题 指派问题 指派问题 指派问题 （三）用节点标号法计算工期并确定关键线路 1)??? 设网络计划起点节点的标号值为零，即b1＝0。 2)??? 顺箭线方向逐个计算节点的标号值。每个节点的标号值，等于以该节点为完成节点的各工作的开始节点标号值与相应工作持续时间之和的最大值，即： bj＝max{bi+Di－j} 将标号值的来源节点及得出的标号值标注在节点上方。 3)节点标号完成后，终点节点的标号值即为计算工期。 4)? 从网络计划终点节点开始，逆箭线方向按源节点寻求出关键线路。 【例3】某已知网络计划如图所示，试用标号法求出工期并找出关键线路。 关键线路是由关键工序连成的线路，其特点： ⑴关键线路指从网络图起始节点到终止节点作业时间最长的线路，其长度就是网络计划的工期。 ⑵关键线路上各工序总时差为零或为负值或为最小正值。 ⑶一个网络计划中可以有多条关键工序，且至少有一条关键线路。 决策树法 这也是一种基于期望值的方法，但它所用的不是决策表，而是用图（树）： 把上例改为：若前三年销路好，则后七年销路好的概率为0.8；若前三年销路不好，则后七年销路好的概率为0.1。此时如何决策？ * * 一般线性规划问题的对偶问题 对偶问题对应表 约束条件：n个 第j个约束类型为“≥” 第j个约束类型为“≤” 第j个约束类型为“＝” 变量数：n个 第j个变量≤ 0 第j个变量≥ 0 第j个变量是自由变量 变量数： m个 第i个变量≥0 第i个变量≤0 第i个变量是自由变量 约束条件： m个 第i个约束类型为“≥” 第i个约束类型为“≤” 第i个约束类型为“＝” 目标函数max 目标函数min 对偶问题（原问题） 原问题（对偶问题） 例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。 且为整数 用图解法求出最优解 x1＝3/2, x2 = 10/3 且有Z = 29/6 x1 x2 ⑴ ⑵ 3 3 (3/2,10/3) 现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3), (2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务 人员 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 求解过程如下： 第一步，变换系数矩阵： －5 第二步，试指派： ◎ ◎ ◎ ? ? 找到 3 个独立零元素 但 m = 3 n = 4 第三步，作最少的直线覆盖所有0元素： ◎ ◎ ◎ ? ? √ √ √ 独立零元素的个数m等于最少直线数l，即l＝m=3n=4； 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派： 0 0 0 0 0 0 得到4个独立零元素， 所以最优解矩阵为： ◎ ◎ ◎ ? ? √ √ √ ◎ ◎ ◎ ? ? 15 ◎ ◎ ◎ ? ? ◎ 5 E I 1 2 6 A B D 4 M 3 3 5 4 8 5 H 4 4 C 2 7 F 7 3 3 J G 7 图某工程网络图 5 E （⑥，17） I 1 2 6 A B D 4 M 3 3 5 4 8 5 H 4 4 C 2 7 F 7 3 3 J G 5 图对节点进行标号 （⑤，14） （①，5） b1=0 （②③，5） （④，10） （⑤，10） （①，2） （源节点号，标号值） 图例： 5 E （⑥，17） I 1 2 6 A B D 4 M 3 3 5 4 8 5 H 4 4 C 2 7 F 7 3 3 J G 5 图12－23 据源节点逆线找出关键线路 （⑤，14） （①，5） b1=0 （②③，5） （④，10） （⑤，10） （①，2） 期望值法 期望值最大方案为最优方案。例: 生产10年，减去投资： 最优方案 a*= a1 40 100 销路好θ1（0.7） 150 300 投资 －20 a1 20 a2 销路差θ2 （0.3） 方案 决策点 方案节点 2 1 大厂 3 小厂 0.7 0.3 100 -20 0.7 0.3 40 20 10年 190 340 0.7