運籌學/運輸與分配問題

運輸與分配問題涉及將來源和工作分配到目的地和機器。我們首先討論運輸問題。

假設一家公司有 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。

現在可以使用單純形法求解這個問題。下一節將討論一種方便的程式。