下载掌阅APP，畅读海量书库
立即打开
线性优化是在 线性约束 条件下求解 线性目标函数 的极值问题。
称一个优化问题为（约束型）线性优化问题，如果
（1）问题的解可以表示为 n 维决策向量：
x =（ x 1 ， x 2 ，…， x n ） T
（2）问题的目标函数可以表示为线性形式：
f （ x ）= c 1 x 1 + c 2 x 2 +…+ c n x n
（3）问题的等式/不等式约束可以表示成线性形式：
其中，参数的数量 n 称为问题的维，约束的数量 m 称为问题的阶。例如式（1 - 13）即为 n 维 m 阶线性优化问题，目标函数的系数 c ij 称为价值系数，约束条件的系数 a ij 称为约束系数，常数 b i 称为资源系数。
线性优化的标准形式为
矩阵形式是
其中， x =（ x 1 ， x 2 ，…， x n ） T 称为决策向量， c =（ c 1 ， c 2 ，…， c n ） T 称为价值向量， A =（ a ij ） m × n 称为约束矩阵， b =（ b 1 ， b 2 ，…， b m ） T 称为资源向量。
任意的线性优化问题最终都可以转换为上述等式约束的标准形式，方法如下：
（1）若目标函数为极大值，则通过取反即可转换为极小值问题。
（2）若约束条件为不等式，则考虑两种情况：①若不等式为≤，则可以在不等式左侧加上一个非负的松弛变量转换为等式；②若不等式为≥，则可以在不等式左侧减去一个非负的剩余变量转换为等式。
（3）若存在无约束的变量
x
i
，则可以将该变量转换为
。
对于线性优化标准形式 A m × n x n ×1 = b m ×1 的约束矩阵 A ，通过操作列向量可以重排为 B 和 D 的分块矩阵，即
其中，矩阵
B
∈
R
m
×
m
称为线性优化问题的基。根据rank
A
=
m
，可知矩阵
B
非退化。根据
B
可以构造新的约束方程
，则由det
B
≠0可知存在逆矩阵
B
-1
，从而可以解得
将此
m
维向量
补充
n
-
m
个零元素，即扩充为
n
维向量
，此
x
=
称为优化问题
Ax
=
b
在基
B
下的基本解。基本解
x
的元素称为基变量。进一步地，如果基本解
x
=（
x
1
，
x
2
，…，
x
n
）
T
满足
x
i
≥0，则
x
称为基本可行解。
如果线性优化具有最优解，则其一定可以在基本可行解中找到。因此，可以先找到所有基本可行解，然后代入目标函数，寻找最大值。但是
m
×
n
的系数矩阵具有
个基本可行解，求解复杂度较高。
对于目标函数 f （ x ）= c T x ，集合{ x ∈ R n | c T x = c }构成超平面；上部 H + ={ x ∈ R n | c T x ≥ c }为正闭半空间，下部 H - ={ x ∈ R n | c T x ≤ c }为负闭半空间。对于约束函数 A m × n x = b m ×1 ，集合{ x ∈ R n | A m × n x ≤ b m ×1 }构成多面凸集，而非空且有界的多面凸集构成凸多面体。可以证明，线性优化的基本可行解 x 对应凸多面体的顶点。
因此，逐次遍历顶点即可搜寻到线性优化的最优解，这种迭代算法称为单纯形法。单纯形法的基本思路是，先从可行域的某个顶点（对应一个基本可行解）开始，转换到另外一个顶点，直到目标函数达到最优，则所得即为最优解。相对于暴力尝试方法，单纯形法从一个基本可行解切换到另一个基本可行解时不是盲目尝试，而是首先沿着边切换到与其相邻的极点，然后只切换到能改良优化目标的极点。重复这样的做法，直到再也找不到可以改良目标的相邻极点，此时极点就是线性优化的最优解。