运筹学03-单纯形法

第三章 单纯形法3.1 线性规划问题的标准形式3.2 线性规划问题的解3.3 单纯形法3.4 求初始基的人工变量法3.1 线性规划问题的标准形式目标函数约束条件(1) 线性规划模型一般形式价值系数决策变量技术系数右端常数(2) 线性规划模型标准形式简记形式(3) 线性规划模型其它形式矩阵形式价值向量决策向量 系数矩阵 右端向量价值向量决策向量 右端向量向量形式列向量对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式 :(4) 一般型向标准型的转化l目标函数l目标函数为极小化l约束条件l分两种情况：大于和小于l决策变量l可能存在小于零的情况1.极小化目标函数的问题：设目标函数为Min f = c1x1 + c2x2 + + cnxn 则可以令 z -f ， 该极小化问题与下面的极大化问题有相同的最优解，即Max z = -c1x1 - c2x2 - - cnxn 但 必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Min f - Max z2、 约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ + ain xn bi可以引进一个新的变量 s ， 使它等于约束右边与左边之差s = bi (ai1 x1 + ai2 x2 + + ain xn )显然， s 也具有非负约束，即 s0 ，这时新的约束条件成为ai1 x1+ai2 x2+ + ain xn+s = bi变量 s 称为 松弛变量l Max Z=40X1+ 50X2X1 +2X2 30 s.t 3X1 +2X2 60 引入 松弛变量 X3、 X4、 X5 2X2 24 X1 , X2 0l Max Z=40X1+ 50X2+0 X3 +0 X4+0 X5 X1 +2X2 + X3 30 s.t 3X1 +2X2 + X4 602X2 + X5 24 X1 , X5 0当约束条件为ai1 x1+ai2 x2+ +ain xn bi 时，类似地令s = (ai1 x1+ai2 x2+ + ain xn)- bi 显然， s 也具有非负约束，即 s0， 这时新的约束条件成为ai1 x1+ai2 x2+ + ain xn-s = bi变量 s称为 剩余变量Max Z=2X1+ 5X2+6X3 +8X44X1+6X2+ X3 +2X4 12 s.t X1+ X2+7X3+5X4 14 2X2+ X3+3X4 8 X1 , , X4 0引入 剩余变量 ： X5、 X6、 X7Max Z=2X1+ 5X2+6X3 +8X4 4X1+6X2+ X3 +2X4 - X5 12 s.t X1+ X2+7X3+5X4 - X6 142X2+ X3+3X4 - X7 8 X1 , , X7 03. 决策变量如果某个变量的约束条件为或者可令 或者代入原问题如果某个变量为自由变量，则可令且X1+X2 5s.t -6 X1 10X20令 X1 = X1 +6 -6+6 X1+6 10+60 X1 16X1 +X2 11s.t X1 16X1 , X2 03X1+2X2 8s.t X1 -4X2 14X20, X1 无限制令 X1= X1- X1 3 X1 -3 X1 “ +2X2 8s.t X1 - X1 “ - 4X2 14X1 , X1“ ,X2 0例：将线性规划模型 Min Z = -X1+2X2 -3X3X1+X2 +X3 7s.t X1 -X2 +X3 2X1， X20， X3无限制化为标准型解： 令 X3 =X4 - X5 加松弛变量 X6 加剩余变量 X7 令 Z= -ZMax Z= X1 -2X2 +3X4 -3X5 X1 +X2 +X4 -X5 +X6=7X1 -X2 +X4 -X5 -X7 =2X1 , X2 , X4 , , X7 0s.t3.2 线性规划问题的解(1) 解的基本概念定义 在线性规划问题中，约束方程组 (2)的系数矩阵 A(假定 )的任意一个 阶的非奇异 (可逆 )的子方阵 B(即 )，称为线性规划问题的一个 基阵 或 基 。基阵 非基阵基向量非基向量基变量 非基变量令则定义 在约束方程组 (2) 中，对于一个选定的基 B， 令所有的非基变量为零得到的解，称为相应于基 B的基本解。定义 在基本解中，若该基本解满足非负约束，即 ，则称此基本解为 基本可行解 ，简称 基可行解 ；对应的基 B称为 可行基 。定义 在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为 非退化解 ，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题 ；若 基本可行解中，有基变量为零，则称为 退化解 ，该问题称为 退化的线性规划问题 。基本解中最多有 m个非零分量。基本解的数目不超过 个。非可行解非可行解解的集合：解的集合：可行解可行解 基本解基本解最优解最优解基本可行解基本可行解解空间例 现有线性规划问题试求其基本解、基本可行解并判断是否为退化解。解 : (1)首先将原问题转化为标准型引入松弛变量 x3和 x4(2) 求基本解由上式得可能的基阵由于所有 |B| 0,所以有 6个基阵和6个基本解。对于基阵 令则对于基阵 令则为 基本可行解， B13为可行基为 基本可行解， B12为可行基对于基阵 令则对于基阵 令则对于基阵 令则对于基阵 令则为