【公式求解】线性规划(5)

例:已知某商品6个仓库的存货量,8个客户对该商品的需求量,单位商品运价如下表所示。试确定6个仓库到8个客户的商品调运数量,使总的运输费用最小。

仓库/客户 V1 V2 V3 V4 V5 V6 V7 V8 存货量
W1 6 2 6 7 4 2 5 9 60
W2 4 9 5 3 8 5 8 2 55
W3 5 2 1 9 7 4 3 3 51
W4 7 6 7 3 9 2 7 1 43
W5 2 3 9 5 7 2 6 5 41
W6 5 5 2 2 8 1 4 3 52
需求量 35 37 22 32 41 32 43 38

解:设$ x_{ij} $表示第i个仓库运到第j个客户的商品数量,$ c_{ij} $表示第i个仓库到第j个客户的单位运价,$ d_{j} $表示第j个客户的需求量,$ e_{i} $表示第i个仓库的存货量,建立如下的线性规划模型
$ min \quad z = \sum\limits_{i=1}^{6}\sum\limits_{j=1}^{8}c_{ij}x_{ij} $
$ s.t. \begin{cases}
\sum\limits_{j=1}^{8}x_{ij} \leq e_{i} \\
\sum\limits_{i=1}^{6}x_{ij} = d_{j} \\
x_{ij} \geq 0
\end{cases}
$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import numpy as np
import cvxpy as cp
import pandas as pd

o = np.array([
6,2,6,7,4,2,5,9,60,
4,9,5,3,8,5,8,2,55,
5,2,1,9,7,4,3,3,51,
7,6,7,3,9,2,7,1,43,
2,3,9,5,7,2,6,5,41,
5,5,2,2,8,1,4,3,52,
35,37,22,32,41,32,43,38,0
]).reshape(7,9)

# print(o)
c = o[:-1,:-1]

d = o[-1,:-1].reshape(1,-1)
e = o[:-1,-1].reshape(-1,1)

x = cp.Variable((6,8))
obj = cp.Minimize(cp.sum(cp.multiply(c,x))) # 构造目标函数

con = [cp.sum(x,axis=1,keepdims=True)<=e,
cp.sum(x,axis=0,keepdims=True)==d,
x>=0
] # 构造约束条件

prob = cp.Problem(obj, con) # 构造模型

prob.solve(solver='GLPK_MI', verbose=True) # 求解模型

print('最优解为:', x.value)
print('最优值为:', prob.value)
0%