[运筹学]01. 线性规划问题初探

运筹学 01 — 线性规划问题

问题的识别
在投入到线性规划问题的各种计算之前，我想到的问题是，我如何在实际生活中识别出一个问题是线性规划问题，得以后续使用求解线性规划的方法对线性规划问题进行求解。

出术语本身出发，线性规划问题的识别点在于「线性」和「规划」两点上。
规划即我们所面对的问题是一个求最值或极值的问题，是在若干方案中选择一个方案进行实施。更具体一些，规划体现在如何从「我们拥有的资源」到「收益最大化/代价最小化」这样一个HOW的过程中。
线性体现在将问题抽象为数学模型（数学描述）后，变量都是一次的。对应于实际中，说明资源所带来的收益或行动所付出的代价是恒定的，不发生变化的（变化率为0）。

问题的抽象
于是，线性规划问题的提出，是为了在资源有限的情况下，为追求利益最大/代价最小。
资源有限，表现为线性规划中的约束条件。
利益最大/代价最小，表现为线性规划的目标函数。
而最终得到的方案，表现为线性规划中的决策变量

决策变量、目标函数、约束条件，即为线性规划问题的共同特征，也即线性规划模型的三要素。
综上，LP问题都可用一组决策变量(x1，x2，…，xn)表示某一决策方案；这组决策变量的值就代表一个具体的确定方案。一般这些变量取值都是非负的；
一般都存在一定的约束条件，这些约束条件可 以用一组线性等式或线性不等式来表示；
都有一个要求达到的目标，它可以用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。

线性规划中解的相关概念
可行解：满足线性规划约束条件的解，即满足约束条件(1.2)、(1.3)的解，称为可行解，记为： X=( x1,x2,···,xn)T
最优解：使目标函数（1.1）达到最值（最大或最小） 的可行解，记为X=(x1
*,x2 *,···,xn *)。
基：设矩阵Am×n（m<n）的秩为m， B是 A中m ×m阶非奇异子阵，|B| ≠ 0，即B的各列线性 无关，则称B是系数矩阵A的一个基。
若设LP问题为：
Max Z = CX
st. AX = b
X ≥ 0
则将A写成分块矩阵的形式，LP可改写为：
Max Z = CX
st. AX = (B,N)X = b
X ≥ 0