运筹学对偶问题PPT(完整版).ppt

运筹学对偶问题;4.1对偶问题;MaxZ=40x1+50x2;MaxZ=40x1+50x2;通过使用所有资源对外加工所获得的收益;(2)对偶问题的形式;原始问题

MaxZ=CX

s.t.AX≤b

X≥0;例2：求线性规划问题的对偶规划;例3：求线性规划问题的对偶规划;3x1+2x2?60

MaxZ=40x1+50x2

设三种资源的使用单价分别为y1,y2,y3

例2：求线性规划问题的对偶规划

(1)对偶问题的提出

(2)对偶单纯形法的迭代步骤

对偶问题变量类型约束?变量?0

2x2?24

(5)产品的差额成本（ReducedCost）

ATY-YS=C

在一对变量中，其中一个大于0，另一个一定等于0

定理5若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是

一个问题无界，则另一问题无可行解。

所得不得低于生产的获利

推论2、(P)有可行解,但无有限最优解，则(D)无可行解。

,则它们是(P),(D)的最优解。

（1）边际利润大于0的资源没有剩余

原问题约束类型与??0;上式已为对称型对偶问题，故可写出它的对偶规划;对偶关系对应表;4.2对偶问题的基本性质;定理2(弱对偶定理);推论2、(P)有可行解,但无有限最优解，则(D)无可行解。;定理4(主对偶定理)

若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。;(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型;推论：

若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。;定理5若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是;MaxZ=CX

s.t. AX+XS=b

X,XS≥0;;4.3对偶问题的解;例1MaxZ=40X1+50X2;MaxW’=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7);C;例1、MaxZ=40X1+50X2;;;C

;原线性规划问题称为原问题，此问题为对偶问题，

推论2、(P)有可行解,但无有限最优解，则(D)无可行解。

y1,y2,y3?0

那么xr为进基变量,转4；

对偶问题变量类型约束?变量?0

2对偶问题的基本性质

例3：求线性规划问题的对偶规划

分别为(P),(D)的可行解，且

目标函数??数目标函数系数右边项系数

对偶问题约束类型变量?0约束?

x1，x2?0

定义设原线性规划问题为则称下列线性规划问题

表示减少一件产品所节省的资源可以增加的利润

(2)对偶单纯形法的迭代步骤

所以原问题的目标函数值有上界，即可找到有限最优解；;4.4影子价格;(2)对偶问题;(3)资源影子价格的性质;;;(6)互补松弛关系的经济解释;4.5对偶单纯形法;对偶单纯形法的基本思想;(2)对偶单纯形法的迭代步骤;例;C;C;是;第四章作业

1（选2）、2、4、6、8、9（选2）;感谢观看