《运筹学 第二章线性规划 第二讲 标准型与单纯形法》由会员分享，可在线阅读，更多相关《运筹学 第二章线性规划 第二讲 标准型与单纯形法（36页珍藏版）》请在金锄头文库上搜索。
1、Chapter 1 线性规划 Linear Programming2.3 线性规划的标准型Standard form of LPChapter 1 线性规划 Linear Programming在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。2.3 线性规划的标准型 Standard form of LP线性规划问题的标准型为:1目标函数求最大值（或求最小值）2约束条件都为等式方程3变量xj非负4常数bi非负Chapter 1 线性规划 Linear Programmingmax(或min)Z=c1x1+c2x2+cnxn2.3 线性规划的标准型 Stand
2、ard form of LPChapter 1 线性规划 Linear Programming或写成下列形式：或用矩阵形式2.3 线性规划的标准型 Standard form of LPChapter 1 线性规划 Linear Programming通常X记为： , 称为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般 情况mn，且r()m。其中:2.3 线性规划的标准型 Standard form of LPChapter 1 线性规划 Linear Programming一般形式线性规划模型的标准化准则: （前提 bi 0 ）5. xj0令xj = xj , xj 0 C
3、hapter 1 线性规划 Linear Programming【例1】将下列线性规划化为标准型 【分析】()因为x3无符号要求 ，即x3 可取正值也可取负值，标准型中要求变量非负，所以令 2.3 线性规划的标准型 Standard form of LPChapter 1 线性规划 Linear Programming(3)第二个约束条件是“”号，在“”号左端减去剩余 变量(surplus variable) x5 ，x50，也称松驰变量；2.3 线性规划的标准型 Standard form of LP(2) 第一个约束条件是“”号， 在“”号左端加入松驰变量(slack variable)
4、x4，x40,化为等式；(4)第三个约束条件是“”号且常数项为负数，因此在“”左边加入松驰变量x6，x60，同时两边乘以1。 (5)目标函数是最小值，为了化为求最大值，令Z=Z,得到 max Z=Z，即当Z达到最小值时Z达到最大值。 Chapter 1 线性规划 Linear Programming综合起来得到下列标准型 2.3 线性规划的标准型 Standard form of LPChapter 1 线性规划 Linear Programming当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束 将其化为两个不等式 再加入松驰变量化为等式。 2.3 线性规划的标
5、准型 Standard form of LP2.4 线性规划的有关概念Basic Concepts of LPChapter 1 线性规划 Linear Programming设线性规划的标准型max Z=CX (2.1)AX=b (2.2)X 0 (2.3)式中A 是mn矩阵，mn并且r(A)=m，显然A中至少有一个mm子矩阵B，使得r(B)=m。2.4 基本概念 Basic Concepts 基 (basis)：A中 mm子矩阵 B 并且有r(B)=m，则称B是 线性规划的一个基(或基矩阵basis matrix )。注：基矩阵B必为非奇异矩阵即|B|0。 当m=n时，基矩阵惟一，当m0i
6、表2. 5(1)XBx1x2x3x4bx3211040x4130130j3400 (2)x3x2j (3)x1 x2 j 基变量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/5 2/5400-1-1将3化为12.5 单纯形法Simplex Method3018Chapter 1 线性规划 Linear Programming单纯形法的计算步骤：1. 找一个初始可行基，写出对应的典式，列出初始单 纯形表,其中基变量的检验数必为零； 2. 判断： (a)若j( j，n)，则得到最优解； (b)若存在某个k0且aik(i=1，2,m)，则线性规划
7、具有无界解； (c)若存在k0且aik (i=1,m)不全非正，则进行换基；1.5 单纯形法Simplex Method3. 换基： (a)选进基变量：设k=max j | j 0, 选第k列所对应 的变量xk为进基变量。Chapter 1 线性规划 Linear Programming第个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个aLk为主元素。(c)求新的基可行解：用初等行变换方法将aLk化为, 第 k 列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。(b)选出基变量 ：求最小比值1.5 单纯形法Simplex Method
8、Chapter 1 线性规划 Linear Programming【例4】 用单纯形法求解【解】将数学模型化为标准型：1.5 单纯形法Simplex MethodChapter 1 线性规划 Linear ProgrammingCj12100 bCBXBx1x2x3x4x50x423210150x51/3150120j12100 0x42x2j 1x1 2x2 j 表1. 61/3150120301713751/30902 2025601017/31/31250128/91/92/335/30098/91/97/3最优解X=(25，35/3，0，0，0)T，最优值 Z =145/31.5 单纯形法Simplex MethodChapter 1 线性规划 Linear Programming作业：教材P3435 T 8(1)，11(1)1.3 线性规划的标准型 Standard form of LP下一节：基本概念1.线性规划问题化标准形式；4.单纯形法思想。2. 线性规划常用的概念：可行解、基本解、基本 可行解、最优解、基本最优解、基、可行基、最优基、凸集、极点(凸点)、凸组合；3. 线性规划的三个基本定理。
