问题

建立优化问题的数学模型, 首先要确定问题的决策变量, 决策变量含有多个因素, 因此一般用向量 $\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_n
\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$ 的偏导数.