由前面可知,线性规划问题有各种不同的形式。目标函数有的要求max,有的要求min;约束条件可以是“≤”形式的不等式,也可以是“≥”形式的不等式,还可以是等式。决策变量一般是非负约束,但也允许在(-∞,∞)范围内取值,即无约束。求解线性规划问题时,应将这些多种形式的数学模型统一变换为标准型,这里规定的标准型为:
在标准型中规定各约束条件的右端项bi>0,否则等式两端乘以“-1”。
线性规划模型标准型的特点如下:
(1)目标函数求最大值。
(2)约束条件都为等式方程,且右端常数项bi都大于或等于零。
(3)决策变量xj为非负。
用向量和矩阵符号表示为:
向量 Pj对应的决策变量是 xj。
用矩阵表示为:
这里A 为约束条件的m×n 维系数矩阵,一般m<n;b 为资源向量;C 为价值向量;X 为决策变量向量。
实际碰到的各种线性规划问题的数学模型都应变换为标准型后求解。下面讨论如何变换为标准型的问题。
转化为标准型的步骤如下。
(1)目标函数的转换。
如果是求极小值,即minz=∑cjxj,则可将目标函数乘以(-1),化为求极大值问题。即
令
也就是令maxz′=min(-z),可得到上式。(www.xing528.com)
(2)变量的变换。
若存在取值无约束的变量xj,可令
(3)约束方程的转换。
由不等式转换为等式:
其中xn+1≥0,称为松弛变量;
其中xn+1≥0,称为剩余变量。
(4)变量xj≤0的变换。
可令=-xj。显然,≥0。
例1-3 将下列线性规划问题化为标准型。
解 (1)因为x3无符号要求,即x3可取正值也可取负值,标准型中要求变量非负,所以用替换x3,且
(2)第一个约束条件是“≤”号,故在“≤”左端加入松弛变量x4,x4≥0,化为等式。
(3)第二个约束条件是“≥”号,故在“≥”左端减去剩余变量x5,x5≥0。
(4)第三个约束方程右端的常数项为-5,在方程两边同乘以(-1),将右端常数项化为正数。
(5)目标函数是最小值,为了化为求最大值,令z′=-z,得到max z′=min(-z),即当z达到最小值时,z′达到最大值,反之亦然。
其标准型如下:
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。