对偶理论和灵敏度分析

对偶理论和灵敏度分析第一页，共四十九页，编辑于2023年，星期日1.单纯形的矩阵描述用矩阵语言描述单纯形法的关键是写出两个基本的表达式,设线性规划的标准型为

maxz=CXAX=bX≥0C=(CB,CN)，X=(XB,XN)’，A=(B,N)由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基变量表示基变量的表达式:XB=B-1b-B-1NXN(1)第二页，共四十九页，编辑于2023年，星期日将(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=0Y=CBB-1为单纯形乘子第三页，共四十九页，编辑于2023年，星期日

cxbCBCNθ

XBXNXBB-1bB-1BB-1N-z-CBB-1b

0CN-CBB-1N第四页，共四十九页，编辑于2023年，星期日注意:在初始单位矩阵的位置,在各运算表中就是B-1的所在位置BI……IB-1第五页，共四十九页，编辑于2023年，星期日2.改进单纯形法改进单纯形法又称为逆矩阵法或修正单纯形法,是在原来单纯形法基础上加以改进，关键在于求B-1,有了B-1,单纯形算法的各个表中的数字都可以利用线性规划中的原始数据计算出来。第六页，共四十九页，编辑于2023年，星期日第七页，共四十九页，编辑于2023年，星期日

3对偶理论某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。

产品车间工时单耗甲乙生产能力ABC

10023481236单位产品获利

35maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.第八页，共四十九页，编辑于2023年，星期日若上例中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：①合理安排生产能取得多大利润?②为保持利润水平不降低，资源转让的最低价格是多少？问题①的最优解：x1=4，x2=6，Z*=42。第九页，共四十九页，编辑于2023年，星期日假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有

y1+0y2+3y3≥3同理，对乙产品而言，则有

0y1+2y2+4y3≥5设备台时出让的收益（希望出让的收益最少值）

min=8y1+12y2+36y3显然还有

y1，y2，y3≥0第十页，共四十九页，编辑于2023年，星期日min=8y1+12y2+36y3

y1+0y2+3y3≥3

0y1+2y2+4y3≥5y1，y2，y3≥0S.t.maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.第十一页，共四十九页，编辑于2023年，星期日例

线性规划问题

maxz=3x1+5x2

stx1+3x2

10 7x1+4x2

20 xj0;j=1,2.

对偶问题为：

ming=10y1+20y2 st y1+7y2

3 3y1+4y2

5 yi

0;i=1,2。第十二页，共四十九页，编辑于2023年，星期日

3.1对偶变换的规则第十三页，共四十九页，编辑于2023年，星期日

3.2对偶问题的基本性质为了便于讨论，下面不妨总是假设(1)对称性：对偶问题的对偶是原问题。(2)弱对偶性：对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值，即CX0≤Yb0。弱对偶定理推论：原问题的任何可行解目标函数值是其对偶问题目标函数值的下限；对偶问题的任何可行解目标函数值是原问题目标函数值的上限。第十四页，共四十九页，编辑于2023年，星期日

(3)无界性若原(对偶)问题为无界解，则其对偶(原)问题无可行解当原问题(对偶问题)为无可行解,其对偶问题(原问题)或具有无界解或无可行解。如果原(对偶)问题有可行解，其对偶(原)问题无可行解，则原问题为无界解。(4)强对偶性可行解是最优解的性质(最优性准则定理)若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解（5）主对偶定理

若原问题和对偶问题两者皆可行,则两者均有最优解,且此时目标函数值相等。第十五页，共四十九页，编辑于2023年，星期日

综上所述，一对对偶问题的解必然是下列三种情况之一:原问题和对偶问题都有最优解。一个问题具有无界解，另一个问题无可行解。原问题和对偶问题都无可行解。(6)互补松弛性设X0,Y0分别是原问题和对偶问题的可行解，Xs为原问题的松弛变量的值、Ys为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是：Y0Xs

=

Ys

X0=0第十六页，共四十九页，编辑于2023年，星期日(7)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然,原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解XBXNXS0CN-CBB-1N-CBB-1YS1-YS2-Y第十七页，共四十九页，编辑于2023年，星期日例已知线性规划问题：试用对偶理论证明此线性规划问题无最优解。解：对偶问题为：由第一约束条件显见，对偶问题无可行解因为（0，0，0）为线性规划问题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题无最优解。第十八页，共四十九页，编辑于2023年，星期日例5：线性规划问题最优解为用对偶问题求原问题的最优解。第十九页，共四十九页，编辑于2023年，星期日对偶问题为：将对偶问题的解代入上述约束条件，可知2、3、4式为严格不等式；由松弛互补性，可得x2=x3=x4=0,因y1,y2大于零，所以原问题的两个约束条件应该取等式，故有：第二十页，共四十九页，编辑于2023年，星期日

4.影子价格（对偶价格）对偶变量yi(i=1,2,…,m)表示原问题的第i个约束条件的影子价格，它表示：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。(1)影子价格能指示企业内部挖潜的方向。影子价格越高的资源，它对目标增益的影响越大，同时也表明这种资源越稀缺和贵重。企业的管理者要重视这种资源的管理，挖掘潜力，及时组织资源，由此可以给企业带来较大的收益。(2)影子价格指导企业间的分工与协作。影子价格可以作为企业在接受外协加工任务时，对外协单位使用资源的收费标准，按照影子价格收费，保证了企业与外协单位双方平等互利的格局，可以促进双方合作。第二十一页，共四十九页，编辑于2023年，星期日

(3)影子价格在新产品开发决策中的应用。两种新产品A,B的机会成本（万元）：A单位产品的机会成本=1×3/4+2×0+3×1/4=3/2B单位产品的机会成本=2×3/4+1×0+4×1/4=5/2产品资源AB影子价格(万元)钢材煤机时1221343/401/4单位利润(万元)13第二十二页，共四十九页，编辑于2023年，星期日

由于投产A产品所能提供的单位利润（1万元）不大于投产的机会成本（1.5万元），因此A产品不宜投产；而B产品的机会成本（2.5万元）小于该产品投产后所能提供的利润（3万元），因此投产B产品可以给工厂带来较大的收益。如果新产品B确实为社会所欢迎,而在资源利用上与老产品发生冲突，工厂可以考虑用B产品去更换老产品，以获得更大的经济效益。(4)影子价格在资源采购决策中的应用。当资源的市场价格低于影子价格，企业买进该资源，扩大生产，当资源的市场价格高于影子价格，企业应设法转让该资源。第二十三页，共四十九页，编辑于2023年，星期日

(5)利用影子价格分析工艺改变后对资源节约的收益。例如设工厂现有钢材100吨，其影子价格为3/4，采用新工艺后，钢材可以节约2%，则由此带来的经济收益为：

100×3/4×2%=3/2(万元)第二十四页，共四十九页，编辑于2023年，星期日5.对偶单纯形法对偶单纯形法是应用对偶原理求解原问题线性规划的一种方法,采用的技术是在原问题的单纯形表格上进行对偶处理。注意:对偶单纯形法不是求解对偶问题的单纯形法。第二十五页，共四十九页，编辑于2023年，星期日单纯形法的求解过程是：在保持原始可行(b列保持≥０）的前提下，通过逐步迭代实现对偶可行（检验数行≤０）。换个角度考虑线性规划的求解过程：能否保持对偶可行（检验数行保持≤０）的前提下，通过逐步迭代实现原始可行(b列≥０，从非可行解变成可行解）呢？答案是肯定的，这就是对偶单纯形法的基本思想。第二十六页，共四十九页，编辑于2023年，星期日步骤：（1）根据线性规划问题，列出初始单纯形表。若b列数字还有负分量，检验数保持非正，则（2）确定换出变量选min[(B-1b)i/(B-1b)i<0]对应的变量xl为换出变量（3）确定换入变量θ=min[cj-zj/aij](aij<0)所对应的非基变量xk为换入变量。（4）以alk为主元素进行迭代运算，并重复以上步骤第二十七页，共四十九页，编辑于2023年，星期日利用对偶单纯形法求解以下线性规划问题：第二十八页，共四十九页，编辑于2023年，星期日cjCBXBbx1x2x3x4x5-1-3000-2-3-1-1-2-2100010解法001-3-4-1x3x4x5000-1-3000cj-zj1/33/2x3x1x50101/32/3-4/3100-2/3-1/3-1/3001cj-zj-1/34/31/30-7/30-1/301/20-10x4x1x5½3/21/2010-1/2½-3/2-3/2-1/2-1/21000010-10cj-zj0-5/2-1/200-3/2此时所有的B-1b均≥0，且所有的cj-zj均≤0，此时已得到最优解为：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2第二十九页，共四十九页，编辑于2023年，星期日总结：对偶单纯形法与单纯形法的比较最优解时要求单纯形法对偶单纯形法保持B-1b≥0所有的cj-zj≤0所有的cj-zj≤0B-1b≥0第三十页，共四十九页，编辑于2023年，星期日特点：可以避免加人工变量，简化计算．灵敏度分析和整数规划常借助于对偶单纯形法分析．局限性在于初始单纯形表的检验数行很难满足小于或等于零的要求，即满足检验数行对应的对偶问题的解是可行解．第三十一页，共四十九页，编辑于2023年，星期日6.灵敏度分析灵敏度分析的意义

线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。第三十二页，共四十九页，编辑于2023年，星期日灵敏度分析所要解决的问题：系数在什么范围内变化，不会影响已获得的最优基(即最优解或最优解结构不变)。如果系数的变化超过以上范围，如何在用最简便的方法在原来最优解的基础上求得新的最优解当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。第三十三页，共四十九页，编辑于2023年，星期日6.1右端项bi变化的灵敏度分析bi变化到什么程度可以保持最优基不变？用xB=B-1b≥0。第三十四页，共四十九页，编辑于2023年，星期日例：求以下模型中第二个约束条件右端项b2的变化范围。maxZ=70X1+120X29X1+4X2≤3604X1+5X2

≤2003X1+10X2

≤300X1≥0X2≥0第三十五页，共四十九页，编辑于2023年，星期日

Cj70

120000CBXBbX1

X2

X3X4X5θi

000X3X4X5360200300

9410045010310001904030σj0

70120000

00120X3X4X22405030

7.8010-0.42.5001-0.50.31000.130.7620100σj3600

34000-12070120X3X1X2842024

001-3.121.161000.4-0.2010-0.120.16σj4280

000-13.6-5.2第三十六页，共四十九页，编辑于2023年，星期日解：从最优单纯形表得出：XB=(20,24,84)T最优基为：注意：应为初始数据。还可以从单纯形表中找出B-1.第三十七页，共四十九页，编辑于2023年，星期日设b2由200变为200＋∆b2，则b由

由此得到迭代后的单纯形表：cj70120000CBXBbx1x2x3x4x5θi010001100-3.120.4-0.121.16-0.20.1684-3.12∆b220+0.4∆b224-0,12∆b2x3x1x2070120σj4280+13.6∆b2000-13.6-5.2第三十八页，共四十九页，编辑于2023年，星期日上述解是最优解，必须是可行解：即：解得：－50≤∆b2≤26.9。可知右端项系数b2的变化范围是:

（200－50）～（200＋26.9)第三十九页，共四十九页，编辑于2023年，星期日在此范围内σj≤0，B-1b≥0，最优解仍有效，即最优解的基变量不变，最优解为：最优值为：Z*=4280+13.6∆b2第四十页，共四十九页，编辑于2023年，星期日6.2目标函数中价值系数cj的灵敏度分析分cj是非基变量的系数还是基变量的系数两种情况来讨论。①若cj是非基变量xj的系数，此时，当cj变化∆cj后，要保证最终表中这个检验数仍小于或等于零即可。②若cj是基变量xj的系数，则引起的变化较大。第四十一页，共四十九页，编辑于2023年，星期日例：在模型例1中，求基变量x2的系数变化范围。解：本例的最优单纯形表如下：070120cjCBXBbx3x1x2842024x1x2x3x4x5θi70120000010001100-3.120.4-0.121.16-0.20.16σj4280000-13.6-5.2第四十二页，共四十九页，编辑于2023年，星期日基变量系数c2由120变为120＋∆c2后，可以得到迭代后的单纯形表。cjCBXBbx3x1x2842024x1x2x3x4x5θi70120＋∆c2000010001100-3.120.4-0.121.16-0.20.16σj4280＋24∆c2000-13.6+0.12