线性化方法¶
线性规划求解算法大多是精确算法,所以,将一个组合优化问题转化为线性规划问题是非常有必要的,然而,很多时候,要么是目标函数是非线性函数,要么是约束是非线性约束,很多时候都不能完整的写出一个线性规划的形式来,所以需要用到一些线性化的手段.
两个0-1变量相乘¶
如果说,\(x\)和\(y\)都是0-1变量,目标函数或者约束中存在非线性项\(xy\),可以引入一个新的辅助变量\(z\),并且想方设法建立约束,使得\(z=xy\)
首先,\(z\)是0-1变量,其次,约束关系为:
\[ \begin{cases} z\le x\\ z\le y\\ z\ge x+y-1 \end{cases} \]
这样就将非线性项替换成了线性项
一个连续变量和一个0-1变量相乘¶
不妨设\(x\)是连续变量,依旧是把非线性项的\(xy\)转化为线性项,还是要引入新的变量\(z\),但是,这个\(z\)是一个连续变量,同时引入一个大数M
确保在\(y\)为0的前提下\(z\)也为0:
\[ z\le My \]
确保\(z\)在\(y=1\)的情况下为\(x\):
\[ \begin{cases} z\le x+M(1-y), & \\ z\ge x-M(1-y), & \end{cases} \]
if-else判断变量¶
如果说,存在下面这种形式的变量:
\[ x=\begin{cases} 1, &y\le a \\ 0, &y>a \end{cases} \]
将上述表达式转化为线性约束:
\[ \begin{aligned} &x\le a+M(1-y) \\ &x\ge a-My \end{aligned} \]
如果其中一个不是0-1变量,例如:
\[ x= \begin{cases} g(t), &y\le a \\ f(t), &y>a \end{cases} \]
我们首先要构造一个0-1变量z,满足:
\[ z=\begin{cases} 1, &y\le a \\ 0, &y>a \end{cases} \]
两个变量之间的约束可以通过线性化手段实现,这样子问题就转化为:
\[ x= \begin{cases} g(t), &z=1 \\ f(t), &z=0 \end{cases} \]
也就是:
\[ x=g(t)z+(1-z)f(t) \]
线性规划求解库¶
在python中常常使用pulp库来解决线性规划问题,这个库默认的求解器是CBC,但是这个求解器很慢,可以通过调用gurobi求解器来加速运算(号称最快的求解器).
引入库
建立线性规划问题:
创建变量:
# 连续变量
t_a_ij=pulp.LpVariable.dicts("t_a_ij", (range(m), range(n)), lowBound=0, cat='Continuous')
# 0-1变量
z = pulp.LpVariable.dicts("z", range(n), cat='Binary')
加入约束:
求解问题