运筹学第2章对偶理论

《运筹学第2章对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter2对偶理论(DualityTheory)单纯形法的矩阵描述对偶问题的提出线性规划的对偶理论对偶问题的经济解释－影子价格对偶单纯形法灵敏度分析(选讲)掌握WinQSB软件求解对偶规划本章主要内容：√√√学习要点：1.理解对偶理论，掌握描述一个线性规划问题的对偶问题。2.能够运用对偶单纯形法来求解线性规划问题。3.会用互补松弛条件来考虑一对对偶问题的界。4.了解影子价格、灵敏度分析以及用WinQSB求解对偶规划问题。2.1单纯形法的矩阵描述0.16-0.120102412x2-0.20.4001207

2、x11.16-3.12100840x3-1.20003.41000.10010,33012x220-0.51002.5500x430.8-0.40107.82400x3000127301001033000x540010542000x490001493600x3ɵx5x4x3x2x1B-1bCBXB每一列的含义？每个表中的B和B-1的查找？单纯形法的矩阵描述单纯形法的矩阵描述单纯形法的矩阵描述CBCNbXBXNbBNCBCNbXBXNB-1bIB-1N-CBB-1b0CN-CBB-1N单纯形法的矩阵描述CBCNC

3、S(0)bXBXNXSbBNI0CBCN0CBCNCS(0)bXBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1单纯形法的矩阵描述2.3对偶问题的提出对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？对偶问题的提出俩家具制造商间的对话：唉!我想租您的木工和油漆工一用。咋样？价格嘛……好说，肯定

4、不会让您兄弟吃亏。王老板做家具赚了大钱，可惜我老李有高科技产品，却苦于没有足够的木工和油漆工咋办？只有租咯。Hi：王老板，听说近来家具生意好呀，也帮帮兄弟我哦!家具生意还真赚钱，但是现在的手机生意这么好，不如干脆把我的木工和油漆工租给他，又能收租金又可做生意。价格嘛……好商量，好商量。只是…...王老板李老板引例1对偶问题的提出王老板的家具生产模型：x1、x2是桌、椅生产量。Z是家具销售总收入（总利润）。maxZ=50x1+30x2s.t.4x1+3x2≤120（木工）2x1+x2≤50（油漆工）x1，x2≥0

5、原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。minW=120y1+50y2s.t.4y1+2y2≥503y1+y2≥30y1，y2≥0对偶线性规划问题，记为（D）所得不得低于生产的获利（不吃亏原则）要使对方能够接受（竞争性原则）两个原则对偶问题的提出王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行

6、的一个词，叫什么来着————对偶问题的提出MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目标函数约束条件设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y2402y1+2y2+2y350甲乙资源量A1230B3260C0224单位获利4050引例2通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3对偶问题的提出根据原则2，对方

7、能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：MinW=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3为对偶变量，也称为影子价格对偶问题的提出2.4线性规划的对偶理论MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t原问题（对偶问题）对偶问题（原问题）一、原问题与对偶问题的对应关系MinW=30y1+60y2+24y3y

8、1+3y2402y1+2y2+2y350y1,y2,y30s.t（y1）（y2）（y3）（x1）13040（x2）22250306024minωmaxz3个约束2个变量2个约束3个变量线性规划的对偶理论对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量上述对偶问题称为对称型对偶问题原问题简记为(P)，对偶问题简记为(D