如何用二元变量和月度预算约束来构建项目选择问题？

适用条件

• 每个项目都有相关的成本和净回报。
• 预算约束适用于特定的时间段（例如月份）。
• 决策是二元的（选择或不选择）。

理解与推导

1. 为每个项目 $i$ 定义二元变量 $X_i \in \{0, 1\}$。
2. 识别每个项目的净回报。
3. 构建目标函数：最大化 $\sum (\text{return}_i \cdot X_i)$。
4. 识别每个项目在每个时间段内的成本。
5. 构建预算约束：对于每个时间段 $t$，$\sum (\text{cost}_{i,t} \cdot X_i) \le \text{Budget}_t$。
6. 指定域限制 $X_i \in \{0, 1\}$。

例子

对于四个回报分别为 217、125、88 和 109 的项目，目标是最大化 $217X_1 + 125X_2 + 88X_3 + 109X_4$。一月预算约束为 $58X_1 + 44X_2 + 26X_3 + 23X_4 \le 120$。二月约束为 $25X_1 + 29X_2 + 13X_3 + 17X_4 \le 80$。三月约束为 $43X_1 + 25X_2 + 23X_3 + 29X_4 \le 95$。

容易误解的地方

• 假设 $X_i$ 可以取分数值（例如选择半个项目）。
• 忘记包含二元约束 $X_i \in \{0, 1\}$。
• 混淆目标函数系数（回报）与约束系数（成本）。

观看对应讲解

继续追问

• 给定项目选择示例的最优解是什么？
• 为什么在项目选择中使用二元变量而不是连续变量？
• 固定成本问题与项目选择问题有何不同？