数学规划

I. 线性规划 (Linear Programming)


线性规划的一般式:

$$
\\max(min) Z = c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}
\\s.t.
\left\{
\begin{array}
\\a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}\geq(=\leq)b_{1}
\\a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}\geq(=\leq)b_{2}
\\\cdots
\\a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}\geq(=\leq)b_{m}
\\x_{j}\geq 0 \quad (j=1,2,...,n)
\end{array}
\right.
$$

线性规划的标准式:

$$
\\max(min) Z = c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}
\\s.t.
\left\{
\begin{array}
\\a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}\leq(=\geq)b_{1}
\\a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}\leq(=\geq)b_{2}
\\\cdots
\\a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}\leq(=\geq)b_{m}
\\x_{j}\geq 0 \quad (j=1,2,...,n)
\end{array}
\right.
$$

简写为:

$$
\\max(min) Z = C^TX
\\s.t.
\left
\{
\begin{array}
\\Ax \leq(=\geq) b
\\x \geq 0
\end{array}
\right.
$$

其中

$c=\left(\begin{array}\\c_{1}\\c_{2}\\\vdots\\c_{n}\end{array}\right)$ $x=\left(\begin{array}\\x_{1}\\x_{2}\\\vdots\\x_{n}\end{array}\right)$ $b=\left(\begin{array}\\b_{1}\\b_{2}\\\vdots\\b_{n}\end{array}\right)$

$A=\left(\begin{array}\\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{array}\right)$

1. 线性规划模型特征

  • 目标函数和约束条件全部为线性函数(一次多项式)
  • 变量可取值范围是连续区间

2. 线性规划中的数学名词概念

  • 目标函数:$Z = c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}$
  • 决策变量:目标函数中的$x$变量
    约束条件:$s.t.$中包含的所有的等式和不等式组成约束条件
  • 可行域:约束条件在空间围成的区域,即由可行解组成的域
  • 可行解:可行域中的每个点都是原问题的一个可行解
  • 最优解:能够使目标函数达到最大或最小的可行解
  • 凸集:集合的一种,用于描述可行域,满足以下性质令 $K$为集合,$∀x_{1},x_{2} \in K$,若$αx_{1}+(1−α)x_{2}\in K$,其中α∈[0,1]),则 $K$ 为凸集

凸集

3. 线性规划模型—"运输模型"

设某种货物有m个产地$A_{1},A_{2},...,A_{m}$,和n个销地$B_{1},B_{2},...,B_{n}$,其中$A_{i}$的产量为$a_{i},B_{j}$的销量为$b_{j}$,产地$A_{j}$运往销地$B_{j}$的运价为
$$C_{ij},i = 1,2,...,m;j = 1,2,...,n.$$
求尽可能满足销地需求且总费用最小的运输方案。

  • 供需平衡的数学模型
    $$
    \sum_{i}a_{i} = \sum_{j}b_{j}
    $$
    各个产地的物资总和正好满足所有销地的需求,运输问题的数学模型为
    $$
    \\min z = \sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}
    \\s.t.
    \left
    \{
    \begin{array}
    \\ \sum_{j=1}^nx_{ij} =a_{i},i = 1,...,m
    \\ \sum_{i=1}^nx_{ij} =b_{j},j=1,...,n
    \\ x_{ij}\geq 0,\quad i=1,...,m;\quad j=1,...,n
    \end{array}
    \right.
    $$

ps :供需平衡运输问题一定存在最优解.

  • 供大于需的数学模型

$$
\sum_{i}a_{i} > \sum_{j}b_{j}
$$

各个销地的需求一定能够得到满足,但各个产地的物资不一定全部运走。运输问题的数学模型为

$$
\\min z = \sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}
\\s.t.
\left
\{
\begin{array}
\\ \sum_{j=1}^nx_{ij} \leq a_{i},i = 1,...,m
\\ \sum_{i=1}^nx_{ij} = b_{j},j=1,...,n
\\ x_{ij}\geq 0,\quad i=1,...,m;\quad j=1,...,n
\end{array}
\right.
$$

  • 供小于需的数学模型

$$
\sum_{i}a_{i} < \sum_{j}b_{j}
$$

各个销地的需求不一定能够得到满足,运输问题的数学模型为
$$
\\min z = \sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij}
\\s.t.
\left
\{
\begin{array}
\\ \sum_{j=1}^nx_{ij} = a_{i},i = 1,...,m
\\ \sum_{i=1}^nx_{ij} \leq b_{j},j=1,...,n
\\ x_{ij}\geq 0,\quad i=1,...,m;\quad j=1,...,n
\end{array}
\right.
$$

4. 线性规划求解方法-- 单纯形法

TODO:待补充!

5. 关于线性规划有三条重要定理

  • 定理1 若线性规划存在可行域,则可行域为凸集
  • 定理2 线性规划的基本可行解对应于可行域的顶点
  • 定理3 若线性规划有最优解,则一定存在基本可行解为最优解。

6. 线性规划的对偶问题及灵敏的分析

线性规划的对偶性

对于每一个线性规划P,总存在着另一个线性规划D,两者之间存在着密切的联系,人们可以通过求解对偶规划D来获得原规划P的最优解。
对偶理论
对偶问题可被看作是原始问题的“行列转置”

原问题:
$$
\\min \quad c^Tx
\\s.t.\quad Ax\geq b\quad x\geq 0
$$

对偶问题:
$$
\\max \quad b^T
\\s.t.\quad A^Ty \leq c \quad y \geq 0
$$

ps: 对偶问题的决策变量被称为对偶变量。

由上可看出,原问题的价值系数在对偶问题中成为约束条件的右端项,而对偶问题的价值系数在原问题中成为约束条件的右端项,原问题中的决策变量$x_{i}$的系数行向量变成对偶问题中的决策变量$y_{i}$的系数的列向量,而对偶问题的决策变量$y_{i}$的系数行向量变成原问题中的决策变量$x_{i}$的系数的列向量。

原问题和对偶问题是相对而言的,若把对偶问题看成原问题,则原问题就是其对偶问题,即对偶问题的对偶是原问题。

原问题与对偶问题间的对应关系
原问题与对偶问题的关系

对偶问题基本定理

对偶问题主要有如下定理:

  • 弱对偶定理
  • max问题的任何一个可行解的目标值为min问题目标值的一个下界
  • min型问题任何一个可行解的目标值为max型问题目标值的一个上界
  • 强对偶定理
    若原问题有最优解,那么对偶问题也有最优解,且两个问题最优解的目标函数值相等
  • 最优性定理
    若 $\bar{x}$ 和 $\bar{y}$ 分别为原问题和对偶问题的可行解,那么原问题和对偶问题都有最优解,且当 $c^T\bar{x}=b^T\bar{y}$时,$\bar{x}$和$\bar{y}$分别为原问题和对偶问题的最优解。
  • 互补松弛定理
  • 若$\bar{x}$和$\bar{y}$分别为原问题和对偶问题的可行解,则它们分别是原问题和对偶问题的最优解的充要条件是$\bar{x}^T(A^T\bar{y}-c)=0$和$\bar{y}^T(A\bar{x}−b)=0$
  • ps: 通过互补松弛定理,给出原问题(对偶问题)的最优解,便可求得其对偶问题(原问题)的最优解。
  • 无界性
    若原(对偶)问题为无界解,则对偶(原)问题为无可行解。
    若原(对偶)问题为无可行解,对偶(原)问题或为无界解,或为无可行解。

通过这些定理可以将原来难以解决的原问题通过引入对偶理论从而得以解决

灵敏度分析

在许多实际问题中,数据模型的数据未知,需要根据实际情况进行测量、估计和预测,因此这些数据不是十分精确,数据的略微的变化可能会引起问题解的显著变化。所谓灵敏度分析就是研究输入数据的扰动对LP最优解的影响,或者说是LP最优解在参数变化、约束条件增减、决策变量增减的影响下的稳健性。
灵敏度分析主要就是考虑问题
$$
\\min\quad z=c^Tx
\\s.t. \quad Ax \geq b \quad x\geq 0
$$
中,参数$c_{i},b_{i},A_{i}$的变化是否会引起最优解的变化

  • 参数$c_{i}$的变化
  • $c_{i}$为非基变量价值系数$c_{k}$的变化
    假设$\bar c_{k}=c_{k}+\Delta c_{k}$,则其在单纯形法中的检验数变为$\sigma \bar k=\sigma k+\Delta c_{k}$,只需要让$\sigma \bar k \geq 0 $即$ \sigma k \geq −\Delta c_{k}$即可保证最优解不变
  • $c_{i}$为基变量价值系数$c_{b}$的变化
    假设 $\bar c_{b}=c_{b}+\Delta c_{b}$, 则其在单纯形法中的检验数变为$\sigma \bar b=\sigma b−(0,0,0,..\Delta c_{b},…0,0,0)B^{−1}N$,其中$(0,0,0,..\Delta c_{b},…0,0,0)$为基变量的价值系数的变化量组成的向量,$B_{−1}N$为单纯形表中非基变量对应的系数列组成的矩阵,同样只需要让$\sigma \bar b\geq 0$即可保证最优解不变.
  • 参数$b_{i}$的变化
  • $b_{i}$的变化的时候需要保证$\bar b=B^{-1}(b +\Delta b)\geq 0$,否则需要将$\bar b$作为新的$b$的值代入到原来的单纯形表中,让后通过对偶单纯形法进行求解。对偶单纯形法的步骤与原始单纯形法的步骤非常相似,只是选择出基变量和入基变量的方法不同。出基变量选择为$b_{k}=min{b_{i},i=1,2,..m}$所对应的 $x_{k}$,入基变量选择为下面公式对应的$x_{l}$,
    $$
    \frac{\sigma {l}}{a{kl}}=max \quad [\frac{σ_{j}}{a_{kj}}|a_{kj}<0, \quad j=1,2,…n]
    $$
  • 参数$A_{i}$的变化
  • $A_{k}$不是基阵$B$中的列向量
    假设$A_{k}$变化为$\bar A_{k}=A_{}k+ \Delta A_{k}$而新的单纯形法的校验数$\bar \sigma_{k}=c_{k}-c_{B}B^{-1}\bar A_{k}$只要$\bar \sigma_{k}\geq 0$则原最优解不变
  • $A_{k}$是基阵$B$中的列向量
    此时单纯形表的所有系数都改变了,此时需用单纯形法重新计算

灵敏度分析还包括增加新变量$x_{n+1}$增加新的约束条件等情况对原最优解的影响分析。
TODO:待补充


II. 整数规划

整数规划是一类要求变量取整数值的数学规划,可分为线性和非线性两类。
整数规划是数学规划中一个较弱的分支,目前只能解中等规模的线性整数规划问题,而非线性整数规划问题还没有非常好的办法。

ps: 在此只讨论整数线性规划

1.整数线性规划 (Integer Linear Programming)

整数线性规划问题:部分或全部决策变量取值为整数的线性规划问题称为整数线性规划问题(Integer Linear Programming,简称LIP)。
整数变量:取值为整数的决策变量称为整数决策变量或简称为整数变量。

整数线性规划可分为:
纯整数线性规划(全部决策变量取值整数)(Pure Integer Programming,简称PIP)
混合整数线性规划(部分决策变量取值整数)(Mixed Integer Programming,简称MIP)
0-1整数线性规划(全部整数决策变量为0-1变量)(Binary Integer Programming,简称BIP)

1) 整数线性规划形式

$$
max(min)z = \sum_{j=1}^n c_{j}x_{j}
\\s.t.
\left
\{
\begin{array}
\\a_{11}x_{1}+...+a_{1n}x_{n}\leq(\geq,=)b_{1}
\\\cdots
\\a_{m1}x_{1}+...+a_{mn}x{n}\leq(\geq,=)b_{n}
\\x_{j}\geq 0 \quad x_{j}\in Z \quad j=1,2,...,n
\end{array}
\right.
$$
整数规划最优解不一定在顶点达到整数规划的最优解搜索范围大于对应的线性规划.

2) 松弛问题

一个整数线性规划问题,将其整数约束条件改为非负实数,就成为一个通常的线性规划问题,这个线性规划问题称为原整数线性规划问题的松弛问题。松弛问题可以用单纯形法求解。

3) 整数线性规划可行解和最优解的性质

  • 整数线性规划问题的可行解的集合是它的松弛问题可行解集合的一个子集,不具有凸性。
  • 整数线性规划问题最优解的目标函数值不会优于相应松弛问题最优解的目标函数值

4) 整数线性规划模型特征

  • 目标函数与所有约束均为线性函数(一次多项式)
  • 决策变量取值范围限定为整数

5) 整数规划问题求解方法

TODO:待补充!


2. 0-1整数线性规划

决策变量只在0和1中取值的整数变量的整数规划问题。

1) 0-1整数线性规划模型特征

  • 目标函数与所有约束条件均为线性函数
  • 决策变量取值范围只能是0或1

TODO:待补充!


III. 多目标规划

在实际决策中,衡量方案优劣要考虑多个目标,这些目标中,有主要的,也有次要的;有最大值的,也有最小值的;有定量的,也有定性的;有相互补充的,也有相互对立的,面对这么多要考虑的目标,线性规划则不适用(线性规划只能解决一组线性约束条件下,一个目标的最大或最小值的问题)。

TODO:待补充!

IV. 非线性规划

目标函数为非线性函数或者存在非线性约束条件的数学规划称为非线性规划。
TODO:待补充!