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

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

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

二、线性规划的对偶理论第八页，共八十六页，编辑于2023年，星期四原问题：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非对称型对偶问题如何求解？第九页，共八十六页，编辑于2023年，星期四对偶问题的其变换形式归纳如下原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项变向变向大约束，小变量第十页，共八十六页，编辑于2023年，星期四例一、写出线性规划问题的对偶问题第十一页，共八十六页，编辑于2023年，星期四例二、原问题第十二页，共八十六页，编辑于2023年，星期四例三：第十三页，共八十六页，编辑于2023年，星期四例四、原问题第十四页，共八十六页，编辑于2023年，星期四对偶问题第十五页，共八十六页，编辑于2023年，星期四例五、线性规划问题如下：第十六页，共八十六页，编辑于2023年，星期四第十七页，共八十六页，编辑于2023年，星期四练习：第十八页，共八十六页，编辑于2023年，星期四第十九页，共八十六页，编辑于2023年，星期四（二）、对偶问题的性质1、对称性定理：对偶问题的对偶是原问题。以下讨论仅就“对称形式”讨论。因其他形式都可以转化成“对称形式”，故所有结论适用于所有形式。第二十页，共八十六页，编辑于2023年，星期四2、弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有推论⑴.若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。第二十一页，共八十六页，编辑于2023年，星期四推论⑵.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：问题无界无可行解无可行解问题无界对偶问题原问题第二十二页，共八十六页，编辑于2023年，星期四3、最优性判别定理：

若X*

和Y*分别是P和D

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

的最优解。下面来求原问题和对偶问题的最优解：第二十三页，共八十六页，编辑于2023年，星期四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

第二十四页，共八十六页，编辑于2023年，星期四4、对偶定理（强对偶性）：若一对对偶问题P和D

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

和Y*，则必有CX*=Y*b；②.一个问题无界，则另一个问题无可行解；③.两个都无可行解。第二十六页，共八十六页，编辑于2023年，星期四5、互补松弛定理：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；如果约束条件取严格不等式，则其对应的对偶变量一定为零。严格不等式约束称为松约束，而把严格等式约束称为紧约束。第二十七页，共八十六页，编辑于2023年，星期四例4、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为第二十八页，共八十六页，编辑于2023年，星期四用图解法求出：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）第二十九页，共八十六页，编辑于2023年，星期四又由于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。第三十页，共八十六页，编辑于2023年，星期四例5、已知原问题的最优解为X*=（0.0.4）试求对偶问题的最优解。（最优解与最优值的区别）解：（1）（2）（3）第三十一页，共八十六页，编辑于2023年，星期四将X*=（0.0.4）代入原问题中，有下式：所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为

Y*=（0.0.3），W=12。第三十二页，共八十六页，编辑于2023年，星期四6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。设原问题为：maxZ=CXAX≤

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

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

对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CBB-1b0CN－CBB-1N－CBB-1第三十三页，共八十六页，编辑于2023年，星期四例一、第三十四页，共八十六页，编辑于2023年，星期四cj1018000cBxBbx1x2x3x4x50x3170521000x4100230100x515015001-Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初始表最终表第三十五页，共八十六页，编辑于2023年，星期四由上表可知：

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

Y*=（0.32/7.6/7），W=4100/7第三十六页，共八十六页，编辑于2023年，星期四例二、第三十七页，共八十六页，编辑于2023年，星期四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第三十八页，共八十六页，编辑于2023年，星期四所以，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第三十九页，共八十六页，编辑于2023年，星期四定义：在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*

的改变量y*i

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

第四十页，共八十六页，编辑于2023年，星期四设：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的变化率。第四十一页，共八十六页，编辑于2023年，星期四其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第i个约束条件的影子价格。第四十二页，共八十六页，编辑于2023年，星期四若第i种资源的单位市场价格为mi。当yi>mi

时，企业愿意购进这种资源，单位纯利为yi－mi，则有利可图；如果yi<mi，则企业有偿转让这种资源，，可获单位纯利mi－yi，否则，企业无利可图，甚至亏损。第四十三页，共八十六页，编辑于2023年，星期四012345678123456⑴⑵⑶⑷x2

x1(42)⑴′

X*=（4.2.0.0.0.4）Y*=（0.3/2.1/8.0）最优值为14最优值没有发生变化即y1=0第四十四页，共八十六页，编辑于2023年，星期四012345678123456⑴⑵⑶⑷x2

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

如果存在（最小比值原则，保证所有的检验数<=0）则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。如果不存一个alj<0,则原问题无可行解，那么对偶问题就存在无界解。第五十页，共八十六页，编辑于2023年，星期四④按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解。即所有的检验数小于等于零并且右端项大于等于零。跳出循环地方的有几处？（保证原问题与对偶问题都有可行解，这时就得到两问题的最优解，为什么？？）第五十一页，共八十六页，编辑于2023年，星期四例一、用对偶单纯形法求解：解：将模型转化为如果用单纯形法如何求解？第五十二页，共八十六页，编辑于2023年，星期四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第五十三页，共八十六页，编辑于2023年，星期四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第五十四页，共八十六页，编辑于2023年，星期四

所以，

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

原问题Z*=72

其对偶问题的最优解为：

Y*=(1/3.3.7/3)，W*=72第五十五页，共八十六页，编辑于2023年，星期四练习：第五十六页，共八十六页，编辑于2023年，星期四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第五十七页，共八十六页，编辑于2023年，星期四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第五十八页，共八十六页，编辑于2023年，星期四灵敏度分析的步骤：

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

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

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

4.按以下原则得出结论或决定继续计算的步骤。五、灵敏度分析第五十九页，共八十六页，编辑于2023年，星期四σj=cj－CBB－1Pj=B－1Pj

=B－1b关键是求B-1即找单位矩阵I第六十页，共八十六页，编辑于2023年，星期四求下列LP问题第六十一页，共八十六页，编辑于2023年，星期四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第六十二页，共八十六页，编辑于2023年，星期四B3=（P2，P3，P6）=B3－1=第六十三页，共八十六页，编辑于2023年，星期四

求下列LP问题的最优解

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

10010-12000-1-3第六十八页，共八十六页，编辑于2023年，星期四σ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）第六十九页，共八十六页，编辑于2023年，星期四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）第七十页，共八十六页，编辑于2023年，星期四XB=B－1b例：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。

二、右端常数bi的变化分析第七十一页，共八十六页，编辑于2023年，星期四cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14x2

10010-12000-1-3最优基：B=（P3，P1，P2）B－1=第七十二页，共八十六页，编辑于2023年，星期四（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第七十三页，共八十六页，编辑于2023年，星期四（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第七十四页，共八十六页，编辑于2023年，星期四三、增加一个新变量的分析例2.10（续例2.8）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6=。问它的价值系数c6符合什么条件才必须安排它的生产？设c6=3，新的最优生产计划是什么？第七十五页，共八十六页，编辑于2023年，星期四σ6=c6－CBB－1P6=c6－（0，5，4）=c6－5/2=B－1P6==第七十六页，共八十六页，编辑于2023年，星期四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第七十七页，共八十六页，编辑于2023年，星期四四、增加新的约束条件的分析例2.11假设在例2.8中，还要考虑一个新的资源约束：4x1+2x2≤1504x1+2x2+x6=150X*=（35，10，25，0，0）T第七十八页，共八十六页，编辑于2023年，星期四4x1+2x2+x6=150cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x2

10010-1200x6150420001000-1-30不管是单纯形法还对偶单纯形法都是从单位矩阵开始的，因此要先找单位矩阵第七十九页，共八十六页，编辑于2023年，星期四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第八十页，共八十六页，编辑于2023年，星期四