线性规划 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 对偶单纯形算法 基本思想 算法过程 算例 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 算例 2019/7/3 Ludong University

16 迭代1 RHS x4 x5 2019/7/3 Ludong University

17 迭代1 2019/7/3 Ludong University

18 迭代2 x4 x2 2019/7/3 Ludong University

19 迭代2 2019/7/3 Ludong University

20 x1 x2 2019/7/3 Ludong University

21 问题 关于单纯形算法和对偶单纯行算法 1.单纯形算法从一个基本可行解开始迭代，对偶单纯形算法从一个正则解开始迭代；
2.单纯形算法可以判断原问题无界，对偶单纯形算法可以判断原问题无可行解； 3.在迭代中，单纯形算法首先根据检验数确定一个进基变量，对偶单纯形算法首先根据右端向量确定一个出基变量. 对于对偶单纯形算法，如何列出含有 原始问题的一个基本解； 对偶问题的一个可行解， 的第一个初始单纯形表？ 2019/7/3 Ludong University

22 习题和作业题 习题：习题21（P.77） 作业题：习题22(2)(3)（P.78） 2019/7/3 Ludong University