1.31.4线性规划的基本概念

1、Chapter 1 线性规划线性规划 Linear Programming1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming 在用单纯法求解线性规划问题时，为了讨论问在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。题方便，需将线性规划模型化为统一的标准形式。 1.3 线性规划的标准型线性规划的标准型 Standard form of LP线性规划问题的标准型为线性规划问题的标准型为: 1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值） 2约束条

2、件都为等式方程约束条件都为等式方程 3变量变量xj非负非负 4常数常数bi非负非负 Chapter 1 线性规划线性规划 Linear Programmingmibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2, 1,0,2, 1,022112222212111212111max(或min)Z=c1x1+c2x2+cnxn 1.3 线性规划的标准型线性规划的标准型 Standard form of LP注：本教材默认标准型中目标函数是注：本教材默认标准型中目标函数是 maxChapter 1 线性规划线性规划 Linear ProgrammingnjjjxcZ1m

3、axnjxmibxajnjijij, 2 , 1, 0, 2 , 1,10maxXbAXCXZ或写成下列形式或写成下列形式： 或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming111211121222221212, , )nnnmmmnnmaaaxbaaaxbAXbCc ccaaaxb ； (通常通常X记为：记为： , 称称为约束方程为约束方程的系数矩阵，的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，一般是决策变量的个数，一般情况情况mn，且，

4、且r()m。TnxxxX),(21max0ZCXAXbX其中其中:1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming一般形式线性规划模型的标准化准则一般形式线性规划模型的标准化准则: （前提（前提 b bi 0 ）cxZ min.1injjijbxa1. 2injjijbxa1. 3cxZmax01iniinnjjijxbxxa01iniinnjjijxbxxa无符号要求ix.40, 0, iiiiixxxxx5. xj0令令xj = xj , xj 0 Chapter 1 线性规划线性规划

5、 Linear Programming【例【例1】将下列线性规划化为标准型】将下列线性规划化为标准型 3213minxxxZ无符号要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxx【分析】【分析】()因为因为x3无符号要求无符号要求 ，即，即x3 可取正值也可取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 0,33333 xxxxx其中1.3 线性规划的标准型线性规划的标准型 Standard form of LPChapter 1 线性规划线性规划 Linear Programming (3)第二个约束条件是第

6、二个约束条件是“”号，在号，在“”号左端减去剩余号左端减去剩余 变量变量(surplus variable) x5 ，x50，也称松驰变量；，也称松驰变量；1.3 线性规划的标准型线性规划的标准型 Standard form of LP(2) 第一个约束条件是第一个约束条件是“”号，号， 在在“”号左端加入松驰变量号左端加入松驰变量 (slack variable) x4，x40, 化为等式；化为等式；(4)第三个约束条件是第三个约束条件是“”号且常数项为负数，因此在号且常数项为负数，因此在“”左边加入松驰变量左边加入松驰变量x6，x60，同时两边乘以，同时两边乘以1。 (5)目标函数是最小值

7、，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令Z=Z, 得到得到 max Z=Z，即当，即当Z达到最小值时达到最小值时Z达到最大值。达到最大值。 3213minxxxZ无符号要求、32132132132100) 3(523)2(3) 1 (82xxxxxxxxxxxxChapter 1 线性规划线性规划 Linear Programming综合起来得到下列标准型综合起来得到下列标准型 332133maxxxxxZ 05)(233826543321633215332143321xxxxxxxxxxxxxxxxxxxxxx、1.3 线性规划的标准型线性规划的标准型 Standard

8、form of LPChapter 1 线性规划线性规划 Linear Programming当某个约束是绝对值不等式时，将绝对值不等式化为两个不等当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束式，再化为等式，例如约束 974321xxx将其化为两个不等式将其化为两个不等式 974974321321xxxxxx再加入松驰变量化为等式。再加入松驰变量化为等式。 1.3 线性规划的标准型线性规划的标准型 Standard form of LP1.4 线性规划的有关概念线性规划的有关概念 Basic Concepts of LPChapter 1 线性规划线性规划 L

9、inear Programming 设线性规划的标准型设线性规划的标准型 max Z=CX (1.1) AX=b (1.2) X 0 (1.3) 式中式中A 是是mn矩阵，矩阵，mn并且并且r(A)=m，显然，显然A中至少中至少有一个有一个mm子矩阵子矩阵B，使得，使得r(B)=m。1.4 基本概念基本概念 Basic Concepts 基基 (basis)：A中中 mm子矩阵子矩阵 B 并且有并且有r(B)=m，则称，则称B是线性规划的一个是线性规划的一个基基(或或基矩阵基矩阵basis matrix )。mnC注：注：基矩阵基矩阵B必为非奇异矩阵即必为非奇异矩阵即|B|0。当当m=n时，基

10、矩阵惟一，当时，基矩阵惟一，当mn时，基矩阵就可能有多个，但数时，基矩阵就可能有多个，但数目不超过目不超过Chapter 1 线性规划线性规划 Linear Programming【例【例2】线性规划】线性规划 32124maxxxxZ5 , 1, 0226103553214321jxxxxxxxxxj 求所有基矩阵求所有基矩阵。 【解】约束方程的系数矩阵为【解】约束方程的系数矩阵为25矩阵矩阵 10261001115A1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Programming10261001115A,610151B,01

11、0152B,110053B26114B10019B,12017B,02118B,16016B,06115B容易看出容易看出r(A)=2，2阶子矩阵有阶子矩阵有C52=10个，其中第个，其中第1列与列与第第3列构成的列构成的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即 Chapter 1 线性规划线性规划 Linear Programming当确定某一矩阵为基矩阵时，则基矩阵对应的列向量当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为称为基向量基向量(basic vector)，其余列向量称为，其余列向量称为非基向量非基向量; 基向量对应的变量称为基向量对应的变量称

12、为基变量基变量(basic variable)， 非基向量对应的变量称为非基向量对应的变量称为非基变量非基变量 ；在上例中在上例中B2的基向量是的基向量是A中的第一列和第四列，其余列中的第一列和第四列，其余列向量是非基向量，向量是非基向量，x1、x4是基变量，是基变量，x2、x3、x5是非基是非基变量。变量。基变量、非基变量是针对某一确定基而言的基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。不同的基对应的基变量和非基变量也不同。 010152B10261001115A1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 L

13、inear Programming 可行解可行解(feasible solution): 满足式满足式(1.2)及及(1.3)的解的解X=（x1, x2 , xn)T 称为可行解；称为可行解； 基本可行解基本可行解(basic feasible solution): 若基本解是可行解若基本解是可行解 则称为是基本可行解（也称基可行解）。则称为是基本可行解（也称基可行解）。 基本解基本解(basic solution) : 对某一确定的基对某一确定的基B，令，令非基变量非基变量 等于零等于零，利用式，利用式(1.2)解出基变量，则这组解称为基解出基变量，则这组解称为基 的的 基本解。基本解。 最

14、优解最优解(optimal solution): 满足式满足式(1.1)的可行解称为最优的可行解称为最优 解，即使得目标函数达到解，即使得目标函数达到最大值最大值的的可行解可行解就是最优解；就是最优解；非可行解非可行解(infeasible solution) 无界解无界解 (unbounded solution)1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Programming显然，只要基本解中的基变量的解满足式显然，只要基本解中的基变量的解满足式(1.3)的非负的非负要求，那么这个基本解就是基本可行解。要求，那么这个基本解就是

15、基本可行解。 在上例中，对在上例中，对来说，来说，x1, x2是基变量，是基变量，x3 , x4 ，x5是是非基变量，令非基变量，令x3=x4=x5=0，则式，则式(1.2)为为2610352121xxxx,610151B 因因|B1|，由克莱姆法则知，由克莱姆法则知，x1、x2有有惟一解惟一解x12/5, x2=1, 从而从而基本解为基本解为TX)0 , 0 , 0 , 1 ,52()1(1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Programming对对B2来说，来说，x1, x4,为基变量，令非变量为基变量，令非变量x2,

16、 x3, x5为零，由为零，由式式(1.2)得得 ，x4=4，则基本解为，则基本解为511xTX)0 , 4 , 0 , 0 ,51()2(,010152B反之，反之，可行解不一定是基本可行解可行解不一定是基本可行解，如，如 满足式满足式(1.2)(1.3)，但不是任何基矩阵的基本解。，但不是任何基矩阵的基本解。TX) 1 ,27,21, 0 , 0(在在 中中x10, 不是可行解，因此也不是基本可行解。不是可行解，因此也不是基本可行解。 (2)XChapter 1 线性规划线性规划 Linear Programming可行基可行基: 基可行解对应的基称为可行基；基可行解对应的基称为可行基；

17、最优基最优基: 基本最优解对应的基称为最优基；基本最优解对应的基称为最优基； 如上述如上述B3就是最优基，最优基肯定是可行基。就是最优基，最优基肯定是可行基。1.4 基本概念基本概念 Basic Concepts 基本最优解基本最优解: 最优解是基本解称为基本最优解。例如最优解是基本解称为基本最优解。例如 满足式满足式(1.1)(1.3)是最优解是最优解, 又是又是B3的的基本解基本解, 因此它是基本最优解。因此它是基本最优解。TX) 8 , 0 , 0 , 0 ,53(注：注：当最优解惟一时，最优解亦是基本最优解，当最优解惟一时，最优解亦是基本最优解， 当最优解不惟一时，则最优解不一定是基本

18、最优解。当最优解不惟一时，则最优解不一定是基本最优解。Chapter 1 线性规划线性规划 Linear Programming基本最优解、最优解、基本可行解、基本解、可行基本最优解、最优解、基本可行解、基本解、可行解的关系解的关系:基本最优解基本最优解基本可行解基本可行解可行解可行解最最 优优 解解基本解基本解1.4 基本概念基本概念 Basic Concepts Chapter 1 线性规划线性规划 Linear Programming凸集凸集(Convex set): 设设 K 是是 n 维空间维空间 Rn 的一个点集，对的一个点集，对 任意两点任意两点 时，则称时，则称K为凸集。为凸集

19、。,)2()1(KXX、) 10()1 ()2()1(KXXX当 就是以就是以X(1)、X(2)为端点的线为端点的线段方程段方程, 点点X的位置由的位置由的值确定的值确定, 当当=0时时, X=X(2), 当当=1时时X=X(1)。)2()1()1 (XXX第第2节节 LP的几何意义的几何意义 Chapter 1 线性规划线性规划 Linear Programming凸组合凸组合(Convex combination) : 设设 是是Rn中的点，若存在中的点，若存在 使得使得 成立，成立， 称称X为为 的凸组合。的凸组合。)()2() 1 (,KXXXX及，且，021iK11KiiiKiiXX

20、1)()2() 1 (,KXXX第第2节节 LP的几何意义的几何意义 Chapter 1 线性规划线性规划 Linear Programming极点极点(Extreme point): : 设设K是凸集，是凸集， ，若，若X不能用不能用K中中两个不同的点两个不同的点 的凸组合表示为的凸组合表示为KX )2()1(,XX ) 10 ( ) 1 ( ) 2 ( ) 1 ( X X X 则称则称X是是K的一个极点或顶点。的一个极点或顶点。 X是凸集是凸集K的极点，即的极点，即X不可能不可能是是K中某一线段的内点，只能中某一线段的内点，只能是是K中某一线段的端点。中某一线段的端点。 1Q2QO3Q4Q

21、第第2节节 LP的几何意义的几何意义 Chapter 1 线性规划线性规划 Linear Programming【定理定理1】 若线性规划问题若线性规划问题(P)的可行域的可行域 D 非空非空, 则则 D 是凸是凸集。集。 关于线性规划问题的几个定理关于线性规划问题的几个定理 (P) max Z=CX (1.1) AX=b (1.2) X 0 (1.3) 第第2节节 LP的几何意义的几何意义 Chapter 1 线性规划线性规划 Linear Programming【定理定理1】 若线性规划可行域若线性规划可行域D 非空非空, 则则 D 是凸集。是凸集。 【引理引理1】 线性规划问题的可行解线

22、性规划问题的可行解TnxxxX),.,(21为基本可行解的充要条件是为基本可行解的充要条件是X的正分量所对应的的正分量所对应的系数列向量是线性独立的。系数列向量是线性独立的。第第2节节 LP的几何意义的几何意义 Chapter 1 线性规划线性规划 Linear Programming【定理定理1】 若线性规划可行域若线性规划可行域 D 非空非空, 则则 D 是凸集。是凸集。 【定理定理2】 线性规划的可行域线性规划的可行域D 的点的点 X 是极点的充要是极点的充要条件为条件为 X 是基本可行解。是基本可行解。线性规划的基本定理线性规划的基本定理注：注：定理定理2 2刻划了可行域的极点与基本可行解的对应关系，极刻划了可行域的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点一一对应，有可能两个或几个基本可行解对应于同一极点( (退退化基本可行解时化基本可行解时) )。第第2节节 LP的几何意义的几何意义 Chapter 1 线性规划线性规划 Linear Programming【定理定理1】 若线性规划可行域若线性规划可行域 D 非空非空, 则则 D 是凸集。是凸集。 【定理定理2】 线性规划的可行解集合线性规划的可行解集合 K 的点