自由变量
线性规划中的自由变量
自由变量有多个义项。一个是指谓词公式中出现的自由变量,其对应的是约束变量;另一个是指线性规划中没有非负性条件的设计变量。
自由变量(free variable)是指线性规划中没有非负性条件的设计变量。若问题中含有这种变量,为构成线性规划标准式,常以两个相减的非负设计变量替代之,使优化设计数学模型中的所有设计变量均为非负设计变量。替代前后的最优解是等价的。具有自由变量的线性规划问题有时亦可利用对偶理论化为对偶问题直接求解。
自由变量在线性规划问题数学模型中,如果出现没有非负限制,可以为正,也可以为负的变量就称其为自由变量。化标准形时,需引进两个非负变量,,令将自由变量转化为有非负要求约束的变量。
各种线性规划模型都需要转化成标准型后求解。下面介绍各种转化方法。
(1)最小化问题的转化。求min z等价于求max(-z),因此,只需改变目标函数的符号就可以实现最大化和最小化之间的转换。
(2)不等式约束的处理。不等式约束可以通过引入松弛变量剩余变量转化为等式约束,具体为:
等价于
其中称为松弛变量。
等价于
其中称为剩余变量。
(3)非正变量与符号无限制变量的处理。
若,令,则新变量为非负变量。
若为符号无限制变量(称为自由变量),可令,即以两个非负变量之差来代替自由变量。
从以上讨论可见,任何形式的线性规划都可转化为标准型。
参考资料
最新修订时间:2023-01-05 10:28
目录
概述
参考资料