线性规划的标准形式

标准形式的定义

• 目标函数：最大化线性目标函数 其中，x 是决策变量向量，c  是目标系数向量。

• 约束条件：等式形式约束 A x = b, 其中，A 是约束系数矩阵，b 是常数项向量。

• 变量非负约束： 。

因此，标准形式可以写成：

.

如何将线性规划问题化为标准形式？

在实际问题中，线性规划模型的形式可能不符合标准形式，需要进行如下转换：

1. 目标函数方向转换

• 如果目标函数是最小化（min⁡z ），将其转换为最大化形式： 。 因此，将目标函数的系数乘以 -1。

2. 不等式约束转为等式约束

• “≤”约束： 如果某约束为 则引入松弛变量 ，

• “≥”约束： 如果某约束为 则引入剩余变量（也叫过剩变量）：

3. 消除自由变量

• 如果某变量无非负约束（即 可以取正数或负数），用两个非负变量替换： 其中 。

4. 确保变量非负

• 标准形式要求所有变量均满足非负约束，因此需要处理自由变量或带负号的变量。

示例

原始问题

标准化过程

1. 目标函数方向转换： 将 min⁡z 转换为 max⁡z ：

2. 处理约束：

   • 第一约束 ： 引入剩余变量 ：

   • 第二约束 ： 引入松弛变量 ：

3. 处理自由变量： 为自由变量，替换为，其中 。

4. 整理结果： 标准形式为：

subject to: