华北理工大学：《运筹学》课程教学课件（讲稿）第2章 对偶理论与灵敏度分析

第二章 对偶理论与灵敏度分析

第二章 对偶理论与灵 敏度分析

82.1单纯形法矩阵描述一、为什摩要研究单纯形法的矩阵描述？&进一步讨论修正单纯形法&便于理论推导（如对偶定理的证明）怎样进行矩阵描述？关键写出两个基本的表达式

一、为什麽要研究单纯形法的矩阵描述？ 一、为什麽要研究单纯形法的矩阵描述？ & 进一步讨论修正单纯形法 进一步讨论修正单纯形法 & 便于理论推导（如对偶定理的证明） 便于理论推导（如对偶定理的证明） 二、怎样进行矩阵描述？ 二、怎样进行矩阵描述？ 关键——写出两个基本的表达式。 写出两个基本的表达式。 §2.1 单纯形法矩阵描述 单纯形法矩阵描述

1、准备工作：（1）标准型的矩阵形式CXMaxZ=AXbS.t.X0≥（2）将式中矩阵写成分块矩阵形式C =(CB:Cn)X =(XB:X~)AA =(P,P2,".:,P)=(B:N)

1、准备工作： （1）标准型的矩阵形式 ）标准型的矩阵形式—— ⎩⎨⎧ ≥= = 0 . . X AX b s t MaxZ CX （2）将式中矩阵写成分块矩阵形式 ）将式中矩阵写成分块矩阵形式 ( ) C CB CN = M T X XB X N = ( M ) ( , , , ) ( ) A P1 P2 L Pn BMN Δ = =

2、将分块形式代入矩阵形式标准型，得出两个基本表达式(1)由约束条件(XBAX =(B N)= BXβ + NX = b可得用非基变量表示基变量的表达式Xβ=B'(b-NX)=B"b-B'NX(2.2)

2、将分块形式代入矩阵形式标准 、将分块形式代入矩阵形式标准 型，得出两个基本表达式： 型，得出两个基本表达式： （1）由约束条件 BX NX b X X AX B N B N N B = + = ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = ( ) 可得 用非基变量表示基变量的表达式： 用非基变量表示基变量的表达式： B N B NXN X B b NX B b 1 1 1 ( ) − − − = − = − （2.2）

（2）将式（2.2）代入目标函数的表达式可得：用非基变量表示目标函数的表达式：XBZ=CX=(CBCN)=C,Xβ+CNXNXN)=C(B"b-B'NX)+CXN=C,B"b-C,B-'NX +CX令O~=C-C,B'N得=C,B"b+(C-C,B'M)X(2.3)Z=C,Bb+0nX

（ ） 令 得 2.3 ( ) ( ) ( ) 1 1 1 1 1 1 1 1 B N N B N B N N N B B B N N N B N N N B B N N N B B N Z C B b X C B b C C B N X C C B N C B b C B NX C X C B b B NX C X C X C X X X Z CX C C σ σ = + = + − = − = − + = − + = + ⎟⎟⎟⎠⎞ ⎜⎜⎜⎝⎛ = = − − − − − − − − （2）将式（2.2）代入目标函数的表达式， ）代入目标函数的表达式， 可得：用非基变量表示目标函数的表达式： 用非基变量表示目标函数的表达式：

非基变量检验数O=C-C,B-IN基变量检验数β=C-C,B-"B=0^=C-C,B-A所有变量检验数计算公式写成分量的形式O, =C,-CβB-Pm, =cj -Zcaji=1

1 σ N N C CB B N− 非基变量检验数 = − 1 0 σ B B C CB B B− 基变量检验数 = − = 1 σ A B C C B A− 所有变量检验数计算公式 = − 1 σ j j C CB B Pj − 写成分量的形式 = − ∑ = = − m i j j i ij c c a 1 σ

单纯形表的矩阵形式0SCnC;初始表XBXNs系数基变量解向量bN0BXsI0CBCna单纯形表以B为基的XBB-1bIB-1NB-1C0CN-CβB-1NC,Ba

cj CB CN 0 系数 基变量 解向量 XB XN XS 0 XS b B N I σj CB CN 0 . . CB XB B－1b I B－1N B－1 σj 0 CN－CBB－1N －CBB－1 初始表 以 B为基的 单纯形表 单纯形表的矩阵形式

初始表经过若干次行的初等变换转化为以B为基的单纯形表，在这个过程中：(1)初始单纯形表中矩阵B变成为单位矩阵I，从而把单位矩阵I变成B-1；(2)初始单纯形表中基变量的值X。=b，迭代后的表中Xβ =B-1b;(3)初始单纯形表中系数矩阵（BNI），迭代后的表中系数矩阵（IB-1NB-1）；(4)初始矩阵中变量x;的系数列向量P，迭代后为Pi则有P'= B-"P

1 Pj B Pj − ′ = 初始表经过若干次行的初等变换转化为以B为基的单 纯形表，在这个过程中： (1)初始单纯形表中矩阵B变成为单位矩阵I，从而把单 位矩阵I变成B-1; (2) 初始单纯形表中基变量的值XS ＝b，迭代后的表中 XB ＝B－1b; (3)初始单纯形表中系数矩阵（ＢＮＩ），迭代后的表 中系数矩阵（Ｉ B－1N B－1）; (4)初始矩阵中变量xj的系数列向量Pj，迭代后为Pj′ ，则有

例：求下列LP问题的最优解z = 3xi - X2 - X3maxXi -2x2 +X3 ≤11- 4xi +X2 +2x ≥3 2x1+X3 =1X1,X2,X3 ≥ 0

例：求下列LP问题的最优解 ⎪⎪⎩ ⎪⎪⎨⎧ ≥ − + = − + + ≥ − + ≤ = − − , , 0 2 1 4 2 3 2 11 max 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x x x z x x x

3-100-1-M-MCCBXBbXiX4X6XX2X3Xs01-21100110x432-410-1I-M0X6001-200I-M[1]X7000-M3-6M-1+M-1+3Ma03-20100-110X4001-2-M10-1[1]X61-1-2010001X31000-M-1+M-3M+1ai0-212[3] 012.-50X4-21010-101-1X21-2100001-1x3福10000-1-3M+1°i310042/3-5/31/3-2/3Xi-1110100-1-2X2-190012/3-4/34/3-7/3X3000-1/3-1/3-M+1/3-M+2/3ai

0 0 0 0 1 0 1 0 x 7 x 6 -M -M σ j 3-6M -1+M -1+3M -M 0 -1 0 1 2 [1] -2 1 0 1 -4 -2 11 3 1 x 4 x 6 x 7 0 -M -M x 5 x 3 x 2 x1 X b CB B c 3 -1 -1 0 j 0 1 0 0 x 4 0 -1 -2 1 0 1 0 0 -1 0 0 0 1 -2 [1] 0 3 0 -2 10 1 1 x 4 x 6 x 3 0 -M -1 1 0 0 σ 1 -1+M 0 -M 0 -3M+1 j 0 -5 -2 1 2 1 0 -2 -1 0 0 0 1 0 1 0 [3] 0 -2 12 1 1 x 4 x 2 x 3 1 0 0 σ 1 0 0 -1 0 -3M+1 j 0 -1 -1 0 -M+1/3 -M+2/3 -5/3 -2 -7/3 2/3 1 4/3 σ 0 0 0 -1/3 j -2/3 -1 -4/3 0 0 1 0 1 0 1 0 0 4 1 9 x1 x 2 x 3 3 -1 -1 -1/3 1/3 0 2/3