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

《运筹学课件第2章 线性规划的对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、5-4单纯形法计算的向量矩阵描述线性规划的标准形式初始单纯形表初始解非基变量基变量bBAIcj-zjN0,…,0基可行解基变量非基变量B-1bIB-1AB-1cj-zj0,…,0-y1,…,-ym关系：CBC0CBC0CB最终单纯形表s.t.例1用单纯形法求解线性规划问题解：将上述问题化为标准形式cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj23000[]cj→23000CB基bx1x2x3x4x5cj-zjx3x4x20033

2、01001/5164001062010-2/52000-3/5[]BNx1x2x3x4x2x3x4x50x362010010-2/50x416400100103x2301001001/52000000-3/5x1x2x3x4x2x3x4x50x312221021000x416400100100x5150500500123003000B-1B-1NB-1bNY1+BY2+Y3=bB-1NY1+Y2+B-1Y3=B-1b-CBB-1IIcj→23000CB基bx1x2x3x4x50x312221000

3、x416400100x51505001cj-zj230000x40100cj→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj-zj00-10-1/50x40100cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj23000[]cj→23000CB基bx1x2x3x4x5cj-zjx3x4x2003301001/5164001062010-2/52000-3/5[]c

4、j→23000CB基bx1x2x3x4x5cj-zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/55-4单纯形法计算的向量矩阵描述线性规划的标准形式初始单纯形表初始解非基变量基变量bBAIcj-zjN0,…,0基可行解基变量非基变量B-1bIB-1AB-1cj-zj0,…,0-y1,…,-ym关系：CBC0CBC0CB最终单纯形表cj→23000CB基bx1x2x3x4x50x312221000x416400100x51505001cj-zj2300

5、00x40100cj→23000CB基bx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5cj-zj00-10-1/50x40100线性规划问题具有对偶性,即任何一个线性规划问题,都存在另一个线性规划问题与之对应.如果把其中一个问题叫做原问题,则另外一个就叫做它的对偶问题.并称这两个相互联系的问题为一对对偶问题.研究对偶问题之间的关系及其性质,就是线性规划的对偶理论(DualityTheory).第2章线性规划的对偶理论§1对偶问题的提出§2原问题与对偶

6、问题§3对偶问题的基本性质§4影子价格§5对偶单纯形法§6灵敏度分析§7参数线性规划常山机器厂用A、B、C三种设备生产I、II两种产品。问该企业应如何安排生产使总的利润收入为最大。占用设备时间(h)III用于生产的能力设备A2212设备B4016设备C0515利润(元)23例1生产计划问题2-1对偶问题的提出模型s.t.现有四海机器厂,为扩大生产想租常山机器厂的设备,问常山机器厂分别以每小时什么价格才愿意出租自己的设备呢?设设备A,B,C每小时的出租价格分别为y1,y2,和y3元出租条件:租金收入

7、≥生产的获利。四海机器厂接受条件:租金要低LP1LP2s.t.LP2模型LP1矩阵形式见P54-P55原始问题Maxz=CXs.t.AX≤bX≥0对偶问题Minw=bTYs.t.ATY≥CTY≥0≤maxbACCTATbT≥maxmnmn对偶的定义规范对偶问题minz=CXs.t.AX≥bX≥0maxw=bTYs.t.ATY≤CY≥0maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥02-2原问题与对偶问题对应关系：(1)(2)变量的个数约束条件个数=(3)(原)约束条件

8、≤(4)右端项目标函数的系数(对偶)约束条件≥原问题对偶问题一般形式矩阵形式【例】写出下列线性规划的对偶问题【解】这是一个规范形式的线性规划，设Y=（y1，y2），则有线性规划的对偶模型DualmodelofLP从而对偶问题为对偶变量yi也可写成xi的形式。线性规划的对偶模型DualmodelofLP【例】写出下列线性规划的对偶问题【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“≥”约束，即线性规划的对偶模型DualmodelofLP若给出的线性规