《运筹学03单纯形法的进一步讨论：人工变量法》由会员分享，可在线阅读，更多相关《运筹学03单纯形法的进一步讨论：人工变量法（24页珍藏版）》请在金锄头文库上搜索。
1、复习：单纯形法5 单纯形法的进一步讨论: 人工变量法人工变量法（确定初始可行基）：原约束方程：AX=b加入人工变量：xn+1，xn+m人工变量是虚拟变量，加入原方程中是作为临时基变 量，经过基变换，将人工变量均能换成非基变量，所得解 是最优解；若在最终表中检验数小于零，而且基变量中还 有某个非零的人工变量，原问题无可行解。1、大M法方法：在约束条件中，加入人工变量后，要求目标函数 不受影响？目标函数中人工变量的系数取（-M）。理由：目标函数实现最大化，就必须将人工变量从基变量 中换出，否则目标函数就不可能取得最大化。例1：用大M法求解如下线性规划问题11 1 -2 1 1 0 0 0 11 3
2、 -4 1 2 0 -1 1 0 3/2 1 -2 0 1 0 0 0 1 10 M 1 6xx4 x 310 3 -2 0 1 0 0 -1 1 0 1 0 0 -1 1 -2 11 -2 0 1 0 0 0 1-3 x11 x21 x34 1 0 0 1/3 -2/3 2/3 -5/31 0 1 0 0 -1 1 -29 0 0 1 0 2/3 4/3 -7/3-3 1 1 0 0 M M-1 0 0 0 1 M-1 M+1zj- cj0 0 0 1/3 1/3 M-1/3 M-2/3 zj- cj0 x41 x21 x312 3 0 0 1 -2 2 -5 41 0 1 0 0 -1 1
3、 -21 -2 0 1 0 0 0 1cj0 M MX4 X6 X7b CBXBX1X2X3X4X5X6X7i-3+6M 1-M 1-3M 0 M 0 0cj-zj-1 1-M 0 0 M 0 3M-1cj-zj最优解是目标函数为-2。例4： max z=4x1+3x2 -3x1+2x26 s.t. -x1+3x23x1, x2 0x1x2无可行解x1x22、两阶段法 第一阶段： 建立一个辅助线性规划并求解，以此判断原线性规划是否存在可行解 。 辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函 数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准 型的约束条件。 所有人工变
4、量都变成非基变量，目标函数值为0，原问题存在基 可行解。转到第二阶段。 若目标函数值不为0，至少有一个人工变量不能从基变量中转出 ，原问题没有可行解。停止。第二阶段： 从第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题 的目标函数系数，用单纯形法计算，直到得到最优解为止。例2：同上第一阶段：求解辅助规划问题11 1 -2 1 1 0 0 0 11 3 -4 1 2 0 -1 1 0 3/2 1 -2 0 1 0 0 0 1 10 1 0 6xx4 x 310 3 -2 0 1 0 0 -1 1 0 1 0 0 -1 1 -2 11 -2 0 1 0 0 0 10 0 0 0 0 1 1
5、0 0 0 0 0 1 1zj- cj0 x40 x20 x312 3 0 0 1 -2 2 -5 41 0 1 0 0 -1 1 -21 -2 0 1 0 0 0 0cj0 1 1X4 X6 X7b CBXBX1X2X3X4X5X6X7i6 -1 -3 0 1 0 0cj-zj0 -1 0 0 1 0 3cj-zj12 3 0 0 1 -2 4 1 0 1 0 0 -1 1 -2 0 1 0 0-3 1 1 2xx1 x 34 1 0 0 1/3 -2/3 1 0 1 0 0 -19 0 0 1 2/3 -4/3-3 1 1 0 0 cj0 1 1X4 X2 X3b CBXBX1X2X3X4
6、X5i-1 0 0 0 1cj-zj0 0 0 1/3 1/3cj-zjx6，x7是人工变量，第一阶段求解的最优结果是=0，因此 得最优解为： 第二阶段：取消人工变量，添入原问题目标函数的系 数，求解相应的线性规划。最优解为：最优值为：z= -2两阶段法：辅助规划； 去掉人工变量，单纯形法。对目标函数求max的线性规划问题,用单纯形法计算步骤的框图唯一最优解NNNYYY添加松弛变量、人工变 量, 列出初始单纯形表计算非基变量 对应的检验数j所有j0基变量中 有非零的 人工变量某非基 变量检 验数为 零无可行解无穷多最优解对某j0 有aij0无界解令k=maxj对所有aik0计算 i=bi/ai
7、k 令s=mini xs为换出变量 ask为主元素迭代运算 . 用非基变量xk替换基变量xs; . 对主元素行(第s行)，令 bs/askbs;asj/askasj . 对主元素列(第k列)，令1ask；0其它元素 表中其它行列元素令 aij-asj/askaikaijbi-bs/askaikbiYN用大M法和两阶段法求解以下问题第二章 对偶理论与灵敏度分析1 单纯形法的矩阵描述线性规划 max z=CX max z=CX+OXs (1) AXb AX+IXs =b X0 X0, Xs0 其中 I 是mm 单位矩阵，松弛变量Xs=( xn+1, xn+2,xn+m)T . 设B是一个可行基矩阵
8、，N表示非基变量的系数矩阵 (A，I)(B，N)对应决策变量 约束条件对应目标函数的价值向量原线性规划可改写为单纯形表的几个特征: 1、检验数: 非基变量的检验数(等于对应的目标系数)cj zj=( CNCBB-1N)j基变量的检验系数为零，即 cj zj= CBCBB-1 B=0进一步，非基底变量可分解XN （XN1，Xs），其中 XN1 表示除去松弛变量以后的非基变量；Xs是松弛变量，其目标 系数为零。Xs的检验数cj zj=( 0CBB-1)j= CBB-1 所有的检验数可用CCBB-1A与CBB-1表示(B-1b)i是向量(B-1b)中的第i个元素，(B-1Pj)i是向量(B-1Pj)
9、中的第i个元素，j=1,2,n2、规则的表达形式基变量非基变量等式右端XB XN1XS系数矩阵IB-1N1B-1B-1b检验数0CN1-CBB-1N1-CBB-1-CBB-1b3、单纯形表的矩阵表达形式 1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为 B-1；2）初始单纯形表中基变量Xs=b，迭代后的表中变为XB=B-1b；3）初始单纯形表中的系数矩阵A，I=B，N1，I，迭代后的 表中约束系数矩阵为：B-1A，B-1I=B-1B，B-1N1，B-1I=I， B-1N1， B-1；4）初始单纯形表中变量xj的系数向量为Pj，迭代后为Pj，则有 Pj=B-1 Pj；2 改进的单纯形算法主要是计算 的差别 用改进的单纯形法求解下面的线性规划问题
