运筹学第二章线性规划的对偶理论.ppt
《运筹学第二章线性规划的对偶理论.ppt》由会员分享,可在线阅读,更多相关《运筹学第二章线性规划的对偶理论.ppt(43页珍藏版)》请在三一办公上搜索。
1、第二章 线性规划,解:设生产x1的产品I,x2的产品II,则,目标函数 max z 2x1+3x2约束条件 x1+2x2 8 4 x1 16 4x2 12 x1 x2 0,线性规划的对偶理论,例1 某厂可生产产品和,生产I需1台设备,4单位原料A,生产II需2台设备,4单位原料B。该厂每生产一件产品获利2元每生产一件产品获利3元。现有8台设备,16单位原料A,12单位原料B,问如何安排计划使获利最多?,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.1 对偶问题的提出,我们从另一个角度来讨论这个问题:假设不生产产品,而将所有资源出租或
2、外售。问题:考虑每种资源如何定价。,4.1 对偶问题的提出,例1 产品:1台设备,4单位原料A,获利2元;产品:2台设备,4单位原料B,获利3元。现有:8台设备,16单位原料A,12单位原料B,设y1,y2,y3分别表示出售单位设备台时的租金和出让原材料A,B的附加额。根据题意可得:,y1+4y22,2 y1+4y33,,=8 y1+16y2+12y3,要实现出租的愿望,只能在满足所有产品的利润条件下,必须使尽可能的小。,4.1 对偶问题的提出,为此需解决如下的线性规划问题:,与,关系?,对原模型设:,C=(2,3),b=(8,16,12)T,X=(x1,x2)T,Y=(y1,y2,y3),则
3、可得:,4.1 对偶问题的提出,和,我们把(5.2)式的问题称为(5.1)式问题的对偶线性规划问题。,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.2 原问题与对偶问题的关系,1对称式的对偶,“”不等式约束条件的原问题与“”不等式约束条件的对偶问题,称为对称式的一对对偶问题。,原问题:,对偶问题:,n个变量,m个约束条件,m个变量,n个约束条件,2约束条件全部为“=”的对偶,原问题:,其中 Y1=(y1,y2,ym),Y2=(ym+1,ym+2,y2m),对偶问题,4.2 原问题与对偶问题的关系,3约束条件为“”的对偶,原问题:,对
4、偶问题,4变量0的对偶,原问题:,令X=X1,对偶问题,5变量无约束的对偶,原问题:,对偶问题,6原问题与对偶问题的关系表,例:求下列线性规划问题的对偶问题,C=(5,4,6),b=(2,3,-5,1)T,解:,因原问题有3个变量,4个约束条件,所以对偶问题4个变量,3个约束条件。设变量Y=(y1,y2,y3,y4),min=2y1+3y25y3+y4,于是,y1+y23y3+y45,2y1+2y3y44,y2+y3+y46,y10,y2,y3 0,y4无约束,第二章 线性规划,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶单纯形法 灵敏度分析,4.3 对偶问题的基本性质,1
5、对称性:对偶问题的对偶问题是原问题。,证:,设原问题为:max z=CX;AXb;X0,则,对偶问题为:min=Yb;YAC;Y 0,因min=max(),max()=Yb;YAC;Y 0,min(1)=CX;AX b;X 0,对偶问题,又因min(1)=max(1),max(1)=CX;AX b;X 0,这就是原问题。,4.3 对偶问题的基本性质,2弱对偶性:若X(0)是原问题的可行解,Y(0)是对偶问题的可行解,则存在CX(0)Y(0)b。,证:,设原问题为:max z=CX;AXb;X0,则,因X(0)是原问题的可行解,所以AX(0)b,又因Y(0)是对偶问题的可行解,所以Y(0)AC,
6、Y(0)A X(0)Y(0)b,因此,CX(0)Y(0)A X(0)Y(0)b,结论成立。,对偶问题为:min=Yb;YAC;Y 0,Y(0)A X(0)CX(0),4.3 对偶问题的基本性质,3无界性:若原问题无界解,则其对偶问题无可行解。,证:由弱对偶性可知结论成立。(CX(0)Y(0)b),4最优性:若X(0)是原问题的可行解,Y(0)是对偶问题的可行解,且CX(0)=Y(0)b,则X(0),Y(0)是最优解。,证:,设Y(1)是对偶问题的任意可行解,由性质2可得,Y(1)b CX(0)=Y(0)b,则,Y(0)是对偶问题的最优解。,设X(1)是原问题的任意可行解,由性质2可得,CX(0
7、)=Y(0)b CX(1),则,X(0)是原问题的最优解。,4.3 对偶问题的基本性质,5对偶定理:若原问题有最优解,那么对偶问题也有优解;且目标函数值相等。,证:,设X(0)是原问题的最优解,它对应的基B,必有CCBB-1A0,且 z=CX(0)=CBB-1b。,令Y(0)=CBB-1,显然,Y(0)AC。,所以 Y(0)是对偶问题的可行解。,又因Y(0)b=CBB-1b=CX(0),由性质4可知Y(0)是对偶问题的最优解。,因此,结论成立。,6互补松弛性:若X(0)是原问题的可行解,Y(0)是对偶问题的可行解,则YX(0)=0和Y(0)X=0 当且仅当X(0),Y(0)是最优解。,证:,设
8、原问题和对偶问题的标准型是,将原问题目标函数中的系数向量C用C=YAY代替:,z=(YAY)X=YA X YX(5.3),对偶问题目标函数中的系数向量,用b=AX+X代替:,=Y(AX+X)=YA X+YX(5.4),Y X(0)=0和Y(0)X=0,则Y(0)b=Y(0)A X(0)=CX(0),X(0),Y(0)最优解,则Y(0)b=Y(0)AX(0)=CX(0)(性质3),所以Y X(0)=0和Y(0)X=0。,X(0),Y(0)是最优解,7设原问题:max z=CX;AX+X=b;X,X 0 对偶问题:min=Yb;YA Y=C;Y,Y 0。则原问题单纯形表的检验数行对应其对偶问题的一
9、个基解。其关系如表:,这里Y1对应原问题的基变量XB的剩余变量,Y2对应原问题的非基变量XN的剩余变量。,证:,设B是一可行基,于是A=(B,N),4.3 对偶问题的基本性质,其中Y=(Y1,Y2),当原问题的解为:XB=B-1b 时,其检验参数为 CNCBB-1N 与CBB-1。,令Y=CBB-1,将它代入(5.5)和(5.6)得,Y1=0,Y2=CNCBB-1N,因此,结论成立。,4.3 对偶问题的基本性质,8单纯形乘子Y的定理:若B是原问题的一最优可行基,则单纯形乘子Y=CBB-1是对偶问题的一个最优解。,证:设X(0)是对应基B的原问题的最优解,则,显然,Y AC。,所以 Y 是对偶问
10、题的可行解。,又因Yb=CBB-1 b=CX(0),由性质4可知Y 是对偶问题的最优解。,因此,结论成立。,CCBB-1A0,且 z=C X(0)CBB-1b。,根据本性质,可以从原问题最优解的单纯形表中直接得到对偶问题的最优解。,9最优对偶变量(影子价格)的经济解释,从对偶定理可知,当达到最优解时,原问题和对偶问题的目标函数值相等,即z=CX(0)=Y(0)b=CBB-1b.,也即z=CX(0)=Y(0)b=CBB-1b=y1(0)b1+y2(0)b2+ym(0)bm 其中 X(0),Y(0)分别是原问题和对偶问题的最优解。,现在考虑在最优解处,常数项bi的微小变动对目标函数值的影响(不改变
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第二 线性规划 对偶 理论
链接地址:https://www.31ppt.com/p-5849619.html