第三章+线性规划的对偶问题VIP免费

1第三章线性规划的对偶问题对偶线性规划对偶定理对偶单纯形法第一节对偶问题对偶问题概念：任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者就称为“对偶”问题。对偶问题是对原问题从另一角度进行的描述其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。3对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。对偶线性规划设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）32304假设计划期内甲乙两种产品各生产吨，1212121212maxZ=32x+30x3x+4x365x+4x409x+8x76x0,x012x,x设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230用图解法或单纯形法可求得最优解(元)即在计划期内甲产品生产吨，乙产品生产8吨，可以使总利润达到最大，为元。4*X=(,8)32maxZ=282322823435现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设分别为设备A，B，C每台时的租价，•约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润•目标函数：所获租金总额尽量少．（价格应该尽量低，这样，才能有竞争力）•价格应该是非负的123y,y,y1231231233y+5y+9y324y+4y+8y30y0,y0,y0123minW=36y+40y+76y6由此可得两个对称的线性规划：1212121212maxZ=32x+30x3x+4x365x+4x409x+8x76x0,x04*X=(,8)3T2maxZ=2823123123123123minW=36y+40y+76y3y+5y+9y324y+4y+8y30y0,y0,y0719*Y=(,0,)662minW=2823设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）32307123123123yminW=(36,40,76)yyy35932y44830yyy0y121212xmaxZ=(32,30)x3436x5440x9876x0x矩阵形式：8可以得到另一个线性规划：称之为原线性规划问题的对偶问题，对偶线性规划TminZ=CXAXbX0TTmaxW=bACY0YY考虑如下具有不等式约束的线性规划问题9定理：若线性规划问题（LP）的第(1)kkm个约束为等式约束，即1122kkknnkaxaxaxb则其对偶线性规划（DP）的第k个变量ky为自由变量。证明：等式约束等价于1122kkknnkaxaxaxb1122kkknnkaxaxaxb则LP为1122minnnzcxcxcxs.t.111122111nnaxaxaxby1122'kkknnkkaxaxaxby1122"kkknnkkaxaxaxby1122mmmnnmmaxaxaxby12,,,0nxxx10111122111nnaxaxaxby……………1122'kkknnkkaxaxaxby1122"kkknnkkaxaxaxby……………1122mmmnnmmaxaxaxby则DP为11max'"kkkkmmwbybybybys.t.1111111'"kkkkmmayayayayc11'"lklkklkmlmlayayayayc11'"nknkknkmnmnayayayayc1,,',",,0kkmyyyy令'"kkkyyy，则ky为自由变量。11推论：若线性规划问题（LP）的第(1)kkm个变量ky为自由变量，则其对偶线性规划（DP）的第个约束为等式约束。12若令线性规划标准型的对偶规划为：线性规划问题标准型的对偶问题TminZ=CXAbX-A-bX01TTT1221TTT12211YmaxW=(b,-b)=b(Y-Y)YY(A,-A)=A(Y-Y)C...