运筹学期末总复习

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