《运筹学》课件 第3章 对偶和灵敏度分析

第3章对偶理论与灵敏度分析第2章内容提要3.1单纯形法的矩阵描述3.2对偶问题的提出3.3线性规划的对偶理论3.4影子价格3.5对偶单纯形法3.6灵敏度分析3.1单纯形法的矩阵描述介绍用矩阵来描述单纯形法的计算过程，有助于加深对单纯形法的理解，和学习对偶理论。设线性规划问题：Max

z=CXAX=bX

0其中松驰变量

Xs=(xn+1,xn+2,…

,

xn+m)TI是m

m阶单位矩阵化为标准型：Max

z=CX+0Xs(3.1)AX+IXs=b(3.2)X

0,Xs

0(3.3)设B是一个可行基，则可将系数矩阵(A,I)分为两块(B,N)，N是非基变量的系数矩阵。对应于B的变量xB1,xB2,…

,

xBm是基变量，用向量XB=(xB1,xB2,…

,

xBm)T表示其它为非基变量，则同时将C也分为两块(CB,CN)，则这时可将(3.1),(3.2),(3.3)式改写为

Max

z=CBXB+CNXN(3.4)BXB+NXN=b(3.5)XB

0,XN

0(3.6)将(3.5)式移项后，得到

BXB=b-NXN

(3.7)给(3.7)式左乘B-1后，得到XB的表达式

XB=B-1b-B-1NXN

(3.8)将(3.8)式代入目标函数，得

z=CBB-1b+(CN-CBB-1N)XN

(3.9)

XB=B-1b-B-1NXN

(3.8)z=CBB-1b+(CN-CBB-1N)XN

(3.9)令非基变量XN=0，得到一个基可行解则，目标函数值

z=CBB-1b

XB=B-1b-B-1NXN

(3.8)

z=CBB-1b+(CN-CBB-1N)XN

(3.9)从上式中可以看到：非基变量XN的系数CN-CBB-1N就是检验数，即

N=CN-CBB-1N因为XB在式(3.9)中的系数是0，即CB-CBB-1B=0故包括基变量在内的所有检验数可用C-CBB-1A≤0表示。松驰变量检验数为-CBB-1，故所有检验数可用

C-CBB-1A和-CBB-1，即

C-YA和-Y表示。将式(3.8)和(3.9)综合写成矩阵式如下：

XB=B-1b-B-1NXN

(2.8)

z=CBB-1b+(CN-CBB-1N)XN

(2.9)右端项RHS基变量非基变量XBXN1XsB-1bIB-1N1B-1-CBB-1b0CN1-CBB-1N1-CBB-1在单纯形表中表示如下：3.2对偶问题的提出在第1章例1中讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题。假设该工厂的决策者决定不生产产品I，II，而将其所有资源出租或外售，这时工厂的决策者就要考虑给每种资源如何定价的问题。某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示：III合计设备128台时原材料A4016千克原材料B0412千克该工厂每生产一件I

可获得2元，每生产一件产品II可获得3元。问应如何安排计划使该工厂获得最多？其数学模型归结为：目标函数Max

z=2x1+3x2约束条件x1+2x2

84x1

16s.t.4x2

12x1,x2

0设用y1,y2,y3

分别表示出租单位设备台时的租金和出让单位原材料A,B的利润。若用一个单位设备台时和4个单位原材料A可以生产一件产品I可获得2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入不应低于生产一件产品I的利润，即

y1+4y2≥2换一种思维的角度同理，将每生产每件产品II的设备台时和材料出租和出让的所有收入不应低于生产一件产品II的利润，即

2y1+4y3≥3把工厂所有设备台时和资源都出租或出让，其收入为

w=8y1+16y2+12y3从工厂的决策者来看，当然w

越大越好，但从接受者来看他的支付越少越好。因此决策者只能在满足所有产品利润的条件下，使其总收入尽可能地小。即解如下线性规划问题

Min

w=8y1+16y2+12y3y1+4y2≥22y1+4y3≥3y1,y2,y3≥0这个问题即为原问题的对偶问题。在马克思辩证法的视域中，矛盾并非实体而是一种关系，它作为“对立面的统一”，也就是“两极相联”。对偶问题和原问题之间的关系就是一种“两极相联”的关系，苏轼的名句“横看成岭侧成峰，远近高低各不同”就解释了这一现象。思政探讨矩阵形式的对偶问题从前面知检验数C-CBB-1A和-CBB-1均非正时，线性规划问题达到最优解，即

C-YA≤0和-Y≤0则Y≥0，YA

≥C对单纯形因子Y=CBB-1两边同乘b得Yb=CBB-1b=z因Y的上界为无限大，所以只存在最小值。由此得另一个线性规划问题：

Minw=YbYA

≥CY≥0此即原问题{Max

z=CX|AX≤b,X≥0}的对偶问题3.3线性规划的对偶理论原问题与对偶问题的关系3.3.1原问题与对偶问题的关系左右不对称，左→右≠右→左原问题P(或对偶问题)对偶问题D(或原问题)

目标函数maxz

目标函数minw

变量n个

约束条件n

个

变量≥0

约束条件≥

变量≤0

约束条件≤

变量无约束

约束条件

=

变量m个

约束条件m

个

变量≥0

约束条件≤

变量≤0

约束条件≥

变量无约束

约束条件

=

约束条件右端项

目标函数变量的系数

约束条件右端项

目标函数变量的系数例写出下述线形规划问题的对偶问题MaxZ=5x1+4x2+6x3x1+2x2≥2x1+x3≤3-3x1+2x2+x3≤-5x1-x2+x3＝1x1≥0;x2≤0,;x3无约束minW=2y1+3y2-5y3+y4y1+y2-3y3+y4≥52y1+2y3-y4≤4y2+y3+y4=6y1≤0,y2,y3

≥0,y4无约束例写出下述线形规划问题的对偶问题minZ=2x1+3x2-5x3+x4x1+x2-3x3+x4≥52x1+2x3-x4≤4x2+x3+x4＝6x1≤0,x2,x3≥0;x4无约束maxZ’=5y1+4y2+6y3y1+2y2≥2y1+y3≤3-3y1+2y2+y3≤-5y1-y2+y3=1y1≥0,y2≤0,y3无约束写出下列问题的对偶问题：解：先将约束条件变形为“≤”形式再根据非对称形式的对应关系，直接写出对偶规划

3.3.2对偶问题的基本性质对称性弱对偶性无界性可行解是最优解时的性质对偶定理互补松驰性解的关系1对称性对偶问题的对偶是原问题。对原问题：Max

z=CXAX≤bX≥0对(1)式两边取负号有

-Min

w=-Yb又因Minw=-Max(-w)故可得

Max(-w)=-Yb-YA≤-CY≥0其对偶问题：Min

w=Yb（1）YA≥CY≥0它的对偶问题是：Min-w‘

=-CX;-AX≥-b;X≥0又因Min–w’=-Max(w’)

故可得

Max

w‘=Maxz=CX

AX≤bX≥02弱对偶性若是原问题的可行解，是对偶问题的可行解，则存在3无界性若原问题(对偶问题)无界解，则对偶问题(原问题)无可行解。4可行解是最优解的性质若是原问题的可行解，是对偶问题的可行解，则当，是最优解。5对偶定理若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。试用对偶理论判断下面线性规划是否有最优解解:

此规划存在可行解，其对偶规划为显然，对偶规划没有可行解，因此，原规划没有最优解。推论若原问题有一个对应于基B的最优解，那么此时的单纯形乘子Y＝CBB-1是对偶问题的一个最优解

maxZ=3x1+5x2x1+x3=82x2+x4=123x1+4x2+x5=36

例Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9Cj35000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1最终单纯型表求其对偶问题的最优解？求解下面线性规划问题，并根据最优单纯形表中的检验数，给出其对偶问题的最优解。

解引入松弛变量、将模型化为标准型，经求解后得到其最优单纯形表

c43700 cBxBB-1bx1x2x3x4x5

3x225-3/4103/4-1/2 7x3255/401-1/41/2

Z

250-10/400-1/2-2 对偶规划的最优解为:6互补松驰性若X*和Y*分别是原问题和对偶问题的可行解，那么它们为最优解的充要条件是(C-Y*A)X=0和Y(b-AX*)=0若由最优解得约束条件为绝对不等式，则对偶问题对应变量为零。变量最优解值大于零，对偶问题对应约束条件取等号。Key例已知线性规划问题Min

z=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5

≥4

2x1-x2+3x3+x4+x5

≥3x1,x2,x3,x4,x5≥0其对偶问题的最优解为y1=4/5,y2=3/5，试应用对偶理论求原问题的解。将y1=4/5,y2=3/5的值代入，得知

为严格不等式，于是由互补松驰性，必有

x2=x3=x4=0

解：写出对偶问题：Max

S=4y1+3y2y1+2y2≤2

y1-y2≤3

2y1+3y2≤5

y1+y2≤2

3y1+y2≤3

y1,y2≥0又因y1,y2>0，故原问题的两个约束条件必为紧约束，即有

x1+3x5=4

2x1+x5=3解得

x1=x5=1即X*=(1,0,0,0,1)T,Z*=57解的关系则原问题单纯表的检验数行对应其对偶问题的一个基解。Ys1是对应原问题中基变量XB的剩余变量，Ys2是对应原问题中基变量XN的剩余变量设原问题：Max

z=CXAX+Xs=bX,Xs≥0其对偶问题：Min

w=YbYA-Ys=CY,Ys≥0XBXNXs0CN1-CBB-1N1-CBB-1Ys1-Ys2-YB-1在单纯表中的位置可将(3.4),(3.5)式

Max

z=CBXB+CNXN(3.4)BXB+NXN=b(3.5)改写为

-z+CBXB+CN1XN1+0Xs

=0BXB+NXN+IXs=b最后得B-1即为初始基变量在最终单纯形表中的列向量组成。B-1初始基变量B-1为初始基变量在最终单纯形表中的列向量组成。3.4影子价格前面讲到，在单纯法的每一步迭代中，目标函数取值z=CBB-1b和检验数CN-CBB-1N中都有乘子

Y=CBB-1那么Y的经济意义是什么呢？设B是{maxz=CX|AX≤b,X≥0}的最优基，则z*=CBB-1b=Y*b两边对b求偏导有

z*/

b=CBB-1=Y*从对偶问题来看，变量yi*的经济意义是在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。这种资源的单位改变量引起目标函数的价值改变量，称为该资源的影子价格。影子价格的特征影子价格的大小客观地反映了资源在系统内的稀缺程度。根据互补松驰定理的条件，如果某一资源在系统内供大于求，其影子价格就为零。即增加该资源的供应不会引起系统目标的任何变化。如果某一资源是稀缺资源（即相应约束条件的剩余变量为零），则影子价格必然大于零。影子价格越高，资源在系统中越稀缺。影子价格的特征在完全市场经济条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大再生产；而当某种资源的市场价格高于影子价格时，企业应卖掉已有资源。影子价格是一种边际价值，与经济学所说的边际成本的概念相似，因而在经济管理中有重要的应用价值。影子价格是对系统资源的一种最优估价，只有当系统达到最优时，才能赋予该资源的这种价值，因此影子价格也称为最优价格。影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，影子价格是一种动态价格。事实上，如例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是：原问题对偶问题cj4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5Z3600-1/5-6/5用单纯形法求得原问题最优表为：由此，它们的最优解分别是X*=(6,4)T和Y*=(1/5,6/5)

最优值为：Z*=W*=36=24y1*+26y2*

其中y1*=1/5表示单独对材料增加1个单位，可使Z值增加1/5个单位的利润；y2*=6/5表示单独对工时增加1个单位，可使Z值增加6/5个单位的利润。

2.影子价格的定义

把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格。影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。51X*=(4,2)T，Z*=14Q(4,2)Z=14x1x24x1=164x2=12x1+2x2=844083Q(4.25,1.875)Z=14.125Q(4,2.5)Z=15.5Q(4,2)Z=14

MaxZ=2x1+3x2

x1+2x2≤8s.t.4x1≤164x2≤12

x1

,x2

≥0

8X1*=(4,2.5)T，Z1*=15.5X2*=(4.25,1.875)T，Z2*=14.125X3*=(4,2)T，Z3*=1452

1001/4000-21/21011/2-1/804422x1

0x5

3x2

x1x2x3x4x5

CBXBb

2300

0cj-1400-3/2-1/80下面是LP问题的最优单纯形表，其中x3,x4,x5为松弛变量则对偶问题的最优解为Y*=(1.5,0.125,0)T53资源的影子价格是针对具体生产或具体企业而言的：同一种资源在不同的生产条件下或不同的范围内可能有不同的影子价格；A产品的市场价格发生变化，资源的影子价格也会发生变化；C资源的数量结构不同，资源的影子价格也不同。b

III设备128台时原材料A4016公斤原材料B0412公斤23a21=3(1.5,1/6,0)c2=4(2,0,0)b1=10(0,0.5,0.75)

（2）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给（3）可以预测产品的价格产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。（4）可作为同类企业经济效益评估指标之一。对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。

（1）指出企业挖潜革新的途径影价>0，说明该资源已耗尽，成为短线资源。影价=0，说明该资源有剩余，成为长线资源。影子价格的参谋作用:案例讨论假设你是一家煤矿企业的经营者，根据以下新闻素材及本节所学的影子价格理论，你会对企业的经营发展做出什么样的决策？“碳达峰”是指我国承诺在2030年前，煤炭、石油、天然气等化石能源燃烧活动和工业生产过程以及土地利用变化与林业等活动产生的温室气体排放不再增长，达到峰值；“碳中和”是指在一定时间内直接或间接产生的温室气体排放总量，通过植树造林、节能减排等形式，以抵消自身产生的二氧化碳排放量，实现二氧化碳“零排放”。2021年9月25日，。人大重阳于会上发布报告《纠正运动式“减碳”：来自欧美国家的教训与启示》，报告原标题为《欧美碳减排经验教训及对中国的借鉴意义》，载《新经济导刊》2021年第02期，作者王文系中国人民大学重阳金融研究院执行院长、赵越系中国人民大学重阳金融研究院助理研究员。3.5对偶单纯形法根据对偶理论，也可以这样求解线性规划问题：初始解不一定要是基可行解，可以从非基可行解开始，逐步迭代达到最优解。对左端项b

可不作非负要求。对减去剩余变量的约束条件两端同乘-1后，可找到初始基变量。对偶单纯法步骤根据线性规划问题，列出初始单纯形表。检查b列数字：若都为非负，而检验数均非正，则已得最优解。若至少还有一个负分量，且检验数均非正，则进入第2步。确定换出变量按min{(B-1b)i|(B-1b)i<0}=(B-1b)l对应的基变量为换出变量。即b列负数中最小的一个对应的基变量换出。最“富”(负)的b确定换入变量在单纯形表中检查xl所在行的各个系数

alj(j=1,2,…,n)

若所有alj≥0

，则无可行解。若存在alj<0

，计算

，并按

规则所对应的非基变量为换入变量。迭代以

alk为主元素，按原单纯形法在表中进行迭代运算，得到新的单纯形表。重复1-4的步骤，直到找到最优解例用对偶单纯法求解线性规划问题

Min

w=2x1+3x2+4x3

x1+2x2+x3

≥32x1-

x2+3x3

≥4x1,x2,x3

≥0这个问题化为

Maxz=-2x1-3x2-4x3

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4x1,x2,x3,x4,x5

≥0对偶单纯

形法求解cBxBbx1x2x3x4x5-2-3-400x4x500-3-4-1-2-21-1-31001-2-3-400cj-zj

1[-2]4/3换出变量的确定min{(B-1b)i|(B-1b)i<0}=(B-1b)l-4计算

确定换入变量x4x10-2-10-5/2-1/21/23/210-1/2-1/20-4-10-1cj-zj

12

8/52x2x1-3-22/5010-1/57/5-2/5-1/51/5-2/500-9/5-8/5-1/5cj-zj

1-z=28/511/5[-5/2]取得最优解X*=(11/5,2/5,0,0,0)TZ*=28/5最终单纯形表对偶问题的最优解为Y*=(8/5,1/5)x2x1-3-22/5010-1/57/5-2/5-1/51/5-2/500-9/5-8/5-1/5cj-zj

1-z=28/511/5cBxBbx1x2x3x4x5-2-3-400B-1熟练掌握对偶单纯形法练习：用对偶单纯形方法求解：解:

（1）引入松弛变量x3,x4,x5

化为标准形，并在约束等式两侧同乘-1，得到取x3,x4,x5为基变量，此式即为典式形式，并且检验数皆非正，因此可构初始对偶单纯形表例用对偶单纯形法求解下面线性规划解:

构造对偶单纯形表进行迭代，从最后的表可以看到，B-1b列元素中有-2<0，并且，-2所在行各元素皆非负，因此，原规划没有可行解。3.6灵敏度分析灵敏度分析，是指对系统或事物因周围条件变化显示出来的敏感性程度的分析。资源向量的灵敏度分析Rangeoffeasibilityforright-hand-sidecoefficients(bi)价值向量的灵敏度分析Rangeofoptimalityforobjectivefunctioncoefficients(cj)技术系数的灵敏度分析Rangeofoptimalityformatrixcoefficients(aij)灵敏度分析不需要用单纯形法从头再算只需把发生变化的个别系数，经过一定计算后，直接填入最终单纯形表中，并进行检查和分析如最优解改变，可用单纯形法或对偶单纯法继续迭代计算，直到找到新的最优解。1.目标函数系数变化的灵敏度分析

假定只有一个cj变化，假定cj从cj变到cj*=cj+Δcj，当Δcj在什么范围内变化时，不会影响最优解。(1)分析什么？(2)怎么分析？最优解不变的充要条件是：假定只有一个cj变化，分两种情况讨论：1）cj

是非基变量的系数

设cj变化量为

cj，若希望cj变化后最优基不变，检验数应满足以下条件：

j’

=(cj+

cj)-cBB-1pj

=

cj-cBB-1pj

+

cj=

j+

cj

0

得到:

cj

-

j

由

cj

-

j及最优条件

j

0，cj只在增加方向受限制，在下降方向不受限制：cj增加时，变量对目标函数的贡献增加，增加足够大时，检验数会大于零，使该变量入基而引起最优基改变;cj下降时，变量对目标函数的贡献下降，检验数变得更负，最优基不会变化。非基变量目标系数允许变化范围为: -

cj

-

j

j

JN

满足以上条件，解和目标值不会改变。非基变量Cj的变化范围非基变量Cj变化，只影响它自己的检验数Cj35000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3检验数j000-1/2-1

例

Maxz=-2x1-3x2-4x3S.t.

-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥0最优单纯形表

从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。2)cj是基变量的系数

基变量的cj变化会引起cBB-1变化,从而引起所有检验数变化。若要使所有检验数满足最优条件,有以下条件:

k=ck-(cB+

cB)B-1pk

0k

JN假定cj是当前基的第r个基变量，即：

cj=(

cB)r

cB=(0,...,(

cB)r,...,0) =(0,...,

cj,...,0)从而有：

k’

=ck-(cB+

cB)B-1pk =ck-cBB-1pk-(0,..,(

cB)r,..,0)B-1pk =

k-

cj(B-1pk)r

0 k

JN令

rk=(B-1pk)r

得：

k’

=

k-

cj

rk

0 k

JN在上述变化范围内：目标函数值的改变量：

z=

cjxj

对偶解的改变量：

y=

cBB-1

原问题的最优基和最优解不会改变。解不等式组

k’

=

k-

cj

rk

0k

JN

得

cj

的变化范围：

maxk{-

,

k/

rk

rk>0}

cj

mink{+

,

k/

rk

rk<0}基变量CBl的变化范围CjC15000比值CBXBbx1x2x3x4x50x340012/3-1/35x260101/20C1x14100-2/31/3检验数j0002C1/3-5/2-C1/3例胜利家具厂生产桌子和椅子两种家具。桌子售价50元。椅子售价30元，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大?max

z=50x1+30x2

4x1+3x2

120 2x1+x2

50x1,x2

0例:对上例的目标函数系数进行敏感性分析。解：家具厂问题的最优单纯形表：c1:x1在基的第二行(r=2),非基变量下标k=3和4,

23=-1/2,

24=3/2,可得:max{-

,-15/1.5}

c1

min{+

,-5/(-0.5)}-10

c1

10即:0－30×1－（50＋

c1）×(－1/2)0;

0－30×(-2)－（50＋

c1）×3/20c2：x2在基的第一行，r＝1，

13＝1，

14＝-2，可得：max{-

,(-5)/(1)}

c2

min{+

,(-15)/(-2)}-5

c2

7.5即:0－(30+

c2)×1－50×(－1/2)0;

0－(30+

c2)×(-2)－50×3/202.右边项发生变化的灵敏度分析(1)分析什么？

假定只有一个br变化，假定br从br变到br*=br+Δbr，当Δbr在什么范围内变化时，不会影响最优基。（不改变产品种类，只调整数量）(2)怎么分析？最优基不变的充要条件是：为了保持最优基不变，应使，即

解不等式组，得

例如

参数bi的变化范围

b3发生变化例:

对例的右边项进行敏感性分析。1)对b1进行分析：

i=1对应基的第一列，

11=

13=1，

21=

23=-0.5max{-

,-20/1}

b1

min{+

,-15/(-0.5)}

20

b1

30即：

20

b1

30对b2进行分析：i=2对应基的第二列，

12=

14=-2，

22=

24=1.5max{-

,-15/1.5}

b2

min{+

,-20/(-2)}

10

b2

103