运筹学/运输与分配问题

运输与分配问题涉及将来源和工作分配到目的地和机器。我们首先讨论运输问题。

假设一家公司有 m 家工厂生产产品，有 n 个销售点出售产品。将产品从工厂运送到销售点需要一定费用，费用取决于多个因素，并且每个工厂和销售点的选择费用都不一样。每个工厂生产产品的总量是固定的，每个销售点可以存储的总量也是固定的。问题是，应该从每个工厂向每个销售点供应多少产品，才能使总成本最小。

让我们考虑一个例子。

假设一家汽车公司在城市 A、B 和 C 有三家工厂，在 D 和 E 有两个主要的配送中心。下一季这三家工厂的产能分别为 1000 辆、1500 辆和 1200 辆。两个配送中心的季度需求量分别为 2300 辆和 1400 辆。工厂与配送中心之间的运输成本（取决于里程、运输公司等）如下所示。

成本表	配送中心 D	配送中心 E
工厂 A	80	215
工厂 B	100	108
工厂 C	102	68

哪家工厂应该向哪个销售点供应多少辆车，才能使总成本最小？

这个问题可以被表述为一个线性规划模型。

令 $x_{ij}$ 是从源 i 到目的地 j 的运输车辆数量。那么我们的目标是将总成本最小化，总成本为 $80x_{11}+215x_{12}+100x_{21}+108x_{22}+102x_{31}+68x_{32}$。约束条件是由每个工厂要运输的车辆数量和每个中心能够接收的车辆数量决定的。

整个模型是

最小化 z = $80x_{11}+215x_{12}+100x_{21}+108x_{22}+102x_{31}+68x_{32}$

受制于

$x_{11}+x_{12}=1000$;

$x_{21}+x_{22}=1500$;

$x_{31}+x_{32}=1200$;

$x_{11}+x_{21}+x_{31}=2300$;

$x_{12}+x_{22}+x_{32}=1400$;

$x_{ij}\geq 0$ 且为整数，i = 1,2,3, j = 1,2。

现在可以使用单纯形法求解这个问题。下一节将讨论一种方便的程序。