建立线性规划标准模型

子任务2.2　建立线性规划标准模型

2.2.1　任务引入

【任务2-4】　将下列非标准型线性规划问题转化为标准型。

【任务2-5】　将下列非标准型线性规划模型化为标准型。

2.2.2　任务分析

数学模型是用数学方法（字母、数字、符号、公式等）对研究对象的数量关系所进行的定量描述。线性规划模型就是从实际的优化问题中抽象出来的，描述目标与条件相互关系的数学模型。无论目标是大是小，也无论条件的多寡与差异，线性规划模型最基本的要素是一致的，一般都包括以下3个方面：都是由决策变量、约束条件（线性等式或不等式）及目标函数（最大或最小）3部分组成的。我们已经看到线性规划问题可能有各种不同的形式。目标函数，有的要求实现最大化，有的要求实现最小化，约束条件可以是“≤”形式的不等式，也可以是“≥”形式的不等式，还可以是等式。这种多样性给讨论问题带来了不方便，为了便于以后讨论，我们有必要建立线性规划问题的标准形式。

2.2.3　知识构建

1）线性规划问题的标准模型

一般线性规划问题的标准模型为：

或简记为

上述标准模型有以下4个特征：

①决策变量全大于或等于零；

②约束条件全为线性等式；

③约束条件右端常数项全部为非负数；

④目标函数值总为最大。

2）非标准型线性规划问题的标准化

如果我们得到的一个线性规划问题不具有以上所说的4个特征，那么我们可以通过一定的数学变形将非标准型线性规划问题标准化，具体方法如下：

①若目标函数取最小值minz=CX，由于求z的最小值就是求-z的最大值，所以可以将其转化为max（-z）=-CX。

②当约束条件中第i个方程出现a_i1x₁+a_i2x₂+…+a_inx_n≤b_i时，则增加一个“松弛变量”x_i+1≥0，使它成为等式a_i1x₁+a_i2x₂+…+a_inx_n+x_i+1=b_i。同样，当约束条件中第i个方程出现a_i1x₁+a_i2x₂+…+a_inx_n≥b_i时，则减去一个“松弛变量”x_i+1≥0，使它成为等式a_i1x₁+a_i2x₂+…+a_inx_n-x_i+1=b_i。

③当决策变量x_j不满足x_j≥0时，则增加两个新的非负决策变最x′j≥0和x″j≥0，用x′j-x″j替代x_j，即令x_j=x′j-x″j。

④当约束条件中第i个方程右瑞出现常数项b_i＜0时，则在方程两边同时乘以-1，得到-b_i＞0。

这样，我们就可以将任意一个非标准型线性规划问题转化为标准型了。

2.2.4　任务实施

按照前面的转换方法，执行下列步骤：

步骤1　将min z；转化为max-z；

步骤2　令x₃=x₃′-x₃″，且x₃′＞0，x₃″＞0；

步骤3　将第一个约束方程的左边减去一个非负的松弛变量x₄，将第2、第3个约束方程的左边分别加上一个非负的松弛变量x₅和x₆。

这样，可以将任务2-4原来的线性规划问题标准化为：

同理对任务2-5实施标准化：

①因x₃无约束，故用x₃′- x₃″替换模型中的x₃，其中，x₃′，x₃″≥0；

②在第一个约束不等式左端加入松弛变量x₄，并将“≤”改为“=”；

③在第二个约束不等式左端减去松弛变量x₅，并将“≥”改为“=”；

④因b₃=-5，故将第3个约束两端各乘以-1；

⑤令z′=-z，将目标函数min z改为max z′；这样可将原线性规划转化为标准型：