对偶问题与灵敏度分析课件

对偶问题与灵敏度分析OR113.1对偶问题3.1.1对偶问题的提出回顾例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？产品A产品B资源限制劳动力设备原材料9434510360200300单位利润

70

120OR12对偶模型设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。出租收入不低于生产收入：

9y1+4y2+3y3≥704y1+5y2+10y3≥120目标：ω=360y1+200y2+300y3出租收入越多越好？至少不低于某数OR13原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3≥704X1+5X2≤200(3.1)4y1+5y2+10y3≥120(3.2)3X1+10X2≤300y1≥0,

y2≥0,

y3≥0X1≥0X2≥0OR143.1.2对偶规则原问题一般模型：对偶问题一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0OR15对偶规则原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反OR16对偶规则.

原问题

对偶问题目标函数maxmin目标函数约束条件

≤

≥=≥变量≤无约束

≥变量符号≤

无约束≥

≤

约束条件=OR17对偶规则简捷记法原问题标准则对偶问题标准原问题不标准则对偶问题不标准例题2maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3≤32x1+x2-4x3+x4+3x5

≥7y1+3y3≤2x1+2x3-x4≤

4-4y1+2y2≤-6-x1+3x2-x4+x5=-2y1-y2-y3≥0x1，x2，x3

≥0;3y1+y3=1x4≤

0;x5无限制y1≥0y2≤0y3

无约束

OR183.1.3对偶问题的基本性质对称性：对偶问题的对偶问题是原问题弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值(鞍型图)无界性：原问题无界，对偶问题无可行解对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1OR193.1.4对偶最优解的经济解释—影子价格Z=ω=CX=Yb

Z/

b=(Yb)’=YZ=Yb=∑yibi的意义：Y是检验数的反数。在Y确定的前提下，每增加一个单位的i种资源，对目标函数的贡献。结合例题1讲解影子价格：y1=0:第一种资源过剩

y2=13.6：设备台时最紧张，每增加一个台时，利润增加13.6元。y3=5.2…影子价格所含有的信息：1、资源紧缺状况

2、确定资源转让基价参见：P403、取得紧缺资源的代价OR1103.2灵敏度分析为什么进行灵敏度分析？灵敏度分析的两把尺子：

σj=Cj-CBB-1pj≤0；

xB=B-1b≥03.2.1价值系数的灵敏度分析

Cj变化到什么程度可以保持最优基不变？用

（参看P96）例题4：87.5≤C2≤233.33；36≤C1≤96OR111灵敏度分析右端项的灵敏度分析：

bi变化到什么程度可以保持最优基不变？用尺度

xB=B-1b≥0例题5：1

-3.12

1.16360

B-1b=00.4-0.2200≥00-0.120.16b3b3的变化范围：227.586≤b3≤400OR112其它形式的灵敏度分析

新产品的分析：在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。例题6：新增一种C产品，单位利润110元，使用劳动力6工时，设备5台时，原材料7公斤，问要否调整产品结构？先算检验数σj=Cj-CBB-1pjσ6=C6-YP6=110-（0，13.6，5.2）（6，5，7）T

=110-104.4=5.6大于零，有利可图，将P6左乘B-1，加入到末表之中，继续迭代，直到求得最优解。OR1133.3用计算机进行灵敏度分析例题7参见P102OR114习题课：P78——2.10（1）唯一最优解：H3≤0，H5≤0

，

H1

≥0（2）无穷多最优解：

H3=0，H1

≥0，H5

0，H2>0

或H5=0，H1

≥0，H3

0，H4>0（3）无界解：

H5≥0，H4

0

，H1

≥0，H3

0（4）退化最优解：H1=0

，H3

0，H5

0（5）非最优解，X1进基，X2出基：

H1

≥0，H3>0

，H2>0，5H2<H17OR115习题课：P79——2.111、对2、错，可能有最优解3、对4、对5、错6、错7、错在“可行”8、对9、错OR116习题课：P81——2.16设白天电视广告X1个，黄金时间电视广告X2个，广播广告X3个，杂志广告X4个maxZ=40X1+90X2+50X3+2X4

8X1+15X2+6X3+3X4≤1630X1+40X2+20X3+X4

≥2008X1+15X2≤10X1

≥3X2≥2X3≥5X3

≤10X4

≥5X4

≤10X

j≥0j=1、2、3、4OR117习题课：P81——2.17设A产品生产X1单位，B产品生产X2单位，C产品销毁X3单位maxZ=5X1+10X2+3（2X2-X3）-1X32X1+3X2≤2003X1+4X2≤2402X2-X3≤10X1、X2、X3

≥0OR118习题课：P107——3.21、对，根据若对偶性2、对，同上3、对，同上4、对，因为影子价格是每增加一个单位的某种资源，对目标函数的贡献程度5、对，根据强对偶定理OR119习题课P107——3.5