第3章 对偶模型.pptxVIP

第3章 对偶模型 主讲：范建平 博士3.1 线性规划的对偶关系3.1.1 对偶问题【例3-1】考虑范例，这是一个分配三种有限资源(即A、B、C三个车间每周最大生产能力6、8、18个工时)于两项生产活动(即生产甲、乙两种产品)的资源分配或经营规划问题。 产品车间单耗/(工时/件)最大生产能力/(工时/周)甲乙A106B028C2318利润/(1×100元/件)32 假如该厂因故不能投产甲、乙两种新产品，而已调拨完毕的资源闲置不用是一种浪费。因此，现拟将原用于生产这两种产品的三种有限资源(即各车间的工时)全都承揽对外加工，则应如何考定这三种工时的价格？3.1.1 对偶问题 解：由于价格等于成本加利润，而这三个车间的生产成本在不长一段时间内相对稳定，可视为常数，故只需考定这三种工时的利润。 为此，将A、B、C三个车间承揽对外加工每个工时可获得的利润设为y1, y2, y3(元/工时)，将这三个车间的生产能力6、8、18个工时全用于对外加工所获总利润为w(元/周)，见表3-1.工时利润(百元/工时) 产品车间单耗/(工时/件)最大生产能力(工时/周)甲乙y1A106y2B028y3C2318单位产品利润:(1×100元/件)32总利润:w(1×100元/周) 将式(0)作为目标函数，将式①、②、③作为约束条件，(初步)构成一个LP模型，只不过目标要求尚待确定。Max？Min？3.1.1 对偶问题3.1.1 对偶问题 本例与范例反映了同一个实际经济问题的两个侧面，或同一问题的两种对偶提法。称范例为原本问题或原问题，称本例为范例这个原问题的对偶问题。称式(3-1)为原本模型，称(3-2)为对偶模型。 也可称LP模型(3-1)、(3-2)为原本、对偶问题。实际上这二者互为对偶。 将LP模型(3-2)的变量y1, y2, y3 称为对偶变量，它们构成的向量记为： Y=( y1, y2, y3 )T称为对偶变矢，其维数等于原本模型的阶数m，本例即为m=3。 由前已知，对偶问题和原问题的最优值恰好相等。 w*=22=z* 这不是偶然。3.1.2 对偶关系3.1.2 对偶关系 这两个相互对偶的LP问题(P1)、(D1)具有相同的三类参数A、b、C，因此知道其中任一问题，则另一问题可由上述关系1中的模型结构唯一确定。3.1.2 对偶关系 在表3-3中，将第Ⅰ行和式号Ⅰ列遮住，余下就是对偶模型(D1)；而将第Ⅱ列和式号Ⅱ行遮住，余下就是原本模型(P1)。不难由已知模型确定另一模型。课堂练习1写出下列线性规划的对偶问题【解】3.1.2 对偶关系【例3-2】写出下列LP问题的对偶模型 在表3-4中，将第Ⅰ行和式号Ⅰ遮住，余下就是对偶问题。据此，不难写出对偶模型(D2) 。 对比关系1与关系2的问题(P)与(D)，不难看出：1°(P)与(D)的目标要求大小相反：max??min2°(P)与(D)的系数阵互为转置阵(aij)m×n ?? (aji)n×m 3°(P)与(D)的变量与约束相互对应关系如下： 3.1.2 对偶关系 与模型自身目标相反者为规范，相同者为非规范。 综上，可以归纳得出更一般的对偶关系。写出LP模型的一般步骤1°按(0)，由已知模型的目标要求推定对偶模型的目标要求；2°按①，由已知模型的约数个数推定对偶模型的变量个数；3°按②，由已知模型的右端常数推定对偶模型的目标函数；4°按(a,b,c)，由已知模型的变量数据推定对偶模型的约束数据；5°按(d)，由已知模型的变量形式推定对偶模型的约束形式；6°按③④⑤，由已知模型的约束形式推定对偶模型的变量形式。【例3-3】试写出下列Lp模型的对偶问题课堂练习2写出下列线性规划的对偶问题 【解】=≥≤≤y1≤0，y2≥0，y3无约束3.2 线性规划的对偶性质 线性规划的对偶关系具有良好的性质及其经济意义。学习对偶性质有助于加深了解线性规划的基本性质。3.2.1 基本性质3.2.1 基本性质 其思路是：现将(D1)等价化成(P1)的形式，然后推导出其对偶模型恰是(P1)。 于是，可按(P1)?(D1)的规则，由(PD)推导出(DP)；再将(DP)化成等价的(P1)。3.2.1 基本性质3.2.1 基本性质3.2.1 基本性质 3.2.1 基本性质 问题(P1),(D1)的决策变量的个数分别为2和3，二者不相等。 标准化后，问题(Ps),(Ds)的变量个数就相等了，均为5个。 即变矢X，Y的维数相同，其中蕴含着一种互补性。z*=22=w*更一般的规范原本、对偶问题及其标准型：3.2.1 基本性质3.2.1 基本性质3.2.1 基本性质3.2.1 基本性质 因此，若要求解原本、对偶问题，则可采用单纯形法，只需任解其一，便能得到二者的解。这恰是单纯形法的独特属性——原本、对偶兼容性——所具高超成效与实用价值的