运筹学——对偶问题与灵敏度分析

《运筹学——对偶问题与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章对偶问题与灵敏度分析重点与难点：1、对偶问题的定义，对偶定理，对偶问题最优解的经济含义，由最优单纯形表求对偶问题最优解；2、对偶单纯形法的特点，对偶单纯形法求解；3、灵敏度分析：价值系数cj发生变化，右端常数bi发生变化，增加一个变量，增加一个约束，A中对应非基变量的一列元素发生变化。OR11第二章对偶问题与灵敏度分析要求：了解LP对偶问题的实际背景了解对偶问题的建立规则与基本性质掌握对偶最优解的计算及其经济解释掌握LP的灵敏度分析OR122.1对偶问题2.1.1对偶问题的提出回顾例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的（资源的）价格底线是多少？产品

2、A产品B资源限制劳动力设备原材料9434510360200300单位利润70120OR13对偶模型设每个工时收费Y1元，每设备台时费用Y2元，每单位原材料收费Y3元。出租收入不低于生产收入：9y1+4y2+3y3≥704y1+5y2+10y3≥120目标：ω=360y1+200y2+300y3出租收入越多越好？还是至少不低于某数？OR14原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2minω=360y1+200y2+300y39X1+4X2≤3609y1+4y2+3y3≥704X1+5X2≤2004y1+5y2+10y3≥1203X1+10X2≤300y1≥0,y2≥0

3、,y3≥0X1≥0X2≥0OR152.1.2对偶规则原问题一般模型：对偶问题一般模型：maxZ=CXminω=YbAX≤bYA≥CX≥0Y≥0OR16对偶规则P57.原问题（或对偶问题）对偶问题（或原问题）目标函数maxz目标函数min⍵n个n个变量约束条件≥0≥≤0≤无约束＝约束条件变量≤≥m个m个≥0≤0＝无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项OR17例题2：写出下列原问题的对偶问题OR18例题3：写出以下模型的对偶问题例题3maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3≤32x1+x2-4x3+x4+3x5≥7y1

4、+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无约束OR19例题4：写出以下模型的对偶问题OR110例4的解法OR1112.1.3对偶问题的基本性质1.对称性：对偶问题的对偶问题是原问题。2.弱对偶性：若是最大化原问题的可行解，是对偶问题的可行解，则存。3.无界性：若原问题为无界解，则对偶问题无可行解。（注：该性质的逆不存在。当原问题无可行解时，其对偶问题可能为无界解，也可能无可行解。）4.最优解定理：若两互为对偶的问题均有可行解，且可行解对应的目标函数值

5、相等，则该可行解分别为他们的最优解。OR112性质3的应用P60已知LP问题：试用对偶理论证明上述LP问题无最优解。OR1135.对偶定理：若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1。6.互补松弛性：在LP的最优解中，若对应某一约束条件的对偶变量值不为零，则该约束条件取严格等式；反之，若约束条件取严格等式，则其对应的对偶变量一定为零。（另一解释：在互为对偶的两个问题中，①若原问题的某个变量取正数，则对偶问题相应的约束条件必取“＝”式；②若原问题的某个约束条件取不等式，则对偶问题相应的变量为零。）OR114性质6的应用P60已

6、知线性规划问题：已知其对偶问题的最优解为：试用对偶理论找出原问题的最优解。OR1157.设原问题是maxz=CX,AX+Xs=b;X,Xs≥0,其对偶问题是min⍵=Yb,YA-Ys=C,Y,Ys≥0,则原问题单纯形表的检验数行对应其对偶问题的一个基解CBB-1（符号相反），其对应关系如下：OR116非基变量基变量XBXNXS0XSbBNICBCN0CBCN初始单纯形表XNXBXSI=B-1BB-1NB-1CBXBB-1bCBCN00CN-CBB-1N_-CBB-1互为对偶问题在单纯形表间关系：1、原问题的基解对应于对偶问题的检验数。2、原问题的松弛变量对应对偶问题的决策变量。3、原问题的基变

7、量对应对偶问题的非基变量。OR117某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？回顾例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的（资源的）价格底线是多少？产品A产品B资源限制劳动力设备原材料9434510360200300单位利润70120OR118CjC1C2…CnCBXBbX