练习1

某公司在如下3个地方生产商品，并运送到另外7个地点进行销售，请问该公司如何配送运输的成本最低？

import numpy as np
from scipy.optimize import linprog

# 定义成本矩阵，inf表示无限大，表示不可运输
cost_matrix = [
    [np.inf, 14, 11, np.inf, 16, np.inf, 8],
    [27, 8, 12, 9, 26, np.inf, 17],
    [24, np.inf, np.inf, 13, 28, 99, np.inf]
]

# 将inf替换为一个足够大的数字，以避免数值问题
large_number = 1e6
cost_matrix = np.where(np.isinf(cost_matrix), large_number, cost_matrix)

# 将成本矩阵展平成一维数组
c = cost_matrix.flatten()

# 定义供应量和需求量
supply = [1400, 2600, 2900]
demand = [900, 1200, 600, 400, 1700, 1100, 1000]

# 构建约束矩阵
num_supply = len(supply)
num_demand = len(demand)

A_eq = []
b_eq = []

# 供应量约束
for i in range(num_supply):
    constraint = [0] * (num_supply * num_demand)
    for j in range(num_demand):
        constraint[i * num_demand + j] = 1
    A_eq.append(constraint)
    b_eq.append(supply[i])

# 需求量约束
for j in range(num_demand):
    constraint = [0] * (num_supply * num_demand)
    for i in range(num_supply):
        constraint[i * num_demand + j] = 1
    A_eq.append(constraint)
    b_eq.append(demand[j])

A_eq = np.array(A_eq)
b_eq = np.array(b_eq)

# 定义变量边界
x_bounds = [(0, None)] * (num_supply * num_demand)

# 求解线性规划问题
result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=x_bounds, method='highs')

# 输出结果
if result.success:
    print("Optimal value:", result.fun)
    x_values = result.x.reshape((num_supply, num_demand))
    print("x values:")
    print(x_values)
else:
    print("No solution found")

Optimal value: 200500.0
x values:
[[   0.    0.    0.    0.  800.    0.  600.]
 [   0. 1200.  600.  400.    0.    0.  400.]
 [ 900.    0.    0.    0.  900. 1100.    0.]]

练习2

如下表的运输问题中总需要量超过总供应量(方框中的数字是单位运费)。假定对销地\(B_1\)、\(B_2\)和\(B_3\)未满足需要量的单位罚款成本是5、3和2，试建立该问题的数学模型，并探讨能否将其转变为产销平衡运输问题。

2.1 数学模型

设 \(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]$$

2.2 转化为平衡型运输问题

为将其转化为平衡型运输问题，定义一个虚拟产地 \(A_4\)​，其供应量为未满足的总需求量，即 \(\sum d_j - \sum s_i = 145 - 105 = 40\)。
新增的运费矩阵行对应的是虚拟产地 \(A_4\)​​，其到各个销地 \(B_j\)​ 的运费为对应的罚款成本。

新的运费矩阵为：

新的供应量向量\(s\) 为：

需求量向量保持不变：

2.3 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.]]

练习3

在下表不平衡运输问题中(方框中的数字是单位运费)，若产地 有单位物质未运出，就要发生存储成本。假定在产地 、 和 的单位存储成本是5、4和3，又假定产地 的供应量必须全部运出，试建立该问题的数学模型，并探讨能否将其转变为产销平衡运输问题。

练习4

某厂月底安排某一产品在下月四周生产计划。估计每件产品在第一周与第二周的生产成本为150元，后两周的生产成本为170元，各周产品需求量分别为700件、800件、1000件和1200件。工厂每周至多生产产品900件，在第二周、第三周可加班生产。加班生产时每周可增产三百件，但生产成本每件需增加30元。过剩产品的储存费为每周15元。安排生产，使总成本最小，建立运输模型。

需求总量：700 + 800 + 1000 + 1200 = 3700
最高需求量：900 + 900 + 300 + 900 + 300 + 900 = 4200
需求缺少：4200 - 3700 = 500

练习5

有甲、乙、丙3个城市，每年分别需要煤炭320、250、350万吨，由A、B两个煤矿负责供应。已知煤矿年产量A为400万吨；B为450万吨，从两煤矿至各城市煤炭运价(元/吨)见表3-51。由于需求大于产量，经协商平均，甲城市必要时可少供0～30万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费为最低的调运方案。

练习6

某餐馆承办㝠会, 每晚连续举行, 共举行五次。宣会上需用特殊的餐巾, 根据参加的人数, 预计每晚的需要量为：第一天 1000 条，第二天700条，第三天 800 条，第四工 1200 条，第五工 1500 条，五天之后，所有的餐巾作废。㝠会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐市需要1元的费周, 送洗时可选择两种方式:快洗仅需要一天时间, 每条洗涤费用为 0.2 元, 慢洗需要两天时间, 每条洗涤费用 0.1 元。问：如何安排,可使总费用最低?

建立模型

设 \(x_j\) 一第 \(j\) 天使用新毛巾的数量; \(y_{i j}\) 一第 \(i\) 天送第 \(j\) 天使用快洗餐巾的数量; \(\mathrm{z}_{\mathrm{ij}}\) 一第 \(\mathrm{i}\) 天送第 \(\mathrm{j}\) 天使用慢洗餐巾的数量;

产销平衡表
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline 供应需求 & I & II & III & IV & V & VI & 产量 \
\hline 新 购 & 1 & 1 & 1 & 1 & 1 & 0 & 5200 \
\hline 第一天 & M & 0.2 & 0.1 & 0.1 & 0.1 & 0 & 1000 \
\hline 第二天 & M & M & 0.2 & 0.1 & 0.1 & 0 & 700 \
\hline 第三天 & M & M & M & 0.2 & 0.1 & 0 & 800 \
\hline 第四天 & M & M & M & 0.2 & 0.1 & 0 & 1200 \
\hline 销 量 & 1000 & 700 & 800 & 1200 & 1500 & 3700 & \
\hline
\end{tabular}

练习7

例一：某工厂按合同规定必须于当年的每个季度末分别提供 \(10 、 15 、 25 、 20\)台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货, 每台每积压一个季度需要存储维护费
\begin{tabular}{c|c|c}
\hline \begin{tabular}{c}
季 \
度
\end{tabular} & \begin{tabular}{c}
生产能力 \
(台)
\end{tabular} & \begin{tabular}{c}
单位成本 \
(万元/台)
\end{tabular} \
\hline I & 25 & 10.8 \
II & 35 & 11.1 \
III & 30 & 11.0 \
IV & 10 & 11.3 \
\hline
\end{tabular}
用 0.15 万元。要求在完成合同的情况下, 做出使全年生产费用最小的决策。

模型:
设 \(x_{i j}\) 第 \(i\) 季度生产, 用于第 \(\mathrm{j}\) 季度交货的数量。
obj. \(\quad \min \quad z=\sum_{i=1 j=1}^4 \sum_{i j}^4 c_{i j}\)

单位费用表:
\begin{tabular}{|c|c|c|c|c|}
\hline & & & & : 万元 \
\hline 供应 需求 & I & II & III & IV \
\hline I & 10.8 & 10.95 & 11.10 & 11.25 \
\hline II & M & 11.10 & 11.25 & 11.40 \
\hline III & M & M & 11.00 & 11.15 \
\hline IV & M & M & M & 11.30 \
\hline
\end{tabular}

练习8

分配甲、乙、丙、丁4个人去完成A、B、C、D、E 5项任务，每个人完成各项任务的时间见表3-52。由于任务数多于人数，故考虑：
(1) 任务E必须完成，其他4项中可任选3项完成；
(2) 其中有一人完成两项，其他每人完成一项。
试分别确定最优分配方案，使完成任务的总时间为最少。