运筹学讲稿第7次课2学时0上次课复习：线性规划相关要点。本次课题（或教材章节题目）：第二章对偶理论与灵敏度分析$2.1单纯形法的矩阵描述0教学要求：掌握单纯形法的矩阵描述重点：单纯形法的矩阵描述难点：B的求法及作用教学手段及教具：多媒体教学。讲授内容及时间分配：50分钟$2.1单纯形法的矩阵描述50分钟p792、30P781、(1)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社陶谦坎主编《运筹学应用案例》机械工业出版社注：本页为每次课教案首页第16页
运筹学讲稿 第 16 页 第 7 次课 2 学时 注：本页为每次课教案首页 上次课复习： 线性规划相关要点。 本次课题（或教材章节题目）：第二章 对偶理论与灵敏度分析§2.1 单纯形法的矩阵描述 教学要求： 掌握单纯形法的矩阵描述 重 点：单纯形法的矩阵描述 难 点：B-1 的求法及作用 教学手段及教具：多媒体教学。 讲授内容及时间分配： §2.1 单纯形法的矩阵描述 50 分钟 p79 2、3 50 分钟 课后作业 P78 1、（1） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿第二章对偶理论与灵敏度分析S2.1单纯形法的矩阵描述表 2-1CBCN0c系数基变量解向量XBXNXsBN10Xsb001CBCN..XB/B'NBICBB-'b0j0CN-CBB-'N-CBB-!其中X=（xsl，X2，Xm）是松弛变量组成的列向量。从表2-1可以清楚地看到，以B为基的单纯形表中的增广矩阵，是以B-左乘初始表的增广矩阵的结果：因此，在B为基的表中，与初始表单位矩阵相同位置上即为B的逆矩阵B-!。这是一个很有用的普遍规律。这一点还可以利用初等变换知识加以说明：初始表经过若干次行的初等变换转化为以B为基的单纯形表，在这个过程中，它把矩阵B变成为单位矩阵1，从而把单位矩阵I变成。注：为加深对B-及各表达式的理解，课堂练习作业2、317第页
运筹学讲稿 第 17 页 第二章 对偶理论与灵敏度分析 §2.1 单纯形法的矩阵描述 表 2-1 cj CB CN 0 系数 基变量 解向量 XB XN XS 0 XS b B N I σj CB CN 0 . . CB XB B－1 b I B－1 N B－1 σj 0 CN－CBB－1 N －CBB－1 其中 XS=（xs1，xs2，xsm）T是松弛变量组成的列向量。从表 2-1 可以清楚地看到，以 B 为基的单 纯形表中的增广矩阵，是以 B－1 左乘初始表的增广矩阵的结果；因此，在 B 为基的表中，与初始表单 位矩阵相同位置上即为 B 的逆矩阵 B－1 。这是一个很有用的普遍规律。这一点还可以利用初等变换知 识加以说明：初始表经过若干次行的初等变换转化为以 B 为基的单纯形表，在这个过程中，它把矩阵 B 变成为单位矩阵 I，从而把单位矩阵 I 变成。 注：为加深对 B－1 及各表达式的理解，课堂练习作业 2、3
运筹学讲稿第8次课2学时0上次课复习：单纯形法的矩阵描述本次课题（或教材章节题目）：$2.2对偶问题的概念$2.3对偶问题的基本性质0教学要求：掌握一般形式对偶问题的对应规律、理解并应用对偶定理重点：一般形式对偶问题的对应规律、对偶定理难点：对偶定理教学手段及教具：多媒体教学。讲授内容及时间分配：$2.2.1对偶问题的提出20分钟30分钟S2.2.2一般形式的对偶问题$2.3对偶问题的基本性质50分钟0P794、(1)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社注：本页为每次课教案首页第18页
运筹学讲稿 第 18 页 第 8 次课 2 学时 注：本页为每次课教案首页 上次课复习： 单纯形法的矩阵描述 本次课题（或教材章节题目）：§2.2 对偶问题的概念§2.3 对偶问题的基本性质 教学要求： 掌握一般形式对偶问题的对应规律、理解并应用对偶定理 重 点： 一般形式对偶问题的对应规律、对偶定理 难 点：对偶定理 教学手段及教具：多媒体教学。 讲授内容及时间分配： §2.2.1 对偶问题的提出 20 分钟 §2.2.2 一般形式的对偶问题 30 分钟 §2.3 对偶问题的基本性质 50 分钟 课后作业 P79 4、（1） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿82.2对偶问题的概念82.2.1对偶问题的提出原问题max z=Cx[AX <b(2.11)LX≥0它的对偶问题minw=Yb[YA≥C(2.12)[Y≥0注意：Y=（yi，y2，…，ym）是行向量。表 2-2原问题对偶问题（1）决策变量X≥0 (n个)Y≥0(m个)（2）目标函数max z=Cxminw=YbAX<≤b(m个)YA≥C (n个)（3）约束条件AT（4）系数矩阵Abc（5）右端向量cb（6）价值向量82.2.2一般形式的对偶问题表2-3原问题（对偶问题）max对偶问题（原问题）minA约束条件系数矩阵约束条件系数矩阵的转置c目标函数价值向量约束条件右端常数向量b约束条件右端常数向量目标函数价值向量Saz0x,≥0i=l[0 0 个技术的来n个变量x≤0i=la=cx无约束i=ly,≥0Zax,≤b,j=lRm个变量y≤Om个技术约束Za,x,≥bj=1nEa,x, =b,无约束j=lS2.3对偶问题的基本性质定理1对偶问题的对偶是与原问题。第19页
运筹学讲稿 第 19 页 §2.2 对偶问题的概念 §2.2.1 对偶问题的提出 原问题 ⎩ ⎨ ⎧ ≥ ≤ = 0 b max X AX z CX （2.11） 它的对偶问题 ⎩ ⎨ ⎧ ≥ ≥ = 0 min b Y YA C w Y （2.12） 注意：Y=（y1，y2，.，ym）是行向量。 表 2-2 原问题 对偶问题 （1）决策变量 （2）目标函数 （3）约束条件 （4）系数矩阵 （5）右端向量 （6）价值向量 X≥0（n 个） max z=CX AX≤b（m 个） A b C Y≥0（m 个） min w=Yb YA≥C（n 个） AT C b §2.2.2 一般形式的对偶问题 表 2-3 原问题（对偶问题）max 对偶问题（原问题）min A C b 约束条件系数矩阵 目标函数价值向量 约束条件右端常数向量 约束条件系数矩阵的转置 约束条件右端常数向量 目标函数价值向量 n 个变量 ⎪ ⎪ ⎪ ⎭ ⎪ ⎪ ⎪ ⎬ ⎫ = ≤ ≥ ∑ ∑ ∑ = = = j m i ij i j m i ij i j m i ij i a y c a y c a y c 1 1 1 n 个技术约束 m 个技术约束 ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ = ≥ ≤ ∑ ∑ ∑ = = = i n j ij j i n j ij j i n j ij j a x b a x b a x b 1 1 1 m 个变量 §2.3 对偶问题的基本性质 定理 1 对偶问题的对偶是与原问题。 xj≥0 xj≤0 xj 无约束 yi≥0 yi≤0 yi 无约束
运筹学讲稿定理2（弱对偶定理）设X=(xi,x2，,x）与Y=(yi,y2，,ym）分别是（2.9）与（2.10）的可行解，则CX≤Yb。）设X，Y分别为问题（2.3）与（2.4）的可行解，且CX=Yb，则定理3（最优性判定定理）两者均为最优解。第20页
运筹学讲稿 第 20 页 定理 2（弱对偶定理） 设 T n X (x , x , , x ) = 1 2 L 与 ( , , , ) 1 2 m Y = y y L y 分别是（2.9）与（2.10） 的可行解，则CX ≤ Yb 。 定理 3（最优性判定定理） 设 X ，Y 分别为问题（2.3）与（2.4）的可行解，且CX = Yb，则 两者均为最优解