练习1
如下表的运输问题中总需要量超过总供应量(方框中的数字是单位运费)。假定对销地\(B_1\)、\(B_2\)和\(B_3\)未满足需要量的单位罚款成本是5、3和2，试建立该问题的数学模型，并探讨能否将其转变为产销平衡运输问题。
| 产地\销地 | B1 | B2 | B3 | 供 应 量 |
|---|---|---|---|---|
| A1 | 5 | 1 | 7 | 10 |
| A2 | 6 | 4 | 6 | 80 |
| A3 | 3 | 2 | 5 | 15 |
| 需求量 | 75 | 20 | 50 | 145\105 |
数学模型
设 \(x_{ij}\) 为从产地 \(A_i\) 运输到销地 $B_jBj 的货物量。
- 目标函数
最小化总运输成本和罚款成本： $$\min \sum_{i=1}^{3} \sum_{j=1}^{3} c_{ij} x_{ij} + \sum_{j=1}^{3} p_j y_j$$其中，
\(c_{ij}\) 是从 \(A_i\) 到 \(B_j\) 的单位运费；\(p_j\) 是销地 \(B_j\) 的单位罚款成本；\(y_j\) 是销地 \(B_j\) 的未满足需要量。
- 约束条件
供应量约束： \(\sum\_{j=1}^{3} x_{ij} \leq s_i \quad \forall i = 1, 2, 3\)
需求量约束（包括未满足的部分）： \(\sum_{i=1}^{3} x_{ij} + y_j = d_j \quad \forall j = 1, 2, 3\)
非负性约束： \(x_{ij} \geq 0 \quad \forall i = 1, 2, 3；y_j \geq 0 \quad \forall j = 1, 2, 3\) - 参数
单位运价\(c_{ij}:\)
供应量 \(s_i\)：
$$ s = [10, 80, 15]$$
需求量\(d_j\)：
单位罚款成本\(p_j\)：
$$p = [5, 3, 2]$$
转化为平衡型运输问题
为将其转化为平衡型运输问题，定义一个虚拟产地 \(A_4\)，其供应量为未满足的总需求量，即 \(\sum d_j - \sum s_i = 145 - 105 = 40\)。
新增的运费矩阵行对应的是虚拟产地 \(A_4\)，其到各个销地 \(B_j\) 的运费为对应的罚款成本。
新的运费矩阵为：
\[\begin{matrix} & B_1 & B_2 & B_3 \\ A_1 & 5 & 1 & 7 \\ A_2 & 6 & 4 & 6 \\ A_3 & 3 & 2 & 5 \\ A_4 & 5 & 3 & 2 \\ \end{matrix} \]新的供应量向量\(s\) 为：
\[s = [10, 80, 15, 40] \]需求量向量保持不变：
\[d = [75, 20, 50] \]Python计算程序
import numpy as np
from scipy.optimize import linprog
# 定义参数
c = [5, 1, 7, 6, 4, 6, 3, 2, 5, 5, 3, 2]
s = [10, 80, 15, 40]
d = [75, 20, 50]
# 构建目标函数系数向量
c = np.array(c)
# 构建约束矩阵
A_eq = [
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1]
]
A_eq = np.array(A_eq)
b_eq = np.array(s + d)
# 定义边界
x_bounds = [(0, None) for _ in range(len(c))]
# 求解线性规划问题
result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=x_bounds, method='highs')
# 输出结果
if result.success:
print("Optimal value:", result.fun)
print("x values:", result.x.reshape(4, 3))
else:
print("No solution found")
Optimal value: 595.0
x values:
[[ 0. 10. 0.]
[60. 10. 10.]
[15. 0. 0.]
[ 0. 0. 40.]]
练习2
在下表不平衡运输问题中(方框中的数字是单位运费)，若产地 有单位物质未运出，就要发生存储成本。假定在产地 、 和 的单位存储成本是5、4和3，又假定产地 的供应量必须全部运出，试建立该问题的数学模型，并探讨能否将其转变为产销平衡运输问题。
| 产地\销地 | B1 | B2 | B3 | 供 应 量 |
|---|---|---|---|---|
| A1 | 1 | 2 | 1 | 20 |
| A2 | 0 | 4 | 5 | 40 |
| A3 | 2 | 3 | 3 | 30 |
| 需求量 | 30 | 20 | 20 | 70\90 |
练习3
有甲、乙、丙3个城市，每年分别需要煤炭320、250、350万吨，由A、B两个煤矿负责供应。已知煤矿年产量A为400万吨；B为450万吨，从两煤矿至各城市煤炭运价(元/吨)见表3-51。由于需求大于产量，经协商平均，甲城市必要时可少供0～30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费为最低的调运方案。
| 产地\销地 | 甲 | 乙 | 丙 | 供 应 量 |
|---|---|---|---|---|
| A | 15 | 18 | 22 | |
| B | 21 | 25 | 16 | |
| 需求量 | 30 | 20 | 20 | 70\90 |
练习
分配甲、乙、丙、丁4个人去完成A、B、C、D、E 5项任务，每个人完成各项任务的时间见表3-52。由于任务数多于人数，故考虑：
(1) 任务E必须完成，其他4项中可任选3项完成；
(2) 其中有一人完成两项，其他每人完成一项。
试分别确定最优分配方案，使完成任务的总时间为最少。
| 人员\任务 | A | B | C | D | E |
|---|---|---|---|---|---|
| 甲 | 25 | 29 | 31 | 42 | 37 |
| 乙 | 39 | 38 | 26 | 20 | 33 |
| 丙 | 34 | 27 | 28 | 40 | 32 |
| 丁 | 24 | 42 | 36 | 23 | 45 |