深圳大学管理学院：《运筹学》课程教学资源（PPT课件讲稿）规划论（单纯型法）运筹学1类 高阶运筹学 线性规划（单纯形法的矩阵描述及改进单纯形法介绍）

第一节单形法的矩哗猶述 改进单红形法介绍 单纯形法的矩阵描述 继续 改进单纯形法介绍

第一节 单纯形法的矩阵描述 及改进单纯形法介绍 ◼ 单纯形法的矩阵描述 ◼ 改进单纯形法介绍 返回 继续

单纯法的距哗逑 设线性规划间题 max 2=CX .t AX=b X≥0 上不妨设基为 B=(PP2…P) 回 则A=(P1P2…B)=(B:M X=(XB X C=(CR CN) 基变量 非基变量 F!园

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 单纯形法的矩阵描述 不妨设基为 ( ) B P1 P2  Pm = 基变量 非基变量 0 . max  = = X s t AX b z CX 设线性规划问题 ( ) ( ) ( ) ( ) 1 2 B N B N n X X X C C C A P P P B N = = 则 =  = 

约束方程组 AX=b→(BN B N = BX B +NX=b 上上页 →XB=B(b-NX)=b-MXN 其中b=B-1b.N=B-1N 回令x=0得当前的基解为:当前基解 X b=Bb B

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 B N N B N N B X B b NX b NX BX NX b X X AX b B N ~ ~ ( ) ( ) 1  = − = − = + =         =  − 单纯形法的矩阵描述 其中 b B b N B N 1 ~ 1 , ~ − − = = 令 X N = 0 得当前的基解为： XB b B b ~ −1 = = 当前基解 约束方程组

恐线性 目标函数 Z=(CC XB=CRXB+CN NX N =CRB b+(CN-CRBN)XN 上上页 CRO+(CN-CBN)XN 令X=0得当前的目标函数值为: 回 oCB=CB b 当前目标值 !

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 B N B N B N B N B B N N N B B N C b C C N X C B b C C B N X C X C X X X z C C ) ~ ( ~ ( ) ( ) 1 1 = + − = + − = +         = − − 当前目标值 目标函数 z C b C B b B B 1 0 ~ − = = 令 X N = 0 得当前的目标函数值为： 单纯形法的矩阵描述

检验数 6÷人 C-CN N B m+1 Cn)-(C1…Cn)n1…) 上上页 on+=+I-CBP 当前检验数 回 二 C-C D n B 其中P=BP 7当前对应的系数列

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划    N N B m n m m n n m B m n n B n C C N C C C C P P C C P C C P = − = −  = − = − + + + + + ~ ( ) ( )( ~ ~ ) ~ ~ 1 1 1 1 1 1     当前检验数 单纯形法的矩阵描述 检验数 其中 Pj B Pj ~ −1 = 当前x j 对应的系数列

阵单细形法计算的述 线性规划问题 max z=CX AX<b S.乙 X≥0 上上页 化为标准型,引入松弛变量X max z=CX+0X 回 AX+IX=b st X≥0,X≥0 F!园

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 矩阵单纯形法计算的描述 线性规划问题  0 . . max   = X AX b s t z CX 化为标准型，引入松弛变量 Xs      + = = + 0, 0 . . max 0 s s s X X AX IX b st z CX X

阵单纯影法计算的述 恐线性 初始单纯形表 非基变量基变量 上上页 YR XX 0X、b|BN 10 B N 初始基变量 F!园

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 初始单纯形表 0 0 j j B N s B N s c z C C X b B N I X X X − 非基变量 基变量 初始基变量 矩阵单纯形法计算的描述

阵单纯影法计算的述 恐线性 当基变量为X2时,新的单纯形表 基变量 非基变量 X 上上页 XB bI B N B C 0 CM-CPBN -CRB 当前基解当前检验数 F!园

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 1 1 1 1 0 − − − − c − z C −C B N −C B C X B b I B N B X X X j j N B B B B B N s 基变量 非基变量 当基变量为 XB 时，新的单纯形表 矩阵单纯形法计算的描述 当前基解 当前检验数

修正单纯形法简介 线原因: 单纯形法的目的是要求问题的最优解, 而在迭代过程中,单纯形表中的某些列与 上上页 求最优解关系不大。因此,对单纯形法进 行修正。 彐路 回每次选代关键求出B1,P→b,F,G,O 需要换入的变量对应的列 F!园

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 修正单纯形法简介 ◼ 原因： 单纯形法的目的是要求问题的最优解， 而在迭代过程中，单纯形表中的某些列与 求最优解关系不大。因此，对单纯形法进 行修正。 B Pk b Pk j i −1 ,  ~ , ~ , , 需要换入的变量对应的列 ◼ 思路： 每次迭代关键求出

修正单纯形法简介 恐线性 □修正草鲍形法的优点: 能够从问题的原来参数(A,b,C) 计算出单纯形表中所有的数据,只要导 上上页 出B即可。 单纯形表中的任一数字,只要作部分的 矩阵乘法即可获得。 回 F!园

返回 上页 下页 对 偶 问 题 单 纯 形 法 矩 阵 描 述 大 规 模 线 性 规 划 ◼ 修正单纯形法的优点： ◼ 能够从问题的原来参数（A，b，C）， 计算出单纯形表中所有的数据，只要导 出 即可。 ◼ 单纯形表中的任一数字，只要作部分的 矩阵乘法即可获得。 −1 B 修正单纯形法简介