cuopt-numerical-optimization-formulation

数值优化建模

介绍如何从问题描述出发，在 LP、MILP 和 QP 中构建清晰模型的概念与工作流。此处不涉及 API 代码。

什么是 LP / MILP / QP

• LP：线性目标函数、线性约束、连续变量。
• MILP：与 LP 相同，但包含一些整数或二元变量（例如排程、设施选址、选择）。
• QP：二次目标函数（例如 x²、x·y 项——投资组合方差、最小二乘），线性约束。cuOpt 目前对 QP 的支持处于 beta 阶段。

识别问题类型

属性	LP	MILP	QP
目标函数	线性	线性	二次（xᵀQx + cᵀx）
约束	线性	线性	线性（不支持二次约束）
变量	连续	混合：连续 + 整数/二元	连续
方向	min 或 max	min 或 max	仅限最小化（最大化时取负）

如果目标函数完全是线性的，优先使用 LP/MILP——不要人为引入二次项。如果有任何变量是整数或二元变量，那么无论其他情况如何，该问题都属于 MILP。

建模必需问题

如果以下事项尚不明确，请询问用户：

1. 决策变量 — 有哪些变量？取值范围是什么？
2. 目标函数 — 最小化还是最大化？线性还是二次？对于 QP：是否有平方项或交叉项（x²、x·y）？如果要最大化二次函数，用户必须将其取负后进行最小化。
3. 约束 — 线性不等式/等式？（不支持二次约束。）
4. 变量类型 — 全部为连续变量（LP / QP），还是包含整数/二元变量（MILP）？
5. 凸性（仅限 QP） — 对于最小化，二次型（矩阵 Q）应为半正定，以确保问题定义良好。

典型建模元素

• 连续变量 — 产量、流量、分配、投资组合权重。
• 二元变量 — 开/关、是/否（例如，设施是否启用、是否选择某项）。
• 关联约束 — 例如，仅当设施启用时才允许生产（Big-M 或指示变量）。
• 资源约束 — 对用量的线性上限（材料、时间、产能）。
• 二次目标项 — 方差（xᵀQx）、平方误差（‖Ax − b‖²）、交互项。

典型 QP 用例

• 投资组合优化 — 在满足收益和预算约束的前提下最小化方差。
• 最小二乘 — 在满足线性约束的前提下最小化 ‖Ax − b‖²。
• 其他带线性约束的二次目标函数。

---

问题陈述解析

用户给出问题文本时，应将每个句子分类，然后在建模前进行总结。无论问题属于 LP / MILP / QP，以下解析框架都适用。

将每个句子归类为参数/已知条件、约束、决策或目标函数。留意隐含约束（例如，措辞中表明已承诺与可选的区别）和隐含目标函数（例如，“确定计划”加上成本 → 最小化总成本）。

**歧义：**如果仍有任何歧义，请询问用户，或求解所有合理的解释并报告全部结果；不要擅自假设只有一种解释。

🔒 强制要求：有疑问时——先询问

• 如果无法确定是否应纳入某项约束或数值，请询问用户并说明可能的解释。

🔒 强制要求：完整流程运行——尝试所有变体

• 当用户要求运行完整流程（例如端到端、完整流水线）时，运行所有合理的变体并报告全部结果，让用户选择；不要擅自假设只有一种解释。

三类标签

标签	含义	示例（句子类型）
参数 / 已知量	固定数据、输入、事实。不是由模型选择的。	“需求量为 100 件。”“有 3 家工厂。”“单位成本为 $5。”
约束	必须满足的条件。可能是明确表述，也可能隐含在措辞中。	“产能为 200。”“必须满足所有需求。”“至少要安排 2 个班次。”
决策	我们要选择或优化的内容。	“生产多少。”“开放哪些设施。”“雇用多少名员工。”
目标	要最小化或最大化的内容。可能是明确的（“最小化成本”），也可能是隐含的（给出成本后要求“确定计划”）。	“最小化总成本。”“确定生产计划”（已给出成本）→ 最小化总成本。

隐含约束：已承诺与可选措辞

已承诺 / 固定措辞 → 视为参数或隐含约束（提及的所有内容都是已知条件或必须发生的事项）。不是决策。

措辞	解读	原因
“计划生产 X 件产品”	约束：必须生产全部 X 件。	属于承诺；生产量已固定。
“运营 3 家工厂”	参数：3 家工厂都已开放。不是选址问题。	当前状态已固定。
“雇用 N 名员工”	参数：N 名员工都已受雇。不是招聘决策。	人员规模已给定。
“产能为 C”	参数（C）+ 约束：使用量 ≤ C。	产能已固定。
“必须满足所有需求”	约束：满足需求。	明确要求。

可选 / 决策措辞 → 视为决策。

措辞	解读	原因
“最多可生产……”	决策：生产多少。	产量可选。
“可以选择开放”（工厂、场所）	决策：开放哪些。	由决策确定选择。
“考虑招聘”	决策：招聘多少人。	正在考虑招聘。
“决定订购多少”	决策：订购数量。	明确的决策。
“希望最小化 / 最大化……”	目标（驱动决策）。	目标；决策是实现目标的手段。

隐含目标——不要遗漏

如果问题要求“确定计划”（或类似表述），但没有明确说明“最小化”或“最大化”，目标往往是隐含的。你必须识别目标，并在建立模型前说明；不要构建没有目标的模型。

措辞 / 背景	可能的隐含目标	原因
“确定生产计划”+ 给出成本（单位成本、每小时成本等）	最小化总成本（生产 + 检验 / 销售 + 加班等）	需要选择计划；已给出成本 → 自然目标是最小化总成本。
“确定计划”+ 给出成本和收入	最大化利润（收入 − 成本）	收入和成本两方面的数据都有 → 优化利润。
“尝试确定月度生产计划”+ 给出车间工时成本、检验 / 销售成本	最小化总成本	已给出所有成本项；没有可用于最大化的收入 → 最小化总成本。

**规则：**如果问题提供了成本（或成本和收入）数据，并要求“确定”“找出”或“制定”计划，务必明确说明目标（例如：“我将目标视为最小化总成本，因为只给出了成本数据。”）。如果成本和收入都已给出，请说明采用“最小化成本”还是“最大化利润”。若不明确，请询问用户。

解析工作流

1. 拆分问题文本，将其拆分为句子或逻辑分句。
2. 标注每一项：参数/已知条件 | 约束 | 决策 | 目标（如有说明）。
3. 识别目标（显式或隐式）： 如果问题说“最小化/最大化 X”，这就是目标。如果问题只说“确定方案”（或“寻找”“制定”），但给出了成本（可能还包括收入），那么目标就是隐式的——请明确说明（例如，最小化总成本或最大化利润）；如果存在歧义，请向用户确认。
4. 标记隐式约束：针对每个句子，思考：“这是在陈述固定事实或要求（→ 参数/约束），还是我们要作出的选择（→ 决策）？”
5. 通过动词和情态动词消除歧义：
   • “是”“有”“运营”“雇用”“计划”（固定/已承诺）→ 参数或隐式约束。
   • “可能”“可以选择”“考虑”“决定”“想要”（可选）→ 决策或目标。
6. 🔒 必须遵守 — 如果仍有任何歧义（例如，某个数值或约束可能有两种解读）：询问用户哪种解读正确，或求解所有合理的解读并报告所有结果。不要擅自假定只有一种解读。
7. 总结：在写出数学公式之前，向用户列出参数、约束（显式 + 已标记的隐式约束）、决策和目标（显式或推断）。

解析检查清单

• 每个句子都有标注（参数 | 约束 | 决策 | 如有说明则标注目标）。
• 已识别目标： 显式（“最小化/最大化”）或隐式（“确定方案” + 成本 → 最小化总成本；+ 收入 → 最大化利润）。写出目标后再建立公式。
• 表示承诺的措辞（“计划”“运营”“雇用”）→ 不是决策。
• 表示可选项的措辞（“可能”“可以选择”“考虑”）→ 决策。
• 已明确写出由承诺性措辞隐含的约束（例如，“必须生产所有 X”）。
• 🔒 必须遵守 — 歧义： 任何可能有两种解读的措辞 → 我已询问用户，或将求解所有解读并报告所有结果（不得默默采用单一解读）。
• 在建立公式前已完成总结（参数、约束、决策、目标）。

示例

文本：“公司运营 3 家工厂，并计划生产 500 件产品。公司可以支付额外成本使用加班。最小化总成本。”

句子 / 短语	标签	说明
“运营 3 家工厂”	参数	3 家工厂全部开放；并非选择设施。
“计划生产 500 件产品”	约束（隐式）	必须生产全部 500 件。
“可以支付额外成本使用加班”	决策	加班多少属于决策。
“最小化总成本”	目标	指导决策。

结果：参数 = 3 家工厂、500 件的生产目标。约束 = 必须生产恰好 500 件（“计划生产”隐含的约束）。决策 = 各工厂的生产分配、加班量。目标 = 最小化成本。

隐式目标示例： 如果问题要求“确定生产计划”（或类似表述），并给出成本组成部分（例如，车间、检验、销售），但没有说明“最小化”或“最大化”，那么目标就是隐式的：最小化总成本。务必明确写出：“目标是最小化总成本。”

---

QP 规则：仅最小化

QP 目标必须是最小化。若要最大化二次表达式，应将其取负后再进行最小化；然后将最优值取负。

要使最小化问题定义良好，二次型 Q 应为半正定。如果 Q 不定，则该问题是非凸的，且可能不存在有限最优值。

---

常见模式

后续部分介绍特定的 LP/MILP 建模模式。每种模式相互独立——请阅读与问题相匹配的部分。

带整数生产量的分段线性目标函数

对凹分段线性利润／成本函数建模时（例如，大宗销售的边际利润递减），标准做法是使用连续分段变量，并将每个变量的上限设为对应分段的宽度。对于利润为凹函数的最大化问题，求解器会自然优先填满利润较高的分段。

注意： 如果生产数量是离散的（件、单位、物品），则总产量变量必须为整数，尽管分段变量可以保持为连续变量。否则，LP 松弛可能会得到分数形式的总产量，其目标值会高于或低于真正的整数最优值。

模式

x_total  — INTEGER (total production of a product)
s1, s2, … — CONTINUOUS (amount sold in each price segment, bounded by segment width)

Link: x_total = s1 + s2 + …
Resource constraints use x_total.
Objective uses segment variables × segment profit rates.

下料优化／余料问题

在下料优化问题中，废料面积既包括切边损耗（每种下料方案中的未使用宽度），也包括超额生产（产出的条料超过需求的部分）。如果只最小化切边损耗（每种方案的废料宽度 × 长度），就会忽略超额生产，导致目标值不正确。

正确的目标函数

由于需求的有用材料总面积是常量，最小化废料等价于最小化消耗的材料总面积：

minimize  sum_j (roll_width_j × x_j)

其中，x_j 是使用方案 j 切割的长度。废料面积为：

waste = total_material_area − required_useful_area

其中，required_useful_area = sum_i (order_width_i × order_length_i)。

注意

使用 sum_j (waste_width_j × x_j) 作为目标函数只能计算切边损耗——即每种方案中未使用的条料。它不会惩罚订单的超额生产。求解器会超额生产窄幅订单，以便高效填充下料方案，但这些多余材料仍然是废料。始终应使用材料总面积作为目标函数。

目标规划（优先级／字典序）

目标规划按优先级顺序优化多个目标。应采用顺序求解的方式实现——每个优先级阶段求解一次。

建模模式

1. 硬约束——容量限制、非负性等。这些约束在每个阶段都成立。
2. 目标约束——对每个目标引入偏差变量（d⁻ 表示未达成，d⁺ 表示超额达成），并写成等式：expression + d⁻ − d⁺ = target。
3. 按优先级顺序求解：
   • 阶段 1：最小化（或最大化）最高优先级目标对应的偏差。
   • 阶段 k：将所有更高优先级的偏差固定在其最优值，然后优化优先级 k 对应的偏差。

目标规划中的变量类型

偏差变量（d⁻、d⁺）以及松弛／闲置时间变量始终为连续变量。但是，如果决策变量表示离散／可计数的数量（生产的单位数、车辆数、工作人员数等），它们仍必须为整数。不要因为存在连续偏差变量就将所有变量都设为连续变量——决策变量是否为整数会直接影响可行性和目标值。

多期库存／采购模型

在涉及多期采购、销售和仓库容量的问题中，应根据问题的时间假设决定包含哪些容量约束。

模式

对每个库存平衡关系为 stock[t] = stock[t-1] + buy[t] - sell[t] 的时期 t：

• 期末容量（变量上界）：stock[t] <= capacity——始终需要。
• 采购后容量（显式约束）：stock[t-1] + buy[t] <= capacity——防止在该时期发生任何销售之前，采购量超过仓库容量。

何时加入采购后的约束

• 加入：当问题指出或暗示某一时期内先采购、后销售（顺序操作），或者仓库在任何时刻都不能超过容量时。
• 省略：当某一时期内的采购和销售同时进行（常见于教科书中的交易／库存问题），且容量仅适用于期末库存时。许多经典问题只约束期末库存。

**与销售约束的关键交互：**如果模型已有 sell[t] <= stock[t-1]（本期购入的粮食不能在本期售出），那么即使没有采购后的约束，模型也有界。销售约束可防止无界的买卖循环。此时，采购后的约束只是额外的物理限制，并非数学上的必要条件。

**默认情况：**如果问题未说明期内的时序，只使用期末容量约束（stock[t] <= capacity）。只有在问题明确要求时，才加入采购后的约束。

具有共享混合／中间加工的混合问题

在某些混合问题中，必须先将一部分原材料混合在一起（例如在混合罐中），再将其分配给不同产品。由此产生的中间物具有均匀成分——不能将不同的原材料分别分配给不同产品。

为什么标准混合 LP 在此处不适用

标准混合 LP 使用变量 x[i][j]（产品 j 中原材料 i 的用量），并允许将每种原材料自由分配给每种产品。当原材料经过共享的混合步骤时，所有接收该中间物的产品中，这些原材料的比例必须完全相同。这一比例约束是双线性的（x[A,1]*x[B,2] = x[B,1]*x[A,2]），无法直接用 LP 表示。

线性化策略

1. **分配给单一产品：**如果分析表明该中间物只有用于一种产品时才有利可图，就将全部中间物分配给该产品（将分配给其他产品的中间物设为零）。这样比例约束就自然满足了。这是最常见的情况——尝试一般拆分方案前，先检查该中间物用于各产品时的盈利情况。

2. **对中间物浓度进行参数化：**将中间物的硫含量／质量浓度固定为参数 σ。对于每个固定的 σ，问题都是一个标准 LP（中间物变为具有已知属性的虚拟原材料）。对一组 σ 值求解，或利用问题结构解析求出最优解。

3. **枚举情景：**当产品只有 2–3 种时，枚举中间物的接收产品（全部分配给 A、全部分配给 B、拆分分配）。对于只有一个接收产品的每种情景，LP 都是标准问题。对于拆分情景，使用策略 2。

盈利情况检查

建模前，检查在各产品中使用该中间物是否有利可图：

• 将该中间物的每吨最低成本（使用成本最低且可行的原材料配比）与各产品的销售价格进行比较。
• 如果某产品 j 满足 cost_intermediate > sell_price[j]，就不应将中间物分配给该产品。仅使用原材料 C（或其他直接投入）也可能无利可图，条件是 cost_C > sell_price[j]。
• 这项分析通常可以完全避免双线性拆分问题。