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

《运筹学课件__运筹学__胡运权_第四版_复习要点.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一般线性规划问题的对偶问题对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数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)现求整数解（最

2、优解）：如用“舍入取整法”可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务人员ABCD甲67112乙4598丙31104丁5982指派问题求解过程如下：第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=

3、3

4、应工作持续时间之和的最大值，即：bj＝max{bi+Di－j}将标号值的来源节点及得出的标号值标注在节点上方。3)节点标号完成后，终点节点的标号值即为计算工期。4)从网络计划终点节点开始，逆箭线方向按源节点寻求出关键线路。【例3】某已知网络计划如图所示，试用标号法求出工期并找出关键线路。5EI126ABD4M335485H44C27F733JG7图某工程网络图5E（⑥，17）I126ABD4M335485H44C27F733JG5图对节点进行标号（⑤，14）（①，5）b1=0（②③，5）（④，10）（⑤，10）（①，2）（源节点号，标号值）图例：5E（⑥，17）I126ABD4

5、M335485H44C27F733JG5图12－23据源节点逆线找出关键线路（⑤，14）（①，5）b1=0（②③，5）（④，10）（⑤，10）（①，2）关键线路是由关键工序连成的线路，其特点：⑴关键线路指从网络图起始节点到终止节点作业时间最长的线路，其长度就是网络计划的工期。⑵关键线路上各工序总时差为零或为负值或为最小正值。⑶一个网络计划中可以有多条关键工序，且至少有一条关键线路。期望值法期望值最大方案为最优方案。例:生产10年，减去投资：最优方案a*=a1方案投资销路好θ1（0.7）销路差θ2（0.3）a1300100－20a21504020这也是一种基于期望值的方法，但它所

6、用的不是决策表，而是用图（树）：决策树法决策点方案节点21大厂3小厂0.70.3100-200.70.3402010年190340把上例改为：若前三年销路好，则后七年销路好的概率为0.8；若前三年销路不好，则后七年销路好的概率为0.1。此时如何决策？0.70.3