基于TRE文章的非线性模型化线性方法

之前写过一篇有关TRE优化模型详解的博文：

https://www.cnblogs.com/zoubilin/p/17270435.html

这篇文章里面的附录给出了非线性模型化线性的方式，具体内容如下：

• 首先是篇文章的变量和原模型（具体见我上面那篇笔记）：
  
  
• 其次这篇文章附录给出的非线性化线性的方法：
  
  
  我觉得很经典，所以这几天我废了九牛二虎之力推导了这个附录的公式，并复现了它的化线性的过程•́‸ก

一、目标函数#

• 目标函数中的非线性项为：

$$Max\sum _{t\in T}\sum _{z\in Z}[P_{bz}^t\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)+P_{ez}^t\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)]$$

• 引入决策变量：

$$Y_{bzi}^t=\{\begin{array}{l}1,if\mathrm{在}t\mathrm{时}\mathrm{期}z\mathrm{区}\mathrm{域}\mathrm{渠}\mathrm{道}b\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{是}\mathrm{第}i\mathrm{个}\mathrm{价}\mathrm{格}\\ 0,else\end{array}$$

$$Y_{ezi}^t=\{\begin{array}{l}1,if\mathrm{在}t\mathrm{时}\mathrm{期}z\mathrm{区}\mathrm{域}\mathrm{渠}\mathrm{道}e\mathrm{对}\mathrm{应}\mathrm{的}\mathrm{是}\mathrm{第}i\mathrm{个}\mathrm{价}\mathrm{格}\\ 0,else\end{array}$$

• 此时应加入下面约束条件，即式(A.13)~式(A.14) 和式(A.28)~式(A.29)：

  $$\sum _{i\in I_{bzi}^t}{Y}_{bzi}^t=1$$
  $$\sum _{i\in I_{ezi}^t}{Y}_{ezi}^t=1$$
  $$Y_{bzi}^t,Y_{ezi}^t\in \{0,1\}$$

• 引入价格集合（已知量），其中$I_{bz}^t、I_{ez}^t$为对应渠道的可选择价格数量，$i=1,2,...,I_{bz}^t\mathrm{或}i=1,2,...,I_{ez}^t$：

$${\mathrm{\Omega }}_{bz}^t=\{P_{bzi}^t{\}}_{i\in I_{bz}^t}$$

$${\mathrm{\Omega }}_{ez}^t=\{P_{ezi}^t{\}}_{i\in I_{ez}^t}$$

• 那么有：$P_{bz}^t=\sum _{i\in I_{bz}^t}{P}_{bzi}^t{Y}_{bzi}^t$、$P_{ez}^t=\sum _{i\in I_{ez}^t}{P}_{ezi}^t{Y}_{ezi}^t$

• 此时，目标函数变为：

$$Max\sum _{t\in T}\sum _{z\in Z}[\sum _{i\in I_{bz}^t}{P}_{bzi}^t{Y}_{bzi}^t\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)+\sum _{i\in I_{ez}^t}{P}_{ezi}^t{Y}_{ezi}^t\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)]$$

• 目标函数中仍存在非线性项$Y_{bzi}^t\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$和$Y_{ezi}^t\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)$

  所以需要再引入下面决策变量，也就是式(A.6)~式(A.7)：

  $$V_{bzi}^t=Y_{bzi}^t\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$$
  $$V_{ezi}^t=Y_{ezi}^t\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)$$

  此时目标函数变为下式，也就是式(A.8) 的由来：

$$Max\sum _{t\in T}\sum _{z\in Z}[(\sum _{i\in I_{bz}^t}{P}_{bzi}^t{V}_{bzi}^t)+(\sum _{i\in I_{ez}^t}{P}_{ezi}^t{V}_{ezi}^t)]$$

设$\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$的上限为$a$，$\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)$的上限为$b$，要彻底转换目标函数变为线性，需要增加新的约束如下，包含了式(A.15)-式(A.18)、式(A.33)-式(A.34)：

$$V_{bzi}^t\le a{Y}_{bzi}^t$$

$$V_{ezi}^t\le b{Y}_{ezi}^t$$

$$V_{bzi}^t\le \sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$$

$$V_{ezi}^t\le \sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)$$

$$V_{bzi}^t\ge [\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)]-a(1-Y_{bzi}^t)$$

$$V_{ezi}^t\ge [\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)]-b(1-Y_{ezi}^t)$$

$$V_{bzi}^t,V_{ezi}^t\ge 0$$

$$\sum _{i\in I_{bzi}^t}{V}_{bzi}^t=\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$$

$$\sum _{i\in I_{ezi}^t}{V}_{ezi}^t=\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)$$

二、约束条件#

• 非线性项为$D_{bz}^t(P_z^t)$和$D_{ez}^t(P_z^t)$

• 经过上面的转换，有：

  • $e^{{\beta }_{0z}+{\beta }_{1z}{P}_{bz}^t}=e^{{\beta }_{0z}+{\beta }_{1z}\sum _{i\in I_{bz}^t}(P_{bzi}^t{Y}_{bzi}^t)}$其中，$Y_{bzi}^t$是一个0-1变量，所以又可以写成：$e^{{\beta }_{0z}+{\beta }_{1z}{P}_{bz}^t}=\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{e}^{{\beta }_{0z}+{\beta }_{1z}{P}_{bzi}^t}$.

  • 同理，$e^{{\beta }_{0z}+{\beta }_{1z}{P}_{ez}^t}=\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{e}^{{\beta }_{0z}+{\beta }_{1z}{P}_{ezi}^t}$

• 令

  $$r_{bzi}^t=e^{{\beta }_{0z}+{\beta }_{1z}{P}_{bzi}^t}$$
  $$r_{ezi}^t=e^{{\beta }_{0z}+{\beta }_{1z}{P}_{ezi}^t}$$

  即式(A.1)~式(A.2)，那么有：

  $$D_{bz}^t(P_z^t)=n_z^t\times \frac{\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{r}_{bzi}^t}{\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{r}_{bzi}^t+\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{r}_{ezi}^t+1}$$
  $$D_{ez}^t(P_z^t)=n_z^t\times \frac{\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{r}_{ezi}^t}{\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{r}_{bzi}^t+\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{r}_{ezi}^t+1}$$

• 为了将$D_{bz}^t(P_z^t)$和$D_{ez}^t(P_z^t)$化为线性，令：

  $$R_z^t=\frac{1}{\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{r}_{bzi}^t+\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{r}_{ezi}^t+1}$$

  即式(A.3)。那么$D_{bz}^t(P_z^t)=n_z^t{R}_z^t\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{r}_{bzi}^t$，$D_{ez}^t(P_z^t)=n_z^t{R}_z^t\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{r}_{ezi}^t$，需要明确的是：$\sum _{i\in I_{bz}^t}{Y}_{bzi}^t{r}_{bzi}^t+\sum _{i\in I_{ez}^t}{Y}_{ezi}^t{r}_{ezi}^t\ge 0$，故$R_z^t\le 1$

• 此时仍存在非线性项$\sum _{i\in I_{bz}^t}{R}_z^t{Y}_{bzi}^t{r}_{bzi}^t$和$\sum _{i\in I_{ez}^t}{R}_z^t{Y}_{ezi}^t{r}_{ezi}^t$

  令：

  $$U_{bzi}^t=R_z^t{Y}_{bzi}^t$$
  $$U_{ezi}^t=R_z^t{Y}_{ezi}^t$$

  即式(A.4)-式(A.5)。此时需要新增的约束条件如下，包含了式(A.21)-式(A.27)、式(A.32)-式(A.34)：

  $$U_{bzi}^t,U_{ezi}^t\ge 0$$
  $$R_z^t\ge 0$$
  $$U_{bzi}^t\le Y_{bzi}^t$$
  $$U_{ezi}^t\le Y_{ezi}^t$$
  $$U_{bzi}^t\le R_z^t$$
  $$U_{ezi}^t\le R_z^t$$
  $$U_{bzi}^t\le R_z^t-(1-Y_{bzi}^t)$$
  $$U_{ezi}^t\le R_z^t-(1-Y_{ezi}^t)$$
  $$\sum _{i\in I_{bzi}^t}{U}_{bzi}^t=R_z^t$$
  $$\sum _{i\in I_{ezi}^t}{U}_{ezi}^t=R_z^t$$

$$R_z^t+\sum _{i\in I_{bz}^t}{U}_{bzi}^t{r}_{bzi}^t+\sum _{i\in I_{ez}^t}{U}_{ezi}^t{r}_{ezi}^t=1$$

• 此时约束条件(6)、(7)变为：

$$\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)\le n_z^t\sum _{i\in I_{bz}^t}{U}_{bzi}^t{r}_{bzi}^t$$

$$\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)\le n_z^t\sum _{i\in I_{ez}^t}{U}_{ezi}^t{r}_{ezi}^t$$

• 那么$a=n_z^t\sum _{i\in I_{bz}^t}{U}_{bzi}^t{r}_{bzi}^t$，$b=n_z^t\sum _{i\in I_{ez}^t}{U}_{ezi}^t{r}_{ezi}^t$。约束$V_{bzi}^t\le a{Y}_{bzi}^t$和$V_{ezi}^t\le b{Y}_{ezi}^t$分别变为：

  $$V_{bzi}^t\le (n_z^t\sum _{i\in I_{bz}^t}{U}_{bzi}^t{r}_{bzi}^t)Y_{bzi}^t=n_z^t{U}_{bzi}^t\sum _{i\in I_{bz}^t}{r}_{bzi}^t{Y}_{bzi}^t$$
  $$V_{ezi}^t\le (n_z^t\sum _{i\in I_{ez}^t}{U}_{ezi}^t{r}_{ezi}^t)Y_{ezi}^t=n_z^t{U}_{ezi}^t\sum _{i\in I_{ez}^t}{r}_{ezi}^t{Y}_{ezi}^t$$

  • 已知$V_{bzi}^t\ge 0$，当$Y_{bzi}^t=0$时，上面的第一条约束条件变为$V_{bzi}^t\le 0$，此时$V_{bzi}^t$应为0；当$Y_{ezi}^t=1$时，上面的约束条件变为$V_{bzi}^t\le n_z^t{U}_{bzi}^t{r}_{bzi}^t$，此时$V_{bzi}^t$的取值应当为$0\le V_{bzi}^t\le n_z^t{U}_{bzi}^t{r}_{bzi}^t$。

    综上和同理，在约束$V_{bzi}^t,V_{ezi}^t\ge 0$下，式(A.19) 和式(A.20) 被推导出：

  $$V_{bzi}^t\le a{Y}_{bzi}^t\to V_{bzi}^t\le n_z^t{U}_{bzi}^t{r}_{bzi}^t$$
  $$V_{ezi}^t\le b{Y}_{ezi}^t\to V_{bzi}^t\le n_z^t{U}_{bzi}^t{r}_{bzi}^t$$

  • 对于约束条件$V_{bzi}^t\ge [\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)]-a(1-Y_{bzi}^t)$和$V_{ezi}^t\ge [\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)]-b(1-Y_{ezi}^t)$，它们分别变为：

    $$V_{bzi}^t\ge [\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)]-(n_z^t\sum _{i\in I_{bz}^t}{U}_{bzi}^t{r}_{bzi}^t)(1-Y_{bzi}^t)$$
    $$V_{ezi}^t\ge [\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)]-(n_z^t\sum _{i\in I_{ez}^t}{U}_{ezi}^t{r}_{ezi}^t)(1-Y_{ezi}^t)$$

    当$Y_{bzi}^t=0$时，上面第一条约束条件变为$\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)\le n_z^t\sum _{i\in I_{bz}^t}{U}_{bzi}^t{r}_{bzi}^t$这与文中式（6）相同；当$Y_{bzi}^t=1$时，它则变为$V_{bzi}^t=\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$，而这又被约束条件$\sum _{i\in I_{bzi}^t}{V}_{bzi}^t=\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)$包含。

    综上及同理，约束条件$V_{bzi}^t\ge [\sum _{w\in Z}(S_{bwz}^t+S_{ewz}^t)]-a(1-Y_{bzi}^t)$和$V_{ezi}^t\ge [\sum _{w\in Z}(O_{bwz}^t+O_{ewz}^t)]-b(1-Y_{ezi}^t)$均属于重复约束，可被消除。

由此，所有公式已全部被推出，但还多了两条约束：

• 对于约束条件$U_{bzi}^t\le R_z^t-(1-Y_{bzi}^t)$有：

  • $Y_{bzi}^t=0$时，$R_z^t\ge 0$，该约束已存在；$Y_z^t=1$时，$U_{bzi}^t=R_z^t$，该约束已被$\sum _{i\in I_{bzi}^t}{U}_{bzi}^t=R_z^t$所包含。

  • 综上及同理，约束条件$U_{bzi}^t\le R_z^t-(1-Y_{bzi}^t)$和$U_{ezi}^t\le R_z^t-(1-Y_{ezi}^t)$属于重复约束，均可被删除。

以上就是这篇论文公式全部的推导，上面是所使用的非线性化线性的方法简例如下。

三、简例#

(1) 带有0-1变量的非线性规划问题#

$$z=x_1{x}_2$$

其中决策变量$x_1\in \{0,1\}$,$0\le x_2\le a$

那么我们可以用下面的方法化为线性规划：

• 首先设一个新的决策变量$y=x_1{x}_2$，并将问题转化为：

  $$y\le a{x}_1$$
  $$y\le x_2$$
  $$y\ge x_2-a(1-x_1)$$
  $$y\ge 0$$

• 由此，问题变为了线性问题

(2) 带分母变量的非线性规划问题#

$$min\frac{x+2y+3}{4x+5y}$$

$s.t.$

$$6x+7y\le 8$$

$$9x+10y\ge 0$$

$$x,y\ge 0$$

• 令$z=\frac{1}{4x+5y}$，此时目标函数变为：$(x+2y)z+3z$，但仍含有非线性项，此时我们又令：$xz=u,yz=v$，那么可以得到：

  $$minu+2v+3z$$

  $s.t.$

  $$6u+7v\le 8z$$
  $$9u+10v\ge 0$$
  $$u,v,z\ge 0$$

• 解上面的线性规划问题，可得到$u,v,z$的精确解，之后可代入式子解方程，得到$x,y$的精确解。