运筹学第二章对偶理论与灵敏度分析.ppt

第二章对偶理论与灵敏度分析第一章例1中：美佳公司利用自身资源生产两种家电产品，其线形规划问题表示为：maxz=2x1+x2
5x2≤15
St.6x1+2x2≤24
x1＋x2≤5
x1、x2≥0
现假定有某公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。maxz=2x1+x2
5x2≤15
6x1+2x2≤24
x1+x2≤5
x1、x2≥0Maxz=CX
AX≤b
X≥01,若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然。
2,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵。
3,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。
4,原问题与对偶问题互为对偶问题。非对称形式的对偶问题原问题若互为对偶的线性规划分别有可行解

则其相应的目标函数值满足推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。若X和Y分别是互为对偶的线性规划的可行解，且使
CX=Yb，则X和Y分别是相应线性规划问题的最优解。性质4：互补松弛性§2.3影子价格当线形规划原问题与对偶问题同时取得最优解时，其对偶最优解y＊i代表在资源最优利用条件下对单位第i种资源的估价，这个估价称为这种资源的影子价格。

其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。原问题是利润最大化的生产计划问题Minw=b1y1+b2y2+…….+bmym
a11y1+a21y2+……..+am1ym–ym+1=c1
a12y1+a22y2+……..+am2ym–ym+2=c2
…………………………………………….…
a1ny1+a2ny2+……..+amnym–ym+n=cn
y1,y2,……ym+n≥01、影子价格依赖于资源的利用情况，各企业不同。y1
y2

ym机会成本在利润最大化的生产计划中
（1）边际利润大于0的资源没有剩余
（2）有剩余的资源边际利润等于0
（3）安排生产的产品机会成本等于利润
（4）机会成本大于利润的产品不安排生产单纯形法与对偶单纯形法比较单纯形法的步骤对偶单纯形法的步骤如何用？例:如何用？对应B的基解：用大M法求解灵敏度分析的两把尺子：
σj=Cj-CBB-1pj≤0；
xB=B-1b≥0第一章例1中，若家电Ⅰ的利润降至1.5元/件，家电Ⅱ的利润增至2元/件，最优生产计划是否改变；右端常数变化灵敏度分析RANGESINWHICHTHEBASISISUNCHANGED:
OBJCOEFFICIENTRANGES
VARIABLECURRENTALLOWABLEALLOWABLE
COEFINCREASEDECREASE
X12.0000001.0000001.000000
X21.0000001.0000000.333333
RIGHTHANDSIDERANGES
ROWCURRENTALLOWABLEALLOWABLE
RHSINCREASEDECREASE
215.000000INFINITY7.500000
324.0000006.0000006.000000
45.0000001.0000001.000000DAKOTA家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE
1)280.0000

VARIABLEVALUEREDUCEDCOST
DESKS2.0000000.000000
TABLES0.0000005.000000
CHAIRS8.0000000.000000

ROWSLACKORSURPLUSDUALPRICES
2)24.0000000.000000
3)0.00000010.000000
4)0.00000010.000000
5)5.0000000.000000
NO.ITERATIONS=2RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES
VARIABLECURRENTALLOWABLEALLOWABLE
COEFINCREASEDECREASE
DESKS60.00000020.0000004.000000
TABLES30.0000005.000000INFINITY
CHAIRS20.0000002.5000005.000000

RIGHTHANDSIDERANGES
ROWCURRENTALLOWABLEALLOWABLE
RHSINCREASEDECREASE
248.000000INFIN