线性规划01可行区域与基本可行解

线性规划

LinearProgrammingLudongUniversity2024/1/17LudongUniversity2线性规划线性规划问题可行区域与根本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析2024/1/17LudongUniversity3线性规划问题线性规划实例线性规划模型

生产方案问题运输问题一般形式标准形式标准形式概念形式转换2024/1/17LudongUniversity4生产方案问题某工厂用三种原料生产三种产品，的条件如表2.1.1所示，试制订总利润最大的生产方案单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）3542024/1/17LudongUniversity5问题分析2024/1/17LudongUniversity6模型2024/1/17LudongUniversity7运输问题2024/1/17LudongUniversity8问题分析2024/1/17LudongUniversity9模型2024/1/17LudongUniversity10一般形式目标函数约束条件自由变量非负变量2024/1/17LudongUniversity11注释2024/1/17LudongUniversity12标准形式与标准形式标准形式标准形式2024/1/17LudongUniversity13概念2024/1/17LudongUniversity14模型转换约束转换实例目标转换变量转换2024/1/17LudongUniversity15约束转换1不等式变等式不等式变不等式等式变不等式2024/1/17LudongUniversity16约束转换2等式变不等式不等式变等式松弛变量剩余变量或不等式变不等式2024/1/17LudongUniversity17将LP转化为标准形式例2024/1/17LudongUniversity18思考题和练习题

思考题：习题2〔P.73〕练习题：习题1，3，4〔P.72〕2024/1/17LudongUniversity19可行区域与根本可行解图解法

可行域的几何结构

根本可行解与根本定理2024/1/17LudongUniversity20图解法2024/1/17LudongUniversity21解线性规划2024/1/17LudongUniversity22结论关于LP的解可能出现的情况：可行域是空集。可行域无界无最优解。最优解存在且唯一，那么一定在顶点上到达。最优解存在且不唯一，一定存在顶点是最优解。2024/1/17LudongUniversity23可行域的几何结构凸集可行域的凸性根本假设2024/1/17LudongUniversity24凸集2024/1/17LudongUniversity25可行域的凸性2024/1/17LudongUniversity26问题1.可行域顶点的个数是否有限？2.最优解是否一定在可行域顶点上到达？3.如何找到顶点？4.如何从一个顶点转移到另一个顶点?2024/1/17LudongUniversity27根本可行解与根本定理根本可行解的定义根本定理问题

2024/1/17LudongUniversity28根本可行解与根本定理根本可行解的定义根本定理问题令分块

左乘2024/1/17LudongUniversity29根本可行解的定义如果，称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的那么称该规划为非退化的。2024/1/17LudongUniversity30根本可行解的定义2024/1/17LudongUniversity31根本定理2024/1/17LudongUniversity32问题根本可行解不一定都是最优解，最优解也不一定都是根本可行解。如果有两个根本可行解是最优解，那么两解的凸组合也都是最优解。如果最优解不唯一，那么会有多个根本可行解是最优解，它们必然在同一个面上。如果可行解个数有限，那么可以在基可行解中寻找最优解。剩余的问题是如何判断一个基可行解是最优解？如果不是那么如何从一个基可行解转到另一个基可行解？2024/1/17LudongUniversity33思考题和练习题

思考题：定理和定理一起被称为线性规划的根本定理，试证明定理和定理。练习题：习题5(4)，8，9〔P.72〕课堂作业长征医院在每天各时段内需护士人数如下表所示该医院安排4个护士上班班次：早班6:00-14:00，白班8:00-16:00，晚班14:00-22:00，夜班22:00-6:00〔次日〕，每名护士值一个班次。〔1〕该医院每天至少需多少名护士才能满足值班需要。〔2〕有人提议为简化管理，共设早晚夜三个班，取消白班，这种情况下又需要多少名护士能