线性规划的基本概念
建立优化问题的数学模型, 首先要确定问题的决策变量, 决策变量含有多个因素, 因此一般用向量 $\vec{x}=(x_1,x_2,\ldots,x_n)^T$ 来表示. 当然这些 $x_i$ 是有限定范围的. 设 $\vec{x}\in\Omega$, 称 $\Omega$ 为可行域.
另外这些变量 $x_i$ 之间满足一些约束条件, 记为 $g_i(\vec{x})\leqslant 0$, $(i=1,2,\ldots,m)$. 从而数学模型可以表示如下:
\[
\begin{aligned}
&\min_{\vec{x}\in\Omega} z=f(\vec{x})\qquad(1)\\
\text{s. t.} \ &g_i(\vec{x})\leqslant 0,\quad\text{for}\ i=1,2,\ldots,m.\qquad(2)
\end{aligned}
\]
由上述 (1) 和 (2) 组成的模型属于约束优化, 若只有 (1) 式, 则称为无约束优化, $f(x)$ 称为目标函数, 而 $g_i(\vec{x})\leqslant 0$, $(i=1,2,\ldots,m)$ 称为约束条件.
当 $f(x)$ 和 $g_i(x)$ 均为线性函数时, 上述优化问题称为线性规划问题. 只要其中某个函数是非线性的, 则称为非线性规划问题.
决策变量、目标函数、约束条件构成了线性规划的三个基本要素.
对于线性规划问题, 若决策变量的取值限定为整数, 则称之为整数线性规划问题.
对于线性规划问题, 由于 $g_i(x)\leqslant 0$ 是 $\mathbb{R}^n$ 中的超平面, 因此可行域 $\Omega$ 是 $\mathbb{R}^n$ 中的凸多面体. 从而 $f(x)$ 的最优值一定在该凸多面体 $\Omega$ 的某个顶点处取得(也可能在 $\Omega$ 的某个线段或某个面或某个高维的边界上取得).
不妨设 $g_i(x)=a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n-b_i\leqslant 0$, 于是 $g_i(x)\leqslant 0$, $i=1,2,\ldots,m$ 可以改写为
\[
\begin{pmatrix}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
\vdots\\
x_n
\end{pmatrix}
\leqslant
\begin{pmatrix}
b_1\\
b_2\\
\vdots\\
b_m
\end{pmatrix}
\]
在实际问题中, 对于不等式 $g_i(x)=a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\leqslant b_i$ 不要进行约化. 我们一般称 $b_i$ 为第 $i$ 种资源的供给量.
我们会求第 $i$ 种资源的影子价格(dual price), 以及 $b_i$ 可以变动的范围(Range). 研究 $b_i$ 的变动范围, 被称为敏感分析.
所谓影子价格, 实际上是效益 $z$ 关于 $b_i$ 的偏导数.
对于 $g_i(x)\leqslant b_i$, $i=1,2,\ldots,m$, 我们引入非负变量 $x_{n+1}$ 使得 $g_i(x)+a_{i,n+1}x_{n+1}=b_i$. 从而将约束从不等式变为等式. 一般的, 对一些变量通过平移或镜像对称变换 $x'_i=-x_i$ 使得所有 $x_i$ 都非负. 于是上面的线性规划问题可以变为
\[
\min z=f(x)=c_1 x_1+c_2 x_2+\cdots+c_n x_n+0x_{n+1}.
\]
\[
\begin{pmatrix}
a_{11}&a_{12}&\cdots&a_{1n}&a_{1,n+1}\\
a_{21}&a_{22}&\cdots&a_{2n}&a_{2,n+1}\\
\vdots&\vdots&\ddots&\vdots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}&a_{m,n+1}\\
\end{pmatrix}
\begin{pmatrix}
x_1\\
x_2\\
\vdots\\
x_n\\
x_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
b_1\\
b_2\\
\vdots\\
b_m
\end{pmatrix}
\]
若记 $\vec{c}=(c_1,c_2,\ldots,c_n,0)$, $\vec{x}=(x_1,x_2,\ldots,x_n,x_{n+1})^T$, $A_{m\times(n+1)}$ 为上面线性方程组的系数矩阵, $\vec{b}=(b_1,b_2,\ldots,b_m)^T$, 则线性规划问题可写成如下矩阵的形式:
\[
\begin{aligned}
\min z=f(x)=cx,\\
A\vec{x}=\vec{b}.
\end{aligned}
\]
若令 $\Phi(x)=A\vec{x}-\vec{b}$, 则有 Lagrange 乘数法, 若函数 $f(x)$ 在 $x^0$ 取得极值, 则存在 $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_m)\in\mathbb{R}^m$, 使得
\[
Jf(x^0)-\lambda\cdot J\Phi(x^0)=0.
\]
此即
\[
c-\lambda\cdot A=0.
\]
也就是说对于线性规划问题, Lagrange 乘数法在求解上没有帮助. 线性规划的求解本质上取决于由约束决定的凸多面体.