运筹学期末总复习.pptx

运筹学期末总复习运筹学期末总复习第一、二章第一、二章1、线性规划数学模型的标准形式：、线性规划数学模型的标准形式：特点：特点：a、目标函数：、目标函数：maxb、约束条件：等式、约束条件：等式c、决策变量、决策变量00d d、b bi i00线性规划数学模型的三个要素：线性规划数学模型的三个要素：决策变量、目标函数、约束条件决策变量、目标函数、约束条件2 2、线性规划问题解的四种情况、线性规划问题解的四种情况:唯一最优解唯一最优解 无穷多最优解无穷多最优解 无界解无界解 无解无解(无可行解无可行解)列出初始单纯形表列出初始单纯形表寻找初始基可行解寻找初始基可行解计算计算，进行最优性检验，进行最优性检验所有所有00 是是否否存在非存在非基变量基变量检验数检验数=0=0 否否是是唯一最唯一最优解优解无穷多无穷多最优解最优解 是否有换出变量是否有换出变量 否否无无界界解解 寻找换入，换出变量寻找换入，换出变量 求新基可行解求新基可行解3 3、单纯形法计算步骤、单纯形法计算步骤存在人工存在人工变量变量0 0 否否是是无无解解 线性规划原问题与对偶问题的关系见：P52 表2-2对称形式：4 4、线性规划问题的对偶问题：、线性规划问题的对偶问题：变量对应方程、方程对应变量变量对应方程、方程对应变量对称对应对称、不对称对应不对称对称对应对称、不对称对应不对称无约束对应等式、等式对应无约束无约束对应等式、等式对应无约束max z=C Xs.t.AX bX 0min w=bYs.t.AY CY 0弱对偶性及其推论弱对偶性及其推论最优性最优性强对偶性强对偶性互补松弛性互补松弛性变量的对应关系（变量的对应关系（P55P55表表2 25 5，2 26 6的的比较）比较）5 5、对偶问题的性质：、对偶问题的性质：6 6、灵敏度分析、灵敏度分析（1 1）系数）系数c cj j变化变化（2 2）b bi i变化变化（3 3）增加一变量）增加一变量x xj j （4 4）增加一个约束条件）增加一个约束条件（5 5）a aijij发生变化发生变化练习题：练习题：1 1、写出下列线性规划问题的标准形式及对偶问题。、写出下列线性规划问题的标准形式及对偶问题。（1 1）（2 2）（1 1）确定获利最大的产品生产计划；）确定获利最大的产品生产计划；（2 2）求其对偶问题的最优解；）求其对偶问题的最优解；（3 3）产品）产品A A的利润变为的利润变为3 3时，上述最优计划变不变；时，上述最优计划变不变；如变化，请写出新的最优生产计划。如变化，请写出新的最优生产计划。（4 4）若设计一种新产品）若设计一种新产品D D，单件劳动力消耗为，单件劳动力消耗为8 8单位，单位，材料消耗为材料消耗为2 2单位，每件可获利单位，每件可获利3 3元，问该种产品是元，问该种产品是否值得生产？否值得生产？(此时假设此时假设A A的利润仍为的利润仍为1 1元）元）A AB BC C可用量可用量(单位单位)劳动力劳动力6 63 35 56565材材 料料3 34 45 54040产品利润（元产品利润（元/件）件）1 12 24 42 2、某厂生产、某厂生产A,B,CA,B,C三种产品，其所需劳动力、材料三种产品，其所需劳动力、材料等数据见下表。等数据见下表。3 3、求出下列线性规划问题的最优解，并进行灵敏、求出下列线性规划问题的最优解，并进行灵敏度分析度分析（1 1）约束条件）约束条件右端常数由右端常数由2020变为变为3030（2 2）目标函数中）目标函数中x x3 3系数由系数由1313变为变为8 8（3 3）x x1 1的系数列向量由的系数列向量由 变为变为（4 4）增加一个约束条件）增加一个约束条件2x2x1 1+3x+3x2 2+5x+5x3 35050第三章第三章 运输问题运输问题1 1、表上作业法求解运输问题步骤：、表上作业法求解运输问题步骤：（1 1）确定初始运输方案：最小元素法、沃格尔法）确定初始运输方案：最小元素法、沃格尔法判断是否为基可行解：基变量个数为判断是否为基可行解：基变量个数为m+n-1m+n-1个个（2 2）对初始运输方案进行检验，确定是否为最优运）对初始运输方案进行检验，确定是否为最优运输方案：对偶变量法输方案：对偶变量法（3 3）如果不是最优运输方案，进行调整得到新的运）如果不是最优运输方案，进行调整得到新的运输方案：闭回路法输方案：闭回路法（4 4）重复）重复2 2、3 3步直到找到最优运输方案步直到找到最优运输方案2 2、产销不平衡运输问题的处理、产销不平衡运输问题的处理产销不平衡问题产销不平衡问题 产销平衡问题产销平衡问题（1）总产量）总产量 总销量总销量假想一销地假想一销地Bn+1，令销量为，令销量为 ，运价，运价c=0（2）总产量）总产量 总销量总销量假想一产地假想一产地Am+1，令产量为，令产量为 ，一般运价，一般运价c=0练习题：练习题：1 1、用表上作业法求解运输问题、用表上作业法求解运输问题B1B2B3产量A151812A224014A33674销量910111、用图解法求解下述目标规划问题、用图解法求解下述目标规划问题 第四章第四章 目标规划目标规划xj部分或全部取整数部分或全部取整数第五章第五章 整数规划整数规划整数规划问题的松弛问题整数规划问题的松弛问题整数规划的可行域：整数规划的可行域：R 最优目标函数值最优目标函数值Z*松弛问题的可行域：松弛问题的可行域：R 最优目标函数值最优目标函数值Z*则则 ,Z*优于优于Z*例：例：P150 5.11（1）p150 5.12练习题：练习题：1、指派问题的求解指派问题的求解第七章第七章 动态规划动态规划用动态规划的方法求解最短路问题。用动态规划的方法求解最短路问题。第八章第八章 图与网络分析图与网络分析图的基本概念图的基本概念树的性质树的性质最小生成树最小生成树最大流问题最大流问题