对偶关系的进一步思考
摘要:每个线性规划问题总有一个与它对应的对偶线性规划问题。基于对偶关系表,可以由原问题得出对偶问题,但由于变量、约束的复杂关系而使对应关系容易出错。为此,论文总结了“大约变,小约不变,变化仅一次,等号与无约划原问题的对偶问题。但是,原问题和对偶问题的对应关系比较复杂:原问题的约束条件有3种情况,对应的对偶变量也有3种可能;原问题的变量有3种情况,对应的约束条件也有3种可能。总共有18种组合关系,对偶关系只是其中的6种,学生容易记混,导致非对称形式的对偶问题往往出错。
(二)对偶关系的口诀
口诀:大约变,小约不变,变化仅一次,等号与无约束关联。
大约变:“大”即为原问题的目标函数求极大;“约”即为原问题的约束条件;“变”有两层意思:一层意思是对偶变量,另一层意思是指由原问题的约束条件来对应对偶问题的变量时,不等号发生变化,即当原问题的目标函数求极大时,其m个约束条件对应于对偶问题的m个对偶变量,若原问题的约束为“≤”,则对应的对偶变量≥0;若原问题的约束为“≥”,则对应的对偶变量≤0。
小约不变:“小”即为原问题的目标函数求极小,“约”即为原问题的约束条件,“变”指对偶变量,“不变”是指由原问题的约束条件来对应对偶问题的变量时,不等号不发生变化,即当原问题的目标函数求极小时,其m个约束条件对应于对偶问题的m个对偶变量,若原问题的约束为“≤”,则对应的对偶变量≤0;若原问题的约束为“≥”,则对应的对偶变量≥0。
变化仅一次:原问题的约束条件决定的对偶变量不等号反向后,原问题的变量决定对偶约束的不等号就不变了。反之亦然。
等号与无约束关联:当原问题的约束为“=”,则对应的对偶变量就是无约束变量,并且当原问题的变量为无约束时,则对应的对偶约束为“=”。
例1:写出下面原问题的对偶问题。
min z=7x+4x-3x
.-4x+2x-6x≤24-3x-6x-4x≥155x+3x=30x≤0,x取值无约束,x≥0
分析:原问题的目标函数求极小,故遵循“小约不变,等号与无约束关联,变化仅一次”的准则。
解:(1)原问题求极小,则对偶问题求极大,得对偶问题的目标函数:max w=24y+15y+30y
(2)由小约不变:第一个条件为“≤”,得y≤0;第二个条件为“≥”,得y≥0;第三个条件为“=”,得y取值无约束。
(3)变化仅一次:由(2)知,原问题约束条件与对偶变量的不等号同向,则原问题变量与对偶问题的约束条件的不等号反向。
x≤0,故第一个约束为“≥”,得:-4y-3y≥7
x≥0,故第三个约束为“≤”,得:-6y-4y+3y≤-3
(4)等号与无约束关联:x2取值无约束,故第二个约束为“=”,得:2y-6y+5y=4
综上,得到原问题的对偶问题:
max w=24y+15y+30y
.-4y-3y≥72y-6y+5y=4-6y-4y+3y≤-3y≤0,y≥0,y取值无约束
例2:写出下面原问题的对偶问题。
max z=2x-3x+4x
+3x-5x≥23x+x+7x≤3-x+4x+6x≥5x≥0,x≤0,x无约束
分析:
对偶关系的进一步思考 来自淘豆网m.daumloan.com转载请标明出处.
