非线性函数线性化转化方法(乘积式)

我们在建立数学模型时候,可能会遇到将两个决策变量相乘的情况,从而使得我们的模型变成了非线性规划模型。使得一些商业求解软件(如:Gurobi, Cplex等)在对模型求解的时候产生困难。因此,我们需要将非线性表达式转化为线性表达式,降低求解难度。我们根据变量的特点,分为三种情况进行讨论:

1 两个均为0-1变量的情况

当两个变量$x_{1}$和$x_{2}$均为0-1变量时,假设对应的乘积我们用$y$表示,即$y=x_{1} \times x_{2}$, 而且$x_{1}, x_{2} \in \left\{0,1\right\}$,则我们可以采用下列公式组进行转化:
$$\left\{\begin{array}{l}y \le x_{1} \\y \le x_{2} \\y \ge x_{1}+x_{2}-1 \\y \in \left\{0,1\right\}\end{array}\right.$$

2 一个为0-1变量,一个为连续变量的情况

当两个变量$x_{1} \in \left\{0,1\right\}$,而$x_{2} \in [0,u]$时,同样的,假设对应的乘积为$y$,即$y=x_{1} \times x_{2}$,则我们可以采用下列公式组进行转化:
$$\left\{\begin{array}{l}y \le u x_{1} \\ y \le x_{2} \\ y \ge x_{2} - u (1-x_{1}) \\ y \in [0,u]\end{array}\right.$$

3 一个为0-1变量,一个为有上下界的连续变量的情况

此情况,是情况2的一种普通表达方式。当两个变量$x_{1} \in \left\{0,1\right\}$,而$x_{2} \in [l,u]$,且$l \ge 0$时,同样的,假设对应的乘积为$y$,即$y=x_{1} \times x_{2}$,则我们可以采用下列公式组进行转化:
$$\left\{\begin{array}{l}y \le x_{2} \\ y \ge x_{2} - u (1-x_{1}) \\ l x_{1} \le y \le u x_{2} \end{array}\right.$$

标签: 线性转化, GUROBI, CPLEX

添加新评论