运筹学课件第2章 线性规划的对偶理论

第1页5-4单纯形法计算的向量矩阵描述CXzmax0..XbAXts线性规划的标准形式初始单纯形表初始解非基变量基变量bBAIcj-zjN0,…,0基可行解基变量非基变量B-1bIB-1AB-1cj-zj0,…,0-y1,…,-ymN1110),,(BCBCyyYBBm关系：AYCABCCBN1CBC0CBC0CYACAYY0CB0..XbXAXtsa最终单纯形表第2页2132maxxxz122221xx1641x1552x0,21xxs.t.例1用单纯形法求解线性规划问题解：将上述问题化为标准形式5432100032maxxxxxxz)5,,1(01551641222..5241321jxxxxxxxxtsj第3页cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj23000[]cj→23000CB基bx1x2x3x4x5cj-zjx3x4x2003301001/5164001062010-2/52000-3/5[]BNx1x2x3x4x2x3x4x50x362010010-2/50x416400100103x2301001001/52000000-3/5x1x2x3x4x2x3x4x50x312221021000x416400100100x5150500500123003000B-1B-1NB-1bNY1+BY2+Y3=bB-1NY1+Y2+B-1Y3=B-1b-CBB-1II第4页cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj230000x40100cj→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj-zj00-10-1/50x40100),,(),,,(543241PPPIPPPB5/1005/4125/102/11B3431516125/1005/4125/102/11bB5/1005/4125/102/13021BCB5/101b),,(1myy第5页cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj23000[]cj→23000CB基bx1x2x3x4x5cj-zjx3x4x2003301001/5164001062010-2/52000-3/5[]cj→23000CB基bx1x2x3x4x5cj-zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/5第6页5-4单纯形法计算的向量矩阵描述CXzmax0..XbAXts线性规划的标准形式初始单纯形表初始解非基变量基变量bBAIcj-zjN0,…,0基可行解基变量非基变量B-1bIB-1AB-1cj-zj0,…,0-y1,…,-ymN1110),,(BCBCyyYBBm关系：AYCABCCBN1CBC0CBC0CYACAYY0CB0..XbXAXtsa最终单纯形表第7页cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj230000x40100cj→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj-zj00-10-1/50x40100),,(),,,(543241PPPIPPPB5/1005/4125/102/11B3431516125/1005/4125/102/11bB5/1005/4125/102/13021BCB5/101b),,(1myy第8页线性规划问题具有对偶性,即任何一个线性规划问题,都存在另一个线性规划问题与之对应.如果把其中一个问题叫做原问题,则另外一个就叫做它的对偶问题.并称这两个相互联系的问题为一对对偶问题.研究对偶问题之间的关系及其性质,就是线性规划的对偶理论(DualityTheory).第2章线性规划的对偶理论第9页§1对偶问题的提出§2原问题与对偶问题§3对偶问题的基本性质§4影子价格§5对偶单纯形法§6灵敏度分析§7参数线性规划第10页常山机器厂用A、B、C三种设备生产I、II两种产品。问该企业应如何安排生产使总的利润收入为最大。占用设备时间(h)III用于生产的能力设备A2212设备B4016设备C0515利润(元)23例1生产计划问题2-1对偶问题的提出模型2132maxxx122221xx1641x1552x0,21xxs.t.现有四海机器厂,为扩大生产想租常山机器厂的设备,问常山机器厂分别以每小时什么价格才愿意出租自己的设备呢?设设备A,B,C每小时的出租价格分别为y1,y2,和y3元出租条件:租金收入≥生产的获利。四海机器厂接受条件:租金要低0,,352242151612min3213121321yyyyyyyyyywLP1LP2第11页2132maxxx122221xx1641x1552x0,21xxs.t.0,,352242151612min3213121321yyyyyyyyyywLP2模型LP1矩阵形式见P54-P55第12页原始问题Maxz=CXs.t.AX≤bX≥0对偶问题Minw=bTYs.t.ATY≥CTY≥0≤maxbACCTATbT≥maxmnmn对偶的定义第13页规范对偶问题minz=CXs.t.AX≥bX≥0maxw=bTYs.t.ATY≤CY≥0maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0第14页2-2原问题与对偶问题对应关系：minmax(1)(2)变量的个数约束条件个数=(3)(原)约束条件≤(4)右端项目标函数的系数(对偶)约束条件≥第15页原问题对偶问题),,1(0),,1(..min11miynjcyatsybwimijijimiii一般形式0..minYCYAtsYbw矩阵形式0..maxXbAXtsCXz),,1(0),,1(..max11njxmibxatsxczjnjijijnjjj第16页【例】写出下列线性规划的对偶问题0,,15744325min321321321321xxxxxxxxxxxxZ【解】这是一个规范形式的线性规划，设Y=（y1，y2），则有)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyAYyyyybYw，－－线性规划的对偶模型DualmodelofLP第17页从而对偶问题为0,03527544max2121212121yyyyyyyyyyZ对偶变量yi也可写成xi的形式。)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyAYyyyybYw，－－线性规划的对偶模型DualmodelofLP第18页【例】写出下列线性规划的对偶问题0,01038576534max2121212121xxxxxxxxxxZ【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“≥”约束，即3,2,1,03324751086min321321321iyyyyyyyyyywi线性规划的对偶模型DualmodelofLP第19页若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表2-2中的对应关系写出非规范形式的对偶问题。将上述原问题与对偶问题的对应关系列于表2-2例如，原问题是求最小值，按表2-2有下列关系：1.第i个约束是“≤”约束时，第i个对偶变量yj≤02．第i个约束是“=”约束时，第i个对偶变量yi无约束；3．当xj≤0时，第j个对偶约束为“≥”约束，当xj无约束时，第j个对偶约束为“=”约束。线性规划的对偶模型DualmodelofLP第20页原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数系数约束条件右端项约束条件系数矩阵A(AT)目标函数min约束条件右端项目标函数系数约束条件系数矩阵AT(A)变量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约束n个约束第j个约束为≥第j个约束为≤第j个约束为=约束m个约束第i个约束≤第i个约束≥第i个约束为=变量m个变量第i个变量≥0第i个变量≤0第i个变量无约束线性规划的对偶模型DualmodelofLP第21页对偶问题原问题原问题对偶问题),,1(0),,1(..min11miynjcyatsybwimijijimiii一般形式0..minYCYAtsYbw矩阵形式0..maxXbAXtsCXz),,1(0),,1(..max11njxmibxatsxczjnjijijnjjj第22页2-2原问题与对偶问题对应关系：minmax(1)(2)变量的个数约束条件个数=(3)(原)约束条件≤(4)右端项目标函数的系数(对偶)约束条件≥(4)目标函数的系数(4)(4)系数矩阵AT(5)系数矩阵A第23页原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数系数约束条件右端项约束条件系数矩阵A(AT)目标函数min约束条件右端项目标函数系数约束条件系数矩阵AT(A)变量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约束n个约束第j个约束为≥第j个约束为≤第j个约束为=约束m个约束第i个约束≤第i个约束≥第i个约束为=变量m个变量第i个变量≥0第i个变量≤0第i个变量无约束线性规划的对偶模型DualmodelofLP第24页0,0837435522..)1(365max32321321321321xxxxxxxxxxxtsxxxz321835minyyyw无约束1y02y03y54321yyy6752321yyy332321yyy写出下列线性规划的对偶问题第25页),,1(),,1(0),,1(),,1(..)2(max1111111nnjxnnjxmmibxammibxatsxczjjnjijijnjijijnjjj无约束miiiybw1min),,1(01miyi),,1(1mmiyi无约束mijijinjcya11),,1(mijijinnjcya11),,1(第26页321365maxxxxz00332675254..)3(835min32321321321321yyyyyyyyyyytsyyyw03x35321xxx无约束1x02x8374321xxx522321xxx无约束