第二节单纯形法 单纯形法是求解线性规划的主要算法,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
般地,记松弛变量的向量为X,则 AX6 AX-X=b s t st X≥0 XX≥0 问题:松弛变量在目标中的系数为何?——-0 3)当模型中有某变量x没有非负要求,称 为自由变量,则可令x=x-x,x,x"≥0 化为标准型
一般地，记松弛变量的向量为 Xs，则 0 . . X AX b st + = , 0 . . s s X X AX IX b st 0 . . X AX b st − = , 0 . . s s X X AX IX b st 问题：松弛变量在目标中的系数为何？ —— 0。 3) 当模型中有某变量 xk 没有非负要求，称 为自由变量, 则可令 , , 0 / // / // xk = xk − xk xk xk 化为标准型
2基本概念 (1)可行解与最优解 可行解:满足全体约束的解,记为X 最优解:可行解中最优的,记为X,则对任可行 解X,有CX≤CX。 直观上,可行解是可行域中的点,是一个可行的方案; 最优解是可行域的角点,是一个最优的方案
2.基本概念 （1）可行解与最优解 可行解：满足全体约束的解，记为X； 解 ，有 。 最优解：可行解中最优的，记为 则对任可行 * , X CX CX X 直观上，可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优的方案
(2)基矩阵与基变量 基矩阵(简称基):系数阵A中的m阶可逆子阵,记 为B;其余部分称为非基矩阵,记为N 基向量:基B中的列;其余称非基向量。 基变量:与基向量P对应的决策变量x,记其组成的 向量为XB;与非基向量对应的变量称非基变 量,记其组成的向量为XN 例3:下面为某线性规划的约束 +2x+ 2x1-x2+x4=3 x1,…x4≥0 请例举出其基矩阵和相应的基向量、基变量
（2）基矩阵与基变量 基矩阵(简称基)：系数阵A中的m阶可逆子阵，记 为B；其余部分称为非基矩阵，记为N。 基向量：基B中的列；其余称非基向量。 基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。 1 2 3 1 2 4 1 4 3 2 1 2 3 , , 0 x x x x x x x x + + = − + = 例 ：下面为某线性规划的约束 请例举出其基矩阵和相应的基向量、基变量
例3:下面为某线性规划的约束 +2x,+ x,-x2 +x 3 x,≥0 请例举出其基矩阵和相应的基向量、基变量。 1210 解:本例中,A 2-101}4中的阶可逆子阵有 B 其相应的基向量为,P,基变量为x,x,X 2 B 其相应的基向量为P,P,基变量为x,x,X 问题:本例的A中一共有几个基? 般地,m×n阶矩阵基的个数最多有多少个?——C个
1 2 3 1 2 4 1 4 3 2 1 2 3 , , 0 x x x x x x x x + + = − + = 例 ：下面为某线性规划的约束 请例举出其基矩阵和相应的基向量、基变量。 解：本例中， ， 中的2阶可逆子阵有 1 0 0 1 1 2 2 1 A A − = —— 6个。 一般地，m×n 阶矩阵A中基的个数最多有多少个？ — —C 个。 , , , ; 1 0 0 1 4 3 1 3 4 3 4 1 = = x x B ，其相应的基向量为P P 基变量为x x ，X 其相应的基向量为 基变量为 。 = − = 2 1 2 1 2 1 2 2 , , , , , 1 2 2 1 x x B P P x x X 问题：本例的A中一共有几个基？
(3)基本解与基本可行解 当A中的基B取定后,不妨设B表示A中的前m列,则可记A=(BN) 相应地X=(X。X),约束中的AX=b可表示为BN b 即X2=Bb-BNX当取X,=0时,有X。=Bb、X(Bb 0 称AX=b的解X= (Bb 为线性规划的一个基本解 可见:一个基本解是由一个基决定的。 注意:基本解仅是资源约束的解,并未要求其非负,因此其未必可行。 称非负的基本解为基本可行解(简称基可行解)
（3）基本解与基本可行解 ( ) ( ) . 0 , 0 , , , , 1 1 1 1 = − = = = = = = = − − − − B b X B b B N X X X B b X b X X X X X A X b B N A B B A m A B N 即 当取 时，有 相应地 约束中的 可表示为 当 中的基 取定后，不妨设 表示 中的前 列，则可记 （ ） 称 的解 为线性规划的一个基本解； = = − 0 B b A X b X 可见：一个基本解是由一个基决定的。 注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。 称非负的基本解为基本可行解（简称基可行解）