信息系刘康泽
线性规划的标准型
在求解线性规划问题时,为了讨论问题的方便,将线性规划模型化为统一的标准形式。
线性规划的标准型
线性规划问题的标准型的特点是:
;
;
xj 为非负变量;
bi 都大于或等于零。
min f = c1x1+c2x2+…+cnxn
标准型
或用矩阵形式:
或写成下列形式:
其中:
其中c为价值系数向量,A为约束方程的系数矩阵,x为决策向量,b为约束向量,m是约束方程的个数,n是决策变量的个数,一般情况 m≤n,且 r(A)=m。
(2)约束条件为“≤”形式的不等式,则可以在“≤”号的左端添加一个非负松驰变量,把原“≤”型的不等式变为等式“=”。
变为:
(3)约束条件为“≥”形式的不等式,则可以在“≥”号的左端减去一个非负剩余变量,把原“≥”型的不等式变为等式“=”。
标准化方法:
(1)若目标函数是实现最大化,即要求目标
则令:
于是:
变为:
(4)若某个
,则对第个方程两边同时乘以-1 。
(5)若有无非负要求的变量,如变量取正值或负值都可以,
可令:
【例】将下列线性规划化为标准型
解:(1)目标函数是最大化,化为求最小化,令=-f
(2)第一个约束条件是“≤”号,在“≤”左端加入松驰变量 x4 ,x4≥0,化为等式;
(3)第二个约束条件是“≥”号,在“≥”号的左端减去剩余
变量 x5,x5≥0,化为等式;
(4)因为 x3 无符号要求,即 x3 取正值也可取负值,标准型中要求变量非负,所以令:
(5)第三个约束条件是“≤”号,且常数项为负数,因此在“≤”的左边加入松驰变量 x6 ,x6≥0,同时两边乘以-1。
综合起来得到下列标准型:
103线性规划的标准型 来自淘豆网m.daumloan.com转载请标明出处.
