对偶理论与灵敏度分析 本章内容重点 改进单纯形法 线性规划的对偶问题概念、狸论及经 济意义 √线性规划的对偶单纯形法 √线性规划的灵敏度分析
对偶理论与灵敏度分析 本章内容重点 ü改进单纯形法 ü线性规划的对偶问题概念、理论及经 济意义 ü线性规划的对偶单纯形法 ü线性规划的灵敏度分析
单純形法的矩阵描述 设线性规划闷题: 加入松弛变量后得到标准型: 目标函数Mz=CX Max z=cx toXs 约束条件AX≤b AX+XS=b 非负条件X0 X,X>0 以X为基变量,并标记成YB,这射将糸数矩阵(4,D 分为(B,N两块。B是基变量的糸教矩阵,N是非基变量 的糸数矩阵。相应的决策变量分为:X=(XB,XN),同时将 目标函数的糸数C分为CB,CN,分别对应于基变量XB和非 基变量XN,养且记作C=(CB,CN
单纯形法的矩阵描述 设线性规划问题 : 目标函数 Max Z=CX 约束条件 AX≤b 非负条件 X≥0 加入松弛变量后得到标准型: Max Z=CX +0Xs AX+IXs=b X，Xs≥0 以Xs为基变量，并标记成XB，这时将系数矩阵(A，I) 分为(B，N)两块。B是基变量的系数矩阵，N是非基变量 的系数矩阵。相应的决策变量分为: X=(XB，XN)T ，同时将 目标函数的系数C分为CB，CN，分别对应于基变量XB和非 基变量XN，并且记作C=(CB, CN)
单純形法的矩阵描述 若经过迭代运算后,在基矩阵中可能还存在松弛变量或 全无松弛变量。为了阐述方便,设: B X X NI X SI A= N SI X S2 B,N,S分别表示对应基变量、非基变量、松弛变量的 糸数矩阵。这肘线性规划问题可以表示为: 目标函数Maz=CBXB+CNXN=CBXB+CMXM+Cs2Xs2(2-1 约束条件BXB+NXN=BXB+N1XM+S2Xs2=b (2-2) 非负条件XBXN≥0
单纯形法的矩阵描述 若经过迭代运算后，在基矩阵中可能还存在松弛变量或 全无松弛变量。为了阐述方便，设: ú û ù ê ë é = ú û ù ê ë é = ú û ù ê ë é = ú û ù ê ë é = ú û ù ê ë é = 2 1 2 1 2 1 1 1 ; ; ; ; S N N N B A X X X X X X X X X S S S S N N S B B B，N，S分别表示对应基变量、非基变量、松弛变量的 系数矩阵。这时线性规划问题可以表示为: 条件 0 (2 3) 约束条件 (2 2) 目标 (2 1) 1 1 2 2 1 1 2 2 ³ - + = + + = - = + = + + - B N B N B N S B B N N B B N N S S X X BX NX BX N X S X b MaxZ C X C X C X C X C X 非负 ， 函数
单純形法的矩阵描述 将(2-2)式移项后得到: BXB=6-MXNI-S2Xs2 给等式两边左乘B1后得到: XB=Bb-B MXNI-BS2Xs2 将(2-4)式代入目标函数(2-1)式,因S2是单位矩阵,得到: Z=CBBb+(CNI-CBBMXN +(Cs2-CBBD)Xs2(2-5) 令非基叟量XN=0,可得到一个基本可行解: Bb 此附目标函数值为:Z=CBb
单纯形法的矩阵描述 将(2-2)式移项后得到: BXB b N1X N1 S2XS2 = - - 给等式两边左乘B-1后得到: (2 4) 2 2 1 1 1 1 1 = - - - - - - XB B b B N X N B S XS 将(2-4)式代入目标函数(2-1)式，因S2是单位矩阵，得到: ( ) ( ) (2 5) 2 1 1 1 2 1 1 1 = + - + - - - - - B N B N S B XS Z C B b C C B N X C C B I 令非基变量XN=0，可得到一个基本可行解: 此时目标函数值为: ú û ù ê ë é = -0 1 (1) B b X Z CBB b -1 =
单純形法的矩阵描述 (1)检验数的表示 非基变量的糸数(CM1-CBN)就是上章中用符号c表示的 检验数。因为Cs2=0,I是草位矩阵,故Xs2的糸数是-CBB1。 XB在(2-5)式中的糸数为0,实质上是 CB-CBB1B=0,因此所 有`量的检验数可以用C-CB14和CBB1表示。 (2)0规则表示为: 6= min (Bb (B b) (B Pi) (BP)>0 (B Pi) 这里的(B1b.表示(B1b)中的第计个元素,(BP表示向 量BP)中的第个元素
单纯形法的矩阵描述 j i i j i j i i B P B b B P B P B b ( ) ( ) ( ) 0 ( ) ( ) min 1 1 1 1 1 - - - - - = úû ù êë é q = > (1)检验数的表示: 非基变量的系数(CN1-CBB-1N1)就是上章中用符号cj-zj表示的 检验数。因为CS2=0,I是单位矩阵,故XS2的系数是-CBB-1。 XB在(2-5)式中的系数为0，实质上是CB-CBB-1B=0，因此所 有变量的检验数可以用C-CBB-1A和-CBB-1表示。 (2) θ规则表示为: 这里的(B-1b)i表示(B-1b)中的第i个元素， (B-1Pj)i表示向 量(B-1Pj)中的第i个元素
单純形法的矩阵描述 (3)单纯形表与矩阵表示的关糸: XB+B MXN+B Xs2=Bb z+(CMI-CRB MXNI-CRB Xs2=-CrB b BN B B b 10C、-C,BN,-CnB1X CB b 基叟量 非基变量 等式右边 X S RH 条数矩阵|B1B=I B-INI B B-1b 检验数 0 CMI-CBB- N CpB-1 CpB-1b
单纯形法的矩阵描述 ú û ù ê ë é- = úû ù êë é - ú û ù ê ë é - - - - - - - - C B b B b X X X z C C B N C B B N B B N N B N B B 1 1 1 1 1 1 1 1 2 1 1 0 0 I (3)单纯形表与矩阵表示的关系: z C C B N X C B X C B b X B N X B X B b N B N B S B B N S 1 2 1 1 1 1 1 1 2 1 1 1 1 ( ) - - - - - - - + - - = - + + = 基变量 非基变量 等式右边 系数矩阵 检验数 0 B B = I -1 XB XN XS RHS B b N B-1 -1 B 1 -1 CN1-CBB-1N1 -CBB-1 -CBB-1b
对偶规剡 引例: 某工厂拥有A、B、C三种类型的设备,生产甲、乙两种产 品。每件产品在生产中需要占用的设备机肘数,每件产品可以 获得的利涧以及三种设备可利用的时数如下表所示。求获录大 利涧的生产方。 资娠|甲产品乙产品资遞限额 设备4 360 设各B 943 200 设备C 10 300 单位利澳70 120
引例： 某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产 品。每件产品在生产中需要占用的设备机时数，每件产品可以 获得的利润以及三种设备可利用的时数如下表所示。求获最大 利润的生产方案。 资 源 甲产品 乙产品 资源限额 设备A 9 4 360 设备B 4 5 200 设备C 3 10 300 单位利润 70 120
对偶视州 Maxf(x)=70x1+120x2 9x+4x2<360 4x1+5x2≤200 原问题 s·t 3x;+10x,<300 x1;x Minf(x)=360w1+200n2+300n3 9w1+4w2+3w3≥70 对偶问题 t{4w,+ 5形,+10形2≥120 w2
s · t 9 x1+ 4 x2 ≤360 4x1 + 5 x2 ≤200 3 x1+ 10 x2≤300 x1，x2≥0 Max f(x)=70x1+ 120 x2 原问题 9w1+ 4w2 + 3w3 ≥ 70 4w1+ 5w2 + 10w3 ≥ 120 w1，w2，w3 ≥0 s · t Min f(x)=360w1+ 200w2 + 300w3 对偶问题
对偶规剡 从另一角度提出的线性规划闷题。进一步讨论宅们 之间的关糸。 (1)第1节得到非基变量检验数表达式是CN-CBB1N与 -CB-1,当检验数 CN-CDB-IN<O (2-4) CpB-1<o (2-5) 这表示线性规划问题巳得到最优解。也是作为得到 最优解的判断条件。 上述两式都有乘子CB1,称它为单纯形乘子,用符 号Y=CBB1表示。 由(2-5)式,可得到Y0
从另一角度提出的线性规划问题。进一步讨论它们 之间的关系。 (1)第1节得到非基变量检验数表达式是CN-CBB-1N与 -CBB-1 ，当检验数 CN-CBB-1N≤0 (2-4) -CBB-1≤0 (2-5) 这表示线性规划问题已得到最优解。也是作为得到 最优解的判断条件。 上述两式都有乘子CBB-1 ，称它为单纯形乘子，用符 号Y= CBB-1表示。 由(2-5)式，可得到Y≥0
对偶规剡 (2)对应基变量XB的检验数是0。 宅是CBCB1B=0。包抬基变量在内的所有检验数 可用CCBA≤0表示。 从此可得C-CB1A=CYA≤0 移项后,得到YA≥C (3)Y由(2-5)式,得到 Y=- CDB (2-6) 将(2-6)式两边右乘b,得到 Yb=-CBB-b (2-7) Yb= CRB-b=z 因Y的上界为无限大,所以只存在最小值
(2) 对应基变量XB的检验数是0。 它是CB- CBB-1B=0。包括基变量在内的所有检验数 可用C- CBB-1A≤0表示。 从此可得C-CBB-1A=C-YA≤0 移项后，得到YA≥C (3) Y由(2-5)式，得到 -Y=- CBB-1 (2-6) 将(2-6)式两边右乘b，得到 -Yb=- CBB-1b (2-7) Yb= CBB-1b=z 因Y的上界为无限大，所以只存在最小值