运筹学复习大纲

1、复习大纲复习大纲2 ) 问题的形式特征问题的形式特征 上述两问题的经济内涵虽然不同，但具有如上述两问题的经济内涵虽然不同，但具有如下共同形式特征：下共同形式特征：n决策变量决策变量 (Decision Variables) 用一组可控变用一组可控变量表示待定的方案；量表示待定的方案；n约束条件约束条件 (Constraints) 依据客观条件而列出依据客观条件而列出的、必须严格满足的一组线性等式或不等式；的、必须严格满足的一组线性等式或不等式；n目标函数目标函数 (Objective Function) 按选择的指标按选择的指标及要求所拟定的，需要加以优化的线性函数。及要求所拟定的，需要加以优

2、化的线性函数。Q1Q2(1/2, 3/2)Q3-x1+x2=1z=0 x1+x2=2 图解问题图解问题max z=x1+3x2 s.t. - x1+x2 1 x1+x2 2 x1 0 x2 0z=3=x1+3x2Ox2x11212-1-13z=2z=51图解法原理图解法原理 (图图1.1)Q1Q2(1/2, 3/2)Q3-x1+x2=1z=0 x1+x2=2 图解问题图解问题max z=x1+3x2 s.t. - x1+x2 1 x1+x2 2 x1 0 x2 0z=3=x1+3x2Ox2x11212-1-13z=2z=51图解法原理图解法原理 (图图1.1)2. 问题的分析问题的分析 线性规

3、划问题的求解结果会出现多种线性规划问题的求解结果会出现多种情况，借助图解法可以考察线性规划问题情况，借助图解法可以考察线性规划问题解的状况。解的状况。n 唯一解唯一解n 多重解多重解n 无界解无界解n 无可行解无可行解1. 线性规划问题的标准型线性规划问题的标准型 线性规划问题的标准形式定义为线性规划问题的标准形式定义为max z=c1 x1 + c2 x2+cj xj+cn xn (1.1)s.t. a11x1+a12x2+a1 jxj+a1nxn = b1 a21x1+a22x2+a2 jxj+a2nxn = b2 (1.2) am1x1+am2x2+amjxj+amnxn=bm x1 ,

4、 x2 , , xj , , xn0 (1.3)其中：其中：aij，bi，cj都是常数，都是常数，xj 是未知变量是未知变量,并并有有 bi0,（i =1,2,m；j =1,2,n）, nm0。数学模型组成要素的称谓数学模型组成要素的称谓 函数函数式式(1.1) 目标函数目标函数(Objective function) 线性方程组线性方程组(1.2) 约束约束方程方程 约束条件约束条件 不等式不等式(1.3) 非负约束非负约束 (constraints) 变量变量xj 决策变量决策变量(Decision variables) 实数实数 : aij 组成系数组成系数(工艺系数工艺系数) bi 右

5、端常数右端常数(限定系数）限定系数） cj 目标函数系数目标函数系数(价值系数价值系数) 参数参数 : m 阶数阶数 n 维数维数数学模型表达符号的设置数学模型表达符号的设置C = (c1 , c2 , , cn ) 价值向量价值向量 b = (b1 , b2 , , bm )T 资源（限定）向量资源（限定）向量 Pj = (a1j , a2j , amj )T 系数（列）向量系数（列）向量 A = (P1, P2 , , Pn ) (mn)系数矩阵系数矩阵 X = (x1 , x2 , , xn )T 决策（变量）向量决策（变量）向量0 = (0 , 0 , , 0 )T n 维零向量维零向

6、量1）线性规划问题标准化的方法）线性规划问题标准化的方法n 目标函数的等价变换目标函数的等价变换n 约束条件的平衡转换约束条件的平衡转换n 决策变量的非负变换决策变量的非负变换(1) 目标函数的等价变换目标函数的等价变换目标函数为极小化目标函数为极小化目标函数含有常数项目标函数含有常数项 目标函数为极小化目标函数为极小化 极小化问题的目标函数为极小化问题的目标函数为 min z = c1x1+c2x2+cnxn依据图依据图1.11 所示所示 的对称原理，令：的对称原理，令： z = - z , cj = - cj ( j =1,2,n )将目标函数变换为将目标函数变换为 max z = - c

7、1x1 -c2x2 -cnxn即即 max z= c1x1+c2x2+cnxn目标函数含有常数项目标函数含有常数项 含有常数项的目标函数可以表示为：含有常数项的目标函数可以表示为： max z = c0+c1x1+c2x2+cnxn 将参数项将参数项c0移到等号的左边，令移到等号的左边，令z= z - c0 ,即即z = z+ c0 ,则可得到原目标函数的等价形式则可得到原目标函数的等价形式 max z= c1x1+c2x2+cnxn 显然，显然，z和和z的取值仅相差一个常数项的取值仅相差一个常数项，并且两者并且两者的可行域相同，其原理如图的可行域相同，其原理如图1.12 所示。所示。(2)

8、约束条件的平衡转换约束条件的平衡转换n左向不等式约束的平衡转换左向不等式约束的平衡转换n右向不等式约束的平衡转换右向不等式约束的平衡转换左向不等式约束的平衡转换左向不等式约束的平衡转换 左向不等式约束条件为小于或等于形式，简左向不等式约束条件为小于或等于形式，简称为左向不等式约束，如称为左向不等式约束，如ai1x1+ai2x2+aijxj+ainxnbi 引于非负变量引于非负变量 xn+i 0，左向不等式左端加上这个，左向不等式左端加上这个新变量即可化上式为等式新变量即可化上式为等式 ai1x1+ai2x2+aijxj+ainxn+ xn+i = bi 式中新增的非负变量式中新增的非负变量 x

9、n+i 称为称为松弛松弛(Slack)变量变量。约束平衡转换的示例约束平衡转换的示例max z= 2x1+3x2+0 x3+0 x4 +0 x5s. t. x1+ 2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1, x2 , x3 , x4 , x5 0 将生产计划问题数学模型的约束化为将生产计划问题数学模型的约束化为平衡条件平衡条件max z= 2x1+3xs. t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0右向不等式约束的平衡转换右向不等式约束的平衡转换 右向不等式约束条件为大于或等于形右向不等式约束条件为大于或等于形式，如式，如 a1

10、1x1+a12x2+a1nxnb1 同理，它可以化为下述等式约束条件同理，它可以化为下述等式约束条件 a11x1+a12x2+a1nxn - xn+1 = b1 式中新增的非负变量式中新增的非负变量 xn+1 称为称为剩余变量剩余变量(Surplus variable)，也可称为松弛变量。，也可称为松弛变量。饮食问题的标准化饮食问题的标准化将饮食问题的数学模型化为标准型将饮食问题的数学模型化为标准型min z=c1 x1 + c2 x2+cn xns.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1 , x2 ,

11、 , xn0(3) 决策变量决策变量 决策变量为非正变量决策变量为非正变量 决策变量为自由变量决策变量为自由变量 决策变量为有界变量决策变量为有界变量非正决策变量非正决策变量 非正限制的决策变量非正限制的决策变量xj可表示为可表示为 xj 0它可用非负变量它可用非负变量xj替换，即令替换，即令 xj = - xj , xj0代入原问题。代入原问题。自由变量自由变量 决策变量决策变量xj的取值无约束，则称为自由变量。的取值无约束，则称为自由变量。自由变量可用两个非负的变量之差来代替，即设自由变量可用两个非负的变量之差来代替，即设 xj0, xj0 令令 xj= xj- xj, 代入原问题。这样即

12、可对变量实施非负约束，又代入原问题。这样即可对变量实施非负约束，又保持了问题线性关系。保持了问题线性关系。自由变量（续）自由变量（续） 自由变量取值的正与负由自由变量取值的正与负由xj和和xj取值的取值的大小决定，即大小决定，即 , 0 , 0 , 0jjjjjjjxxxxxxx上界变量上界变量 有上界限制的决策变量有上界限制的决策变量xj可表示为可表示为 0 xjdj 对于这种情况可将变量的上界限制对于这种情况可将变量的上界限制 xjdj 当作一个约束条件，然后按左向不等式约束处理，当作一个约束条件，然后按左向不等式约束处理，将其转化为等式约束条件。即令将其转化为等式约束条件。即令 xj +

13、 xn+j=dj, xn+j0上界变量（续）上界变量（续） 示例示例 例例1.1 的数学模型实质上是一例变量有的数学模型实质上是一例变量有上界的问题。由此，可得到它的另外一种标准形上界的问题。由此，可得到它的另外一种标准形式。式。max z= 2x1+3xs. t. x1+ 2x28 4x1 16 4x2 12 x1, x2 0max z=2x1+ 3x2s. t. x1+ 2x28 0 x14 0 x23max z=2x1+ 3x2s. t. x1+2x2+x3 =8 x1 +x4 =4 x2 +x5 =3 x1, x2, , x50下界变量下界变量 若变量若变量 xj ej ( 0 ) 称

14、称 xj 有下界，将上述关系式移项可得有下界，将上述关系式移项可得 xj - ej0 令令 xj= xj - ej 0 将其代入原问题。将其代入原问题。 要注意的是，用变量要注意的是，用变量 xj 替代替代 xj 后，目标函后，目标函数将出现常数项。数将出现常数项。2) 线性规划问题标准化的步骤线性规划问题标准化的步骤 将线性规划问题转化为标准形式的一将线性规划问题转化为标准形式的一般步骤依次为：般步骤依次为：F 先决策变量先决策变量F 再约束条件再约束条件F 最后目标函数最后目标函数线性规划问题标准化示例线性规划问题标准化示例 将下述问题转化为标准形式将下述问题转化为标准形式 min z =

15、 2x1+x2-3x3+x4-2x5 s. t. x1+x2+x3+x4+x5 = 9 x1- x2+x3- x4+x5 3 x10, x22, 0 x33, x401.2 线性规划问题的解线性规划问题的解 解的概念解的概念 基基(本本)解解 基本定理基本定理1.2.1 解的概念解的概念 线性规划问题的标准型可以表示为：线性规划问题的标准型可以表示为：max z=c1x1+c2x2+cmxm+cm+1xm+cnxn (1.4 ) s. t. P1x1+P2x2+Pmxm+Pm+1xm+1+Pnxn=b (1.5) x1, x2, xm, xm+1, xn0 (1.6) 设设A= ( P1, P

16、2 , Pm, Pm+1,Pn ) 是约束方程（是约束方程（1.5）的的mn系数矩阵，其秩为系数矩阵，其秩为m。1. 可行解可行解u解解( (Solution) ) 若有数组若有数组X0= (x10,x20,xn0)T 满足满足约束条件约束条件（1.5），则），则X0称为该方程组的解。称为该方程组的解。u可行解可行解( (Feasible solution) )满足约束条件满足约束条件（1.6）的解的解X0称为线性规划问题的可行解；所有可行解称为线性规划问题的可行解；所有可行解构成的集合称为线性规划问题的构成的集合称为线性规划问题的可行域可行域( (Feasible region） D= |

17、AX b, X 0 2. 最优解最优解u最优解最优解( (Optimal solution) ) 满足（满足（1.4）的可行）的可行解解X，即使目标函数达到最大值的解，叫作线，即使目标函数达到最大值的解，叫作线性规划问题最优解。对于任何可行解性规划问题最优解。对于任何可行解X0 0 D D, ,都都有有 X0 0 X 0, 1 j n ，选取第选取第 k 列列的非基本变量的非基本变量 xk 为换入变量。为换入变量。2.2 单纯形法的运算格式单纯形法的运算格式 为了便于理解计算关系，设计一种计算表格，为了便于理解计算关系，设计一种计算表格，称为称为单纯形表单纯形表(tableau)，其功能与增广

18、矩阵相似。，其功能与增广矩阵相似。表表2.7 单纯形表单纯形表 ( 表样表样 )cj -c0 c1 c2 cl cm cm+1 ck cn cB xB b x1 x2 xl xm xm+1 xk xn i c1 x1 b10 1 0 0 0 b1 m+1 b1k b1n 1 c2 x2 b20 0 1 0 0 b2 m+1 b2k b2n 2 cl xl bl0 0 0 1 0 bl m+1 blk bln l cm xm bm0 0 0 0 1 bm m+1 bmk bmn m -1 z -z0 0 0 0 0 m+1 k n j 可行基与最优基的判別可行基与最优基的判別B= (P1,P2,

19、 Pm ) N= (Pm+1, Pm+2, Pn )XB= (x1,x2, xm )T XN= (xm+1, xm+2, xn )T 则则 A=(B, N ) , X= (XB , XN )T C=(CB, CN)T = ( B , N)T 对于可行基对于可行基 XB 0 , XN = 对于最优基对于最优基 B = 0 , N02.3.1 最优解判別定理最优解判別定理 定理定理 2.1 ( 最优性判据最优性判据 ) 若若X(*)为对应于为对应于基基 B 的可行解的可行解, ,且且对于所有的对于所有的 j =1,2, ,n 有有 j 0, ,即即有有 B= 0和和 N0， 则则X(*)为最优解为

20、最优解。 满足满足( (1.4) )的可行解的可行解X(*)，即使目标函数达到最大值的解，叫作线性规划问题最即使目标函数达到最大值的解，叫作线性规划问题最优解。对于任何可行解优解。对于任何可行解X(0) D, ,都有都有 X(0) X(*) + 最优解最优解X的目标函数值的目标函数值z(*)=X(*)叫作最优值叫作最优值。2.3.2 唯一性判据唯一性判据 定理定理 2.2 ( 唯一性判据唯一性判据 ) 设设 =( B N) 0为对为对应于基最优解应于基最优解X(*) 的检验数的检验数： (1)若有若有 N 0 ，则线性规划问题具有唯一解，则线性规划问题具有唯一解X(*)； (2)若若 N 0

21、,且且列向量列向量 P =(b1k , b2k , , bmk)T 0, 则线则线性规划问题无最优解性规划问题无最优解(也称无解也称无解)。单纯形法的计算步骤单纯形法的计算步骤单纯形算法的步骤单纯形算法的步骤 将线性规划问题化为标准形式，执行下将线性规划问题化为标准形式，执行下列步骤：列步骤： 步步 1 找出初始可行基找出初始可行基 B0，确定初始基可，确定初始基可行解行解 X(0)，建立初始单纯形表，建立初始单纯形表 T( B0 ) = (bij)，转下一步；转下一步； 步步 2 检查检验数，若检查检验数，若j0 ( j=1,2,n)，则当前基可行解是最优解，计算结束。否则，则当前基可行解是

22、最优解，计算结束。否则，转下一步；转下一步；单纯形算法的步骤单纯形算法的步骤 (续续 1 ) 步步 3 按按 k=maxj | j0, 1 j n ， 或按或按k = min j |j 0 , 1 j n 选取第选取第 k 列的非基本变量列的非基本变量 xk 为换入变量。若为换入变量。若bik0 ( i=1,2, m )，则此问题无最优解，停止计，则此问题无最优解，停止计算。否则，转下一步；算。否则，转下一步； 单纯形算法的步骤单纯形算法的步骤(续续 2 ) 步步 4 按按 = min bi0/bik | bik 0 , 1 i m 或按或按 l = min Ji | (bi0/bik)= ,

23、 1 i m 确定第确定第 l 行的基本变量行的基本变量 xJi 为换入变量，转下一为换入变量，转下一步；步； 单纯形算法的步骤单纯形算法的步骤(续续 3 ) 步步5 对当前单纯形表对当前单纯形表 T( B ) = ( bij ) 实行实行( l , k )旋转变换旋转变换 j = j -(k / blk) blj ( j = 0,1, , n ) 得到新的单纯形表得到新的单纯形表 T( B ) = (bij ) ，返回步，返回步 2。 bij / blk ( i=l , j=0,1, , n ) bij = bij -(bik / blk) blj (1ilm ,0jn)单纯形法的计算步骤单

24、纯形法的计算步骤u例例1.8 用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解 0,30340243max21212121xxxxxxxxZ解：解：1）将问题化为标准型，加入松驰变量将问题化为标准型，加入松驰变量x3、x4则标准型为则标准型为: 0,30340243max432142132121xxxxxxxxxxxxZ单纯形法的计算步骤单纯形法的计算步骤u2）求出线性规划的初始基可行解，列出初始单）求出线性规划的初始基可行解，列出初始单纯形表。纯形表。cj3400icB基基bx1x2x3x40 x34021100 x430130134003)1020(3)(2141131 a

25、cacc1 检验数检验数j 单纯形法的计算步骤单纯形法的计算步骤u3）进行最优性检验）进行最优性检验如果表中所有检验数如果表中所有检验数 ，则表中的基可行解就是问题，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。的最优解，计算停止。否则继续下一步。0ju4）从一个基可行解转换到另一个目标值更大的基可行解，）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表列出新的单纯形表确定换入基的变量。选择确定换入基的变量。选择 ，对应的变量，对应的变量xj作为换入变作为换入变量，当有一个以上检验数大于量，当有一个以上检验数大于0时，一般选择最大的一个时，一般选择最大的一个检验数

26、，即：检验数，即： ，其对应的，其对应的xk作为换入作为换入变量。变量。确定换出变量。根据下式计算并选择确定换出变量。根据下式计算并选择 ，选最小的选最小的对应基对应基变量作为换出变量。变量作为换出变量。0 j0|max jjk 0minikikiLaab单纯形法的计算步骤单纯形法的计算步骤用换入变量用换入变量xk替换基变量中的换出变量，得到一个新的替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。可以画出一个新的单纯形表。5）重复）重复3）、）、4）步直到计算）步直到计算结束结束为止。

27、为止。单纯形法的计算步骤单纯形法的计算步骤cj3400icB基变量基变量bx1x2x3x40 x34021100 x430130134000 x34x23x14x2j j j 换入列换入列bi /ai2，ai204010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/5400113 单纯形法的运用与改进单纯形法的运用与改进u 初始可行基与人工变量法初始可行基与人工变量法u 求上界变量的单纯形法求上界变量的单纯形法u 单纯形法的讨论单纯形法的讨论u 单纯形法的矩阵描述单纯形法的矩阵描述u 改进

28、单纯形法改进单纯形法单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法u人工变量法：人工变量法：u前面讨论了在标准型中系数矩阵有单位矩阵，前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。很容易确定一组基可行解。在实际问题中有些模在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。量，得到一组基变量。这种人为加的变量称为这种人为加的变量称为人人工变量工变量，构成的可行基称为，构成的可行基称为人工基人工基，用大用大MM法

29、或法或两阶段法求解两阶段法求解，这种用人工变量作桥梁的求解方，这种用人工变量作桥梁的求解方法称为人工变量法。法称为人工变量法。3.1.1 辅助问题及人工变量辅助问题及人工变量( A ) max z=c1 x1 + c2 x2+cn xn s.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1 , x2 , , xn0 ( B )max =-xn+1 -xn+2 - -xn+ms.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 am1x1+amnxn +xn+m=bm

30、 x1 xn 0 , xn+1 xn+m 0 X0= (x10,x20,xn0)T Y 0=(x10,x20,xn0,0,0)T 0=0X =(x1, x2,xn )T =0 Y =(x1,x2, xn,xn+1,xn+m )T辅助问题的性质辅助问题的性质 问题问题(B)是问题是问题(A)的的辅助问题，辅助问题，( B )中的单位中的单位矩阵称为人工基，它对应矩阵称为人工基，它对应的的m个变量叫做人工变量个变量叫做人工变量(artificial variables)。 辅助问题辅助问题 ( B )有两个有两个特点：特点： ( i )约束方程为典式，约束方程为典式，表明有可行解；表明有可行解；

31、( ii)目标函数有上界，目标函数有上界，一定有最优解。一定有最优解。( B )max =-xn+1 -xn+2 - -xn+ms.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 am1x1+amnxn +xn+m=bm x1 xn 0 , xn+1 xn+m 0 B 0 = (Pm+1 ,Pm+2 , ,Pn) Y (0) =( 0,0, b1, b2 , bm)T 原理与应用原理与应用 定理定理3.1 问题问题 ( A ) 有可行解的充要条有可行解的充要条件是：问题件是：问题 ( B ) 的目标函数最优值等于零。的目标函数最优值等于零。 推论推论

32、3.1 问题问题 ( B ) 的最优基的基变的最优基的基变量组中不含人工变量，则这个最优基和相量组中不含人工变量，则这个最优基和相应的基最优解分别是问题应的基最优解分别是问题 ( A )的可行基和的可行基和基可行解。基可行解。 原理与应用原理与应用 ( 续续 ) 结论结论3.1 问题问题 ( B ) 的最优基的第的最优基的第l个基变量个基变量为人工变量，并且目标函数最优值等于零，而最为人工变量，并且目标函数最优值等于零，而最优单纯形表中非人工变量在第优单纯形表中非人工变量在第 l 行的系数全为零，行的系数全为零，则表示问题则表示问题 ( A) 的第的第 l 个约束方程是多余的，应个约束方程是多

33、余的，应予删除。予删除。 标准形式线性规划问题的标准形式线性规划问题的 m个约束方程被假个约束方程被假设为是相互独立的，上述结论中的情形在理论上设为是相互独立的，上述结论中的情形在理论上不会出现，但在实际中经常碰到。不会出现，但在实际中经常碰到。3.1.2 两阶段法两阶段法 依据推论依据推论3.1 ，可将问题，可将问题(A)的求解分为两的求解分为两阶段：阶段： 阶段阶段 1 从人工基开始，从人工基开始，用单纯形法求解问用单纯形法求解问题题(B) ，或是得到问题，或是得到问题(A)的一个可行基和相应的的一个可行基和相应的基可行解，或是证实问题基可行解，或是证实问题(A)沒有可行解；沒有可行解；

34、阶段阶段 2 从阶段从阶段1得到的初始可行基出发得到的初始可行基出发，用，用单纯形法单纯形法寻找问题寻找问题 (A) 的的最优解，或是查明问题最优解，或是查明问题 (A) 沒有最优解。沒有最优解。两阶段法算例两阶段法算例例例3.1 用两阶段法求解问题用两阶段法求解问题max z=3 x1 - x2- x3 s.t. x1-2x2+ x3 +x4 =11 -4x1+x2 +2 x3 -x5 =3 -2x1 +x3 =1 x1 , x2 , , x50得得: : max z=3 x1 - x2- x3 s.t. 3x1 +x4 -2 x5 =12 x2 -x5 =1 -2x1 +x3 =1 x1

35、, x2 , , x50解：解： max = - x6 - x7 s.t. x1-2x2+ x3 +x4 =11 -4x1+x2 +2x3 -x5+ x6 =3 -2x1 +x3 + x7=1 x1 , x2 , , x70表表3.1 求可行解求可行解 ( 阶段阶段 I )cj 0 0 0 0 0 -1 -1 CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 x4 11 1 -2 1 1 0 0 0 11 -1 x6 3 -4 1 2 0 -1 1 0 3/2 -1 x7 1 -2 0 1 0 0 0 1 1 -z 4 -6 1 3 0 -1 0 0 j 0 x4 10 3 -

36、2 0 1 0 0 -1 - -1 x6 1 0 1 0 0 -1 1 -2 1 0 x3 1 -2 0 1 0 0 0 1 - -z 1 0 1 0 0 -1 0 -3 j 0 x4 12 3 0 0 1 -2 2 -5 0 x2 1 0 1 0 0 -1 1 -2 - 0 x3 1 -2 0 1 0 0 0 1 - -z 0 0 0 0 0 0 -1 -1 j 表表3.2 求最优解求最优解 ( 阶段阶段 II )cj3-1-100CBXBbx1x2x3x4x5i0 x4123001-24-1x210100-1-1x31-20100-z21000-1 j3x141001/3-2/3-1x21

37、0100-1-1x390012/3-4/3-z-2000-1/3-1/3 j3.1.3 大大 法法 大大 法是将原问题及其辅助问题合并，法是将原问题及其辅助问题合并，集线性规划问题可行解和最优解的求证于集线性规划问题可行解和最优解的求证于一役。一役。 大大 法也称法也称罚函数法罚函数法。大大 法的机理法的机理 形象地解释，变量在目标函数中的价值系数愈大，其形象地解释，变量在目标函数中的价值系数愈大，其对目标函数值的贡献愈大，则被录用为最优解的基变量的对目标函数值的贡献愈大，则被录用为最优解的基变量的可能性愈大。人工变量都是初始基变量，可能性愈大。人工变量都是初始基变量，为了尽可能将人为了尽可能

38、将人工变量从基变量组中换出工变量从基变量组中换出，通常，通常把人工变量在合并问题目把人工变量在合并问题目标函数中的系数赋一个绝对值标函数中的系数赋一个绝对值 M 充分大的负数充分大的负数 M ， M 称为惩罚因子称为惩罚因子。迭代过程中，其价值系数迭代过程中，其价值系数 M 将迫使次人将迫使次人工变量逐步换出基变量组，换出一个就删除一个工变量逐步换出基变量组，换出一个就删除一个。在这种。在这种机制下，如果人工变量仍留在最优基的基变量组中，则可机制下，如果人工变量仍留在最优基的基变量组中，则可断定原问题沒有可行解。断定原问题沒有可行解。大大 法算例法算例 例例3.1 max z=3 x1 - x

39、2- x3 s.t. x1-2x2+ x3 +x4 =11 -4x1+x2 +2 x3 -x5 =3 -2x1 +x3 =1 x1 , x2 , , x50 解：解： max z=3 x1 - x2- x3+0 x4+0 x5 -M x6 -M x7 s.t. x1-2x2+ x3 +x4 =11 -4x1+x2 +2x3 -x5 + x6 =3 -2x1 + x3 + x7 =1 x1 , x2 , , x70 辅助问题辅助问题max = - x6 - x7s.t. x1-2x2+ x3 +x4 =11 -4x1+x2+2x3 -x5+x6 =3 -2x1 +x3 +x7=1 x1 , x2

40、 , , x70表表3.3 大大 法法 的求解过程的求解过程cj 3 -1 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 x4 11 1 -2 1 1 0 0 0 11 -M x6 3 -4 1 2 0 -1 1 0 3/2 -M x7 1 -2 0 1 0 0 0 1 1 -z 3-6M -1+M -1+3M 0 -M 0 0 j 0 x4 10 3 -2 0 1 0 0 -1 - -M x6 1 0 1 0 0 -1 1 -2 1 -1 x3 1 -2 0 1 0 0 0 1 - -z 1 -1+M 0 0 -M 0 1-3M j 表表3.3

41、大大 法的求解过程法的求解过程( 续续 1 )表表3.3 大大 法的求解过程法的求解过程( 续续 2 )cj 3 -1 -1 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 i 0 x4 12 3 0 0 1 -2 4 -1 x2 1 0 1 0 0 -1 - -1 x3 1 -2 0 1 0 0 - -z 2 1 0 0 0 -1 j 3 x1 4 1 0 0 1/3 -2/3 -1 x2 1 0 1 0 0 -1 -1 x3 9 0 0 1 2/3 -4/3 -z -2 0 0 0 -1/3 -1/3 j 表表3.3 大大 法的求解过程法的求解过程cj3-1-

42、100-M-MCBXBbx1x2x3x4x5x6x7i0 x4111-21100011-Mx63-4120-1103/2-Mx71-20100011-z3-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x31-2010001-z1-1+M00-M01-3M表表3.3 大大 法的求解过程法的求解过程( 续续 1 )cj3-1-100-M-MCBXBbx1x2x3x4x5x6x7i0 x4103-20100-1-Mx610100-11-21-1x31-2010001-1-1+M00-M01-3M0 x4123001-22-54-1x210100-1

43、1-2-1x31-2010001-1000-11- M -1- M表表3.3 大大 法的求解过程法的求解过程( 续续 2 )cj3-1-100-M-MCBXBbx1x2x3x4x5x6x7i0 x4123001-22-54-1x210100-11-2-1x31-2010001-21000-11- M-1- M3x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-2000-1/3 -1/3 1/3-M 2/3-M单纯形表的矩阵形式单纯形表的矩阵形式 I B-1N B-1b T(B) = 0 CN - CB B-1N - CBB-1b

44、I B-1Pm+1 B-1Pk B-1Pn B-1b= 0 cm+1-CBB-1Pm+1 ck-CBB-1Pk cn-CB B-1Pn -CBB-1b 单纯形表中的数据单纯形表中的数据:基变量基变量 非基变量非基变量等式右边等式右边系数矩阵系数矩阵检验数检验数1 1 0BXB B111111111 NsNBBBXXRH SB NBB bCCB NCBCB b用矩阵法直接求指定可行解用矩阵法直接求指定可行解 (附：表附：表3.13)B=(P1, P5, P2) CB=(c1, c5, c2)=(2, 0, 3) cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 8

45、 1 2 1 0 0 4 0 x4 16 4 0 0 1 0 - 0 x5 12 0 4 0 0 1 3 -1 z 0 2 3 0 0 0 j 0 x3 2 1 0 1 0 -1/2 2 0 x4 16 4 0 0 1 0 4 3 x2 3 0 1 0 0 1/4 - -1 z -9 2 0 0 0 -3/4 j 2 x1 2 1 0 1 0 -1/2 - 0 x4 8 0 0 -4 1 2 4 3 x2 3 0 1 0 0 1/4 12 -1 z -13 0 0 -2 0 1/4 j 2 x1 4 1 0 0 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2

46、-1/8 0 -1 z -14 0 0 -3/2 -1/8 0 j = 0 - (3/2, 1/8, 0 )001= 0 - 0 = -05 = c5-CB B-1 P5= 0 - (3/2, 1/8, 0 )010= 0 - 1/8 = -1/84 = c4-CB B-1 P4= 3 - (3/2, 1/8, 0 )204= 3 - 3 = 02 = c2-CB B-1 P2= 2 - (3/2, 1/8, 0 )140= 2 - 2 = 01 = c1-CB B-1 P1 0 1/4 0 -2 1/2 11/2 -1/8 0B-1P5=0010 = 1 0 0 1/4 0 -2 1/2 1

47、1/2 -1/8 0B-1P4=0101/4 = 1/2 -1/8 0 1/4 0 -2 1/2 11/2 -1/8 0B-1P3=1000= -2 1/2 0 1/4 0 -2 1/2 11/2 -1/8 0B-1P2=2040= 0 1 0 1/4 0 -2 1/2 11/2 -1/8 0B-1P1=1401= 0 0 1 0 2 = 4 0 0 0 1 4 0 1/4 0B-1= -2 1/2 1 1/2 -1/8 0 j j = cj - CB B-1 PjCB B-1= ( 3/2, 1/8, 0 ) 0 1/4 0 -2 1/2 11/2 -1/8 0B-1b =816124= 4

48、 2= 0 - (3/2, 1/8, 0 )100= 0 - 3/2 = -3/23 = c3-CB B-1 P3= 0 - (3/2, 1/8, 0 )81612= 0 - 14 = -14-z* = c0-CB B-1 b改进单纯形法的出发点改进单纯形法的出发点 单纯形法求解线性规划问题时，单纯形表单纯形法求解线性规划问题时，单纯形表中的所有数据每次迭代都要计算和更新一次，中的所有数据每次迭代都要计算和更新一次，而直接与迭代有关的数据只是其中一部分。若而直接与迭代有关的数据只是其中一部分。若用计算机求解，无关数据的计算就会占用很多用计算机求解，无关数据的计算就会占用很多的存储单元，特别是求

49、解规模很大的问题时，的存储单元，特别是求解规模很大的问题时，计算效率就低了。另一方面，单纯形法的迭代计算效率就低了。另一方面，单纯形法的迭代过程中，所有数据可由当前基矩阵的逆与原始过程中，所有数据可由当前基矩阵的逆与原始数据直接求出。因此，只要有了逆矩阵迭代方数据直接求出。因此，只要有了逆矩阵迭代方法，就可以做到用什么算什么。法，就可以做到用什么算什么。基变换的要点基变换的要点B = (P1, P2 , Pl-1, Pl , Pl-1 , Pm)j j = cj - CB B-1 Pj N N = CN - CB B-1N k=maxj | j0, 1 j n ，k = min j |j 0

50、, 1 j n B-1Pk=( b1k , b2k , , bl-1 k , bl k ,bl+1 k , , bmk )TB-1 b =( b10 , b20 , , bl-1 0 , bl 0 ,bl+1 0 , , bm0 )T =min bi0/bik | bik 0 , 1 i m = bl 0/bl k l = min Ji | (bi0/bik)= , 1 i m B= (P1, P2 , Pl-1, Pk , Pl-1 , Pm)基变换的要点基变换的要点B = (P1, P2 , Pl-1, Pl , Pl-1 , Pm)j j = cj - CB B-1 Pj N N = C

51、N - CB B-1N k=maxj | j0, 1 j n ，k = min j |j 0 , 1 j n B-1Pk=( b1k , b2k , , bl-1 k , bl k ,bl+1 k , , bmk )TB-1 b =( b10 , b20 , , bl-1 0 , bl 0 ,bl+1 0 , , bm0 )T =min bi0/bik | bik 0 , 1 i m = bl 0/bl k l = min Ji | (bi0/bik)= , 1 i m B= (P1, P2 , Pl-1, Pk , Pl-1 , Pm)改进单纯形法算例改进单纯形法算例 用改进单纯形法求解用改

52、进单纯形法求解 max z =2x1+3x2 s.t. x1+ 2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1, x2 , , x50改进单纯形法算例改进单纯形法算例 (循环循环 0 ) B0 = ( P3 , P4 , P5 ) N0 = ( P1 , P2 ) CB0= ( c3 , c4 , c5 ) CN 0 = ( c1 , c2 )步步 1 计算单纯形乘子计算单纯形乘子Y0和检验数和检验数N0 0 Y0= CB0 B0-1=( 0, 0, 0 )N0 0=CN 0 -CB0 B0-1N0=( 2 , 3 )=(1 ,2)由此确定由此确定 k=2，即

53、，即P2为进基列；为进基列；步步 2 计算计算 B0-1P2和和 B0-1 b，求出，求出= 3，确定确定 l=3，即，即B0 的第的第3列列P5为出基列；为出基列；步步 3 得到新基得到新基B1=( P3 , P4 , P2 )，计算，计算 B1-1=E1 B0-1 ，或对，或对B0-1实施实施(3,2)旋转旋转变换，即变换，即 ( B0-1 B0-1P2 ) (B1-1 e3 )，返回步返回步 1 。P1P2P3P4P5b121008A40010160400112cj23000 xBB-1B-1b B-1Px3100824x4010160-x50011243x310-1/220 x4010

54、160 x2001/431/Y0= CB0 B0-1= ( 0 , 0 , 0 ) 1 0 0 0 1 0 0 0 1= ( 0 , 0 , 0 )/N0 0=CN 0-CB0 B0-1N0=( 2, 3 ) - ( 0 , 0 , 0 ) 1 2 4 0 0 4=(2,3)-(0 ,0)=(2,3)=( 1, 2) / 1 0 0 0 1 0 0 0 1B0-1b =816128 = 16 12/ 1 0 0 0 1 0 0 0 1B0-1P2=2042 = 0 4改进单纯形法算例改进单纯形法算例 (循环循环 1 ) B1 = ( P3 , P4 , P2 ) N1 = ( P1 , P5

55、) CB1= ( c3 , c4 , c2 ) CN 1 = ( c1 , c5 )步步 1 计算单纯形乘子计算单纯形乘子Y1和检验数和检验数N1 1 Y1= CB1 B1-1=( 0, 0, 3/4 )N1 1=CN 1-CB1 B1-1N1=(2,-3/4)=(1 ,5)由此确定由此确定 k=1，即，即P1为进基列；为进基列；步步 2 计算计算 B1-1P1和和 B1-1 b，求出，求出=2，确定确定 l=1，即，即B0 的第的第1列列P3为出基列；为出基列；步步 3 得到新基得到新基B1=( P1 , P4 , P2 )，计算，计算 B2-1=E2 B1-1 ，或对，或对B1-1实施实施

56、(1,1)旋转旋转变换，即变换，即 ( B1-1 B1-1P1 ) (B2-1 e1 )，返回步返回步 1 。P1P2P3P4P5b121008A40010160400112cj23000 xBB-1B-1b B-1Px3100824x4010160-x50011243x310-1/2212x40101644x2001/430-x110-1/221x4-41280 x2001/430/Y1= CB1 B1-1= ( 0 , 0 , 3 )1 0 -1/20 1 00 0 1/4= ( 0 , 0 , 3/4 )/N1 1=CN 1-CB1 B1-1N1=( 2, 0 )- ( 0 , 0 ,

57、3/4 ) 1 0 4 0 0 1=(2 , 0)-(0 , 3/4)=( 2 , -3/4)/ 1 0 -1/2 0 1 0 0 0 1/4B1-1P1=1401= 4 0/ 1 0 -1/2 0 1 0 0 0 1/4B1-1b =816122= 16 3改进单纯形法算例改进单纯形法算例 (循环循环 2 ) B2 = ( P1 , P4 , P2 ) N2 = ( P3 , P5 ) CB2= ( c1 , c4 , c2 ) CN 2 = ( c3 , c5 )步步 1 计算单纯形乘子计算单纯形乘子Y2和检验数和检验数N2 2 Y2= CB2 B2-1=( 2, 0, -1/4 )N2

58、2=CN 2-CB2 B2-1N2=(-2,1/4)=(3 ,5)由此确定由此确定 k=5，即，即P5为进基列；为进基列；步步 2 计算计算 B2-1P5和和 B1-1 b，求出，求出=4，确定确定 l=2，即，即B2 的第的第2列列P4为出基列；为出基列；步步 3 得到新基得到新基B3=( P1 , P5 , P2 )，计算，计算 B3-1=E3 B2-1 ，或对，或对B2-1实施实施(2,5)旋转旋转变换，即变换，即 ( B2-1 B2-1P5) (B3-1 e2 )，返回步返回步 1 。P1P2P3P4P5b121008A40010160400112cj23000 xBB-1B-1b B

59、-1Px3100824x4010160-x50011243x310-1/2212x40101644x2001/430-x110-1/22-1/2-x4-412824x2001/431/412x101/4040 x5-21/2141x21/2-1/8020/Y2= CB2 B2-1= ( 2 , 0 , 3 ) 1 0 -1/2-4 1 0 0 0 1/4= ( 2 , 0 , -1/4 )/N2 2=CN 2-CB2 B2-1N2=( 0, 0 )- (2 , 0 , -1/4 ) 1 0 0 0 0 1=(0 , 0)-(2 ,-1/4)=( -2 , 1/4 )/ 1 0 -1/2 -4

60、1 2 0 0 1/4B2-1P5 =0011/2= 2 1/4改进单纯形法算例改进单纯形法算例 (循环循环 3 ) B3 = ( P1 , P5 , P2 ) N3 = ( P3 , P4 ) CB3= ( c1 , c5 , c2 ) CN 3 = ( c3 , c4 )步步 1 计算单纯形乘子计算单纯形乘子Y3和检验数和检验数N3 3 Y3= CB3 B3-1=( 3/2, 1/8, 0 )N3 3=CN 3-CB3 B3-1N3=(-3/2,-1/8) =(3 ,4 )由此确定当前基由此确定当前基 B3 = ( P1 , P5 , P2 ) 是是最优基，相应的最优解为最优基，相应的最优