第2章-线性规划01-可行区域与基本可行解.ppt

线性规划LinearProgramming,LudongUniversity,2020/6/15,LudongUniversity,2,线性规划,线性规划问题可行区域与基本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析,2020/6/15,LudongUniversity,3,线性规划问题,线性规划实例线性规划模型,生产计划问题运输问题,一般形式规范形式标准形式概念形式转换,2020/6/15,LudongUniversity,4,生产计划问题,某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划,表2.1.1,2020/6/15,LudongUniversity,5,问题分析,2020/6/15,LudongUniversity,6,模型,2020/6/15,LudongUniversity,7,运输问题,2020/6/15,LudongUniversity,8,问题分析,2020/6/15,LudongUniversity,9,模型,2020/6/15,LudongUniversity,10,一般形式,目标函数,约束条件,自由变量,非负变量,2020/6/15,LudongUniversity,11,注释,2020/6/15,LudongUniversity,12,规范形式与标准形式,标准形式,规范形式,2020/6/15,LudongUniversity,13,概念,2020/6/15,LudongUniversity,14,模型转换,约束转换实例,目标转换,变量转换,2020/6/15,LudongUniversity,15,约束转换1,不等式变等式不等式变不等式,等式变不等式,2020/6/15,LudongUniversity,16,约束转换2,等式变不等式不等式变等式,松弛变量,剩余变量,或,不等式变不等式,2020/6/15,LudongUniversity,17,将LP转化为标准形式,例2.1.3,2020/6/15,LudongUniversity,18,思考题和练习题,思考题：习题2（P.73）练习题：习题1，3，4（P.72）,2020/6/15,LudongUniversity,19,可行区域与基本可行解,图解法可行域的几何结构基本可行解与基本定理,2020/6/15,LudongUniversity,20,图解法,2020/6/15,LudongUniversity,21,解线性规划,例2.2.1,2020/6/15,LudongUniversity,22,结论,关于LP的解可能出现的情况：可行域是空集。可行域无界无最优解。最优解存在且唯一，则一定在顶点上达到。最优解存在且不唯一，一定存在顶点是最优解。,2020/6/15,LudongUniversity,23,可行域的几何结构,凸集可行域的凸性,基本假设,2020/6/15,LudongUniversity,24,凸集,2020/6/15,LudongUniversity,25,可行域的凸性,2020/6/15,LudongUniversity,26,问题,1.可行域顶点的个数是否有限？2.最优解是否一定在可行域顶点上达到？3.如何找到顶点？4.如何从一个顶点转移到另一个顶点?,2020/6/15,LudongUniversity,27,基本可行解与基本定理,基本可行解的定义基本定理问题,2020/6/15,LudongUniversity,28,基本可行解与基本定理,基本可行解的定义,基本定理问题,令,分块,左乘,2020/6/15,LudongUniversity,29,基本可行解的定义,如果，称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。,2020/6/15,LudongUniversity,30,基本可行解的定义,2020/6/15,LudongUniversity,31,基本定理,2020/6/15,LudongUniversity,32,问题,基本可行解不一定都是最优解，最优解也不一定都是基本可行解。如果有两个基本可行解是最优解，则两解的凸组合也都是最优解。如果最优解不唯一，则会有多个基本可行解是最优解，它们必然在同一个面上。如果可行解个数有限，则可以在基可行解中寻找最优解。,剩余的问题是如何判断一个基可行解是最优解？如果不是则如何从一个基可行解转到另一个基可行解？,2020/6/15,LudongUniversity,33,思考题和练习题,思考题：定理2.2.5和定理2.2.6一起被称为线性规划的基本定理，试证明定理2.2.5和定理2.2.6。练习题：习题5(4)，8，9（P.72）,课堂作业,长征医院在每天各时段内需护士人数如下表所示该医院安排4个护士上班班次：早班6:00-14:00，白班8:00-16:00，晚班14:00-22:00，夜班22:00-6:00（次日），每名护士值