运筹学课件__运筹学__胡运权_第四版_复习要点.pptVIP

一般线性规划问题的对偶问题;对偶问题对应表;例：设整数规划问题如下;用图解法求出最优解

x1＝3/2,x2=10/3

且有Z=29/6;有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？;求解过程如下：

第一步，变换系数矩阵：;第三步，作最少的直线覆盖所有0元素：;0;〔三〕用节点标号法计算工期并确定关键线路

1)???设网络方案起点节点的标号值为零，即b1＝0。

2)???顺箭线方向逐个计算节点的标号值。每个节点的标号值，等于以该节点为完成节点的各工作的开始节点标号值与相应工作持续时间之和的最大值，即：

bj＝max{bi+Di－j}

将标号值的来源节点及得出的标号值标注在节点上方。

3)节点标号完成后，终点节点的标号值即为计算工期。

4)?从网络方案终点节点开始，逆箭线方向按源节点寻求出关键线路。;【例3】某网络方案如下图，试用标号法求出工期并找出关键线路。;5;5;关键线路是由关键工序连成的线路，其特点：

⑴关键线路指从网络图起始节点到终止节点作业时间最长的线路，其长度就是网络方案的工期。

⑵关键线路上各工序总时差为零或为负值或为最小正值。

⑶一个网络方案中可以有多条关键工序，且至少有一条关键线路。;期望值法;这也是一种基于期望值的方法，但它所用的不是决策表，而是用图〔树〕：;把上例改为：假设前三年销路好，那么后七年销路好的概率为0.8；假设前三年销路不好，那么后七年销路好的概率为0.1。此时如何决策？