《运筹学教学资料》运筹学第2章.ppt

《《运筹学教学资料》运筹学第2章.ppt》由会员分享，可在线阅读，更多相关《《运筹学教学资料》运筹学第2章.ppt（165页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、a University of Mining and Technology运筹学 0.16-0.120102412x2-0.20.4001207x11.16-3.12100840 x3-1.20003.41000.10010,33012x220-0.51002.5500 x430.8-0.40107.82400 x3000127301001033000 x540010542000 x490001493600 x3x5x4x3x2x1B-1bCBXB每一列的含每一列的含义？义？每个表中的每个表中的B和和B-1的查的查找？找？B从初表中找，从初表中找，B-1从当前表中从当前表中找，相当于初表找，相

4、当于初表中的中的I的位置的位置单单纯纯形形法法的的矩矩阵阵描描述述-5-China University of Mining and Technology运筹学 单纯形法的主要步骤单纯形法的主要步骤因此，单纯形表的主体内容是因此，单纯形表的主体内容是B-1(b,A)CXB-1bB-1AC-CB-1A单纯形表的主要结构单纯形表的主要结构单单纯纯形形法法的的矩矩阵阵描描述述-6-China University of Mining and Technology运筹学 CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1 N 单单纯纯形形法法的的矩矩阵阵描描述

5、述-7-China University of Mining and Technology运筹学 CBCNCS(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1 N-CBB-1 单单纯纯形形法法的的矩矩阵阵描描述述-8-China University of Mining and Technology运筹学 单单纯纯形形法法的的矩矩阵阵描描述述-9-China University of Mining and Technology运筹学 2.2 改进单纯形法改进单纯形法-10-China University of

6、Mining and Technology运筹学 15001/31/311/35X23301-1-2013X500001320j-1001-113X6000-1001-156101/34/304/38X6001x4010 x5000 x606-13218X50513115X40 x3x2x1bXBCB1321/4-1/35/121001X32-5/6-1/61/4-1/31/30-1/21/2-1/4000-20j0015X100103X20P1P1P1思考：思考：P1分分别与别与P1、P1的关系的关系改改 进进 的的 单单 纯纯 形形 法法-11-China University of Mi

7、ning and Technology运筹学 231000CBXBbx1x2x3x4x5x60X41513110050X51823-101060X631-11001-j02310003X251/311/31/300150X5310-2-11030X684/304/31/3016-15100-100改改 进进 的的 单单 纯纯 形形 法法-12-China University of Mining and Technology运筹学 231000CBXBbx1x2x3x4x5x63X251/311/31/300150X5310-2-11030X684/304/31/3016j-15100-100

8、0X240112/3-1/3041X1310-2-110-0X640045/3-4/311j-180020-10改改 进进 的的 单单 纯纯 形形 法法-13-China University of Mining and Technology运筹学 设设设设mm mm系数矩阵系数矩阵系数矩阵系数矩阵A A，求其逆矩阵，求其逆矩阵，求其逆矩阵，求其逆矩阵可以先从第可以先从第可以先从第可以先从第1 1列开始列开始列开始列开始:以下介绍一种比较简便的计算方法以下介绍一种比较简便的计算方法求解线性规划问题的关键是计算求解线性规划问题的关键是计算B-1改改 进进 的的 单单 纯纯 形形 法法-14-Ch

9、ina University of Mining and Technology运筹学 以以a11为主元素为主元素,进行变换进行变换然后构造含有（然后构造含有（1）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵改改 进进 的的 单单 纯纯 形形 法法-15-China University of Mining and Technology运筹学 可得到：可得到：可得到：可得到：而后以第而后以第2列的列的a22(1)为主元素，进行变换为主元素，进行变换改改 进进 的的 单单 纯纯 形形 法法-16-China University of Mining and Technology运筹学

10、 然后构造含有（然后构造含有（然后构造含有（然后构造含有（2 2）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵）列，而其他列都是单位列的矩阵 可得到可得到改改 进进 的的 单单 纯纯 形形 法法-17-China University of Mining and Technology运筹学 重复以上的步骤，直到获得重复以上的步骤，直到获得重复以上的步骤，直到获得重复以上的步骤，直到获得求单纯形表的基矩阵的逆矩阵也可以用这方法。求单纯形表的基矩阵的逆矩阵也可以用这方法。改改 进进 的的 单单 纯纯 形形 法法书上例题自学。书上例题自学。-18-Chin

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

12、样提出的，为什么会产生这样一种问题呢？题是怎样提出的，为什么会产生这样一种问题呢？对偶问题的提出对偶问题的提出-20-China University of Mining and Technology运筹学 俩家具制造商间的对话：俩家具制造商间的对话：唉唉!我想租您的木工和我想租您的木工和油漆工一用。咋样？价油漆工一用。咋样？价格嘛格嘛好说，肯定不好说，肯定不会让您兄弟吃亏。会让您兄弟吃亏。王老板做家王老板做家具赚了大钱，具赚了大钱，可惜我老李可惜我老李有高科技产有高科技产品，却苦于品，却苦于没有足够的没有足够的木工和油漆木工和油漆工咋办？只工咋办？只有租咯。有租咯。Hi：王老板，听：王老板，

13、听说近来家具生意说近来家具生意好呀，也帮帮兄好呀，也帮帮兄弟我哦弟我哦!家具生意还真赚钱，家具生意还真赚钱，但是现在的手机生但是现在的手机生意这么好，不如干意这么好，不如干脆把我的木工和油脆把我的木工和油漆工租给他，又能漆工租给他，又能收租金又可做生意。收租金又可做生意。价格嘛价格嘛好商量，好商量，好商量。只好商量。只是是.王王 老老 板板李李 老老 板板引例引例1对偶问题的提出对偶问题的提出-21-China University of Mining and Technology运筹学 王老板的王老板的家具生产模型家具生产模型：x1、x2是桌、椅生产量。是桌、椅生产量。Z是家具销售总收入（总

14、利润）。是家具销售总收入（总利润）。max Z=50 x1+30 x2s.t.4x1+3x2 120（木工）（木工）2x1+x2 50（油漆工）（油漆工）x1，x2 0原始线性规划问题，记为（原始线性规划问题，记为（P）王老板的王老板的资源出租模型资源出租模型：y1、y2单位木、漆工出租价格。单位木、漆工出租价格。W是资源出租租金总收入。是资源出租租金总收入。min W=120y1+50y2s.t.4y1+2y2 50 3y1+y2 30 y1，y2 0对偶线性规划问题，记为（对偶线性规划问题，记为（D）1.所得不得低于生产的获利所得不得低于生产的获利（不吃亏原则）（不吃亏原则）2.要使对方能

15、够接受要使对方能够接受3.（竞争性原则）（竞争性原则）两个原则两个原则对偶问题的提出对偶问题的提出-22-China University of Mining and Technology运筹学 王老板按（王老板按（D D）的解）的解 y1、y2出租其拥有的木、漆工资源，出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金力（李老板所付出的总租金WW最少）。最少）。按时下最流行的一个词，叫什

16、么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着按时下最流行的一个词，叫什么来着对偶问题的提出对偶问题的提出-23-China University of Mining and Technology运筹学 Max Z=40 x1+50 x2 x1+2x2 30 3x1+2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件设三种资源的使用单价分别为设三种资源的使用单价分别为 y1,y2,y3y1 y2 y3生产单位产品生产单位产品A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A的获利的获利生产单位产品生产单位产品B的资源消耗所得不少于

17、单位产品的资源消耗所得不少于单位产品B的获利的获利y1+3 y2 40 2y1+2 y2+2y3 50甲甲乙乙资源量资源量A1230B3260C0224单位获利单位获利4050引例引例2通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W=30y1+60 y2+24y3对偶问题的提出对偶问题的提出-24-China University of Mining and Technology运筹学 根据原则根据原则2，对方能够接受的价格显然是越低越好，因此，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：此问题可归结为以下数学模型：Min W=30y1+60

18、y2+24y3 y1+3y2 402y1+2 y2+2y3 50y1,y2,y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题，此问题为此问题为对偶问题对偶问题，y1,y2,y3为为对偶变量对偶变量，也称为，也称为影子价格影子价格对偶问题的提出对偶问题的提出-25-China University of Mining and Technology运筹学 2.4 2.4 线性规划的对偶理论线性规划的对偶理论-26-China University of Mining and Technology运筹学 Max Z=40 x1+50 x2 x1+2x2

19、30 3x1+2x2 60 2x2 24 x1，x2 0s.t原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）一、一、一、一、原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系Min W=30y1+60 y2+24y3 y1+3y2 402y1+2 y2+2y3 50y1,y2,y3 0s.t（y1）（y2）（y3）（x1）13040（x2）22250306024minmaxz3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量线性规划的对偶理论线性规划的对偶理论-27-China Univer

20、sity of Mining and Technology运筹学 对偶问题的形式对偶问题的形式定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题l为其对偶问题，其中为其对偶问题，其中yi(i=1,2,m)称为称为对偶变量对偶变量l上述对偶问题称为上述对偶问题称为对称型对称型对称型对称型对偶问题对偶问题l原问题简记为原问题简记为(P)，对偶问题简记为对偶问题简记为(D)称问题称问题(P)和和(D)为为一对对偶问题一对对偶问题线性规划的对偶理论线性规划的对偶理论-28-China University of Mining and Technology运筹学 对

21、称型问题的对偶规则对称型问题的对偶规则对称型问题的对偶规则对称型问题的对偶规则1、给每个原始约束条件定义一个非负对偶变量、给每个原始约束条件定义一个非负对偶变量yi(i=1,2,m)；2、使原问题的目标函数系数、使原问题的目标函数系数 cj 变为其对偶问题约束条变为其对偶问题约束条 件的右端常数；件的右端常数；3、使原问题约束条件的右端常数、使原问题约束条件的右端常数 bi 变为其对偶问题目变为其对偶问题目 标函数的系数；标函数的系数；4、将原问题约束条件的系数矩阵转置，得到其对偶问、将原问题约束条件的系数矩阵转置，得到其对偶问 题约束条件的系数矩阵；题约束条件的系数矩阵；5、改变约束问题不等

22、号的方向，即将、改变约束问题不等号的方向，即将“”改为改为“”；6、原问题为、原问题为“max”型，对偶问题为型，对偶问题为“min”型。型。线性规划的对偶理论线性规划的对偶理论-29-China University of Mining and Technology运筹学 原始原始问题问题Max Z=CXs.t.AXbX 0bACMaxnm对偶问题对偶问题Min W=Ybs.t.YACY 0MinCATbnmY为行向量为行向量线性规划的对偶理论线性规划的对偶理论-30-China University of Mining and Technology运筹学 当原问题为求极小值时，对偶问题为求

23、极大值。当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决

24、定对偶问题变量的原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。的约束方程的匹配形式。线性规划的对偶理论线性规划的对偶理论-31-China University of Mining and Technology运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知为对称型对偶问题解：由原问题的结构可知为对称型对偶问题例例1线性规划的对偶理论线性规划的对偶理论-32-China University of Mining and Technology运筹学 求线

25、性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。对称型，再求其对偶规划。例例2线性规划的对偶理论线性规划的对偶理论-33-China University of Mining and Technology运筹学 求线性规划问题的求线性规划问题的对偶规划对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。对称型，再求其对偶规划。例例3线性规划的对偶理论线性规划的对偶理论-34-China Unive

26、rsity of Mining and Technology运筹学 上式已为对称型对偶问题，故可写出它的对偶规划上式已为对称型对偶问题，故可写出它的对偶规划令令则上式化为则上式化为线性规划的对偶理论线性规划的对偶理论-35-China University of Mining and Technology运筹学 q对偶问题的非对称形式对偶问题的非对称形式min z=2x1+4x2-x3s.t.3x1-x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2 -y1+2y

27、2+y3+3y4 4 2y1-3y2+2y3-y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3:unrq原始问题变量的个数原始问题变量的个数(3)等于对偶问题约束条件的个数等于对偶问题约束条件的个数(3)；原始问题约束条件的个数原始问题约束条件的个数(4)等于对偶问题变量的个数等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用原始问题变量的性质影响对偶问题约束条件的性质，用 表示表示 原始问题约束条件的性质影响对偶问题变量的性质，用原始问题约束条件的性质影响对偶问题变量的性质，用 表示表示线性规划的对偶理论线性规划的对偶理论-36-C

28、hina University of Mining and Technology运筹学 1 原问题为原问题为“max”，对偶问题为，对偶问题为“min”；2 原问题中目标函数系数原问题中目标函数系数 ci 变为其对偶问题约束条件的右端常数；变为其对偶问题约束条件的右端常数；3 原问题约束条件的右端常数原问题约束条件的右端常数 bi 变为其对偶问题目标函数的系数；变为其对偶问题目标函数的系数；4 原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；原问题约束条件的系数矩阵转置，即为其对偶问题的系数矩阵；5 原问题的变量个数原问题的变量个数n等于其对偶问题的约束条件个数等于其对偶问题的约束条件

29、个数n，原问题，原问题 约束约束条件的个数条件的个数m等于其对偶问题变量的个数等于其对偶问题变量的个数m；6 在求极大值的原问题中，在求极大值的原问题中，“”，“”和和“=”的约束条件分别的约束条件分别对应其对偶变量对应其对偶变量“0”，“0”和和“无符号限制无符号限制”；7 在求极大值的原问题中，变量在求极大值的原问题中，变量“0”，“0”和和“无符号限制无符号限制”分别对应其对偶约束条件的分别对应其对偶约束条件的“”，“”和和“=”约束约束.混合型问题的对偶规则：混合型问题的对偶规则：线性规划的对偶理论线性规划的对偶理论-37-China University of Mining and

30、Technology运筹学 原问题（或对偶问题）对偶问题（或原问题）约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项目标函数max目标函数min约束条件m个m个变量00=无约束变量n个n个约束条件00无约束=线性规划的对偶理论线性规划的对偶理论-38-China University of Mining and Technology运筹学 Max Z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0s.ty1y2y3Min W=30y1+60y2+24y3 y1+3y2+0y3 402y1+2y2+2y3 50 y1,y2,y3

31、0 0s.tMax W=-30y1-60y2-24y3 y1+3y2+0y3 y4=402y1+2y2+2y3 y5=50 y1,y2,y3,y4,y5 0 0s.t例例4二、二、二、二、对偶问题的解对偶问题的解对偶问题的解对偶问题的解线性规划的对偶理论线性规划的对偶理论-39-China University of Mining and Technology运筹学 Max W=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7)y1+3y2+0y3 y4+y6=402y1+2y2+2y3 y5+y7=50 y1,y2,y3,y4,y5 0 0s.tcj-30-60-2400-M

32、-MB-1bcByBy1y2y3y4y5y6y7-My6130-10104040/3-My72220-1015050/2j3M-305M-602M-24-M-M00-90M线性规划的对偶理论线性规划的对偶理论-40-China University of Mining and Technology运筹学 cj-30-60-2400-M-MB-1bcByBy1y2y3y4y5y6y7-60y21/310-1/301/3040/3-My74/3022/3-1-2/3170/335/3j4M/3-1002M-242M/3+20-M-5M/3+200800-70M/3-60y21/310-1/301/

33、3040/340-24y32/3011/3-1/2-1/31/235/335/2j600-12-12-M+12-M+12-1080-60y201-1/2-1/21/41/2-1/415/2-30y1103/21/2-3/4-1/23/435/2j00-9-15-15/2-M+30-M-15/2-975线性规划的对偶理论线性规划的对偶理论-41-China University of Mining and Technology运筹学 cj4050000 B-1bcBxBx1x2x3x4x540 x1101/2-1/20150 x5003/2-1/21950 x201-3/41/4015/2j00

34、-35/2-15/20975 Max Z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0s.t x1+2x2+x3=303x1+2x2+x4=60 2x2+x5=24 x1 x5 0 0s.t线性规划的对偶理论线性规划的对偶理论-42-China University of Mining and Technology运筹学 线性规划的对偶理论线性规划的对偶理论-43-China University of Mining and Technology运筹学 原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，

35、对偶问题的剩余变量对应原问题的变量。线性规划的对偶理论线性规划的对偶理论-44-China University of Mining and Technology运筹学 XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x115101/2-1/20 x59003/2-1/21x215/2013/4-1/4000-35/2-15/20YBb对偶问题对偶问题的变量的变量对偶问题的对偶问题的剩余变量剩余变量y1y2y3y4y5y215/201-1/2-1/21/4y135/2103/21/2-3/400-9-15-15/2原问原问题最题最优表优表对偶对偶问题问题最优最

36、优表表 Max Z=40 x1+50 x2 x1+2x2 303x1+2x2 60 2x2 24 x1,x2 0 0s.tMin W=30y1+60y2+24y3 y1+3y2+0y3 402y1+2y2+2y3 50 y1,y2,y3 0 0s.t线性规划的对偶理论线性规划的对偶理论-45-China University of Mining and Technology运筹学 性质性质1 对称性定理对称性定理：对偶问题的对偶是原问题：对偶问题的对偶是原问题 min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0三、三、三、三、对偶原理对偶原理对偶原理对偶原理线性

37、规划的对偶理论线性规划的对偶理论-46-China University of Mining and Technology运筹学 min z=-CXs.t.-AX-bX 0maxw=-Ybs.t.-YA-C Y 0min w=Ybs.t.YAC Y 0max z=CXs.t.AXb X 0对偶的对偶的定义定义对偶的对偶的定义定义简要证明：简要证明：线性规划的对偶理论线性规划的对偶理论-47-China University of Mining and Technology运筹学 性质性质2 弱对偶原理弱对偶原理(弱对偶性弱对偶性)：设设 和和 分别是问题分别是问题(P)和和(D)的可行解，则必

38、有的可行解，则必有推论推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。标函数值的上界。证明：证明：(1)当当X和和Y为原问题和对偶问题的一个可行解为原问题和对偶问题的一个可行解有有原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值线性规划的对偶理论线性规划的对偶理论-48-China University of Mining and Technology运筹学 推论推论2:在一对对偶问题（在

39、一对对偶问题（P）和（）和（D）中，若其中一个问题可行但）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；目标函数无界，则另一个问题无可行解；反之不成立反之不成立。这也是对这也是对偶问题的偶问题的无界性无界性无界性无界性。若（若（P）为无界解，则（）为无界解，则（D）无可行解；）无可行解；若（若（D）为无界解，则（）为无界解，则（P）无可行解。）无可行解。线性规划的对偶理论线性规划的对偶理论推论推论3：在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若一个可行（如）中，若一个可行（如P），），而另一个不可行（如而另一个不可行（如D），则该可行的问题目标函数值无界。），则该可行

40、的问题目标函数值无界。-49-China University of Mining and Technology运筹学 已知原问题已知原问题(LP)，试估计它的目标函数值的界试估计它的目标函数值的界,并验证弱对偶定理并验证弱对偶定理.例例5线性规划的对偶理论线性规划的对偶理论-50-China University of Mining and Technology运筹学 解：解：解：解：问题问题(LP)的对偶问题的对偶问题(DP)为为(DP)线性规划的对偶理论线性规划的对偶理论-51-China University of Mining and Technology运筹学 由观察可知由观察可知

41、 分别是原问题和对偶问题的可行解。分别是原问题和对偶问题的可行解。，弱对偶定理成立。，弱对偶定理成立。且由推论且由推论1知，对偶问题目标函数知，对偶问题目标函数W的下界为的下界为10，原问题目，原问题目标函数标函数Z的上界为的上界为40。且原问题的目标函数值为且原问题的目标函数值为对偶问题的目标函数值为对偶问题的目标函数值为故故线性规划的对偶理论线性规划的对偶理论-52-China University of Mining and Technology运筹学 例：利用对偶性质判断下面问题有无最优解例：利用对偶性质判断下面问题有无最优解例例6解：此问题的对偶问题为解：此问题的对偶问题为不能成立，

42、因此对偶问题不不能成立，因此对偶问题不可行。故由推论可行。故由推论3知原问题知原问题无界。无界。为可行解为可行解线性规划的对偶理论线性规划的对偶理论-53-China University of Mining and Technology运筹学 性质性质3 最优性定理：最优性定理：如果如果 是原问题的可行解，是原问题的可行解，是其对偶是其对偶问题的可行解，并且问题的可行解，并且:则则 是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。线性规划的对偶理论线性规划的对偶理论-54-China University of Mining and Technology运筹学

43、 性质性质4 强强(主主)对偶性：对偶性：若原问题及其对偶问题均具有可行解，若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。则两者均具有最优解，且它们最优解的目标函数值相等。还可推出另一结论：还可推出另一结论：若一对对偶问题中的任意一个有最优解，若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等；若一个问题则另一个也有最优解，且目标函数最优值相等；若一个问题无最优解，则另一问题也无最优解。无最优解，则另一问题也无最优解。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.都有最优解，且目标函数最优值相等；

44、都有最优解，且目标函数最优值相等；2.两个都无可行解；两个都无可行解；3.一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。线性规划的对偶理论线性规划的对偶理论-55-China University of Mining and Technology运筹学 证明：证明：当当X*为原问题的一个最优解，为原问题的一个最优解，B为相应的最优基，通过引为相应的最优基，通过引入松弛变量入松弛变量Xs，将问题，将问题(P)转化为标准型转化为标准型令令CCBCN0解解基系数基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1bCXAC-C

45、BB-1A说明说明Y*可行可行线性规划的对偶理论线性规划的对偶理论-56-China University of Mining and Technology运筹学 问题问题:（1）由性质）由性质4可知，对偶问题最优解的表达式可知，对偶问题最优解的表达式 Y*=?（2）求）求 Y*是否有必要重新求解是否有必要重新求解(D)?不必。可以从原问题（不必。可以从原问题（P）的单纯形终表获得。）的单纯形终表获得。CCBCN0解解基系数基系数基变量基变量XBXNXsCBXBIB-1NB-1B-1b0CN-CBB-1N-CBB-1CBB-1b线性规划的对偶理论线性规划的对偶理论-57-China Unive

46、rsity of Mining and Technology运筹学 性质性质5 互补松弛性互补松弛性：设：设X0和和Y0分别是分别是P问题问题 和和 D问题问题 的可行的可行解，则它们分别是最优解的充要条件是：解，则它们分别是最优解的充要条件是：其中：其中：Xs、Ys为松弛变量为松弛变量。在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。的变量一定为零。紧约束与紧约束与

47、紧约束与紧约束与松约束松约束松约束松约束线性规划的对偶理论线性规划的对偶理论-58-China University of Mining and Technology运筹学 一个约束称为一个约束称为紧约束紧约束，如果该约束在，如果该约束在所有最优解所有最优解上的值使左右上的值使左右取等号。取等号。即我们把严格等式约束称为紧约束（或起作用约束）即我们把严格等式约束称为紧约束（或起作用约束）.不是紧约束的约束称为不是紧约束的约束称为松约束松约束。即把即把某一最优解某一最优解处取严格不等式的约束称为松约束（或不起处取严格不等式的约束称为松约束（或不起作用约束）。作用约束）。对于最优解对于最优解X*和

48、和Y*而言，而言，松约束的对偶约束是紧约束松约束的对偶约束是紧约束.以上关系称为对偶问题的以上关系称为对偶问题的互补松弛关系互补松弛关系或或松紧关系松紧关系。在计算上，。在计算上，若已知一个问题的最优解，则可利用互补松弛条件求另一个问若已知一个问题的最优解，则可利用互补松弛条件求另一个问题的最优解题的最优解.紧约束与松约束紧约束与松约束紧约束与松约束紧约束与松约束松紧关系松紧关系非常重要非常重要线性规划的对偶理论线性规划的对偶理论-59-China University of Mining and Technology运筹学 证证:(:(必要性）必要性）原问题原问题 对偶问题对偶问题线性规划的

49、对偶理论线性规划的对偶理论-60-China University of Mining and Technology运筹学 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0线性规划的对偶理论线性规划的对偶理论-61-China University of Mini

50、ng and Technology运筹学 性质性质5的应用：的应用：该性质给出了已知一个问题最优解求另一个问题最优解该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知的方法，即已知Y求求X或已知或已知X求求Y互补松弛条件互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系：若若Y0，则，则Xs必为必为0；若；若X0，则，则Ys必为必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优