标准模型

文章分类:Optimization
创建时间:2013年4月

模型设定

线性规划模型通常表述为精炼的数学形式,包括三个部分:

  • 目标函数,通常是最大化利润或最小化成本。
  • 约束条件,通常表现为等式或不等式。
  • 变量边界,通常是 x_j\ge 0

任何线性模型,在求解和分析前都应该转换为标准形:

\begin{gather*}
\text{maximize\ } \sum_{j=1}^n{c_jx_j}\\[0.1em]
\begin{aligned}
\sum_{j=1}^n{a_{ij}x_j} = b_i & \text{\quad for\ } i=1,2,\ldots,m \\
x_j\ge 0 & \text{\quad for\ } j=1,2,\ldots,n \\
\end{aligned}
\end{gather*}

即将约束条件中的不等式统一转换为等式。需要注意该标准模型要求 \vect{b}\ge 0

线性规划模型的变量 x_j 一般定义为产量。线性模型标准型中的系数也都可以对应实际经济问题的要素:

  • 右边常数 \vect{b} ——资源向量。
  • 目标函数系数 \vect{c} ——最大化问题通常对应收益问题,因此目标函数系数称为价格向量;最小化问题通常对应成本问题,因此目标函数系数称为成本向量。
  • 约束条件系数 \vect{A} ——技术矩阵。

模型变换

线性规划模型的约束条件存在以下三种形式:

\begin{array}{rcrcccrcl}
a_1 x_1 & + & a_2 x_2 & + & \cdots & + & a_n x_n & \ge & a \\
b_1 x_1 & + & b_2 x_2 & + & \cdots & + & b_n x_n &  =  & b \\
c_1 x_1 & + & c_2 x_2 & + & \cdots & + & c_n x_n & \le & c \\
\end{array}

在求解线性规划问题时,需要将两种不等式转换为标准型中的等式,因此需要掌握转换方法。

目标函数变换

线性规划模型的目标函数只有两种形式:最大化模型和最小化模型。两者之间的变换可以简单地将目标函数系数的符号取反,就可以将最大化函数转换为最小化函数,反之亦然。

不等式间变换

约束条件中 \sum_{j=1}^n{a_jx_j}\le b1 可以变换为 \sum_{j=1}^n{(-a_j)x_j}\ge -b,反之亦反。

不等式变换等式

模型中的任何不等式都可以在引入一个非负变量后变换为一个等式。

  • \sum_{j=1}^n{a_jx_j}\le b 可变换为 \sum_{j=1}^n{a_jx_j} + 1s = b,其中 s\ge 0
  • \sum_{j=1}^n{a_jx_j}\ge b 可变换为 \sum_{j=1}^n{a_jx_j} - 1t = b,其中 t\ge 0

其中:

  • 原有变量 x_j 称为 结构变量
  • 引入变量 s 称为 松弛变量
  • 引入变量 t 称为 剩余变量

变量边界变换

如果线性模型中某些 jx_j 符号不限,存在三种变换方法,要求掌握变量分解法:将 x_j 表示为两个非负变量之差,并用该差值替换所有 x_j。即:

x_j \equiv x_j^{\prime} - x_j^{\prime\prime},\qquad x_j^{\prime}\ge 0,x_j^{\prime\prime}\ge 0

该变换会增加模型的变量数目,但可保留原始关系中的线性属性。