中国矿业大学：《运筹学》课程教学课件（讲稿）Chapter 2 对偶理论（Duality Theory）

运筹学对偶理论Chapter2Theory)(Duality本章主要内容：单纯形法的矩阵描述对偶问题的提出线性规划的对偶理论对偶问题的经济解释一影子价格对偶单纯形法灵敏度分析掌握WinQSB软件求解对偶规划-1-米China University of Mining and Technology

-1- China University of Mining and Technology 运 筹 学 Chapter2 对偶理论 ( Duality Theory ) 单纯形法的矩阵描述 对偶问题的提出 线性规划的对偶理论 对偶问题的经济解释－影子价格 对偶单纯形法 灵敏度分析 掌握WinQSB软件求解对偶规划 本章主要内容：

运筹学学习要点：1.理解对偶理论，掌握描述一个线性规划问题的对偶问题。2.能够运用对偶单纯形法来求解线性规划问题。3.会用互补松弛条件来考虑一对对偶问题的界。4.了解影子价格、灵敏度分析以及用WinQSB求解对偶规划问题。?China University of Mining and Technology

-2- China University of Mining and Technology 运 筹 学 学习要点： 1. 理解对偶理论，掌握描述一个线性规划问题 的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。 4. 了解影子价格、灵敏度分析以及用WinQSB求 解对偶规划问题

运筹学$ 2.1单纯形法矩阵描述3.China University of Mining and Technology

-3- China University of Mining and Technology 运 筹 学 §2.1 单纯形法矩阵描述

运筹学单纯形法的矩阵描述·每一列的含XBB-1bCBX1X2X3X4X5e义?09090041360X3·每个表中的01050440200X4B和B-1的查310100030300X5找？0070129B从初表中找00107.8240-0.430.8X3B-1从当前表中0010502.5-0.520X4找，相当于初表中的I的位置10120300.10,3100X24190003.4-1.29B=(P3,P,P)=504000841-3.121.16X310Lo31072000.4-0.2XIK11.16-3.121001224-0.120.16X200.40.2(B)-1=00.160.12B'(b, A) =(B"b, B"P, B'P..., B"P,)-4-页后退退主页上一页下出China University of Mining and Technology福

-4- China University of Mining and Technology 运 筹 学 x2 12 24 0 1 0 -0.12 0.16 x1 7 20 1 0 0 0.4 -0.2 x3 0 84 0 0 1 -3.12 1.16 3.4 0 0 0 -1.2 x2 12 30 0,3 1 0 0 0.1 100 x4 0 50 2.5 0 0 1 -0.5 20 x3 0 240 7.8 0 1 0 -0.4 30.8 7 12 0 0 0 x5 0 300 3 10 0 0 1 30 x4 0 200 4 5 0 1 0 40 x3 0 360 9 4 1 0 0 90 B x1 x2 x3 x4 x5 ɵ -1 XB CB b   •每一列的含 义？ •每个表中的 B和B-1的查 找？ ( , ) ( , , ,., ) -1 2 -1 1 -1 -1 -1 B P B P B Pn B b A  B b B从初表中找， B-1从当前表中 找，相当于初 表中的I的位置 单纯形法的矩阵描述

单纯形法的矩阵描述运筹学单纯形法的主要步骤Bab(Bb)B。→>XB-CB.B0=min>0=C0(BP)需计算Bb需计算B-A因此，单纯形表的主体内容是B-1(b,A)单纯形表的主要结构CB-1bB-1AC- CB-IAC5-X主页上一页后退退出一页China University of Mining and TechnologyN

-5- China University of Mining and Technology 运 筹 学 单纯形法的主要步骤 因此，单纯形表的主体内容是B-1 (b,A) C X B-1b B-1A σ C- CBB-1A 单纯形表的主要结构 单纯形法的矩阵描述

单纯形法的矩阵描述运筹学max z = C,B-"b +(C -C,B-'N)XXβ + B-'NX~ = B-"bXβ≥0,X≥0CNCBbXBXNB-1b1B-IN0-CgB-1bCn-CgB-1 NCNCBbXNXBbBN-6-宋主页上一页一页后退退出China University of Mining and Technology

-6- China University of Mining and Technology 运 筹 学 CB CN b XB XN b B N CB CN b XB XN B-1b I B-1N -CBB-1b 0 CN -CBB-1 N               0, 0 max ( ) 1 1 1 1 B N B N B N B N X X X B N X B b z C B b C C B N X 单纯形法的矩阵描述

运筹学单纯形法的矩阵描述maxz =CXβ +CXNBX,+ NX~+X, = bs.t.[X, ≥0 Xh ≥0, X, ≥0 (P)CBCNCs(0)bXNXBXsb1BN00CBCNCNCpCs(0)bXBXNXsB-1B-1bIB-N0-CgB-1-CB-1bC-C,B-1 N-7-王主页上一页下一页后退退出China University of Mining and Technology

-7- China University of Mining and Technology 运 筹 学 CB CN CS (0) b XB XN XS b B N I 0 CB CN 0 CB CN CS (0) b XB XN XS B-1b I B-1N B-1 -CBB-1b 0 CN -CBB-1 N -CBB-1 max . . ( ) 0, 0, 0 B B N N B N S B N S z C X C X BX NX X b s t P X X X            单纯形法的矩阵描述

运筹学单纯形法的矩阵描述注：（1）解的几种情况在单纯形表上的体现（Max型）：-唯一最优解：终表非基变量检验数均小于零：多重最优解：终表非基变量检验数中有等于零的：无界解：任意表有正检验数相应的系数列均非正。无解：最优解的基变量中含有人工变量(2)：检验数反Min型单纯形表与Max型的区别仅在于：号，即令负检验数中最小的对应的变量进基：当检验数均大于等于零时为最优。-8-来上一页一页后退退出主页China University of Mining and Technology1

-8- China University of Mining and Technology 运 筹 学 单纯形法的矩阵描述

运筹学$2.2改进单纯形法9China University of Mining and Technology

-9- China University of Mining and Technology 运 筹 学 §2.2 改进单纯形法

运筹学改进的单纯形法0231000bXBCBX,X5X2X3X40015[3]51T010036-1X2003-1101X100002310;30501/31/315X21/3PI10-2103-10O145800106X64/34/31/30000-151-10030001/4-1/4X2思考：P,分1P别与P“一00-1/61/21/30P”的关系20011/45/12-1/3X31000-20-5/6-1/3-1/2g:-10-宋主页页下一页后退退出China University of Mining and Technology-

-10- China University of Mining and Technology 运 筹 学 3 X2 5 1/3 1 1/3 1/3 0 0 15 0 X5 3 [1] 0 -2 -1 1 0 3 σj 0 2 3 1 0 0 0 X 3 1 -1 1 0 0 1 - 0 6 -15 1 0 0 -1 0 0 0 X6 8 4/3 0 4/3 1/3 0 1 6 0 1 x4 0 1 0 x5 0 0 0 x6 0 0 X5 18 2 3 -1 6 0 X4 15 1 [3] 1 5 CB XB b x1 x2 x3 θ 2 3 1 2 X3 1 0 0 1 5/12 -1/3 1/4 -5/6 -1/6 1/4 -1/3 1/3 0 -1/2 1/2 -1/4 σj -20 0 0 0 0 X1 5 1 0 0 0 X2 3 0 1 0 θ . . . . P1 P1 ′ P1 ″ 思考：P1分 别与P1 ′ 、 P1 〞的关系 改进的单纯形法