《运筹学运筹学胡运权第四版复习要点ppt课件》由会员分享，可在线阅读，更多相关《运筹学运筹学胡运权第四版复习要点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个约束类型为个约束类型为“” ;例：例：设整数整数规划划问题如下如下 首先不思索整数首先不思索整数约束，得到束，得到线性性规划划问题普通普通称称为松弛松弛问题。且为整数 ;用图解法求出最优解用图解法求出最优解x1x13/2, x2 = 10/33/2, x2 = 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乙乙4598丙丙31104丁丁5982指派问题;求解过程如下：求解过程如下：第一步，变换系数
4、矩阵：第一步，变换系数矩阵：5第二步，第二步，试指派：指派： 找到找到 3 个独立零元素个独立零元素 但但 m = 3 n = 4指派问题; 第三步，作最少的直线覆盖一切第三步，作最少的直线覆盖一切0元素：元素： 独立零元素的个数独立零元素的个数m等于最少直等于最少直线数数l，即，即lm=3n=4； 第四步，第四步，变换矩矩阵(bij)以添加以添加0元素：没有被直元素：没有被直线覆盖的一切覆盖的一切元素中的最小元素元素中的最小元素为1，然后打，然后打各行都减去各行都减去1；打；打各列都加上各列都加上1，得如下矩，得如下矩阵，并，并转第二步第二步进展展试指派：指派： 指派问题;000 0 00得
5、得到到4个个独独立立零零元元素素， 所所以以最最优解解矩矩阵为： 15 指派问题;l三用三用节点点标号法号法计算工期并确定关算工期并确定关键线路路l1) 1) 设网网络方方案案起起点点节点点的的标号号值为零零，即即b1b10 0。l2) 2) 顺箭箭线方方向向逐逐个个计算算节点点的的标号号值。每每个个节点点的的标号号值，等等于于以以该节点点为完完成成节点点的的各各任任务的的开开场节点点标号号值与与相相应任任务继续时间之和的最大之和的最大值，即：，即：lbjbjmaxbi+Dimaxbi+Dijjl 将将标号号值的的来来源源节点点及及得得出出的的标号号值标注注在在节点上方。点上方。l3)3)节点
6、点标号号完完成成后后，终点点节点点的的标号号值即即为计算工期。算工期。l4) 4) 从从网网络方方案案终点点节点点开开场，逆逆箭箭线方方向向按源按源节点点寻求出关求出关键线路。路。;l 【例3】某知网络方案如下图，试用标号法求出工期并找出关键线路。5E I126ABD4M335485H44C27F733JG7图某工程网络图;5E，17 I126ABD4M335485H44C27F733JG5 图对节点进展标号，14，5 b1=0，5，10，10，2源节点号，标号值图例：;5E，17 I126ABD4M335485H44C27F733JG5 图1223 据源节点逆线找出关键线路，14，5 b1=
7、0，5，10，10，2;l 关关键线路是由关路是由关键工序工序连成的成的线路，其特点：路，其特点：l 关关键线路路指指从从网网络图起起始始节点点到到终止止节点点作作业时间最最长的的线路，其路，其长度就是网度就是网络方案的工期。方案的工期。l 关关键线路路上上各各工工序序总时差差为零零或或为负值或或为最小正最小正值。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;
