线性规划的对偶理论与灵敏度分析.doc

《线性规划的对偶理论与灵敏度分析.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性规划的对偶理论与灵敏度分析主要内容对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划讲授重点对偶基本性质、对偶单纯形方法、灵敏度分析讲授方式讲授式、启发式本章知识结构图第一节线性规划的对偶问题一、对偶问题的提出首先通过实际例子看对偶问题的经济意义。例1第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为：(LP1)maxz＝2xl+x2现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同

2、等数量资源由自己组织生产活动时获取的盈利。设分别用y1、y2、和y3代表单位时间(h)设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和1小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电Ⅱ，盈利1元。由此y1，y2，y3的取值应满足6y2+y3≥25y1+2y2+y3≥1(2.1)又另一公司希望用最小代价把美佳公司的全部资源收买过来，故有minz＝15y1+24y2+5y3(2.2)显然yi≥0(i＝l，2，3)，再综合(2.1)，(2.2)式有。(LP2)min＝15y1+24y2+5y3上述LP1和LP

3、2是两个线性规划问题，通常称前者为原问题，后者是前者的对偶问题。二、对称形式下对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”号，当目标函数求极小时均取“≥”号’。对称形式下线性规划原问题的一般形式为：maxz=c1x1+c2x2+…+cnxn(2.3)用yi（i=1，…，m）代表第i种资源的估价，则其对偶问题的一般形式为:minw=b1y1+b2y2+…+bmym(2.4)用矩阵形式表示，对称形式的线形规划问题的原问题为：maxz=CX(2.5)其对偶问题为：minw=Y’b将上

4、述对称形式下线性规划的原问题与对偶问题进行比较，可以列出如表2-1所示的对应关系。表2－1原问题对偶问题A约束系数矩阵其约束系数矩阵的转置B约束条件的右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端项向量目标函数maxz=CXmin=约束条件AX≤b≥决策变量X≥0Y≥0上述对偶问题中令=，可改写为max=-Y’b如将其作为原问题，并按表2-1所列对应关系写出它的对偶问题则有再令则上式可改写为：可见对偶问题的对偶即原问题。三、非对称形式的原-对偶问题关系因为并非所有线性规划问题具有对称形式，故下面讨论一般情况下线性规划问题如何写出其对

5、偶问题。考虑下面的例子。例2写出下述线性规划问题的对偶问题思路是先将其转换成对称形式，再按表2-1的对应关系来写。下面将对称或不对称线性规划原问题同对偶问题的对应关系，统一归纳为表2-2所示形式。表2-2原问题（对偶变量）对偶问题（原问题）A约束系数矩阵约束条件系数矩阵的转置b约束条件右端项向量目标函数中的价格系数向量c目标函数中的价格系数向量约束条件右端项向量目标函数约束条件原问题（对偶变量）对偶问题（原问题）约束条件第二节对偶问题的基本性质本节的讨论先假定原问题及对偶问题为对称形式线性规划问题，即原问题为：(2.9)其对偶问题为：(2.10)然后说明对偶问

6、题的基本性质在非对称形式时也适用。为本节讨论及后面讲述的需要，这里先介绍有关单纯形法计算的矩阵描述。一、单纯形法计算的矩阵描述对称形式线性规划问题(2.9)的矩阵表达式加上松弛变量后为：(2.11)上式中Xs为松弛变量，Xs=(xn+1,xn+2,…，xn+m)，I为m×m单位矩阵。单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中的系数矩阵为B。将B在初始单纯形表中单独列出，而A中去掉后的若干列后剩下的列组成矩阵N，这样(2.11)的初始单纯形表可列成如表2-3的形式。表2-3非基变量基变量XBXNXs0X

7、sbBNIcj-zjCBCN0当迭代若干步，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换，对应Xs的系数矩阵在新表中应为B-1。故当基变量为XB时，新的单纯形表具有表2-4形式。表2-4基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CB-1N-CBB-1从表2-3和表2-4看出，当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为，则有：(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为；(2)初始单纯形表中基变量＝b,，迭代后的表中＝b,，(3)初始单

8、纯形表中约束系数矩阵为[A，I]＝[B