第二章对偶理念及灵敏度分析

第二章对偶理念及灵敏度分析第1页，课件共86页，创作于2023年2月一、问题的提出例一、资源的合理利用问题已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？第2页，课件共86页，创作于2023年2月一、问题的提出1810单件利润150（设备）51C100（煤炭）32B170（钢材）25A资源限制乙甲单件产消耗品资源第3页，课件共86页，创作于2023年2月下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（收费的最底线）？第4页，课件共86页，创作于2023年2月第5页，课件共86页，创作于2023年2月一、问题的提出该问题的数学模型为：第6页，课件共86页，创作于2023年2月模型对比请总结规律第7页，课件共86页，创作于2023年2月1、对称型对偶问题：已知

P，写出D。（一）、对偶问题的形式

二、线性规划的对偶理论第8页，课件共86页，创作于2023年2月原问题：maxz=2x1+3x2

s.t2x1+2x2≤12

x1+2x2≤8

4x1≤16

4x2≤12

x1≥0x2≥0

对偶问题：minw=12y1+8y2+16y2+12y4

s.t2y1+1y2+4y3+0y4≥2

2y1+2y2+0y3+4y4≥3

y1,y2,y3,y4≥0非对称型对偶问题如何求解？第9页，课件共86页，创作于2023年2月对偶问题的其变换形式归纳如下原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项变向变向大约束，小变量第10页，课件共86页，创作于2023年2月例一、写出线性规划问题的对偶问题第11页，课件共86页，创作于2023年2月例二、原问题第12页，课件共86页，创作于2023年2月例三：第13页，课件共86页，创作于2023年2月例四、原问题第14页，课件共86页，创作于2023年2月对偶问题第15页，课件共86页，创作于2023年2月例五、线性规划问题如下：第16页，课件共86页，创作于2023年2月第17页，课件共86页，创作于2023年2月练习：第18页，课件共86页，创作于2023年2月第19页，课件共86页，创作于2023年2月（二）、对偶问题的性质1、对称性定理：对偶问题的对偶是原问题。以下讨论仅就“对称形式”讨论。因其他形式都可以转化成“对称形式”，故所有结论适用于所有形式。第20页，课件共86页，创作于2023年2月2、弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有推论⑴.若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。第21页，课件共86页，创作于2023年2月推论⑵.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：问题无界无可行解无可行解问题无界对偶问题原问题第22页，课件共86页，创作于2023年2月3、最优性判别定理：

若X*

和Y*分别是P和D

的可行解且CX*=Y*b，则X*.Y*分别是问题P和D

的最优解。下面来求原问题和对偶问题的最优解：第23页，课件共86页，创作于2023年2月Cj

CBCN0系数基

XBXNXSCBXBB-1b

IB-1NB-1

Z=CBB-1b0

CN-CBB-1N

-CBB-1C

-CBB-1A≤0

最优解的判定条件是：-CBB-1≤0

CBB-1≥0

令Y’=CBB-1-CBB-1≤0

由C

-CBB-1A≤0

则CBB-1A≥C即Y’A≥C即A’Y≥C’W=Y’b=CBB-1b=CBX=Z则Y’≥0

则Y≥0

第24页，课件共86页，创作于2023年2月4、对偶定理（强对偶性）：若一对对偶问题P和D

都有可行解，则它们都有最优解，且目标函数的最优值必相等。推论（3）.若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。推论（4）.在一对对偶问题（P）和（D）中，若一个可行，而另一个不可行，则该可行的问题无界。原问题有最优解，则对偶问题只少有一个可行解。并且这一解即为对偶问题的最优解。第25页，课件共86页，创作于2023年2月综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①.都有可行解，都有最优解，分别设为X*

和Y*，则必有CX*=Y*b；②.一个问题无界，则另一个问题无可行解；③.两个都无可行解。第26页，课件共86页，创作于2023年2月5、互补松弛定理：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；如果约束条件取严格不等式，则其对应的对偶变量一定为零。严格不等式约束称为松约束，而把严格等式约束称为紧约束。第27页，课件共86页，创作于2023年2月例4、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为第28页，课件共86页，创作于2023年2月用图解法求出：Y*=（1.3），W=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）第29页，课件共86页，创作于2023年2月又由于y*1＞0，y*2＞0，原问题的约束必为等式，即化简为此方程组为无穷多解令x5=0,得到x1=1，x2=2

即X*1=（1.2.0.0.0）为原问题的一个最优解，Z=11。

再令x5=2/3，得到x1=5/3，x2=0即X*2（5/3.0.0.0.2/3）也是原问题的一个最优解，Z=11。第30页，课件共86页，创作于2023年2月例5、已知原问题的最优解为X*=（0.0.4）试求对偶问题的最优解。（最优解与最优值的区别）解：（1）（2）（3）第31页，课件共86页，创作于2023年2月将X*=（0.0.4）代入原问题中，有下式：所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为

Y*=（0.0.3），W=12。第32页，课件共86页，创作于2023年2月6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。设原问题为：maxZ=CXAX≤

bX≥0引入xs，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0，则求得最优解。此时，xs对应的σjs

为-Y*，故求对偶Y*，只要将最优单纯形表上xs

对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1第33页，课件共86页，创作于2023年2月例一、第34页，课件共86页，创作于2023年2月cj1018000cBxBbx1x2x3x4x50x3170521000x4100230100x515015001-Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最终表第35页，课件共86页，创作于2023年2月由上表可知：

X*=（50/7.200/7），Z=4100/7对偶问题的最优解：

Y*=（0.32/7.6/7），W=4100/7第36页，课件共86页，创作于2023年2月例二、第37页，课件共86页，创作于2023年2月cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3-Mcj3-1-100-M-McBxBbx1x2x3x4x5x6x70x4111-211000-Mx63-4120-110-Mx71-2010001-Z3-6M-1+M-1+3M0-M00第38页，课件共86页，创作于2023年2月所以，X*=（4.1.9），Z=2∴y*1=(0－σ4)=1/3y*2=(－M－σ6)=－M－(1/3－M)=－1/3y*3=(－M－σ7)=－M－(2/3－M)=－2/3Y*=（1/3.－1/3.－2/3）W=2初始基变量的检验数σ4=－1/3，σ6=1/3－M,σ7=2/3－M第39页，课件共86页，创作于2023年2月定义：在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*

的改变量y*i

称为第i个约束条件的影子价格，又称为边际价格。三、对偶问题的经济解释——影子价格

第40页，课件共86页，创作于2023年2月设：B是问题P的最优基，由前式可知，

Z*=CBB-1b=Y*b=y*1b1+y*2b2+…+y*Ibi+…+y*mbm

CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1即y*i

表示Z*对bi的变化率。第41页，课件共86页，创作于2023年2月其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第i个约束条件的影子价格。第42页，课件共86页，创作于2023年2月若第i种资源的单位市场价格为mi。当yi>mi

时，企业愿意购进这种资源，单位纯利为yi－mi，则有利可图；如果yi<mi，则企业有偿转让这种资源，，可获单位纯利mi－yi，否则，企业无利可图，甚至亏损。第43页，课件共86页，创作于2023年2月012345678123456⑴⑵⑶⑷x2

x1(42)⑴′

X*=（4.2.0.0.0.4）Y*=（0.3/2.1/8.0）最优值为14最优值没有发生变化即y1=0第44页，课件共86页，创作于2023年2月012345678123456⑴⑵⑶⑷x2

x1(45/2)⑵′最优值为15.5，变化了3/2，即y2=3/2即b2增加一个单位，y2增加了3/2，即第二种资源的边际价格为3/2第45页，课件共86页，创作于2023年2月生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零。当资源的影子价格不为零时，表明该种资源生产过程已耗尽完毕。第46页，课件共86页，创作于2023年2月第47页，课件共86页，创作于2023年2月对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。对偶单纯形法的基本思想：在保持对偶问题为可行解的基础上（这时原问题一般为非可行解），通过迭代，当原问题也达到可行解时，即得到目标函数最优值。四、对偶单纯形法W=Y’b=CBB-1b=CX=ZY’=CBB-1单位矩阵I行变换，即基变换与第48页，课件共86页，创作于2023年2月3、计算步骤：①建立初始单纯形表，确定原问题或对偶问题的基（单位矩阵）。条件是检验数全部≤0。(原问题是不是可行解没有关系）

基变换：先确定换出变量——b列中的负元素（一般选最小的负元素）对应的基变量出基即第49页，课件共86页，创作于2023年2月

然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。

如果存在（最小比值原则，保证所有的检验数<=0）则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。如果不存一个alj<0,则原问题无可行解，那么对偶问题就存在无界解。第50页，课件共86页，创作于2023年2月④按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解。即所有的检验数小于等于零并且右端项大于等于零。跳出循环地方的有几处？（保证原问题与对偶问题都有可行解，这时就得到两问题的最优解，为什么？？）第51页，课件共86页，创作于2023年2月例一、用对偶单纯形法求解：解：将模型转化为如果用单纯形法如何求解？第52页，课件共86页，创作于2023年2月cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001(-9/-1.-12/-1.-15/-5)-Z′

0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5(-30/-9.-45/-14.-1/5/-3)-15x314/51/51/5100-1/5-Z′

42-6-9000-3第53页，课件共86页，创作于2023年2月cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9.-45/-9.-33/-1)-15x315/71/140101/14-3/14-Z′

501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z′

72000-1/3-3-7/3第54页，课件共86页，创作于2023年2月

所以，

X*=（2.2.2.0.0.0），Z′*=－72，

原问题Z*=72

其对偶问题的最优解为：

Y*=(1/3.3.7/3)，W*=72第55页，课件共86页，创作于2023年2月练习：第56页，课件共86页，创作于2023年2月cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301-Z-2-3-400cj-2-3-400cBxBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z0-4-10-1第57页，课件共86页，创作于2023年2月cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z28/500-3/5-8/5-1/5Y=（8/5.1/5）X=（2/5.11/5.0）Z=28/5第58页，课件共86页，创作于2023年2月灵敏度分析的步骤：

1.将参数的改变通过矩阵计算反映到最终表中；

2.检查原问题是否可行解；

3.检查对偶问题是否可行解；

4.按以下原则得出结论或决定继续计算的步骤。五、灵敏度分析第59页，课件共86页，创作于2023年2月σj=cj－CBB－1Pj=B－1Pj

=B－1b关键是求B-1即找单位矩阵I第60页，课件共86页，创作于2023年2月求下列LP问题第61页，课件共86页，创作于2023年2月Cj0-130-20CBXBbx1x2x3x4x5x60x1713-10200x4120-2[4]1000x6

100-43081σj

0-130-200x1101[5/2]01/4203x330-1/211/4000x6

10-5/20-3/481σj01/20-3/4-20-1x242/5101/104/503x351/5013/102/500x6

11100-1/2101σj-1/500-4/5-12/50第62页，课件共86页，创作于2023年2月B3=（P2，P3，P6）=B3－1=第63页，课件共86页，创作于2023年2月

求下列LP问题的最优解

第64页，课件共86页，创作于2023年2月第65页，课件共86页，创作于2023年2月B4－1=B3=（P4，P2，P3）=B3－1=B4=（P1，P2，P3）=第66页，课件共86页，创作于2023年2月例：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划已知最优表如下。（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。一、价值系数cj的变化分析第67页，课件共86页，创作于2023年2月cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3第68页，课件共86页，创作于2023年2月σ4=c2－5≤0σ5=5－2c2≤05/2≤c2≤5cj5c2

000CBXBbx1x2x3x4x50x3250012-55x1351001-1c2

x2

10010-12000c2-55-2c2最优解X*=（35，10，25，0，0）保持不变。（1）第69页，课件共86页，创作于2023年2月Cj56000CBXBbx1x2x3x4x50x325001[2]-55x1351001-16x2

10010-12σj

0001-70x425/2001/21-5/25x145/210-1/203/26x2

45/2011/20-1/2σj00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2（2）第70页，课件共86页，创作于2023年2月XB=B－1b例：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。

二、右端常数bi的变化分析第71页，课件共86页，创作于2023年2月cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最优基：B=（P3，P1，P2）B－1=第72页，课件共86页，创作于2023年2月（1）B－1==≥0解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变z*=5×（80－b3）+4×（－80+2b3）=80+3b3=也可计算：B－1B－1见书上的P65例6第73页，课件共86页，创作于2023年2月（2）当b3=55时

=x2

x1x50-11/5-3/500σj0-1/52/51020403/5-1/5013051-2/5-1/50050-32-1[-5]x50-1000σj

-101030x2

4100125x152100-25x30x4x3x2x1bXBCB0045Cj第74页，课件共86页，创作于2023年2月三、增加一个新变量的分析例2.10（续例2.8）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6=。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？第75页，课件共86页，创作于2023年2月σ6=c6－CBB－1P6=c6－（0，5，4）=c6－5/2=B－1P6==第76页，课件共86页，创作于2023年2月Cj540003CBXBbx1x2x3x4x5x60x3250012-5[1]5x1351001-11/26x2

10010-120σj

000-1-31/23x6250012-515x145/210-1/203/204x2

10010-120σj00-1/2-2-1/20第77页，课件共86页，创作于2023年2月四、增加新的约束条件的分析例2.11假设在例2.8中，还要考虑一个新的资源约束：4x1+2x2≤1504x1+2x2+x6=150X*=（35，10，25，0，0）T第78页，课件共86页，创作于2023年2月4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x2

10010-1200x6150420001000-1-30不管是单纯形法还对偶单纯形法都是从单位矩阵开始的，因此要先找单位矩阵第79页，课件共86页，创作于2023年2月Cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x210010-1200x6

150420001σj

000-1-300x3250012-505x1351001-104x210010-1200x6

-10000[-2]01σj000-1-300x3150010-515x1301000-11/24x21501002-1/20x4

500010-1/2σj0000-3-1/2第80页，课件共86页，创作于2023年2月五、