算法问题的线性规划建模

1 食谱问题（Diet Problem）

几种食物的每单位所含营养物质及其价格如下表所示，若每天需要2000千卡能量、55克蛋白质和800毫克钙，请问如何构造一个食物的组合，使得满足每天的营养物质需求且耗费金钱最少。

解析： 线性规划问题的最基本形式。可设购买每种食物$x_1,x_2,x_3,x_4$单位，可得线性规划方程： $$ min\; z=3x_1 + 9x_2 + 20x_3 + 19x_4 \\ \begin{align*} s.t.\; 110x_1 + 160x_2 + 420x_3 + 260x_4 &≥ 2000 \\ 4x_1 + 8x_2 + 4x_3 + 14x_4 &≥ 55 \\ 2x_1 + 285x_2 + 22x_3 + 80x_4 &≥ 800 \\ x_1 , x_2 , x_3 , x_4 &≥ 0 \end{align*} $$ 上式可简写为： $$ min\; z=c^Tx \\ \begin{align*} s.t.\; Ax&=b \\ x&\geq 0 \end{align*} $$

2 最大流问题（Maximum Flow Problem）

输入： 一个有向图$G<V,E>$，每条边$e=(u,v)$与容量$C(u,v)$相对应，源节点为$s$，目标节点为$t$。
输出： 求解每条边$e=(u,v)$对应的流量$0\leq f(u,v)\leq C(u,v)$，使到达目标节点的总流量$\sum _{u,(s,u)\in E}f(u,v)$最大。
解析： 对最大流问题进行线性规划建模，可将总流量最大设为线性规划的优化目标。线性规划的约束包括两部分：

1. 进入某个节点的流量之和等于离开某个节点的流量之和；
2. 每条边的流量不小于零且不大于最大容量。

可得线性规划方程： $$ max\; z=\sum _{v,(s,v)\in E}f(s,v) \\ \begin{align*} s.t.\; \sum _{u,(u,v)\in E}f(u,v)-\sum _{w,(v,w)\in E}f(v,w)&=0,&v\in V-s \\ f(u,v)&\geq 0,&(u,v)\in E \\ f(u,v)&\leq C(u,v),&(u,v)\in E \end{align*} $$

3 最小费用流问题（Minimum Cost Flow Problem）

输入： 一个有向图$G<V,E>$，每条边$e=(u,v)$与容量$C(u,v)$、每单位流量花费$a(u,v)$相对应，流量总量为$d$，源节点为$s$，目标节点为$t$。
输出： 求解每条边$e=(u,v)$对应的流量$0\leq f(u,v)\leq C(u,v)$，使到达目标节点的总流量为$d$，且总花费$\sum _{(u,v)\in E}a(u,v)f(u,v)$最小。
解析： 对最小费用流问题进行线性规划建模，可将费用最小设为线性规划的优化目标。线性规划的约束包括三部分：

1. 进入某个节点的流量之和等于离开某个节点的流量之和；
2. 每条边的流量不小于零且不大于最大容量；
3. 总流量为$d$。

可得线性规划方程： $$ min\; z=\sum _{(u,v)\in E}a(u,v)f(u,v) \\ \begin{align*} s.t.\; \sum _{u,(u,v)\in E}f(u,v)-\sum _{w,(v,w)\in E}f(v,w)&=0,&v\in V-s \\ f(u,v)&\geq 0,&(u,v)\in E \\ f(u,v)&\leq C(u,v),&(u,v)\in E \\ \sum _{v,(s,v)\in E}f(s,v)&=d \end{align*} $$

4 多物品流问题（Multi Commodity Flow Problem）

输入： 一个有向图$G<V,E>$，每条边$e=(u,v)$对应容量$C_e$。共有$k$个物品，对第$i$个物品，$s_i,t_i,d_i$分别表示其起点、终点和总量。
输出： 满足多物品流量约束、边容量约束的一个可行解。
解析： 由于只需要求一个可行解，因此优化目标可直接设为$max;z=0$。线性规划的约束包括三部分：

1. 进入某个节点的各物品流量之和等于离开某个节点的各物品流量之和；
2. 每条边的各物品流量不小于零且不大于最大容量；
3. 对于物品$i$，总流量为$d_i$。

设每条边$e$流经的第$i$个物品的流量为$f_i(u,v)$，可得线性规划方程：

$$ max\; z=0 \\ \begin{align*} s.t.\; \sum _{u,(u,v)\in E}f_i(u,v)-\sum _{w,(v,w)\in E}f_i(v,w)&=0,&v\in V-s \\ f_i(u,v)&\geq 0,&(u,v)\in E \\ \sum _{i=1}^k f_i(u,v)&\leq C(u,v),&(u,v)\in E \\ \sum _{v,(s_i,v)\in E}f(s_i,v)&=d_i \end{align*} $$

线性规划是已知的该问题唯一多项式复杂度的解法。

5 SAT问题

SAT问题的介绍可参考此文章：SAT问题简介

概括而言，SAT问题的求解是为一个n元合取范式的变量进行真值指派，使得该式为真。

输入： 一个有m个子句的n元合取范式。
输出： 一组使该式为真的真值指派。

例题：$\Phi=(x_1\vee \neg x_2 \vee x_3)\wedge (\neg x_1\vee x_2\vee \neg x_3)\wedge (x_1\vee x_2 \vee \neg x_3)$
解析： 设线性规划的优化目标为最大化为真的子句数量，设指示第$j$个子句是否为真的变量为$c_j$，可得线性规划方程： $$ \begin{align*} max\;z=\;& c_1 &+&c_2 &+c_3 & \\ s.t.\;& x_1 &+&(1-x_2) &+x_3 &\geq c_1 \\ &(1-x_1)&+&x_2 &+(1-x_3)&\geq c_2 \\ &x_1&+&x_2&+(1-x_3)&\geq c_3 \\ &x_1,&&x_2,&x_3&=0/1 \\ &c_1,&&c_2,&c_3&=0/1 \end{align*} $$ 上式中，约束的左侧表示为真的文字的数量，当至少存在一个为真时，该子句的真值便允许取值为1。当且仅当$z=3$时原问题有解。