对偶理论和灵敏度分析10182.ppt

对偶理论和灵敏度分析 1.单纯形的矩阵描述 用矩阵语言描述单纯形法的关键是写出两个基本的表达式,设线性规划的标准型为 maxz=CX AX=b X≥0 C=(CB,CN)，X=(XB,XN)’，A=(B,N) 由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基变量表示基变量的表达式: XB=B-1b-B-1NXN (1) 将(1)式代入目标函数的表达式,可以得到用非基变量表示目标函数的表达式. Z=CX=(CB,CN)(XB,XN)’=CBXB+CNXN =CB(B-1-B-1NXN)+CNXN =CBB-1b+(CN-CBB-1N)XN =CBB-1b+σNXN 另非基变量等于零，则Z=CBB-1b 注意XB检验数为零,实质上是CB-CBB-1B=0 Y=CBB-1为单纯形乘子 注意:在初始单位矩阵的位置,在各运算表中就是B-1的所在位置 2.改进单纯形法 改进单纯形法又称为逆矩阵法或修正单纯形法,是在原来单纯形法基础上加以改进，关键在于求B-1,有了B-1,单纯形算法的各个表中的数字都可以利用线性规划中的原始数据计算出来。 3对偶理论 某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。 若上例中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。 在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题： ①合理安排生产能取得多大利润? ②为保持利润水平不降低，资源转让的最低价格是多少？ 问题 ①的最优解：x1=4，x2=6，Z*=42。 假设出让A、B、C设备所得利润分别为y1、y2、y3 原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 y1+0y2+3y3≥ 3 同理，对乙产品而言，则有 0y1+2y2+4y3≥ 5 设备台时出让的收益（希望出让的收益最少值） min?=8y1+12y2+36y3 显然还有 y1，y2，y3≥0 3.1对偶变换的规则 3.2对偶问题的基本性质 为了便于讨论，下面不妨总是假设 (1)对称性：对偶问题的对偶是原问题。 (2) 弱对偶性：对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值，即CX0≤Yb0。 弱对偶定理推论： 原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限。 (3)无界性 若原(对偶)问题为无界解，则其对偶(原)问题无可行解 当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解。 如果原(对偶)问题有可行解，其对偶 (原)问题无可行解，则原问题为无界解。 (4)强对偶性 可行解是最优解的性质(最优性准则定理) 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 （5）主对偶定理 若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等。 综上所述，一对对偶问题的解必然是下列三种情况之一: 原问题和对偶问题都有最优解。 一个问题具有无界解，另一个问题无可行解。 原问题和对偶问题都无可行解。 (6)互补松弛性 设X0, Y0分别是原问题和对偶问题的可行解，Xs为原问题的松弛变量的值、Ys为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 ：Y0 Xs = Ys X0 = 0 (7)原问题单纯形表检验数行与对偶问题解的关系 原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解 4.影子价格（对偶价格） 对偶变量yi(i=1,2,…,m)表示原问题的第i个约束条件的影子价格，它表示：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。 (1)影子价格能指示企业内部挖潜的方向。影子价格越高的资源，它对目标增益的影响越大，同时也表明这种资源越稀缺和贵重。企业的管理者要重视这种资源的管理，挖掘潜力，及时组织资源，由此可以给企业带来较大的收益。 (2)影子价格指导企业间的分工与协作。影子价格可以作为企业在接受外协加工任务时，对外协单位使用资源的收费标准，按照影子价格收费，保证了企业与外协单位双方平等互利的格局，可以促进