在商业、工程、科学等多个领域，运筹学作为一门应用数学的分支，扮演着至关重要的角色。它通过数学模型和算法，帮助我们解决各种复杂问题，优化资源分配，提高效率。本文将深入解析四个关键习题，帮助读者掌握运筹学的优化策略。
习题一：线性规划问题
问题描述：某工厂生产两种产品A和B，生产A产品需要3小时机器时间和2小时人工时间，生产B产品需要2小时机器时间和1小时人工时间。工厂每天有8小时机器时间和6小时人工时间。产品A的利润为每件100元，产品B的利润为每件80元。问：如何安排生产计划，使得利润最大化？
解题步骤：
建立模型：设生产A产品x件，B产品y件，目标函数为z = 100x + 80y，约束条件为：
- 3x + 2y ≤ 8（机器时间）
- 2x + y ≤ 6（人工时间）
- x ≥ 0，y ≥ 0
绘制可行域：在坐标系中绘制约束条件，找到可行域。
求解最优解：在可行域内，找到目标函数的最大值。通过计算或图解法，可以得出最优解为x = 2，y = 2，此时利润最大为z = 360元。
代码示例：
from scipy.optimize import linprog
c = [-100, -80] # 目标函数系数
A = [[3, 2], [2, 1]] # 约束条件系数矩阵
b = [8, 6] # 约束条件右侧值
x0_bounds = (0, None) # x0的取值范围
x1_bounds = (0, None) # x1的取值范围
res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='highs')
print("最优解：x0 =", res.x[0], "x1 =", res.x[1])
print("最大利润：", -res.fun)
习题二：整数规划问题
问题描述：某物流公司有5辆货车，每辆货车最多可装载货物100吨。现有3个仓库，仓库1有150吨货物，仓库2有200吨货物，仓库3有250吨货物。问：如何安排运输计划，使得总运输成本最低？
解题步骤：
建立模型：设从仓库1运输到仓库2的货物为x1吨，从仓库1运输到仓库3的货物为x2吨，从仓库2运输到仓库3的货物为x3吨。目标函数为z = 10x1 + 15x2 + 20x3，约束条件为：
- x1 + x2 ≤ 150（仓库1货物）
- x1 + x3 ≤ 200（仓库2货物）
- x2 + x3 ≤ 250（仓库3货物）
- x1, x2, x3 ≥ 0
求解最优解：通过整数规划求解器，可以得到最优解为x1 = 100，x2 = 50，x3 = 0，总运输成本为z = 1750元。
习题三：网络流问题
问题描述：某航空公司有3个始发站和3个目的地，航线费用如下表所示。问：如何安排航班，使得总费用最低？
| 始发站 | 目的地1 | 目的地2 | 目的地3 |
|---|---|---|---|
| A | 100 | 150 | 200 |
| B | 120 | 180 | 250 |
| C | 130 | 160 | 220 |
解题步骤：
建立模型：设从始发站A到目的地1的航班为x1，从始发站A到目的地2的航班为x2，从始发站A到目的地3的航班为x3，从始发站B到目的地1的航班为x4，从始发站B到目的地2的航班为x5，从始发站B到目的地3的航班为x6，从始发站C到目的地1的航班为x7，从始发站C到目的地2的航班为x8，从始发站C到目的地3的航班为x9。目标函数为z = 100x1 + 150x2 + 200x3 + 120x4 + 180x5 + 250x6 + 130x7 + 160x8 + 220x9，约束条件为：
- x1 + x4 + x7 ≤ 3（始发站A）
- x2 + x5 + x8 ≤ 3（始发站B）
- x3 + x6 + x9 ≤ 3（始发站C）
- x1, x2, x3, x4, x5, x6, x7, x8, x9 ≥ 0
求解最优解：通过网络流求解器，可以得到最优解为x1 = 3，x2 = 0，x3 = 0，x4 = 0，x5 = 3，x6 = 0，x7 = 0，x8 = 0，x9 = 3，总费用为z = 930元。
习题四：动态规划问题
问题描述：一个机器人从坐标(0, 0)开始，每次可以向右或向下移动一步，直到到达坐标(n, m)。问：有多少种不同的路径？
解题步骤：
建立模型：设f(i, j)表示从(0, 0)到(i, j)的路径数。则f(i, j) = f(i-1, j) + f(i, j-1)，其中i ≥ 1，j ≥ 1。
求解最优解：通过动态规划求解器，可以得到从(0, 0)到(n, m)的路径数为f(n, m)。
代码示例：
def count_paths(n, m):
dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
dp[i][0] = 1
for j in range(1, m + 1):
dp[0][j] = 1
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n][m]
n = 3
m = 3
print("从(0, 0)到({}, {})的路径数为：{}".format(n, m, count_paths(n, m)))
通过以上四个关键习题的解析，相信读者已经对运筹学的优化策略有了更深入的了解。在实际应用中，我们可以根据具体问题选择合适的模型和算法，实现资源的最优配置。