如何写线性规划

考虑下面的 运输问题。

例子 link

有三个仓库 S1, S2, S3，分别有粮食100吨，200吨，300吨。有四个客户D1, D2, D3, D4，他们对粮食的需求量分别是 120吨，60吨，270吨，150吨。

现在要把粮食运给客户，并且满足客户对粮食的需求量。运输过程有运输成本。运输成本等于单位成本乘以运输量。单位成本取决于从哪个仓库发货，以及运给哪个客户。

单位成本用下表描述。

例如第二行第三列，代表从 A2 运到 D3 的单位运输成本是 300 元/吨。

现在的问题是，要计算每个仓库到每个客户的运输量，使得总运输成本最低。

换句话说，需要填下面这张表。

最右边一列代表仓库 A1, A2, A3 的供给量，因此仓库的总运输量不得超过它的供给量。最下面的一行代表客户 D1, D2, D3, D4 的需求量，因此每个客户收到来自所有仓库的总供给量不得低于它的需求量。

接下来我们把它写成线性规划的形式。

步骤 link

1. 定义指标集合（Index Set）

指标的作用是主要为了简化记号。

定义两个指标

• $i$ - 代表仓库， $i=1, 2, 3$
• $j$ - 代表客户，$j = 1, 2, 3, 4$

2. 定义参数（Parameters）

参数是问题的输入，或者说常量。在这个例子中，输入参数是供给量、需求量、单位运输成本。定义三个记号。

• $s_i$ – 仓库 $i$ 的供给量
• $d_j$ – 仓库 $j$ 的需求量
• $c_{ij}$ – 仓库 $i$ 到客户 $j$ 的单位运输成本

3. 定义决策变量（Decision Variables）

决策变量是算法的输出，也就是要计算的变量。在这个例子中，需要计算每个仓库运给每个客户多少粮食。定义如下记号。

• $x_{ij}$ – 仓库 $i$ 运给客户 $j$ 的粮食重量

4. 描述优化目标（Objective）

根据前面定义的记号，用数学语言描述优化目标。这个例子的目标是最小化总运费。

$$ \min~ \sum_{i=1}^3\sum_{j=1}^4 c_{ij}x_{ij} $$

5. 描述约束条件（Constraints）

用等式或不等式描述约束条件。在这个例子中，有两个主要的约束条件。.

• 第一个条件，每个仓库运出去的粮食总量不超过它的供给量。

$$ \sum_{j=1}^4 x_{ij} \leq s_i,\quad i=1, 2, 3 $$

• 第二个条件，每个客户收到的粮食总量不低于它的需求量。

$$ \sum_{i=1}^3 x_{ij} \leq d_j,\quad j=1, 2, 3, 4 $$

此外，$x_{i,j} \geq 0$。

结果 link

综上，得到如下结果。