北京交通大学：《管理运筹学》课程教学课件（讲稿）第2章 对偶理论（1/2）

北京交通大学经济管理学院提纲schasEtonounanics and Managoment单纯形法的矩阵描述对偶问题的提出北京交通大学

提 纲 • 单纯形法的矩阵描述 • 对偶问题的提出

北京交通大学S2.1单纯形法的矩阵描述经济管理学院School of Eoics andManagomentBojing Jiaotong University2.1典式的矩阵形式对于非标准型的线性规划问题max Z = CXiAX fbs.t.iX301松弛变量标准型为：max z = CXi AX+ X'=bs.t.jXX.3 0北京交通大学

§2.1 单纯形法的矩阵描述 2.1 典式的矩阵形式 对于非标准型的线性规划问题 标准型为： 松弛变量

设B为可行基aeX0CX=Xn-(A,I) =(B, N,I)sXsoC=(CB， Cn， Cs)目标函数：Z = CX =CBXβ+CNXr+CsXs约束条件：eXbAX+X,=(B, N, I) x + ==BXp+NX++IX,=bXs因为B-1存在，故上式可化为Xβ +B-1NX+B-1Xs=B-1b

C=(CB，CN，CS ) （A，I）=(B，N，I ) 设 B 为可行基， 目标函数： Z = CX 约束条件： 因为B-1 存在，故上式可化为 AX+XS =(B, N, I) =BXB+NXN+IXS =b XB +B-1NXN +B-1XS =B-1b =CBXB+CNXN+CSXS

Xβ =B-1b-B-1NX-B-1X.将上式代入目标函数可得Cs=0Z=CBXp+CNX+CsXs= Cβ(B-1b-B-1NXn -B-1Xs)+CNX+CsX=CBB-1b + (Cn-CβB-1M)X+ (-CBB-I)Xs则线性规划模型可表示为：

将上式代入目标函数可得 ￾XB =B- 1b-B- 1N XN -B- 1XS Z=CBXB+CNXN+CSXS =CBB-1b + (CN -CBB-1N)XN + (-CBB-1 )XS = CB (B-1b-B-1NXN -B-1XS）+CNXN+CSXS CS=0 则线性规划模型可表示为：

Z =CrB-1b + (C-CBB-1MX+ (-CβB-I)XsS.t.[Xβ +B-1NX +B-1Xs=B-1bLX 令非基变量X=0，X=0，得到一个基本可行解,aB'boCZ(0) =C,B-1bICCre00单纯形表的相应各部分可表示为：

Z =CBB-1b + (CN -CBB-1N)XN + (-CBB-1 )XS s.t. XB +B-1NXN +B-1XS =B-1b X ￾ 0 令非基变量 XN = 0， XS = 0，得到一个基本可 行解， Z（0）=CBB-1b 单纯形表的相应各部分可表示为：

CpCCs=0CjXXbXnXsCβbBNIXB-AXXBXsXNB-11B-lbB-INCBXB-CpB-10-CgB-lbC-CBB-IN初始单位阵的位置总对应B-1；已知CRB就能求出整个表

X XB XN XS XB B-1b I B-1N B-1 -CBB-1b 0 CN -CBB-1N -CBB-1 B-1A C-CBB-1A CB X XB XN XS CB XB b B N I cj CB CN CS=0 初始单位阵的位置总对应B -1 ;已知 B-1 就能求出整个表

如例1max Z = 2x, +3x2= 8i x+2x2+X3i= 164x+X4s.t.i4x2+ x, = 12i30xt Xi2,X3,X49Ouel2<eu0.4若取基B=(pi,P2,P4)eu4 则@0Ot8iél01/2uecu<euB-10b :16一0C =(2, 3, 0, 0, 0)1/4<eeuu1@124@ 42θ

如例1 C =(2, 3, 0, 0, 0)

相应的基可行解中基变量的值10é- 1/2ue8 üé2u<eeuueu16100B1/2<euueU1<GD42@128F-C,-CBB-X~ =(x3,Xs)S N=CN- C,B-'N0él1/2uelOuete0900= (0,0) - (2,3,0)1/4<eue1<GD420单纯形乘子向量

相应的基可行解中基变量的值 ￾j =cj -CBB-1pj 单纯形乘子向量

0é1- 1/2ué2ueOu<ee,ueo'"-001/ 4p= Bp2eeuueu12@- 44单纯形迭代中的第三张表bCBXBX1X2X3x4Xs202011-1/2xi80020-41X43030101/42000-13-21/4B-1B-lb

单纯形迭代中的第三张表 CB XB b x1 x2 x3 x4 x5 2 x1 2 1 0 1 0 -1/2 0 x4 8 0 0 -4 1 2 3 x2 3 0 1 0 0 1/4 -13 0 0 -2 0 1/4 B-1 B-1b

北京交通大学经济管理学院$2.2线性规划的对偶理论School of Econcnics andManagomentBoijing Jiaotong University1 对偶问题的提出对偶是对同一事物(问题)从不同的角度(立场观察,有两种相对的表述比如：平面中矩形的面积与周长的关系周长一定,面积最大的矩形是正方形面积一定,周长最短的矩形是正方向1买---卖北京交通大学

l 对偶问题的提出 对偶是对同一事物(问题)从不同的角度(立场) 观察,有两种相对的表述. 比如: 平面中矩形的面积与周长的关系. 周长一定,面积最大的矩形是正方形; 面积一定,周长最短的矩形是正方向. l 买-卖 §2.2 线性规划的对偶理论