第三章对偶理论与灵敏度分析

第三章对偶理论与灵敏度分析第一页，共四十一页，编辑于2023年，星期四§1单纯形法的矩阵描述设线性规划问题设B是一个可行基，令（A，I）=（B，N，I），则：第二页，共四十一页，编辑于2023年，星期四1.检验数的矩阵描述：σB=CB-CBB-1B=0σN=CN-CBB-1NσS=-CBB-1

θ=min{(B-1b)i/(B-1Pk)i|(B-1Pk)i>0}=

(B-1b)l/(B-1Pk)lXBbXBXNXsθB-1bIB-1NB-1(B-1b)i(B-1Pk)i-zCBB-1b0CN-CBB-1N-CBB-13.单纯形表的矩阵描述：σ=C-CBB-1A2.θ的矩阵描述：第三页，共四十一页，编辑于2023年，星期四§2改进单纯形法用改进单纯形法求解线性规划问题的计算步骤：1.确定初始可行基B1。求出B1-1；2.计算非基变量的检验数σN。若σN≤0已求的最优解，停止计算,否则进行下一步；3.确定换入变量xk；4.计算B1-1b，B1-1

Pk及θ；若θ≤0那么无最优解，停止计算，否则进行下一步；5.确定换出变量xl;6.计算B2-1；7.重复2—7步。第四页，共四十一页，编辑于2023年，星期四

第五页，共四十一页，编辑于2023年，星期四例：用改进单纯形法求解第六页，共四十一页，编辑于2023年，星期四解：[]第七页，共四十一页，编辑于2023年，星期四[][]第八页，共四十一页，编辑于2023年，星期四[][]第九页，共四十一页，编辑于2023年，星期四[][]第十页，共四十一页，编辑于2023年，星期四§3对偶问题的提出例：

ⅠⅡ设备原材料A原材料B1402048台时16kg12kg利润23x1minx2x1x2y1y2y3第十一页，共四十一页，编辑于2023年，星期四当该问题达到最优时有：

z的上界为无限大，所以只存在最小值。于是得到另一个线性规划问题对线性规划问题对偶问题原问题第十二页，共四十一页，编辑于2023年，星期四§4线性规划的对偶理论4.1原问题与对偶问题的关系第十三页，共四十一页，编辑于2023年，星期四原问题（对偶问题）对偶问题（原问题）例：23-51第十四页，共四十一页，编辑于2023年，星期四第十五页，共四十一页，编辑于2023年，星期四第十六页，共四十一页，编辑于2023年，星期四4.2对偶问题的性质1.对称性对偶问题的对偶是原问题。2.弱对偶性若X*是原问题的可行解，Y*是对偶问题的可行解,则存在CX*≤Y*b证设原问题及对偶问题为maxz=CX，AX≤b，X≥0minω=Yb，YA≥CY≥0∵若X*是原问题的可行解，Y*是对偶问题的可行解∴AX*≤bY*A≥C∴Y*AX*≤Y*bY*AX*≥CX*∴CX*≤Y*AX*≤Y*bCX*Y*b第十七页，共四十一页，编辑于2023年，星期四3.无界性若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。4.可行解是最优解的性质设X^是原问题的可行解，Y^是对偶问题的可行解，当CX^=

Y^b时，X^，

Y^是最优解。5.对偶定理若原问题有最优解，则对偶问题也有最优解，且目标函数相等。6.互补松驰性若X^是原问题的可行解，Y^是对偶问题的可行解，那么Y^Xs=0，Ys

X^=0，当且仅当X^，

Y^为最优解。第十八页，共四十一页，编辑于2023年，星期四6.互补松驰性若X^是原问题的可行解，Y^是对偶问题的可行解，那么Y^Xs=0，Ys

X^=0，但且仅当X^，

Y^为最优解。证：设原问题及对偶问题的标准型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA—YS=CY，YS≥0z=(YA—YS)X=YAX—YSXω=Y(AX+XS)=YAX+YXS∵X^是原问题的可行解，Y^是对偶问题的可行解∴z^=Y^AX^—YSX^ω^=Y^AX^+Y^XS当Y^Xs=0，Ys

X^=0时z^=ω^，则X，Y^是最优解。当X，Y^是最优解时z^=ω^，则Y^Xs=0，Ys

X^=0第十九页，共四十一页，编辑于2023年，星期四例：已知线性规划问题max其对偶问题的最优解为试用对偶理论求原问题的最优解解：max∵∴∴∴第二十页，共四十一页，编辑于2023年，星期四7.设原问题及对偶问题的标准型是maxz=CX，AX+XS=b，X，XS≥0minω=Yb，YA－YS=CY，YS≥0则原问题单纯形表的检验数行对应其对偶问题的一个基解，对应关系如下表：XBXNXs0CN－CBB-1N－CBB-1－Ys1－Ys2－Y证:CBB-1A－(0，－CN+CBB-1N)=CBB-1(B，N)－(0，－CN+CBB-1N)=(CB，CN)=C第二十一页，共四十一页，编辑于2023年，星期四§5对偶问题的经济解释

——影子价格

设B是线性规划问题的一可行基，这目标函数为

所以变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数值的变化。

yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。第二十二页，共四十一页，编辑于2023年，星期四Q2(4,2)X2X10123454321Q1(4,0)Q3(2,3)Q4(0,3)OQ4Q2Q3**A增加4，利润增加4×1/8=1/2设备增加2，利润增加2×3/2=3Q

(5,3/2)Q

(4,3)第二十三页，共四十一页，编辑于2023年，星期四§6对偶单纯形法bXBXNXsθXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1-Ys1-Ys2-YXBbXBXNXsXBB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1≤0变为≤0变为≥

0≥0θ单纯形法对偶单纯形法第二十四页，共四十一页，编辑于2023年，星期四对偶单纯形法的计算步骤：1.确定初始的基，使非基变量的检验数小于等于零。2.若b≥0,则已求得最优解，停止计算，否则进行下一步。3.确定换出变量。计算

min{(B-1b)i|(B-1b)i<0}=(B-1b)l则xl为换出变量。4.确定换入变量。若所有aij

≥0，则无可行解，停止计算；否则计算

θ=min{σj/alj|alj<0}=σk/alk则xk为换入变量。5.以alk为主元素进行迭代。6.重复2—5步。第二十五页，共四十一页，编辑于2023年，星期四例：第二十六页，共四十一页，编辑于2023年，星期四

-2-3-400-3-1-2-110-4-21-301-10-5/21/21-1/221-1/23/20-1/22/501-1/5-2/51/511/5107/51/5-2/5

0-4-10-1

00-3/5-8/5-1/5[][]

1-34/3/0

/8/5-202第二十七页，共四十一页，编辑于2023年，星期四§7灵敏度分析

灵敏度分析的内容：1.当决定线性规划问题的参数aij，bi，cj有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化。2.当决定线性规划问题的参数aij，bi，cj在什么范围内变化时，线性规划问题的最优解或最优基不变。第二十八页，共四十一页，编辑于2023年，星期四

7.1资源数量变化的分析

设b变化为b+Δb，这时最终单纯形表变为XBbXBXNXsθB-1b+B-1ΔbIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1

当B-1(b+Δb)≥0时，最优基不变;当B-1(b+Δb)中有负分量时，可利用对偶单纯形法求解。第二十九页，共四十一页，编辑于2023年，星期四例：第一章例1中，若该厂又从别处抽出4台时用于生产，求这时该厂生产的最优方案。解：计算B-1Δb41001/40

2001-1/4-1/2

301001/4

-17000-1/2-3/4[]//3/4-1/40

+0-8+241001/40

400-21/21

2011/2-1/80

-1400-3/2-1/80

4-44第三十页，共四十一页，编辑于2023年，星期四

例：第一章例1中，资源A在什么范围内变化最优基不变。解：资源A的变化量Δb满足下式时最优基不变。第三十一页，共四十一页，编辑于2023年，星期四

7.2目标函数中价值系数cj的变化1.若cj是非基变量xj的系数，则当CN变化ΔCN后，最终单纯形表的检验数行变为:XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN+ΔCN-CBB-1N-CBB-1

当CN+ΔCN

-CBB-1N≤0时，最优解不变；当CN+ΔCN

-CBB-1N中有正分量时，可利用单纯形法求解。第三十二页，共四十一页，编辑于2023年，星期四2.若cj是基变量xj的系数，则当CB变化ΔCB后，最终单纯形表的检验数行变为:XBbXBXNXsθB-1bIB-1NB-1-zCBB-1b0CN-CBB-1N-CBB-1当非基变量检验数≤0时，最优解不变；当非基变量检验数中有正分量时，可利用单纯形法求解。-zCBB-1b-

ΔCBB-1b0CN-CBB-1N-

ΔCBB-1N-CBB-1-ΔCBB-1ΔCB第三十三页，共四十一页，编辑于2023年，星期四例：第一章例1中，基变量x2在目标函数中的系数c2在什么范围内变化最优解不变。解：基变量x2在目标函数中的系数c2的变化量Δc2满足下式时最优解不变。41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

0

0-3/2--1/8+0Δc2/2Δc2/8Δc22+Δc2第三十四页，共四十一页，编辑于2023年，星期四

例：第一章例1中，出售资源A可获利1/2元，这是最优解发生什么变化。解：当Δc4=1/2时，单纯形表为：41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

+1/2

3/8[]θ

168-1621020-1/2

800-412

30100-1/4

-170000-3/4第三十五页，共四十一页，编辑于2023年，星期四7.3技术系数aij的变化1.增加一列Pn+1。则最终单纯形表增加一列B-1Pn+1，检验数为σn+1=cn+1-CBB-1Pn+1例：第一章例1中，该厂开发一种新产品Ⅲ，已知生产新产品Ⅲ,每件需消耗原材料A，B各为6kg，3kg，使用设备2台时;每件可获利5元。问该厂是否应该生产该产品和生产多少？解：计算第三十六页，共四十一页，编辑于2023年，星期四41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

5/4[]

θ

8/3281103/2-1/8-3/40

200-11/41/21

3/2013/4-3/16-1/8

0-16.500-1/4-7/16-5/80

3/221/4第三十七页，共四十一页，编辑于2023年，星期四

2.改变一列Pj。若Pj变为Pj’，则最终单纯形表增加一列B-1Pj’，检验数为σj=cj’

-CBB-1Pj’，删除一列Pj。例：第一章例1中，该厂生产产品Ⅰ的工艺结构有了改进，已知生产产品Ⅰ,每件需消耗原材料A，B各为5kg，2kg，使用设备2台时;每件可获利4元。试分析对原最优计划有什么影响？解：计算第三十八页，共四十一页，编辑于2023年，星期四41001/40

4 00-21/21

2011/2-1/80

-1400-3/2-1/80

3/816/51001/5012/500-22/51

4/5011/2