单純形法的矩阵描述 (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的上界为无限大，所以只存在最小值