文章目录
一、线性规划标准形式
线性规划标准形式 :
线性规划标准形式特点 :
- 1. 目标函数 : 目标函数都是求最大值 , 如果出现最小值 , 那么将其转为求最大值的形式 ;
- 2. 约束条件 : 约束条件都是等式方程 , 等式右侧的常数项
大于等于
;
大于等于 0 ;
约定 : 决策变量个数为
个 , 约束条件不等式个数为
个 , 约束条件不等式的系数为一个
矩阵 ,
行
列的矩阵 ;
二、线性规划 普通形式 -> 标准形式 目标函数 转化
目标函数 转换 : 求极小值 转为 求极大值 ;
如果目标函数是
可以将目标函数乘以
,
是大于
的数 ,
的最小值时 ,
是最大值 ,
是最大值时 ,
是最小值 , 这里令
, 可以得到
三、线性规划 普通形式 -> 标准形式 无约束的决策变量转化
无约束变量 转换 : 所有的决策变量必须
如果某个决策变量
没有任何约束 , 在标准形式中 , 所有的决策变量必须都大于等于 0 ;
这里令
, 其中
,
四、线性规划 普通形式 -> 标准形式 约束方程 转化
约束方程 转换 : 在线性规划中 , 约束方程都是等式 , 需要将不等式 (
,
) 转为 等式 (
) ;
1. 针对小于等于的不等式 :
等式左边比右边小 , 左侧加上一个 变量
与右侧相等 ;
这个
称为松弛变量 ;
2. 针对大于等于的不等式 :
等式左边比右边小 , 左侧加上一个 变量
与右侧相等 ;
这个
称为剩余变量 ;
五、线性规划 普通形式 -> 标准形式 小于等于 0 的变量转化
如果出现 变量约束
, 需要将该变量约束转为大于等于 0 (
) 的情况 ;
当前
, 令
, 此时
;
六、线性规划 普通形式 -> 标准形式 转化顺序说明
① 先处理变量没有约束的问题 , 需要用两个
的变量替换原来的变量 ;
这里特别注意 , 之后处理 约束方程 , 每个步骤都要讲该变量替换掉 ;
该步骤优先级最高 ;
② 在处理约束方程 , 如果是
不等式 , 需要在不等式左侧加入松弛变量 , 将不等式转为等式 ; 如果是
不等式 , 不等式左侧需要减去一个 剩余变量 , 将不等式转为等式 ;
该处理过程会增加新的变量 , 如松弛变量或剩余变量 , 优先级 低于 处理没有变量约束 的问题 ;
③ 约束方程等式右侧常数必须大于
, 如果右侧的常数小于
, 在等式左右两侧都乘以
;
④ 先将之前 替换 或 新增的变量加入到目标函数中 , 在处理最大值最小值的问题 , 如果目标函数求最大值 , 什么都不用做 , 如果目标函数求最小值 , 需要将 求最小值的目标函数转为求最大值的目标函数 , 两边乘以
;
目标函数需要将之前所有的变量都总结到一起 , 上述两个步骤都会增加新的变量 , 因此转换目标函数的工作放在最后 ;
自下而上 : 变量约束都大于等于
, 约束不等式转等式 , 约束方程右侧大于
, 目标函数必须求最大值 ;
七、线性规划 普通形式 -> 标准形式 转化实例
下面是线性规划问题模型 , 将其转化为标准形式 :
1. 处理变量无约束的问题 ( 变量必须大于 0 )
处理决策变量
无约束的问题 , 在标准形式中 , 所有的变量必须都
;
这里使用
代替
, 新增加的两个变量
注意之后的每个步骤都要考虑 将
转为
;
2. 约束方程
转化 ( 松弛变量 )
该约束条件是
不等式 , 需要在左侧加上 松弛变量
, 将 小于等于不等式 转为等式 ;
3. 约束方程
转化 ( 剩余变量 )
该约束条件是
不等式 , 需要在左侧减去 剩余变量
, 将 大于等于不等式 转为等式 ;
4. 约束方程
转化 ( 右侧常数转正数 )
该式子是等式 , 但是右侧常数小于
, 这里需要将右侧的常数转化为正数 , 在方程两边乘以
;
5. 目标函数转化
转化顺序说明 : 在处理上述转化时 , 需要加入新的变量 , 如 无约束的变量需要增加两个变量 , 约束方程的 松弛变量 和 剩余变量 , 因此目标函数最后转化 ;
( 1 ) 将新增的变量加入
原目标函数为 :
新增的变量 :
没有约束变量 , 使用
代替 ;
不等式时 , 加入了
松弛变量 ;
不等式时 , 加入了
剩余变量 ;
此时加入 新增变量 后的 目标函数 为 :
( 2 ) 最小值 转 最大值
标准形式的目标函数是求最大值 , 这里在上面加入变量的结果的基础上 , 两边乘以
, 得到如下公式 :
6. 最终结果 :