首页 理论教育 线性规划问题的标准化转换方法

线性规划问题的标准化转换方法

时间:2023-05-16 理论教育 版权反馈
【摘要】:由前面可知,线性规划问题有各种不同的形式。求解线性规划问题时,应将这些多种形式的数学模型统一变换为标准型,这里规定的标准型为:在标准型中规定各约束条件的右端项bi>0,否则等式两端乘以“-1”。线性规划模型标准型的特点如下:目标函数求最大值。实际碰到的各种线性规划问题的数学模型都应变换为标准型后求解。转化为标准型的步骤如下。例1-3将下列线性规划问题化为标准型。

线性规划问题的标准化转换方法

由前面可知,线性规划问题有各种不同的形式。目标函数有的要求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′达到最大值,反之亦然。

其标准型如下:

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈