线性规划 Linear Programming

Presentation on theme: "线性规划 Linear Programming"— Presentation transcript:

1 线性规划 Linear Programming
Ludong University

2 线性规划 线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解 对偶理论 灵敏度分析 计算软件 案例分析 2019/7/3
Ludong University

3 线性规划问题 线性规划实例 线性规划模型 生产计划问题 运输问题 一般形式 规范形式 标准形式 概念 形式转换 2019/7/3
Ludong University

4 生产计划问题 某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划 2 3 1500 4 800 5
单位产品所需原料数量（公斤） 产品Q1 产品 Q2 Q3 原料可用量 （公斤/日） 原料P1 2 3 1500 原料P2 4 800 原料P3 5 2000 单位产品的利润（千元） 表2.1.1 2019/7/3 Ludong University

5 问题分析 2019/7/3 Ludong University

6 模型 2019/7/3 Ludong University

7 运输问题 2019/7/3 Ludong University

8 问题分析 2019/7/3 Ludong University

9 模型 2019/7/3 Ludong University

10 一般形式 目标函数 非负变量 自由变量 约束条件 2019/7/3 Ludong University

11 注释 2019/7/3 Ludong University

12 规范形式与标准形式 规范形式 标准形式 2019/7/3 Ludong University

13 概念 2019/7/3 Ludong University

14 模型转换 变量转换 目标转换 约束转换 实例 2019/7/3 Ludong University

15 约束转换1 等式变不等式 不等式变等式 不等式变不等式 2019/7/3 Ludong University

16 约束转换2 等式变不等式 不等式变等式 松弛变量 或 剩余变量 不等式变不等式 2019/7/3 Ludong University

17 将LP转化为标准形式 例2.1.3 2019/7/3 Ludong University

18 思考题和练习题 思考题：习题2（P.73） 练习题：习题1，3，4（P.72） 2019/7/3 Ludong University

19 可行区域与基本可行解 图解法 可行域的几何结构  基本可行解与基本定理 2019/7/3 Ludong University

20 图解法 2019/7/3 Ludong University

21 解线性规划 例2.2.1 2019/7/3 Ludong University

22 结论 关于LP的解可能出现的情况： 可行域是空集。 可行域无界无最优解。 最优解存在且唯一，则一定在顶点上达到。
最优解存在且不唯一，一定存在顶点是最优解。 2019/7/3 Ludong University

23 可行域的几何结构 基本假设 凸集 可行域的凸性 2019/7/3 Ludong University

24 凸集 2019/7/3 Ludong University

25 可行域的凸性 2019/7/3 Ludong University

26 问题 1.可行域顶点的个数是否有限？ 2.最优解是否一定在可行域顶点上达到？ 3.如何找到顶点？ 4.如何从一个顶点转移到另一个顶点?
2019/7/3 Ludong University

27 基本可行解与基本定理 基本可行解的定义 基本定理 问题 2019/7/3 Ludong University

28 基本可行解与基本定理 基本可行解的定义 令 分块 左乘 基本定理 问题 2019/7/3 Ludong University

29 基本可行解的定义 如果 ，称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。 2019/7/3
如果 ，称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。 2019/7/3 Ludong University

30 基本可行解的定义 2019/7/3 Ludong University

31 基本定理 2019/7/3 Ludong University

32 问题 基本可行解不一定都是最优解，最优解也不一定都是基本可行解。 如果有两个基本可行解是最优解，则两解的凸组合也都是最优解。
如果最优解不唯一，则会有多个基本可行解是最优解，它们必然在同一个面上。 如果可行解个数有限，则可以在基可行解中寻找最优解。 剩余的问题是如何判断一个基可行解是最优解？如果不是则如何从一个基可行解转到另一个基可行解？ 2019/7/3 Ludong University

33 思考题和练习题 思考题：定理2.2.5和定理2.2.6一起被称为线性规划的基本定理，试证明定理2.2.5和定理2.2.6。
练习题：习题5(4)，8，9（P.72） 2019/7/3 Ludong University

34 课堂作业 长征医院在每天各时段内需护士人数如下表所示 该医院安排4个护士上班班次：早班6:00-14:00，白班8:00-16:00，晚班14:00-22:00，夜班22:00-6:00（次日），每名护士值一个班次。 （1）该医院每天至少需多少名护士才能满足值班需要。 （2）有人提议为简化管理，共设早晚夜三个班，取消白班，这种情况下又需要多少名护士能满足值班需要。 时段 6:00-8:00 8:00-14:00 14:00-16:00 16:00-22:00 22:00-6:00（次日） 需护士数 25 35 32 28 22 2019/7/3 Ludong University