《运筹学》课程教学课件（PPT讲稿）对偶理论（Duality Theory）

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

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

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

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

运筹学2.1单纯形法的矩阵描边3China University of Mining and Technology

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

运学单纯形法的矩阵描述筹XBB-1bCBX4XIX2X3Xs0·每一列的含00900941360X3义?50100200440X4·每个表中的010030031300xsB和B-1的查000712O找？02407.801-0.430.80X30010502.5-0.520X40012300,310.1100X2003.40-1.2B=(P,P,P)584000-3.1211.16X310037201000.4-0.2XI3.121.161224010-012016X20.400.2(B)-=00.120.16B"(b,A) =(B"b,B"P,BP..... B"P主页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(B"b);>0,=C-CBBBP→0BB。→X。=min0(B'PA),1需计算Bb需计算BA即BA因此，单纯形表的主体内容是B（6A）而相邻两个B只有一列不同，故相邻两B6A)个B-也可通过初等行变换求得。B-bA由此设计了基于初等行变换选代计算的单纯形表。5-主页上页下页后退退出China University of Mining and Technology

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

单纯形法的矩阵描述运筹学单纯形表的主要结构：CXB-bBA0问题：第一张表的B-1-？检验数的公式是什么？B"P在哪里？6主页China University of Mining and Technology

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

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

-7- 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 =C.X+CXNBX,+ NX + X, = bs.t.(P)XB≥0,X~≥0,X,≥0CBCNCs(0)XBbXNXsbBN10CBCN0CBCNCs(0)bXBXNXsB-1bB-INB-110-CB-1b-CpB-1Cn-CBB-IN-8-主页出China University of Mining and Technology中

-8- 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 = +  + + =      单纯形法的矩阵描述

运筹学2.3对偶问题的提出-9China University of Mining and Technology

-9- China University of Mining and Technology 运筹学 2.3 对偶问题的提出

运筹学对偶问题的提出对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？10丰China University of Mining and Technology

-10- China University of Mining and Technology 运筹学 对偶理论是线性规划中最重要的理论之一，是深入了 解线性规划问题结构的重要理论基础。同时，由于问题提 出本身所具有的经济意义，使得它成为对线性规划问题系 统进行经济分析和敏感性分析的重要工具。那么，对偶问 题是怎样提出的，为什么会产生这样一种问题呢？ 对偶问题的提出