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

一般线性规划问题的对偶问题对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数min目标函数max约束条件：m个第i个约束类型为“≥”第i个约束类型为“≤”第i个约束类型为“＝”变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

变量数：n个第j个变量≤0第j个变量≥0第j个变量是自由变量

约束条件：n个第j个约束类型为“≥”第j个约束类型为“≤”第j个约束类型为“＝”例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题〔一般称为松弛问题〕。且为整数用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解〔最优解〕：如用“舍入取整法〞可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如下图。有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982指派问题求解过程如下：第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=3<n=4指派问题第三步，作最少的直线覆盖所有0元素：◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：指派问题000000得到4个独立零元素，所以最优解矩阵为：◎◎◎ØØ√√√◎◎◎ØØ15◎◎◎ØØ◎指派问题〔三〕用节点标号法计算工期并确定关键线路1)

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

顺箭线方向逐个计算节点的标号值。每个节点的标号值，等于以该节点为完成节点的各工作的开始节点标号值与相应工作持续时间之和的最大值，即：bj＝max{bi+Di－j}将标号值的来源节点及得出的标号值标注在节点上方。3)节点标号完成后，终点节点的标号值即为计算工期。4)

从网络方案终点节点开始，逆箭线方向按源节点寻求出关键线路。【例3】某网络方案如下图，试用标号法求出工期并找出关键线路。5EI126ABD4M335485H44C27F733JG7图某工程网络图5E（⑥，17）I126ABD4M335485H44C27F733JG5图对节点进行标号（⑤，14）（①，5）b1=0（②③，5）（④，10）（⑤，10）（①，2）（源节点号，标号值）图例：5E（⑥，17）I126ABD4M335485H44C27F733JG5图12－23据源节点逆线找出关键线路（⑤，14）（①，5）b1=0（②③，5）（④，10）（⑤，10）（①，2）关键线路是由关键工序连成的线路，其特点：⑴关键线路指从网络图起始节点到终止节点作业时间最长的线路，其长度就是网络方案的工期。⑵关键线路上各工序总时差为零或为负值或为最小正值。⑶一个网络方案中可以有多条关键工序，且至少有一条关键线路。期望值法期望值最大方案为最优方案。例:生产10年，减去投资：最优方案a*=a1方案投资销路好θ1（0.7）销路差θ2（0.3）a1300100－20a21504020这也是一种基于期望值的方法，但它所用的不是决策表，而是用图〔树〕：决策树法决策点方案节点21大厂3小厂0.70.3100