第二节单纯形法 单纯形法是求解线性规划的主要算法,1947 年由美国斯坦福大学教授丹捷格(G.B. Danzig) 提出。 尽管在其后的几十年中,又有一些算法问世, 但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率
第二节 单纯形法 单纯形法是求解线性规划的主要算法，1947 年由美国斯坦福大学教授丹捷格（G.B.Danzig） 提出。 尽管在其后的几十年中，又有一些算法问世， 但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率
单纯形法的预备知识 1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型: Maxz= cx AX=b st x≥0 其中,A的秩为m(m≤n,b≥0 标准型的特征:Max型、等式约束、非负约束
1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模 型化为标准型： = = 0 . . X AX b st Maxz CX 标准型的特征：Max型、等式约束、非负约束 一、单纯形法的预备知识 其中，A 的秩为m（m n）,b 0
非8形式何化你准 )Min型化为Max型 加负号 Minz=cx Maxz=-CX 因为,求一个函数 的极小点,等价于求该 函数的负函数的极大点。 注意:Min型化为Max型求解后,最优解不变,但最优值差负号
非标准形式如何化为标准 1) Min型化为Max型 Minz = CX Maxz = −CX / 加负号 因为，求一个函数 的极小点，等价于求该 函数的负函数的极大点。 f (x) − f (x) * x 注意： Min型化为Max型求解后，最优解不变，但最优值差负号
2)不等式约束化为等式约束 分析:以例1中煤的约束为例 9x+4x.<360 之所以“不等”是因为左右两边有一个差额,称为“松 弛量”,若在左边加上这个松弛量,则化为等式。而这 个松弛量也是变量,记为愿,则有 9x+4x2+x 360 称为松弛变量。问题:它的实际意义是什么? 煤资源的“剩余
2) 不等式约束化为等式约束 分析：以例1中煤的约束为例 9x 1 + 4x 2 360 之所以“不等”是因为左右两边有一个差额，称为“松 弛量”，若在左边加上这个松弛量，则化为等式。而这 个松弛量也是变量，记为X3 ，则有 9x 1 + 4x 2 + x 3 = 360 X3称为松弛变量。问题：它的实际意义是什么？ —— 煤资源的“剩余
练习:请将例1的约束化为标准型 9x1+4x2<360 4x1+5x2<200 s t 3x1+10x2<300 x1x2≥0 解:增加松弛变量xx,x,则约束化为 9x1+4x2+ 360 4x1+5x2 +X4 200 s, t 3x1+10x2 300 x.x 4 ≥0 易见,增加的松弛变量的系数恰构成一个单位阵I
练习：请将例1的约束化为标准型 + + + , 0 3 10 300 4 5 200 9 4 360 . . 1 2 1 2 1 2 1 2 x x x x x x x x s t 解：增加松弛变量 x 3 , x 4 , x 5 , 则约束化为 + + = + + = + + = , , , , 0 3 10 300 4 5 200 9 4 360 . . 3 4 5 1 2 5 1 2 4 1 2 3 1 2 x x x x x x x x x x x x x x s t 易见，增加的松弛变量的系数恰构成一个单位阵I