北邮运筹学ch线性规划标准型.ppt

在用单纯法求解线性规划问题时,为了讨论问题方便,需将线性规划模型化为统一的标准形式。
线性规划的标准型
线性规划问题的标准型为
(有时求最小值)
;
。
;
5/30/2018
运筹学北京邮电大学
max(或min)Z=c1x1+c2x2+…+cnxn
5/30/2018
运筹学北京邮电大学
或用矩阵形式:
或写成下列形式:
5/30/2018
运筹学北京邮电大学
其中:
通常X记为: 。称A为约束方程的系数矩阵,m是约束方程的个数,n是决策变量的个数,一般情况m≤n,且r(A)=m。
5/30/2018
运筹学北京邮电大学
【】将下列线性规划化为标准型
【解】(1)因为x3无符号要求,即x3取正值也可取负值,标准型中要求变量非负,所以令
5/30/2018
运筹学北京邮电大学
(2)第一个约束条件是“≤”号,在“≤”左端加入松驰变量x4,x4≥0,化为等式;
(3)第二个约束条件是“≥”号,在“≥”号左端减去剩余变量(也称松驰变量)x5,x5≥0.
5/30/2018
运筹学北京邮电大学
(4)第三个约束条件是≤号且常数项为负数,因此在≤左边加入松驰变量x6,x6≥0,同时两边乘以-1。
(5)目标函数是最小值,为了化为求最大值,令Z′=-Z,得到max Z′=-Z,即当Z达到最小值时Z′达到最大值,反之亦然。
综合起来得到下列标准型
5/30/2018
运筹学北京邮电大学
当某个变量xj≤0时,令x‘j=-,将绝对值不等式化为两个不等式,再化为等式,例如约束
将其化为两个不等式
再加入松驰变量化为等式。
5/30/2018
运筹学北京邮电大学
?
可以对照四条标准逐一判断!
标准形式中的目标函数可以是求最小值。
图解法时不必化为标准型。
。
LP的基本概念
Exit
进入练习
5/30/2018
运筹学北京邮电大学