对偶理论与灵敏度分析.ppt

第二章对偶理论与灵敏度分析1．线性规划的对偶问题例1：美佳公司利用该公司资源生产两种家电产品。现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？
显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利。
设分别用yl，y2和y3代表单位时间（h）设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和l小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电II，盈利1元。由此y1，y2，y3的取值应满足:例2写出下列问题的原问题与对偶问题原问题：设x1，x2为产品1，2的产量对偶问题：设y1,y2,y3,y4分别为A,B,C,D设备的单价对称的含义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。
对称形式下线性规划原问题的一般形式为：用yi(i＝1，…m)代表第i种资源的估价，则其对偶问题的一般形式为：用矩阵形式表示，原问题为:原问题与对偶问题的对应关系1.3非对称形式的原－对偶问题关系1.3非对称形式的原－对偶问题关系1.3非对称形式的原－对偶问题关系例3写出下述线性规划问题的对偶问题解：原问题可化为令y1=y1'-y1"1.4对偶的关系原问题对偶问题
目标函数类型maxmin
目标函数系数目标函数系数右边项系数
与右边项的对应关系右边项系数目标函数系数
变量数与约束数变量数n约束数n
的对应关系约束数m变量数m
原问题变量类型与0
对偶问题约束类型变量0约束
的对应关系无限制＝
原问题约束类型与0
对偶问题变量类型约束变量0
的对应关系＝无限制2．对偶问题的基本性质用矩阵形式表示，原问题为:单纯形法计算的矩阵描述迭代后新的单纯形表为：迭代后新的单纯形表为：可以看出：当B为最优基时看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。
将这个解代入对偶问题的目标函数值，有：例4最终单纯形表：一.对称性：对偶问题的对偶是原问题对
偶若x′是原问题的可行解，y′是对偶问题的可行解。则有cx′≤y′b推论(2)：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。设x′是原问题的可行解，y′是对偶问题的可行解.
当cx′=y′b时x′,y′是最优解。四.强对偶性（对偶定理）五.互补松弛性（松紧定理）即：几个练习2．对偶问题的基本性质1）说明原问题和对偶问题都有最优解.
2）求原问题和对偶问题的最优目标函数值的一个上界和下界.2．对偶问题的基本性质2．对偶问题的基本性质2．对偶问题的基本性质2．对偶问题的基本性质2．对偶问题的基本性质2．对偶问题的基本性质3．影子价格关于影子价格的几点说明（15/4，5/4）
z=8.753．资源的影子价格实际上又是一种机会成本。
在纯市场经济条件下，可以根据影子价格与市场价格的关系确定资源的买进或卖出。5．单纯形表中各个检验数的经济意义4．对偶单纯形法 对偶单纯形法的基本思路：先找出一个对偶问题的可行基，并保持对偶问题为可行解条件下，如不存在XB≥o，通过变换到一个相邻的目标函数值较小的基本解(因对偶问题是求目标函数极小化)，并循环进行，一直到原问题也为可行解(即XB≥o)，这时对偶问题与原问题均为可行解。
在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。对偶单纯形法的计算步骤：4.以ars为主元素，进行迭代变换。
可以证明，按照上述方法进行迭代变换以后，检验数仍保持为非正，即对偶问题仍可行。例5：用对偶单纯形法求解下列问题已获得最优解：
（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）minz=35

对偶问题的最优解为：
（w1,w2,w3,w4,w5,w6）=（-1,5,7,0,0,0）maxy=35从以上计算可以看出，用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引进人工变量，使计算简化。但在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法一般不单独使用，而主要应用于灵敏度分析及整数规划等有关章节中。例:(初始解原始、对偶都不可行的问题)解法1：先解决原始可行性已得到对偶可行解，再用对偶单纯形法求解得到原始可行解，已获得最优解：
（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）minz=17
对偶问题的最优解为：
（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）maxy=17对偶单纯形法的优点：
1简化计算
2减少计算量
3灵敏度分析
缺点：
第一个正则解很难找到5．灵