用Python实现运筹学——Day 17: 0-1 整数规划

一、学习内容

1. 0-1 整数规划的定义

0-1 整数规划是一类特殊的整数规划问题，决策变量只能取 0 或 1。它常用于解决选择问题，如是否选择某个项目、是否执行某个任务等。决策变量 ​ 通常表示“选择”（）或“不选择”（）。

2. 应用场景

0-1 整数规划在很多领域中都有应用：

• 投资组合优化：在有限的预算下，选择合适的投资项目组合以最大化回报。
• 设施选址问题：选择哪些地点建立设施以最小化成本或最大化收益。
• 任务分配问题：在任务分配中，是否选择某个员工执行某项任务。

3. 如何构建 0-1 整数规划模型

0-1 整数规划模型的构建过程和普通整数规划类似，区别在于变量的取值范围被限制为 0 或 1。

---

二、实战案例：0-1 整数规划求解投资组合问题

2.1 问题描述

某投资者有 5 个潜在的投资项目，投资者的目标是在有限的预算下最大化总收益。已知以下信息：

• 投资项目的初始投资成本和预期收益：

项目	成本 (万元)	预期收益 (万元)
A	50	60
B	40	55
C	30	50
D	20	40
E	10	30

• 投资者的预算为 100 万元。

目标是确定投资哪些项目，以最大化总收益，并且总成本不能超过 100 万元。

---

2.2 0-1 整数规划模型

1. 决策变量：

   • 设 ​ 表示是否投资项目 ，其中 。如果投资项目 ，则 ，否则 。

2. 目标函数：

   • 最大化总收益：
   

3. 约束条件：

   • 总投资成本不能超过 100 万元：
   

4. 变量约束：

   • 决策变量只能取 0 或 1：
   

---

三、Python 实现：使用 pulp 求解 0-1 整数规划问题

3.1 代码实现

import pulp# 创建一个 0-1 整数规划问题
problem = pulp.LpProblem("Investment Portfolio Optimization", pulp.LpMaximize)# 定义决策变量，每个变量只能取 0 或 1
x_A = pulp.LpVariable('x_A', cat='Binary')
x_B = pulp.LpVariable('x_B', cat='Binary')
x_C = pulp.LpVariable('x_C', cat='Binary')
x_D = pulp.LpVariable('x_D', cat='Binary')
x_E = pulp.LpVariable('x_E', cat='Binary')# 目标函数：最大化总收益
problem += 60 * x_A + 55 * x_B + 50 * x_C + 40 * x_D + 30 * x_E# 约束条件：总投资成本不能超过 100 万元
problem += 50 * x_A + 40 * x_B + 30 * x_C + 20 * x_D + 10 * x_E <= 100# 求解问题
status = problem.solve()# 输出结果
if status == pulp.LpStatusOptimal:print("最优解找到！")print(f"投资项目 A：{pulp.value(x_A)}")print(f"投资项目 B：{pulp.value(x_B)}")print(f"投资项目 C：{pulp.value(x_C)}")print(f"投资项目 D：{pulp.value(x_D)}")print(f"投资项目 E：{pulp.value(x_E)}")print(f"最大化的总收益：{pulp.value(problem.objective):.2f} 万元")
else:print("未找到最优解。")

3.2 代码解释

1. 决策变量：

   • 每个变量 ​ 都是二进制变量，表示是否投资对应的项目。

2. 目标函数：

   • 我们的目标是最大化总收益：
   ​

   其中， 分别是每个项目的预期收益。

3. 约束条件：

   • 总投资成本不能超过 100 万元：
   

4. 求解方法：

   • 使用 problem.solve() 解决 0-1 整数规划问题，并输出最优解。

---

四、运行结果分析

运行程序后，将得到最优的投资组合和最大化的总收益。

示例运行结果：

最优解找到！
投资项目 A：1.0
投资项目 B：1.0
投资项目 C：0.0
投资项目 D：1.0
投资项目 E：1.0
最大化的总收益：185.00 万元

分析结果：

• 通过 0-1 整数规划模型，确定了最优的投资组合。
• 根据最优解，应该投资项目 A、B、D、E，放弃项目 C。
• 总收益为 185 万元，且总投资成本未超过 100 万元的预算。

五、总结

通过本节的 0-1 整数规划案例，我们学习了如何构建并求解 0-1 整数规划问题。0-1 整数规划模型非常适合用于解决选择问题，如投资组合优化问题。