emp_lp_fundenmental_2016_spring

1、第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础线性规划：基本理论与方法线性规划：基本理论与方法刘红英刘红英北航数学与系统科学学院北航数学与系统科学学院第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础目标函数是线性的，约束条件是线性等式或不等式目标函数是线性的，约束条件是线性等式或不等式线性规划线性规划第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础 问题问题：确定食品数量，满足营养需求，花费最小？

2、：确定食品数量，满足营养需求，花费最小？ 变量：变量：n 种食品，种食品，m 种营养成份；第种营养成份；第 j 种食品的单价种食品的单价每单位第每单位第 j 种食品所含第种食品所含第 i 种营养的数量种营养的数量第第 j 种食品的数量种食品的数量为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型：模型：2.1.1 问题举例问题举例例例1. 1. 配餐问题配餐问题第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础例例4. 其它应用其它应用 博弈论博弈论(game theory)等等( (习题习题2.2

3、6, 2.27) ) 网络流问题网络流问题(network flow, 3.1-3.2节节) 整数线性规划整数线性规划( (3.3-3.4节节) ) 数据包络分析数据包络分析(data envelope analysis, DEA, Charnes & Copper，1986)例例2. 目标函数中含绝对值的问题目标函数中含绝对值的问题例例3. 逐段线性凸函数逐段线性凸函数第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础线性规划线性规划解的解的几何特征几何特征惟一惟一 解解(顶点顶点)！第第 2 章章 线性规划线性规划:

4、基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础无无(下下)界界没有没有 有限有限 解解(-1, -1)一条边一条边( 1, 0)一条边一条边( 0, 1)惟一的顶点惟一的顶点( 1, 1)解的几何特征解的几何特征( 0, 0)(x1, 0), x1 0(0, x2), x20,1Tc*()Tx第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础 无界无界：没有有限最优解：没有有限最优解(极小化时表示无下界，极大化时无上界) 不可行不可行：没有可行解：没有可行解无解无解 有解有解：惟一解或多个解惟一解或

5、多个解( (整条边、面、甚至整个可行集整条边、面、甚至整个可行集) ) 有顶点解有顶点解线性规划解的线性规划解的几何特征几何特征可行集：可行集：多边形多边形( (二维二维) )多面集多面集( (高维空间高维空间) )给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述，从理论上证，从理论上证实上述几何特征，并实上述几何特征，并寻求有效算法寻求有效算法第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础线性规划的一般形式线性规划的一般形式其中其中 c 是是 n 维向量，维向量， 是是 m 维行向量，维行向量， 是实数，

6、这些是实数，这些均是给定的数据；均是给定的数据； 是变量是变量 .第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.1.2 标准形标准形(便于分析分析和设计算法便于分析分析和设计算法)*标准形的标准形的特征特征：极小化极小化、等式约束等式约束、变量非负变量非负其中其中 给定，变量是给定，变量是向量表示：向量表示：其中其中 给定，变量给定，变量是是第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础例例4. 4. 化成标准形化成标准形等价表示为等价表示为第第 2 章章

7、 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础一般形式一般形式 标准形标准形转化转化称称 松弛松弛(slack)/盈余盈余(surplus)变量变量第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础定义定义 设设 B 是是 A 的的m个线性无关列组成的矩阵，个线性无关列组成的矩阵， 置其余置其余列所对应的变量为零，称所得方程组的解是列所对应的变量为零，称所得方程组的解是 Ax = b 的的基基本解本解(basic solution) ;非负基本解是非负基本解是标准形问题标准形问

8、题的的基本可基本可行解行解( (basic feasible solution)；称称 B 是是基基(basis)；称与称与 B 对应的变量为对应的变量为基变量基变量(basic variables)2.1.3 基本可行解基本可行解(*)其中其中满秩假定：满秩假定：m n，且，且 A 的行向量线性无关的行向量线性无关例第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础基本可行解的个数基本可行解的个数不超过不超过 退化退化基本可行解：某个或某些基变量取零的基本可行解！基本可行解：某个或某些基变量取零的基本可行解！问题：问题：基本可行

9、解与基的对应关系？基本可行解与基的对应关系？(见习题见习题2.5)事实：事实： x 是基本可行解是基本可行解当且仅当当且仅当它的正分量对应的列线它的正分量对应的列线性无关性无关.例例. . 基本可行解及几何意义基本可行解及几何意义第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础基本可行解的存在性与基本定理基本可行解的存在性与基本定理(*)定理定理(线性规划基本定理线性规划基本定理) 考虑线性规划标准形，其考虑线性规划标准形，其中中 A 是秩为是秩为 m 的的mn 矩阵矩阵. 若问题有解，则若问题有解，则必有必有某某个基本可行解是

10、最优解个基本可行解是最优解.定理定理 (BFS的存在性的存在性) 考虑考虑LP 标准形，其中标准形，其中A 是秩为是秩为 m 的的mn 矩阵矩阵. 若问题有可行解，则若问题有可行解，则必存在必存在基本可行解基本可行解.第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础“You dont understand anything until you learn it more than one way.” Marvin Minsky (人工智能领域的专家人工智能领域的专家)2.1.5 几何直观几何直观线性规划的基本定理线性规划的基本定

11、理( (标准形标准形) )基本可行解基本可行解线性方程组线性方程组的基本性质的基本性质代数理论代数理论(与与表述形式有关表述形式有关)设计算法设计算法极点极点凸 集 理 论凸 集 理 论几何理论几何理论( (与表述形式与表述形式无关无关) )直观理解直观理解第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础凸集的定义及性质凸集的定义及性质几何解释：连接集合中任两点的线段仍含在该集合中几何解释：连接集合中任两点的线段仍含在该集合中性质性质称集合称集合 C 是锥是锥(cone)，如果，如果 蕴含着对所有蕴含着对所有 有有 . 若锥若锥

12、 C 还是凸的，称为凸锥还是凸的，称为凸锥(convex cone).称称 中的集合中的集合 C 是凸的是凸的(convex)，如果任给，如果任给 个个 x, y 及每个及每个 ，点，点 . 第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础一些重要的凸集一些重要的凸集有限个闭半空间的交集有限个闭半空间的交集多面集多面集(polyhedral set):推推广广平面上：多边形平面上：多边形注：任一线性规划的可行集是注：任一线性规划的可行集是多面集多面集！超平面超平面(hyperplane):(hyperplane):正正/ /负闭

13、半空间：负闭半空间：给定第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础极点极点几何上：极点即不能位于连接该集合中其它两点的开线段几何上：极点即不能位于连接该集合中其它两点的开线段上的点上的点定义定义 称凸集称凸集 C 中的点中的点 x 是是 C 的极点，如果存在的极点，如果存在 C 中的点中的点 y, z 和某和某 ，有，有则必有则必有 y = z.(1)xyz ( 0 , 1 ) 第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础定理定理( (极点与基本可行解的

14、等价性极点与基本可行解的等价性) )推论：推论：(i) 若若 C 非空，则至少有一个极点非空，则至少有一个极点.(ii) 若线性规划有解，则必有一个极点是最优解若线性规划有解，则必有一个极点是最优解.(iii) C 的极点集是有限集的极点集是有限集. 考虑线性规划标准形，其中考虑线性规划标准形，其中 A 是秩为是秩为 m 的的 mn矩阵，令矩阵，令 , 则则 x 是是 C 的极点当且仅当的极点当且仅当 x 是系统是系统 ， 的基本可行解的基本可行解(非负基本解非负基本解).(iv) C 中的点中的点 x 是极点是极点当且仅当当且仅当它的正分量对应的列线性无它的正分量对应的列线性无关关.:,R

15、0nCxA xbx第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础C有有2个极点个极点有有3个基本解，个基本解，2个个可行可行C 有有3个极点个极点有有3个基本解，个基本解，均可行均可行例例2.2. C例例1. 1. C第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础例例3. 3. subject to5个极点个极点x*=(3/2, 1/2)T 极点极点问题问题/ /作业作业( (习题习题2.6)2.6)证明这两个集合的极点是证明这两个集合的极点是一一对应一一对应

16、的！的！考虑集合考虑集合第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础线性规划问题解的几种情况线性规划问题解的几种情况第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.2 单纯形法单纯形法 适用形式：适用形式：标准形标准形(基本可行解等价于极点基本可行解等价于极点) 理论基础：理论基础：线性规划的线性规划的基本定理基本定理！ 基本思想：基本思想：从约束集的从约束集的某个极点某个极点/BFS开始，依次开始，依次移动到移动到相邻极点相邻极点/BFS，直到找出最优解

17、，或判断，直到找出最优解，或判断问题无界问题无界. 初始化：初始化：如何找到一个如何找到一个BFS？ 判断准则：判断准则：何时最优？何时无界？何时最优？何时无界？ 迭代规则：迭代规则：如何从一个极点如何从一个极点/BFS迭代到相邻极点迭代到相邻极点/BFS？第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础基本解基本解基变量基变量非基变量非基变量即可，次序可以打乱！即可，次序可以打乱！只要有只要有 m 个单位列个单位列 e1 , e2 , , em2.1.1 既约既约/相对费用系数相对费用系数不妨设我们已经得到了基变量为不妨设我们

18、已经得到了基变量为 的基本可行解的基本可行解1mx ,x 规范形系数的一种解释 表格中第 j 列的数据用当前基表示 aj 时的系数第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础将将 Ax = b 的任一解的任一解 x 用非基变量用非基变量表示为表示为既约费用系数既约费用系数/相对费用系数相对费用系数(*)相对费用系数的经济解释！(合成费用、相对费用)第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础定理定理(最优性判别最优性判别)在某基本可行解处，如果对所有在某基

19、本可行解处，如果对所有 j 有有 ,0jjjcrz则这个基本可行解是最优的则这个基本可行解是最优的.既约线性规划既约线性规划 假设假设令令第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.2.2 基本可行解的改进基本可行解的改进定理定理( BFS的提高的提高) 给定目标值为给定目标值为 z0 的的非退化非退化基本可行解，且假定存基本可行解，且假定存在在 q 使得使得 rq 0，无无可行解！可行解！ z = 0，有有可行解，且可行解，且 x 是潜在的基本可行解！是潜在的基本可行解！ 基变量中基变量中无无人工变量人工变量 x 是是

20、BFS，B 是对应的基是对应的基 基变量中基变量中有有人工变量人工变量驱赶人工变量出基驱赶人工变量出基假设第假设第 i 个基变量是人工变量，且当前单纯形表个基变量是人工变量，且当前单纯形表第第 i 行的前行的前 n 个数据是个数据是第第 i 个约束冗余；个约束冗余；删除单纯形表的第删除单纯形表的第 i 行数据行数据以以任一非零元任一非零元为转轴元转轴为转轴元转轴得辅助问题的一个新的最优得辅助问题的一个新的最优BFS，且基变量中少，且基变量中少1个人工变量！个人工变量！第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础例例1. 给出

21、下面系统的一个基本可行解，或者说明其无解给出下面系统的一个基本可行解，或者说明其无解引入引入人工人工变量变量目标目标：辅助问题的辅助问题的初始表格初始表格！BFSx = (0, 0, 0, 4, 3)T第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础第一张第一张单纯形表单纯形表第二张第二张单纯形表单纯形表第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础辅助问题的辅助问题的最优值是最优值是0 0. . 原问题的原问题的BFS：第第 2 章章 线性规划线性规划: 基本

22、理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础例例2. 利用两阶段法求解下面的问题利用两阶段法求解下面的问题辅助问题辅助问题第第I阶段：阶段：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础辅助问题的辅助问题的最后一张单纯形表最后一张单纯形表原问题的原问题的初始初始表格：表格：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础原问题的原问题的最优解最优解：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-B

23、UAA数学规划基础数学规划基础两阶段法两阶段法可求解任意的可求解任意的线性规划问题线性规划问题 第第 I 阶段：启动单纯形法阶段：启动单纯形法 构造、求解辅助问题构造、求解辅助问题 判断原问题判断原问题不可行、或可行不可行、或可行 可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形 第第 II 阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题 从上述从上述BFS出发，求解所给问题出发，求解所给问题 原问题原问题无界无界或者或者有解有解第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础两阶段法的例子两阶段法的例子第

24、第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.2.6 修正单纯形法修正单纯形法给定基给定基 B 及对应及对应BFS，即，即 B-1b用用非基非基变量表示变量表示基基变量：变量：用用非基非基变量表示变量表示目标函数目标函数：既约既约/ /相对相对费用向量费用向量*第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础与基矩阵与基矩阵 B 对应的单纯形表对应的单纯形表 每次迭代需要的数据每次迭代需要的数据核心核心计算：计算：B-1单纯形表的最后一行、某列和最后一列单纯形

25、表的最后一行、某列和最后一列 仅需原始数据仅需原始数据(c, A, b)和基和基 B 的逆矩阵的逆矩阵 重要事实：重要事实： 单纯形法的迭代次数典型地为单纯形法的迭代次数典型地为 2m-3m第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础修正单纯形法的计算步骤修正单纯形法的计算步骤步步2 选取选取 q 满足满足步步0 给定给定BFS及对应的及对应的B-1.计算计算 , 步步4 更新更新 B-1, B-1b 和和 ，返步，返步1.步步1 计算计算 .如果如果 停；得最优解停；得最优解.问题问题无界无界；否则，选；否则，选 p 满足

26、满足步步3 计算计算 yq=B-1 aq；若；若 ， 核心问题：核心问题：理论上的表现理论上的表现当前基的逆当前基的逆 新基的逆新基的逆如何更新如何更新如何用初等行变换实现如何用初等行变换实现单纯形乘子单纯形乘子第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础定理 设 ，则 aq 进基 ap 出基后所得新基 满足利用利用初等行变换初等行变换可以实现上述基的逆和单纯形乘子的转换！可以实现上述基的逆和单纯形乘子的转换！(2) 转轴后的单纯形乘子 ，其中 up 表示 B-1 的第 p 行.这里 ei 表示第 i 个 m 维单位向量，向

27、量 v 定义为(1) ，其中基的逆和单纯形乘子的转换基的逆和单纯形乘子的转换(*)第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础相关数据的更新相关数据的更新初等行变换初等行变换设设转轴元转轴元是是 ，即，即 ap 出基，出基， aq 进基进基以为转轴元，以为转轴元，转轴后转轴后即得新基对应的数据！即得新基对应的数据！第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础例例1 求解例求解例2.2.2q = 1a1进基进基，计算，计算 y1.得得第第 2 章章 线性规划

28、线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础转轴：转轴：计算计算 , q = 3计算计算第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础计算计算最优值：最优值：最优解：最优解：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础问题问题. . 设用单纯形法求解标准形式的设用单纯形法求解标准形式的LPLP时得到如下时得到如下 单纯形表单纯形表. .还假设矩阵还假设矩阵A的的后三列形成单位矩阵后三列形成单位矩阵1.1.给出由该

29、表描述的当前基是最优的充分必要条件给出由该表描述的当前基是最优的充分必要条件( (依照表中的系数依照表中的系数).).2.2.假设该基是最优的且假设该基是最优的且 . .找出另外一个最找出另外一个最优基本可行解，其与该表所描述的不同优基本可行解，其与该表所描述的不同. .第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础假定与假定与当前表所联系的基是最优当前表所联系的基是最优的的 假设将原问题中的假设将原问题中的 ，给出使基保，给出使基保持最优的持最优的 的范围的范围. .1.1.假设将原问题中的假设将原问题中的 ，给出使基保，给

30、出使基保持最优的持最优的 的范围的范围问题问题 设用单纯形法求解标准形式的设用单纯形法求解标准形式的LPLP时得到如下单纯时得到如下单纯 形表形表. .还假设矩阵还假设矩阵 A 的的后三列形成单位矩阵后三列形成单位矩阵第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.2.7 单纯形法的效率单纯形法的效率有效性问题有效性问题: : 给定一个问题，求解它需要多长时间给定一个问题，求解它需要多长时间( (时时间复杂度间复杂度) )？求解它需要多少存储空间？求解它需要多少存储空间( (空间复杂度空间复杂度) )？ 平均情况平均情况(a

31、verage case): 典型问题需要多少时间典型问题需要多少时间 从数学上研究很困难从数学上研究很困难 经验研究经验研究两种解答两种解答最坏情况最坏情况(worst case): 最难的问题需要多少时间最难的问题需要多少时间 数学上是可处理的数学上是可处理的 有限值有限值 第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础度量度量(measures)大小的度量大小的度量(measures of size)问题的度量问题的度量 约束的个数约束的个数 m 和和/或者变量的个数或者变量的个数 n 数据个数数据个数mn 非零数据的个数

32、非零数据的个数 尺寸，比如以尺寸，比如以bytes为单位为单位度量时间度量时间(measuring time) 算法的度量算法的度量 迭代次数迭代次数 每次迭代的算术运算次数每次迭代的算术运算次数 每次算术运算的时间每次算术运算的时间(依赖于硬件依赖于硬件)第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础Klee-Minty问题问题(1972)n = 3 时：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础扭曲的立方体扭曲的立方体(A distorted Cube

33、)约束集是如下立方体的约束集是如下立方体的稍微稍微(minor)扭曲：扭曲：n=3时：时：9608第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础指数指数 (Exponential)Klee-Minty的问题说明：的问题说明： 当求解具有当求解具有 n 个变量和约束的问题时，个变量和约束的问题时，最小系数最小系数规则规则有可能需要有可能需要 2n-1 次转轴次转轴(因此因此遍历遍历了扭曲立方体的了扭曲立方体的 2n 个顶个顶点点)当当 n = 70 时，时，假设假设 1 秒钟迭代秒钟迭代 1000 次，求解这个问题需要次，求解这

34、个问题需要 400 亿年；亿年；宇宙的估计年龄是宇宙的估计年龄是 137 亿年亿年.然而每天求解的问题中，变量在然而每天求解的问题中，变量在10,000到到100,000之间的很普遍之间的很普遍.Worst case analysis is just that: worst case.第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础复杂度复杂度(Complexity)排序：排序：O(nlogn)矩阵乘以向量：矩阵乘以向量：O(n2)矩阵乘以矩阵：矩阵乘以矩阵：O(n3)解线性方程组：解线性方程组：O(n3)单纯形法：单纯形法：

35、最坏情况：最坏情况：O(n22n) 平均情况：平均情况：O(n3) 问题：问题： 是否存在求解线性规划的方法，是否存在求解线性规划的方法，它的最坏性能分析是多项式的它的最坏性能分析是多项式的?第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础线性规划的历史线性规划的历史 渊源要追溯到渊源要追溯到Euler、Leibniz、Lagrange等等 G. Dantzig, Von Neumann(Princeton) 和和 L. Kantorovich在在1940s创建了线性规划创建了线性规划 1947年年, G. Dantzig于于发

36、明了发明了单纯形法单纯形法 1979年年，L. Khachain找到了求解线性规划的一种有效方法找到了求解线性规划的一种有效方法(第一个多项式时间算法第一个多项式时间算法椭球法椭球法) 1984年年，N. Karmarkan发现了另一种求解线性规划的有效发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者方法，已证明是单纯形法的强有力的竞争者(投影内点法投影内点法) 现在求解大规模和退化问题最有效的是现在求解大规模和退化问题最有效的是原始对偶路径跟原始对偶路径跟踪内点法踪内点法(9.5节节)第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUA

37、A数学规划基础数学规划基础纽约时报纽约时报时代周刊时代周刊第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础华尔街日报华尔街日报商业周刊商业周刊第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础纽约时报纽约时报华尔街日报华尔街日报第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础1 24225345123123:,0,1 xxx 142512x232423x134514x作业2.30第第 2 章章 线性规

38、划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础l对偶问题对偶问题l对偶定理对偶定理l与单纯形法的关系与单纯形法的关系l互补定理互补定理l对偶单纯形法对偶单纯形法2.3 对偶对偶第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础 原始问题原始问题(primal)：给定数据给定数据2.3.1 对偶问题对偶问题原始变量原始变量 对偶问题对偶问题(dual)：对偶变量对偶变量第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶问

39、题：对称形式的对偶对对偶问题：对称形式的对偶对注注1 对于线性规划，对偶是相互的，即对于线性规划，对偶是相互的，即对偶问题的对偶对偶问题的对偶 是原始问题是原始问题 原始问题原始问题(primal)：给定数据给定数据注注2 2 为了确定任一线性规划问题的对偶，可以利用为了确定任一线性规划问题的对偶，可以利用 对称形式或非对称形式的对偶对！对称形式或非对称形式的对偶对！原始变量原始变量 对偶问题对偶问题(dual)：对偶变量对偶变量第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础 配餐问题配餐问题：确定食品数量，满足营养需求，花费

40、最小？：确定食品数量，满足营养需求，花费最小？n种食品，种食品，m种营养成份；第种营养成份；第 j 种食品的单价种食品的单价每单位第每单位第 j 种食品含第种食品含第 i 种营养的数量种营养的数量 变量变量： 食用第食用第 j 种食品的数量种食品的数量为了健康，每天最少要食用第为了健康，每天最少要食用第 i 种营养的数量种营养的数量 模型：模型：对偶问题：经济解释对偶问题：经济解释对偶问题保健品公司药剂师、营养丸、对偶问题保健品公司药剂师、营养丸、定价问题定价问题第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶问题：一般问题

41、的对偶对偶问题：一般问题的对偶给定数据给定数据 A, b, c；记；记 A 的第的第 i 行为行为 ai，A 的第的第 j 列为列为 aj 原始问题原始问题(primal)： 对偶问题对偶问题(dual)：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶问题：例子对偶问题：例子第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.3.2 对偶定理对偶定理弱对偶定理弱对偶定理. . 设设 和和 分别是原始问题和对偶问题的可行分别是原始问题和对偶问题的可行解，则解，

42、则 . . 推论推论2. 如果原始问题与对偶问题之一无界，则另一个问题如果原始问题与对偶问题之一无界，则另一个问题 没有可行解没有可行解.推论推论1. 设设 和和 分别是原始问题和对偶问题的可行解分别是原始问题和对偶问题的可行解,若若 则则 和和 分别是原始问题和对偶问题最优解分别是原始问题和对偶问题最优解. .考虑对偶问题的初衷！考虑对偶问题的初衷！第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶定理：强对偶定理对偶定理：强对偶定理对于一般形式的线性规划利用对于一般形式的线性规划利用凸集分离凸集分离定理定理证明！证明！强对

43、偶定理强对偶定理. . 如果原始问题和对偶问题之一有解，则另如果原始问题和对偶问题之一有解，则另一个问题也有解，且最优值相等一个问题也有解，且最优值相等. .有解有解无无(下下)界界不可行不可行有解有解无无(上上)界界不可行不可行 对偶问题对偶问题原始问题原始问题第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.3.3 与单纯形法的关系与单纯形法的关系如何由原始问题的解得到对偶问题的解？定理2.3.3. 设标准形线性规划问题有最优解，B是最优基本可行解对应的基，则是其对偶问题的最优解.特例：当系数矩阵A中有单位矩阵时，如何从单

44、纯形表读出当前基的逆矩阵？第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础考虑问题引入松弛变量标准形利用单纯形法求解与单纯形法的关系与单纯形法的关系：例子：例子对偶问题第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础与单纯形法的关系：例子与单纯形法的关系：例子( (续续) )原原问题问题最优解最优解对偶对偶问题问题最优解最优解第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.3.4 灵敏度灵敏度与

45、与互补性互补性 与基与基 B 对应的单纯形乘子对应的单纯形乘子(simplex multiplier) 经济解释经济解释 记记 A 的列向量为的列向量为 aj，对应费用为，对应费用为 cj，j =1 , , n解释为单位向量解释为单位向量 ei 的的合成价格合成价格！解释为解释为 aj 的的相对相对/既约既约费用系数费用系数 最优性：最优性：对所有的对所有的 j 有有 第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础灵敏度灵敏度(sensitivity)与与影子价格影子价格(shadow price)问题：当向量问题：当向量 b

46、 发生微小变化时，问题的最优值如何变化？发生微小变化时，问题的最优值如何变化？假设该问题的最优基是假设该问题的最优基是 B且且 B-1b 0 (非退化！非退化！)令令第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础因为 所以称称 为分量为分量 所对应资源的所对应资源的边际边际价格价格(marginal price) 或者或者影子影子价格价格(shadow price)从而z*z* 第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础互补定理互补定理(线性规划的最优性条

47、件线性规划的最优性条件)用用 aj 表示表示 A 的第的第 j 列，列，ai 表示表示 A 的第的第 i 行行 定理定理. . 设设 和和 分别是分别是非对非对称称形式原始问题和对偶问题形式原始问题和对偶问题的的可行解可行解. 则它们是各自最则它们是各自最优解的优解的充要充要条件是：对所有条件是：对所有 i 有有定理定理. 设设 和和 分别是分别是对称对称形式原始问题和对偶问题的形式原始问题和对偶问题的可行解可行解. 则它们是各自最优则它们是各自最优解的解的充要充要条件是：对所有的条件是：对所有的 i 和和 j 有有课本上定理3.2.1(p.63)的证明要用到互补定理！第第 2 章章 线性规划

48、线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础互补定理互补定理(线性规划的最优性条件线性规划的最优性条件)的应用的应用例例 2.3.5第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础2.3.5 对偶单纯形法对偶单纯形法 适用问题：标准形问题有一个适用问题：标准形问题有一个不可行不可行的基本解，的基本解，但但 对应单纯形乘子是对偶问题的可行解对应单纯形乘子是对偶问题的可行解 单纯形表中的表现：单纯形表中的表现： 第一张单纯形表第一张单纯形表: : 相对费用系数非负，但有基变量取负值！相对

49、费用系数非负，但有基变量取负值！ 转轴过程中：保持相对费用系数非负，直到转轴过程中：保持相对费用系数非负，直到全部全部基变量基变量 取非负值！取非负值！第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础则称则称 x 是标准形问题的是标准形问题的对偶可行对偶可行基本解基本解.定义定义 假设是假设是 Ax = b 的基本解的基本解. 如果如果基本解基本解(互补性互补性)可行对偶可行最优解可行对偶可行最优解初始对偶可行基本解初始对偶可行基本解新的对偶可行基本解新的对偶可行基本解“原始可行对偶可行原始可行对偶可行”的基本解！的基本解！迭代

50、迭代对偶单纯形法：对偶可行基本解对偶单纯形法：对偶可行基本解 是是对偶问题的可行解对偶问题的可行解，即，即 第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础设对偶可行基本解设对偶可行基本解 x 对应的基对应的基 对偶单纯形法：推导对偶单纯形法：推导I I不妨设不妨设 yp0 0； 此外还假设此外还假设 非退化非退化，即，即令令 ，其中，其中 是是 的第的第 p 行，则行，则目的：目的：找新的找新的 使前使前 m 个等式中的某个与后个等式中的某个与后n-m个不等式个不等式中的某个角色互换，同时使中的某个角色互换，同时使对偶对偶目标

51、函数的值目标函数的值增大增大！修正单纯形法第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶单纯形法：推导对偶单纯形法：推导IIII出基变量：取出基变量：取负值负值的基变量的基变量( (* * * * * *) )进基变量：其进基变量：其 p 行的负元素，且取到行的负元素，且取到最小正比值最小正比值 ( (* * * * * *) )第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础步步0 给定对偶可行基本解对应的单纯形表给定对偶可行基本解对应的单纯形表.步步1

52、若对若对每个每个 i 都有都有 ，停；当前，停；当前DFBS是最优的是最优的.步步2 选取选取 p 满足满足 yp0 0 ，这时，第，这时，第 p 个基变量出基个基变量出基.步步4 以以 ypq 为转轴元进行为转轴元进行转轴转轴，更新单纯形表，返步，更新单纯形表，返步1.对偶单纯形法：计算步骤对偶单纯形法：计算步骤步步3 若若 ，问题，问题无可行解无可行解；否则，；否则， 选选 q 满足满足第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础引入盈余变量；并给等式两边同乘引入盈余变量；并给等式两边同乘 -1；得初始表格；得初始表格/

53、第一张第一张单纯形表单纯形表对偶单纯形法：例子对偶单纯形法：例子第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶单纯形法：例子对偶单纯形法：例子( (续续) )最优解：最优解：第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础对偶单纯形法：收敛性对偶单纯形法：收敛性定理定理. . 如果标准形线性规划问题的任一对偶可行基本如果标准形线性规划问题的任一对偶可行基本解所对应的非基变量的相对费用系数解所对应的非基变量的相对费用系数大于零大于零，则对偶，则对偶单纯形法在单

54、纯形法在有限步有限步内终止内终止. . 如果线性规划问题可以用对偶单纯形法求解，则必有界！如果线性规划问题可以用对偶单纯形法求解，则必有界！ 其计算结果只能是其计算结果只能是不可行不可行或者或者有解有解！ 如果线性规划问题可以用单纯形法求解，则其如果线性规划问题可以用单纯形法求解，则其无界无界或或有解有解 两阶段法可以求解任一线性规划问题；两阶段法可以求解任一线性规划问题； 第第I阶段的结果为阶段的结果为可行可行或者或者不可行不可行两种；两种； 对于可行的，在第对于可行的，在第II阶段可得问题阶段可得问题无界无界或或有解有解！第第 2 章章 线性规划线性规划: 基本理论与方法基本理论与方法LHY-SMSS-BUAA数学规划基础数学规划基础 典型典型情况情况( (有显然的对偶可行基本解有显然的对偶可行基本解) ) 一般一般情况情况 已有一个标准形问题的最优解和最优基已有一个标准形问题的最优解和最优基 添加一个添加一个“不等式约束不等式约束”后的新问题后的新问题( (习题习题3.9) )灵敏度分析灵敏度分析对偶单纯形法：启动对偶单纯