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

《复习2运筹学课件胡运权第四版复习要点.ppt》由会员分享，可在线阅读，更多相关《复习2运筹学课件胡运权第四版复习要点.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、”第第j个约束类型为个约束类型为“”例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。称为松弛问题）。且为整数 用图解法求出最优解用图解法求出最优解x x1 13/2,3/2,x x2 2=10/3=10/3且有且有Z=29/6Z=29/6x1x233(3/2,10/3)现现求求整整数数解解（最最优优解解）：如如用用“舍舍入入取取整整法法”可可得得到到4个个点点即即(1，3),(2，3),(1，4),(2，4)。显显然然，它它们们都都不不可可能能是是整整数数规规划划的的最优解。最优解。按按整整数数规

3、规划划约约束束条条件件，其其可可行行解解肯肯定定在在线线性性规规划划问问题题的的可可行行域域内内且且为为整整数数点点。故故整整数数规规划划问问题题的的可可行行解解集集是是一一个个有有限限集集，如图所示。如图所示。有有一一份份中中文文说说明明书书，需需译译成成英英、日日、德德、俄俄四四种种文文字字，分分别别记记作作A A、B B、C C、D D。现现有有甲甲、乙乙、丙丙、丁丁四四人人，他他们们将将中中文文说说明明书书译译成成不不同同语语种种的的说说明明书书所所需需时时间间如如下下表表所所示，问如何分派任务，可使总时间最少？示，问如何分派任务，可使总时间最少？任务任务人员人员ABCD甲甲67112

4、乙乙4598丙丙31104丁丁5982指派问题求解过程如下：求解过程如下：第一步，变换系数矩阵：第一步，变换系数矩阵：5第二步，试指派：第二步，试指派：找到找到 3 个独立零元素个独立零元素 但但 m=3 n=4指派问题 第三步，作最少的直线覆盖所有第三步，作最少的直线覆盖所有0元素：元素：独立零元素的个数独立零元素的个数m等于最少直线数等于最少直线数l，即，即lm=3n=4；第四步，变换矩阵第四步，变换矩阵(bij)以增加以增加0元素：没有被直线覆盖的所有元素：没有被直线覆盖的所有元素中的最小元素为元素中的最小元素为1，然后打，然后打各行都减去各行都减去1；打；打各列都加上各列都加上1，得如

5、下矩阵，并转第二步进行试指派：，得如下矩阵，并转第二步进行试指派：指派问题000 0 00得得到到4个个独独立立零零元元素素，所所以以最最优优解解矩阵为：矩阵为：15 指派问题l（三）用节点标号法计算工期并确定关键线路（三）用节点标号法计算工期并确定关键线路l1)1)设网络计划起点节点的标号值为零，即设网络计划起点节点的标号值为零，即b1b10 0。l2)2)顺顺箭箭线线方方向向逐逐个个计计算算节节点点的的标标号号值值。每每个个节节点点的的标标号号值值，等等于于以以该该节节点点为为完完成成节节点点的的各各工工作作的的开开始始节节点点标标号号值值与相应工作持续时间之和的最大值，即：与相应工作持续

6、时间之和的最大值，即：lbjmaxbi+Dijl 将标号值的来源节点及得出的标号值标注在节点上方。将标号值的来源节点及得出的标号值标注在节点上方。l3)3)节点标号完成后，终点节点的标号值即为计算工期。节点标号完成后，终点节点的标号值即为计算工期。l4)4)从从网网络络计计划划终终点点节节点点开开始始，逆逆箭箭线线方方向向按按源源节节点点寻寻求求出出关键线路。关键线路。l【例3】某某已已知知网网络络计计划划如如图图所所示示，试试用用标标号号法法求求出工期并找出关键线路。出工期并找出关键线路。5E I126ABD4M335485H44C27F733JG7图某工程网络图5E（，17）I126ABD

7、4M335485H44C27F733JG5 图对节点进行标号（，14）（，5）b1=0（，5）（，10）（，10）（，2）（源节点号，标号值）图例：5E（，17）I126ABD4M335485H44C27F733JG5 图1223 据源节点逆线找出关键线路（，14）（，5）b1=0（，5）（，10）（，10）（，2）l 关键线路是由关键工序连成的线路关键线路是由关键工序连成的线路，其特点：，其特点：l 关关键键线线路路指指从从网网络络图图起起始始节节点点到到终终止止节节点点作业时间最长的线路，其长度就是网络计划的工期。作业时间最长的线路，其长度就是网络计划的工期。l 关关键键线线路路上上各各工

8、工序序总总时时差差为为零零或或为为负负值值或或为最小正值。为最小正值。l 一一个个网网络络计计划划中中可可以以有有多多条条关关键键工工序序，且且至少有一条关键线路。至少有一条关键线路。期望值法期望值法期望值最大方案为最优方案。例期望值最大方案为最优方案。例:生产10年，减去投资：最优方案 a*=a1方案方案投资投资 销路好销路好1（0.7）销路差销路差2（0.3）a130010020a21504020 这也是一种基于期望值的方法，但它所用的这也是一种基于期望值的方法，但它所用的不是决策表，而是用图（树）：不是决策表，而是用图（树）：决策树法决策树法决策点决策点方案节点方案节点21大厂3小厂0.70.3100-200.70.3402010年190340把上例改为：若前三年销路好，则后七年销路好的概率为把上例改为：若前三年销路好，则后七年销路好的概率为0.8；若前；若前三年销路不好，则后七年销路好的概率为三年销路不好，则后七年销路好的概率为0.1。此时如何决策？。此时如何决策？0.70.3