运筹学基础及应用第2章线性规划的对偶问题(胡运权版)ppt课件.ppt
《运筹学基础及应用第2章线性规划的对偶问题(胡运权版)ppt课件.ppt》由会员分享,可在线阅读,更多相关《运筹学基础及应用第2章线性规划的对偶问题(胡运权版)ppt课件.ppt(61页珍藏版)》请在三一办公上搜索。
1、运筹学基础及应用,Operations Research,第二章,目,录,CONTENTS,设某工厂生产两种产品甲和乙,生产中需4种设备按A,B,C,D顺序加工,每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 :,产品数据表,问:充分利用设备机时,工厂应生产甲和乙型产品各多少件才能获得最大利润?,1.对偶问题的提出,解:设甲、乙型产品各生产x1及x2件,则数学模型为:,反过来问:若厂长决定不生产甲和乙型产品,决定出租机器用于接受外加工,只收加工费,那么种机器的机时如何定价才是最佳决策?,1.对偶问题的提出,在市场竞争的时代,厂长的最佳决策显然应符合两条:(1)不吃亏
2、原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则,便构成了新规划的不等式约束条件。 (2)竞争性原则。即在上述不吃亏原则下,尽量降低机时总收费,以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4,则新的线性规划数学模型为:,1.对偶问题的提出,把同种问题的两种提法所获得的数学模型用表2表示,将会发现一个有趣的现象。,原问题与对偶问题对比表,对偶性是线性规划问题的最重要的内容之一。每一个线性规划( LP )必然有与之相伴而生的另一个线性规划问题,即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”,记为“P”,另一个称
3、为“对偶问题”,记为“D”。,1.对偶问题的提出,2. 原问题与对偶问题的对应关系,原问题-P,对偶问题-D,2.原问题与对偶问题,2.原问题与对偶问题,(1)对称形式,特点:目标函数求极大值时,所有约束条件为号,变量非负;目标函数求极小值时,所有约束条件为号,变量非负.,2.原问题与对偶问题,例2.1 写出线性规划问题的对偶问题,解:首先将原问题变形为对称形式,注意:以后不强调等式右段项 b0,原因在对偶单纯型表中只保证 而不保证 ,故 b可以是负数。,2.原问题与对偶问题,2.原问题与对偶问题,(2) 非对称型对偶问题,若给出的线性规划不是对称形式,可以先化成对称形式再写对偶问题。也可直接
4、按教材表2-2中的对应关系写出非对称形式的对偶问题。,2.原问题与对偶问题,2.原问题与对偶问题,例2.2 写出下列线性规划问题的对偶问题.,解:原问题的对偶问题为,2.原问题与对偶问题,无约束,例2.3 写出下列线性规划问题的对偶问题.,解:原问题的对偶问题为,2.原问题与对偶问题,例2.4,2.原问题与对偶问题,2.原问题与对偶问题,性质1 对称性定理:对偶问题的对偶是原问题,min Z= - CXs.t. - AX- bX 0,max W = -Ybs.t. YA C Y 0,3.对偶问题的基本性质,性质2 弱对偶原理(弱对偶性):设 和 分别是问题(P)和(D)的可行解,则必有,推论1
5、: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界;反之,对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,推论2: 在一对对偶问题(P)和(D)中,若其中一个问题可行但目标函数无界,则另一个问题无可行解;反之不成立。这也是对偶问题的无界性。(无界性),3.对偶问题的基本性质,例2.5,3.对偶问题的基本性质,推论3:在一对对偶问题(P)和(D)中,若一个可行(如P),而另一个不可行(如D),则该可行的问题目标函数值无界。,试估计它们目标函数的界,并验证弱对偶性原理。,(P),例2.6,3.对偶问题的基本性质,解:,(D),3.对偶问题的基本性质,性质3 最优性定理:如果
6、是原问题的可行解, 是其对偶问题的可行解,并且:,则 是原问题的最优解, 是其对偶问题的最优解。,例如:在一对对偶问题(P)和(D)中,可找到 X*=(0.0.4.4), Y*=(1.2,0.2),且Z=W28 ,则X*,Y*分别是 P和D 的最优解。,3.对偶问题的基本性质,性质4 强对偶性:若原问题及其对偶问题均具有可行解,则两者均具有最优解,且它们最优解的目标函数值相等。,还可推出另一结论:若(LP)与(DP)都有可行解,则两者都有最优解,若一个问题无最优解,则另一问题也无最优解。,性质5 互补松弛性:设X0和Y0分别是P问题 和 D问题 的可行解,则它们分别是最优解的充要条件是:,其中
7、:Xs、Ys为松弛变量,3.对偶问题的基本性质,性质5的应用:该性质给出了已知一个问题最优解求另一个问题最优解的方法,即已知Y求X或已知X求Y,互补松弛条件,由于松弛变量都非负,要使求和式等于零,则必定每一分量为零,因而有下列关系:若Y0,则Xs必为0;若X0,则Ys必为0利用上述关系,建立对偶问题(或原问题)的约束线性方程组,方程组的解即为最优解。,3.对偶问题的基本性质,例2.7 已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,解:写出原问题的对偶问题,即,标准化,3.对偶问题的基本性质,设对偶问题最优解为Y(y1,y2),由互补松弛性定理可知,X和 Y满足:,即:
8、,因为X1=60,X2=20,所以对偶问题的第一、二个约束的松弛变量等于零,即y30,y40,带入方程中:,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为:Y=(1,1),最优值w=26。,3.对偶问题的基本性质,例2.8 已知线性规划,的对偶问题的最优解为Y=(0,-2),求原问题的最优解。,解: 对偶问题是,标准化,3.对偶问题的基本性质,设对偶问题最优解为X(x1,x2 ,x3)T ,由互补松弛性定理可知,X和 Y满足:,将Y =(0,-2)带入由方程可知,y3y50,y41。,y2=-20 x50又y4=10 x20,将x2,x5分别带入原问题约束方程中,得:,解方程组得:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础 应用 线性规划 对偶 问题 胡运权版 ppt 课件
链接地址:https://www.31ppt.com/p-1450155.html