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

Shuanglin Li
2021-11-24 / 1 评论 / 2,071 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2021年11月28日,已超过958天没有更新,若内容或图片失效,请留言反馈。

我们在建立数学模型时候,可能会遇到将两个决策变量相乘的情况,从而使得我们的模型变成了非线性规划模型。使得一些商业求解软件(如: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.$$

本文共 290 个字数,平均阅读时长 ≈ 1分钟
0

打赏

海报

正在生成.....

评论 (1)

取消
  1. 头像
    L Lv.1
    成都 ·MacOS · Google Chrome
    沙发

    很有帮助,最近正在学mosek的优化,正愁分段函数和变量乘法如何线性化。

    回复 删除 垃圾