对偶与灵敏度分析

对偶与灵敏度分析第1页，课件共45页，创作于2023年2月对偶模型的一般式以例7为例，原问题为（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：

原问题（P）对偶问题（D）目标max型目标min型有n个变量（非负）有n个约束（大于等于）有m个约束（小于等于）有m个变量（非负）价格系数资源向量资源向量价格系数技术系数矩阵技术系数矩阵的转置第2页，课件共45页，创作于2023年2月此外，还有一种情形

原问题（P）对偶问题（D）第j个变量为自由变量第j个约束为等式约束第i个约束为等式约束第i个变量为自由变量例8：写出下面线性规划的对偶规划模型：第3页，课件共45页，创作于2023年2月例8：写出下面线性规划的对偶规划模型：第4页，课件共45页，创作于2023年2月二、对偶的性质（P）（D）考虑1.对称性（P）与（D）互为对偶。证：由（P）、（D）的约束可得几何意义：CXYb第5页，课件共45页，创作于2023年2月4.对偶定理若（P）有最优解，则（D）也有最优解，

且最优值相同。证：对（P）增加松弛变量Xs，化为设其最优基为B，终表为其检验数为第6页，课件共45页，创作于2023年2月得证。第7页，课件共45页，创作于2023年2月问题：(1)由性质4可知，对偶问题最优解的表达式Y*=？

(2)

求Y*是否有必要重新求解（D）？

——CBB-1——不必。可以从原问题（P）的单纯形终表获得。例如，在前面的练习中已知的终表为请指出其对偶问题的最优解和最优值。第8页，课件共45页，创作于2023年2月5.互补松弛定理第9页，课件共45页，创作于2023年2月y1…yi…ymym+1…ym+j…yn+m

x1…xj…xnxn+1…xn+i…xn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0直观上第10页，课件共45页，创作于2023年2月

6.对偶问题的经济解释

（1）对偶最优解的经济解释——资源的影子价格（ShadowPrice）CBB-1——对偶问题的最优解——买主的最低出价；——原问题资源的影子价格——当该资源增加1单

位时引起的总收入的增量——卖主的内控价格。例10：例1（煤电油例）的单纯形终表如下：（1）请指出资源煤电油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？第11页，课件共45页，创作于2023年2月例10：例1（煤电油例）的单纯形终表如下：（1）请指出资源煤、电、油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？解：（1）煤、电、油的影子价格分别是0、1.36、0.52；其经济意义是当煤、电、油分别增加1单位时可使总收入分别增加0、1.36、0.52。（2）由单纯形终表还可得到：原问题的最优生产计划、最大收入、资源剩余，对偶问题的最低购买价格、最少的购买费用等。第12页，课件共45页，创作于2023年2月y1y2ym（2）对偶约束的经济解释——产品的机会成本(OpportunityCost)机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源第13页，课件共45页，创作于2023年2月机会成本利润差额成本（3）对偶松弛变量的经济解释——产品的差额成本（ReducedCost）差额成本=机会成本－利润第14页，课件共45页，创作于2023年2月在利润最大化的生产计划中（1）影子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。（4）互补松弛关系的经济解释第15页，课件共45页，创作于2023年2月三、对偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时,已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cj−CBB-1Pj≤0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。第16页，课件共45页，创作于2023年2月设原问题为

maxz=CX

AX=b

X≥0又设B是一个基。不失一般性，令B=(P1，P2，…，Pm)，它对应的变量为XB=(x1，x2，…,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i＜0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是

(1)对应基变量x1，x2，…,xm的检验数是σi=ci

−

CBB-1Pj=0，i=1,2,…,m(2)对应非基变量xm+1，…，xn的检验数是σj=cj−CBB-1Pj≤0，j=m+1,…,n第17页，课件共45页，创作于2023年2月每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。第18页，课件共45页，创作于2023年2月对偶单纯形法的计算步骤如下：

(1)根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。

(2)确定换出变量。按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l对应的基变量xi为换出变量

(3)确定换入变量。在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止计算。若存在αlj＜0(j=1,2,…，n),计算第19页，课件共45页，创作于2023年2月对偶单纯形法的计算步骤如下：按θ规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。

(4)以αlk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)～(4)。第20页，课件共45页，创作于2023年2月例:用对偶单纯形法求解minw=2x1+3x2+4x3x1+2x2+x3≥32x1−x2+3x3≥4x1，x2，x3≥0

解：先将此问题化成下列形式，以便得到对偶问题的初始可行基maxz=−2x1−

3x2−

4x3−x1−

2x2−

x3+x4=−3−2x1+x2−

3x3+x5=−4xj≥0，j=1,2,…,5第21页，课件共45页，创作于2023年2月例6的初始单纯形表，见表。从表看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。

第22页，课件共45页，创作于2023年2月换出变量的确定：换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止计算。按上述对偶单纯形法计算步骤(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l对应的基变量xi为换出变量。计算min(−3,−4)=−4故x5为换出变量。故x1为换入变量。换入、换出变量的所在列、行的交叉处“−2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。第23页，课件共45页，创作于2023年2月第24页，课件共45页，创作于2023年2月表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)第25页，课件共45页，创作于2023年2月对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。第26页，课件共45页，创作于2023年2月三、灵敏度分析

讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范围内变化时可使原最优解或最优基不变？）我们主要讨论C、b和变量结构变化时对解的影响。对解怎样影响？——影响解的-最优性

-可行性第27页，课件共45页，创作于2023年2月1.b变化时的分析第28页，课件共45页，创作于2023年2月例11：在例1（煤电油例）中，其单纯形终表如下：（1）电的影子价格是多少？使最优基仍适用的电的变化范围为何？解：（1）电的影子价格是1.36。第29页，课件共45页，创作于2023年2月例11：在例1（煤电油例）中，其单纯形终表如下：（2）若有人愿以每度1元的价格向该厂供应25度电，是否值得接受？解：（2）值得。因25在B的适用范围内（即影子价格适用），且

1.00-1.36<0。第30页，课件共45页，创作于2023年2月2.C变化时的分析第31页，课件共45页，创作于2023年2月例11：在例1（煤电油例）中，其单纯形终表如下：（3）甲产品的价格在何范围内变化时，现最优解不变？解：甲产品的价格c1是基变量的价格系数。第32页，课件共45页，创作于2023年2月3.增加新变量时的分析

主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产，数学意义是xn+1是否应进基。经济意义：市场价影子价第33页，课件共45页，创作于2023年2月例11：在例1（煤电油例）中，其单纯形终表如下：（4）若现又考虑一新产品丙，其资源单耗为10，2，5，售价为6.5，问该产品是否可投产？故丙产品可以投产。第34页，课件共45页，创作于2023年2月首先将线性规划与经济问题联系起来的是

T.G.Koopman（库普曼）和

L.V.Kamtorovich（康脱罗维奇）二人因此而共同分享了1975年的第7届诺贝尔经济学奖。第35页，课件共45页，创作于2023年2月求解线性规划的计算机软件举例——LINDO、EXCELLINDO可以从下面的网址下载：WWW.L

LINDO由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。输入例：MAX2X+3Y

ST

2)4X+9Y<93)7X+6Y<13

END

可用HELP命令得到帮助。第36页，课件共45页，创作于2023年2月计算结果说明：REDUCEDCOST

为使该变量进基，其价格系数至少应增加的数值；SLACKORSUPLUS

松弛或剩余变量；DUALPRICES

影子价格;ALLOWABLEINCREASE

灵敏度分析中可使最优基不变的系数可增量之上界；ALLOWABLEDECREASE

灵敏度分析中可使最优基不变的系数可减量之上界；第37页，课件共45页，创作于2023年2月例1加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？每天：第38页，课件共45页，创作于2023年2月1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天第39页，课件共45页，创作于2023年2月模型求解

软件实现

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。第40页，课件共45页，创作于2023年2月结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）第41页，课件共45页，创作于2023年2月结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格

35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！第42页，课件共45页，创作于2023年2月RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000IN