第二章线性规划的对偶理论与灵敏度分析教材课件

运筹学赵明霞山西大学经济与管理学院2023/12/61第二章线性规划的对偶理论与灵敏度分析线性规划的对偶问题影子价格对偶单纯形法灵敏度分析2023/12/62例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少件．使获取的利润为最大。设：x1——A产品的生产量

x2——B产品的生产量利润max

z=2x1+x2

约束条件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.第一节线性规划的对偶问题2023/12/635x2

+x3=156x1+2x2+x4=24x1+x2

+

x5=5x1，x2，x3

，x4

，x5

≥0约束条件st.利润maxz=2x1+x2

+0x3+0x4+0x5

标准化最终单纯形表C21000θCBXBbx1x2x3x4x50

0

0x3x4x515245051006201011001σ

21000最优解X*=(7/2,3/2,15/2,0,0)Z*=17/2C21000θCBXBbx1x2x3x4x50

2

1x3x1x215/27/23/20015/4-15/210

01/4-1/2010-1/43/2σ

000-1/4-1/22023/12/645x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥0约束条件把解X=(7/2,3/2)代入原问题(因为x3、x4、x5为附加变量)分析5×3÷2＝15/2245A有空闲B设备已经饱和调试工序也已经满负荷

一个问题？

市场上设备A、设备B和调试工序每小时值多少钱？在什么价位时，才能使美佳公司愿意出让自己的资源？＜＝＝2023/12/656y2+y3分析设：y1—设备A值的价值y2—设备B值的价值

y3—调试工序值的价值≥25y1+2y2+y31≥z=15y1+24y2

+5y3总价值miny1,y2,y3≥0st.2023/12/666y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.z'=-15y1-24y2-5y3maxst.6y2+y3–y4=25y1+2y2+y3–y51=y1,y2,y3,y4,y5≥0C-15-24-500-M-MθCBYBby1y2y3y4y5y6y7-M-My6y721061-10105210-101σM-158M-242M-5-M-M00问题求解2023/12/67C-15-24-500θCBYBby1y2y3y4y5-24-5y2y31/41/2-5/410-1/41/415/2011/2-3/2

σ-15/200-7/2-3/2Y=(0,¼,½,0,0)z'=-17/2z=17/22023/12/68Y=(0,¼,½,0,0)问题分析问题的解6y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.问题：？原问题：利润max

z=2x1+x2

约束条件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.问题的解X*=(7/2,3/2,15/2,0,0)Z*=17/2Z*=17/25*3/2=15/215＜6*7/2+2*3/2=2424=7/2+3/2=55=结论两个问题的最优解的值一致最大值问题可行解的目标值必定不大于最小值问题可行解的目标值一个问题的剩余变量（松弛变量）不为0（即有资源剩余），则对应问题的解为0一个决策变量不为0，则对应的问题的约束条件的剩余变量(松弛变量)为0(即资源彻底用完)估价——影子价格（即增加单位资源所得到的贡献）Z=ω=CX=Yb

Z/

b=(Yb)

'=Y2023/12/69C21000CBXBbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/210

01/4-1/2010-1/43/2σ000-1/4-1/2-σ0001/41/2利润max

z=2x1+x2

约束条件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.6y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.C-15-24-500CBYBby1y2y3y4y5-24-5y2y31/41/2-5/410-1/41/415/2011/2-3/2

σ-15/200-7/2-3/2-σ15/2007/23/2Y=(0,¼,½,0,0)X*=(7/2,3/2,15/2,0,0)问题变量问题剩余松弛变量解的关系2023/12/610一、对偶问题对称形式X

≥0st.AX≤bmaxz=CX其中：C=（c1，c2,…,cn)b=（b1，b2,…,bm)TX=（x1，x2,…,xn)TY=（y1，y2,…,ym)TA=a11a12…a1na11a12…a1n

┇┇…┇am1am2

…anmY

≥0st.ATY≥CTminw=YTb利润max

z=2x1+x2

约束条件5x2

≤156x1+2x2≤24x1+x2≤5x1，x2≥

0st.6y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.2023/12/611非对称形式x1≥0,x2≤

0,x3无约束st.a11x1+a12x2+a13x3

≤b1a21x1+a22x2+a23x3=b2a31x1+a32x2+a33x3≥b3maxz=c1x1+c2x2+c3x3

x1,x2',x3'，x3"

≥0st.a11x1-a12x2'+a13x3'-a13x3"

≤b1a21x1-a22x2'+a23x3'-a23x3"

≤b2-a21x1+a22x2'_a23x3'+a23x3"

≤-b2-a31x1+a32x2'-a33x3'+a33x3"

≤-b3maxz=c1x1-c2x2'+c3x3'-c3x3"

y1,y2',y2"

，y3'≥0st.a11y1+

a21y2'–a21y2"-a31y3'≥c1-a12y1-

a22y2'+a22y2"-a32y3'≥-c2a13y1+

a23y2'–a23y2"-a33y3'≥c3-a13y1-

a23y2'+a23y2"+a33y3'≥-c3minw=b1y1+b2y2'-b2y2"-b3y3'minw=b1y1+b2y2+b3y3a11y1+

a21y2+a31y3≥c1a12y1+

a22y2+a32y3≤

c2a13y1+

a23y2+a33y3

=c3st.y1≥0,y2无约束，y3≤02023/12/612二、对偶规则

原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的系数矩阵转置后为对偶问题系数矩阵变量、约束与系数2023/12/613变量与约束对应关系原问题（对偶问题）对偶问题（原问题）maxz=CX

AX(≤＝≥)bX(≤＝≥)0或无约束minw=Yb

ATY(≤＝≥)C

Y(≤＝≥)0或无约束有n个决策变量xj(j＝0、2……n)xj

≥0变量

xj

≤

0

xj

无约束有n个约束条件对应的约束为≥约束对应的约束为≤

对应的约束为＝有m个约束条件对应的约束为≤

约束对应的约束为≥

对应的约束为＝有m个决策变量yj(j＝0、2……m)yj

≥0变量

yj

≤

0

yj

无约束2023/12/614三、对偶问题的基本性质（对称形）对称性：对偶问题的对偶问题是原问题弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1无界性：原问题无界，对偶问题无可行解需要说明的是：这些性质同样适用于非对称形问题2023/12/615X

≥0st.AX≤bmaxz=CXX,Xs≥0st.AX+IXs=bmaxz=CX+0XsCC0CBXBbXXs0Xsb

AIσCCBCN0CBXBbXBXNXs0Xsb

BNIσCCBCN0CBXBbXBXNXsCBXBB-1b

B-1BB-1NB-1IσCB-CBB-1B

CN-CBB-1N0-CBB-1ICCBCN0CBXBbXBXNXsCBXBB-1b

B-1BB-1NB-1Iσ

0

CN-CBB-1N-CBB-12023/12/616C21000θCBXBbx1x2x3x4x515245051006201011001σ

C21000θCBXBbx1x2x3x4x515/27/23/20015/4-15/210

01/4-1/2010-1/43/2σ

B与B-1B-1=15/4-15/201/4-1/20-1/43/2B=1050620112023/12/617第二节影子价格bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，为区别起见，称为影子价格(shadowprice)。2023/12/6181、资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。2、影子价格是一种边际价格，若对式中目标函数z求bi的偏导数可得。这说明yi*的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数z的增量。2023/12/6193、资源的影子价格实际上又是一种机会成本。在完全市场经济条件下，当第2种资源的市场价格低于影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平，才处于平衡状态。

4、在上一节对偶问题的互补松弛性质中有时，yi=0；当yi>0时，有，这表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。

5、当产品产值大于隐含成本时，表明生产该产品有利，可在计划中安排，否则用这些资源来生产别的产品更为有利，就不在生产计划中安排。这就是单纯形表中各个检验数的经济意义。2023/12/6206、一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。如在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如在社会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上缴的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。2023/12/621第三节对偶单纯形法CCBCN0CBXBbXBXBXsCBXBB-1b

B-1BB-1NB-1Iσ0

CN-CBB-1N-CBB-1对于单纯形法叠代过程本质：确保1）z变大；2）B-1b≥0由对偶理论知道，当原问题为最优解时，-σ≥0且为对偶问题的最优解，因此人们提出对偶单纯形法。叠代过程本质：1）σ≤

0；2）逐步使B-1b≥0与2023/12/6226y2+y3≥25y1+2y2+y31≥z=15y1+24y2

+5y3miny1,y2,y3≥0st.z'=-15y1-24y2-5y3st.max6y2+y3–y4=25y1+2y2+y3–y51=y1,y2,y3,y4,y5=0问题求解z'=-15y1-24y2-5y3+0y4

+0y5

st.max-6y2-y3+y4=-2-5y1-2y2-y3+y5-1=y1,y2,y3,y4,y5≥02023/12/6231.确定出基变量。在常数列中找一个最小的负常量，把这个常量所在行作为出基变量σ0[-6]-110

-5-2-101-2-1y1

y2

y3y4y5bYBCB-15-24-500Cy4

y50

0-15-24-5

002.确定入基变量。在系数列中找负数，把这个常量所在行作为入基变量。2023/12/624σ011/6–1/60-50-2/3–1/311/3-1/3y1y2y3y4y5bYBCB-15-24-500Cσ-5/410-1/41/415/2011/2-3/21/41/2-150-1-40y2y5-24

0-24

-5y2y3-15/200-7/2–3/22023/12/625第四节灵敏度分析灵敏度分析是指系统或事物对周围环境变化显示出来的敏感程度。在LP问题中，aij、cj、bi都有可能发生变化，分析这些变化对最优解或目标值的影响程度就是灵敏度分析。2023/12/626cj通常表示一些估计或预测的数据，随市场而变化；aij通常随工艺技术条件的改变而改变；bi则反映了企业资源状况。CBB-1bC

-CBB-1AB-1bB-1A原始数据A，b，CA=(P1P2…

Pn)①Z0=CBB-1bXB=B-1b②

A=C

-CBB-1A

N=CN-CBB-1N

j=Cj-CBB-1Pj

2023/12/627∆b*=B-1∆b

最优解的增量∆b*与初始b的增量∆b

成B-1倍变化∆Pj*

=B-1∆Pj最优解时的系数增量∆Pj*

与初始的系数增量∆Pj也成B-1倍变化最优性条件可表达为：2023/12/628通常需要分析的项目：(1)参数a，b，C在什么范围内变动，对当前方案无影响？(2)参数b，b，c中的一个(几个)变动，对当前方案影响程度？(3)如果最优方案改变，如何用简便方法求新方案？2023/12/629灵敏度分析的步骤：1、将参数的改变通过计算反映到最终单纯形表上来。

具体计算方法是，按下列公式计算出由参数aij，bi，cj的变化而引起的最终单纯形表上有关数字的变化。

2、检查原问题是否仍为可行解。

3、检查对偶问题是否仍为可行解。

4、按下表所列情况得出结论或决定继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表重新计算2023/12/630一、分析cj的变化线性规划目标函数中变量系数cj的变化仅仅影响到检验数(cj-zj)的变化。所以将cj的变化直接反映到最终单纯形表中，只可能出现上页表中前两种情况。2023/12/631

例1-1：在美佳公司例子中，(1)若家电I的利润降至1.5元/件，而家电II的利润增至2元/件时，美佳公司最优生产计划有何变化；(2)若家电I的利润不变，则家电II的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？2023/12/632

解(1)：将家电I、II的利润变化直接反映到最终单纯形表中得到表如下：cj1.52000CB基bx1x2x3x4x50x315/2001[5/4]-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/4

因变量x4的检验数大于零，故需继续用单纯形法迭代计算，得表如下：cj1.52000CB基bx1x2x3x4x50x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳公司随家电I、II的利润变化应调整为生产2件I，生产3件II。2023/12/633

(2)：设家电II的利润为(1+m)元，反映到最终单纯形表中，得表如下：cj21+m000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21+mx23/2010-1/43/2cj-zj000-1/4+1/4m-1/2-3/2m为使上表中的解仍为最优解，应有：解得：即家电II的利润c2的变化范围应满足：2023/12/634二、分析bi的变化右端项bi的变化在实际问题中反映为可用资源数量的变化。bi变化反映到最终单纯形表上将引起b列数字的变化，在表中可能出现第一或第三的两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。2023/12/635例1-2：在上述美佳公司例子中，(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；(2)若设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。2023/12/636

解(1)：因有，则：将其反映到最终单纯形表中得表如下。由于该表中原问题为非可行解，故用对偶单纯形法继续计算，其结果如下量表所示：2023/12/637cj21000CB基bx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2cj-zj000-1/4-1/2对偶单纯形法处理后结果：cj21000CB基bx1x2x3x4x50x315051002x15110010x420-401-6cj-zj0-100-2由此美佳公司的最优计划改变为只生产5件家电I。2023/12/638

(2)：设调式工序每天可用能力为(5+m)h，因有将其反映到最终单纯形表中，其b列数字为：当b>=0时问题的最优基不变，解得-1<=m<=1。由此调试工序的能力应在4h-6h之间。2023/12/639三、增加一个变量xj的分析增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为：

1、计算

2、计算

3、若，原最优解不变，只需将计算得到的和直接写入最终单纯形表中；若，则按单纯形法继续迭代计算找出最优。

例1-3：在美佳公司例子中，设该公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该种产品是否值得投产；若投产，该公司的最优生产计划有何变化。2023/12/640

解设该公司生产x6件家电III，有c6=3，P6=(3,4,2)T将其反映到最终单纯形表中得表如下:2023/12/641因，故用单纯形法继续迭代计算结果为：cj210003CB基bx1x2x3x4x5x60x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/2[2]cj-zj000-1/4-1/21cj210003CB基bx1x2x3x4x5x60x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40由上表可知，美佳公司新的最优生产计划应该为每天生产7/2件家电I，51/4件家电III。2023/12/642四、分析参数aij的变化

aij的变化使线性规划的约束系数矩阵A发生变化。若变量xj在最终单纯形表中为基变量，则aij的变化分析步骤可参照本节之三；若变量xj在最终单纯形表中为基变量，则aij的变化将使相应的B和B-1发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需引进人工变量先将原问题的解转化为可行解，再用单纯形法求解。

例1-4：在美佳公司的例子中，若家电II每件需设备A、B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。2023/12/643

解先将生产工时变化后的新家电II看作是一种新产品，生产量x2’，仿上一节的步骤直接计算和并反映到最终单纯形表中。其中：将其反映到最终单纯形表中得表如下。2023/12/644因x2已变换为x2’，故用单纯形算法将x2’替换出基变量中的x2，并在下一个表中不再保留x2，得表如下：cj213000CB基bx1x2x2’x3x4x50x315/20011/215/4-15/22x17/2101/201/4-1/21x23/201[1/2]0-1/43/2cj-zj003/20-1/4-1/2cj23000CB基bx1x2’x3x4x50x3-90014-242x121001/2-23x2’3010-1/23cj-zj0001/2-52023/12/645上表中，原问题与对偶问题均非可行解，故先设法使原问题变为可行解。上表中第1行的约束可以写为：x3+4x4-24x5=-9两边同乘以(-1)，再加上人工变量x6得-x3-4x4+24x5+x6=9将上式替换上表第一行，得：cj23000-MCB基bx1x2’x3x4x5x6-Mx6900-1-4[24]12