线性规划模型的标准形式优化

在使用普通单纯形法求解时,第一步就是寻找基本可行解,前提是先将原模型标准化。

(1)标准型的表达方式。

线性规划模型的标准形式定义为模型(1-9)。

也可以写成模型(1-10)和模型(1-11),其中模型(1-11)较为常用。

线性规划模型的标准形式有如下特征:

①目标函数求最大值,即max Z。

②资源限量非负,即b≥0。

③决策变量非负,表示所有决策变量取值均大于等于零,即X≥0。

④约束条件为等式,即AX＝b。

(2)一般形式与标准形式的转换方法。

①决策变量非负。若某决策变量xk为取值无约束(无符号限制),令xk＝x′kx″k(x′k≥0,x″k≥0);若xk≤0,令xk＝－x′k,则x′k≥0。

②目标函数求最大值。对于极小化原问题min Z＝CX,则令Z′＝－Z,原问题则转为求max Z′＝－CX,即当Z′达到最大值时,Z达到最小值,求解后应注意还原,即Z＝－Z′。(www.xing528.com)

③约束条件为等式。

对于“≤”型约束,则在“≤”左端加上一个非负松弛变量,使其变为等式。例如,原问题某一约束为x1＋x2≤3,加入松弛变量后,则变为x1＋x2＋x3＝3。

对于“≥”型约束,则在“≥”左端减去一个非负剩余变量,使其变为等式。例如,原问题某一约束为2x1＋3x2≥4,加入剩余变量后,则变为2x1＋3x2－x4＝4。

注意:不管是松弛变量还是剩余变量,在目标函数中的系数均为零(为什么?)。

④资源限量非负。若某个bi＜0,则将该约束两端同乘－1,以满足非负性的要求。例如,原问题某一约束为5x1＋6x2＝－7,处理后变为－5x1－6x2＝7。

【例1-13】将下面线性规划模型转化为标准型:

解:

①决策变量标准化。由题意可知,x3取值无约束,既可以取正值,也可取负值(－∞＜x3＜＋∞),但标准型中要求变量非负,所以设x3＝x′3－x″3(x′3≥0,x″3≥0),其值可能为正,也可能为负,因此符合x3的取值无约束。对于x1≤0,可令x1＝－x′1,则x′1≥0。

②约束条件标准化。在第一个约束条件“≤”左端加入松弛变量x4,令x4≥0,则原不等式转化为等式－x1＋x2＋x3＋x4＝4;在第二个约束条件“≥”左端减去剩余变量x5,令x5≥0,则原不等式转化为等式－x1＋x2－x3－x5＝－6,同时在等号两端乘以－1,则原不等式转化为等式x1－x2＋x3＋x5＝6。

③目标函数标准化。由于原目标函数求最小值,可令Z′＝－Z,得到max Z′＝max(－Z),即原目标函数转化为max Z′＝－2x1－x2＋2x3。综上,原模型转化为标准型:

注意:若原模型中存在三个变量x1,x2和x3,若没有给出某一变量(如x3)的取值范围,则说明该变量(如x3)的取值无约束。