问题描述
之前面对的决策变量都是连续的，但是在实际应用中，很多决策变量都是完全离散的。譬如背包问题(Knapsack problem)中，我们需要在背包大小限制了我们所能携带的物品重量或者体积的情况下，选择出要携带的最有价值的一组物品。
这里的案例问题来自《运筹学》第二版中的NASA资产预算问题。其描述如下：
假设NASA需要在许多互相竞争的航天任务中分配预算，下表显示了这些航天任务的价值评估以及相互关系，预算的单位为十万美元：
| j | 任务 | 阶段1预算 | 阶段2预算 | 阶段3预算 | 阶段4预算 | 阶段5预算 | 价值 | 互斥任务 | 依赖任务 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 通信卫星 | 6 | - | - | - | - | 200 | - | - |
| 2 | 轨道微波 | 2 | 3 | - | - | - | 3 | - | - |
| 3 | 木卫一登录器 | 3 | 5 | - | - | - | 20 | - | - |
| 4 | 2020天王星轨道卫星 | - | - | - | - | 10 | 50 | 5 | 3 |
| 5 | 2010天王星轨道卫星 | - | 5 | 8 | - | - | 70 | 4 | 3 |
| 6 | 水星探测器 | - | - | 1 | 8 | 4 | 20 | - | 3 |
| 7 | 土星探测器 | 1 | 8 | - | - | - | 5 | - | 3 |
| 8 | 红外成像 | - | - | - | 5 | - | 10 | 11 | - |
| 9 | 陆基外星智能探测计划 | 4 | 5 | - | - | - | 200 | 14 | - |
| 10 | 大型轨道结构 | - | 8 | 4 | - | - | 150 | - | - |
| 11 | 彩色成像 | - | - | 2 | 7 | - | 18 | 8 | 2 |
| 12 | 医疗技术 | 5 | 7 | - | - | - | 8 | - | - |
| 13 | 极轨道平台 | - | 1 | 4 | 1 | 1 | 300 | - | - |
| 14 | 对地同步的外星智能探测计划 | - | 4 | 5 | 3 | 3 | 185 | 9 | - |
| 预算约束 | 10 | 12 | 14 | 14 | 14 |
需要在给定的预算约束下，选择价值最大的一组项目。
决策变量
问题的决策变量比较简单，我们需要挑选的项目，可以表达为：
其中。
目标函数
这里是一个最大问题，可以表达为：
约束条件
此问题中约束条件分为三组：预算约束、互斥约束和依赖约束。
预算约束即每个阶段中选中的任务预算总和不能超过约束：
互斥约束即两个变量至多选择一个，可以用的形式来表达：
依赖约束即选择是选择
的前提，可以用
的形式来表达：
编程求解
在明确了问题之后，编程求解是相对容易的。这里需要注意的是我们的变量因为是0-1变量，因此在设置变量类型时，需要使用LpBinary而非之前使用的LpContinuous。
from pulp import *
# 1. 建立问题
model = LpProblem("NASA资产预算问题", LpMaximize)
# 2. 建立变量
tasks = ["通信卫星", "轨道微波", "木卫一登陆器", "2020天王星轨道卫星", "2010天王星轨道卫星", "水星探测器", "土星探测器",
"红外成像", "陆基外星智能探测计划", "大型轨道结构", "彩色成像", "医疗技术", "极轨道平台", "对地同步的外星智能探测计划" ]
taskVar = LpVariable.dicts("Tasks", tasks, lowBound=0, cat=LpBinary)
# 3. 设置目标函数
values = {"通信卫星": 200,
"轨道微波": 3,
"木卫一登陆器": 20,
"2020天王星轨道卫星": 50,
"2010天王星轨道卫星": 70,
"水星探测器": 20,
"土星探测器": 5,
"红外成像": 10,
"陆基外星智能探测计划": 200,
"大型轨道结构": 150,
"彩色成像": 18,
"医疗技术": 8,
"极轨道平台": 300,
"对地同步的外星智能探测计划": 185}
model += lpSum([values[item] * taskVar[item] for item in tasks]), "项目总价值"
# 4. 施加约束
stage1 = {"通信卫星": 6,
"轨道微波": 2,
"木卫一登陆器": 3,
"2020天王星轨道卫星": 0,
"2010天王星轨道卫星": 0,
"水星探测器": 0,
"土星探测器": 1,
"红外成像": 0,
"陆基外星智能探测计划": 4,
"大型轨道结构": 0,
"彩色成像": 0,
"医疗技术": 5,
"极轨道平台": 0,
"对地同步的外星智能探测计划": 0}
stage2 = {"通信卫星": 0,
"轨道微波": 3,
"木卫一登陆器": 5,
"2020天王星轨道卫星": 0,
"2010天王星轨道卫星": 5,
"水星探测器": 0,
"土星探测器": 8,
"红外成像": 0,
"陆基外星智能探测计划": 5,
"大型轨道结构": 8,
"彩色成像": 0,
"医疗技术": 7,
"极轨道平台": 1,
"对地同步的外星智能探测计划": 4}
stage3 = {"通信卫星": 0,
"轨道微波": 0,
"木卫一登陆器": 0,
"2020天王星轨道卫星": 0,
"2010天王星轨道卫星": 8,
"水星探测器": 1,
"土星探测器": 0,
"红外成像": 0,
"陆基外星智能探测计划": 0,
"大型轨道结构": 4,
"彩色成像": 2,
"医疗技术": 0,
"极轨道平台": 4,
"对地同步的外星智能探测计划": 5}
stage4 = {"通信卫星": 0,
"轨道微波": 0,
"木卫一登陆器": 0,
"2020天王星轨道卫星": 0,
"2010天王星轨道卫星": 0,
"水星探测器": 8,
"土星探测器": 0,
"红外成像": 5,
"陆基外星智能探测计划": 0,
"大型轨道结构": 0,
"彩色成像": 7,
"医疗技术": 0,
"极轨道平台": 1,
"对地同步的外星智能探测计划": 3}
stage5 = {"通信卫星": 0,
"轨道微波": 0,
"木卫一登陆器": 0,
"2020天王星轨道卫星": 10,
"2010天王星轨道卫星": 0,
"水星探测器": 4,
"土星探测器": 0,
"红外成像": 0,
"陆基外星智能探测计划": 0,
"大型轨道结构": 0,
"彩色成像": 0,
"医疗技术": 0,
"极轨道平台": 1,
"对地同步的外星智能探测计划": 3}
model += lpSum([stage1[item]*taskVar[item] for item in tasks]) <= 10, "阶段1"
model += lpSum([stage2[item]*taskVar[item] for item in tasks]) <= 12, "阶段2"
model += lpSum([stage3[item]*taskVar[item] for item in tasks]) <= 14, "阶段3"
model += lpSum([stage4[item]*taskVar[item] for item in tasks]) <= 14, "阶段4"
model += lpSum([stage5[item]*taskVar[item] for item in tasks]) <= 14, "阶段5"
model += taskVar['2020天王星轨道卫星'] + taskVar['2010天王星轨道卫星'] <= 1, "4与5互斥"
model += taskVar['红外成像'] + taskVar['彩色成像'] <= 1, "8与11互斥"
model += taskVar['2020天王星轨道卫星'] <= taskVar['木卫一登陆器'] , "4依赖3"
model += taskVar['2010天王星轨道卫星'] <= taskVar['木卫一登陆器'] , "5依赖3"
model += taskVar['水星探测器'] <= taskVar['木卫一登陆器'] , "6依赖3"
model += taskVar['土星探测器'] <= taskVar['木卫一登陆器'] , "7依赖3"
model += taskVar['彩色成像'] <= taskVar['轨道微波'] , "11依赖2"
# 5. 求解
model.solve()
# 6. 打印结果
print(model)
print("求解状态:", LpStatus[model.status])
for v in model.variables():
print(v.name, "=", v.varValue)
print("最优总价值 = ", value(model.objective))
结果如下：
求解状态: Optimal
Tasks_2010天王星轨道卫星 = 0.0
Tasks_2020天王星轨道卫星 = 0.0
Tasks_医疗技术 = 0.0
Tasks_土星探测器 = 0.0
Tasks_大型轨道结构 = 0.0
Tasks_对地同步的外星智能探测计划 = 1.0
Tasks_彩色成像 = 0.0
Tasks_木卫一登陆器 = 0.0
Tasks_极轨道平台 = 1.0
Tasks_水星探测器 = 0.0
Tasks_红外成像 = 1.0
Tasks_轨道微波 = 0.0
Tasks_通信卫星 = 1.0
Tasks_陆基外星智能探测计划 = 1.0
最优总价值 = 895.0
因此最后的方案是选择14 - 对地同步的外星智能探测计划、13 - 极轨道平台、8 - 红外成像、1 - 通信卫星和9 - 陆基外星智能探测计划。在5个阶段的预算分别为10、10、9、9、4。
