cuopt-numerical-optimization-formulation

数值优化建模

介绍从问题描述到清晰建模的概念和工作流程，涵盖 LP、MILP 和 QP。此处不包含 API 代码。

什么是 LP / MILP / QP

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

识别问题类型

属性	LP	MILP	QP
目标	线性	线性	二次（xᵀQx + cᵀx）
约束	线性	线性	通过二阶锥处理的线性 + 凸二次约束（仅不等式）
变量	连续	混合：连续 + 整数/二元	连续
方向	最小化或最大化	最小化或最大化	仅最小化（最大化时取相反数）
对偶值 / 灵敏度	对偶值 + 约化成本	无（整数最优解）	对偶值 + 约化成本

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

求解后的灵敏度分析（仅 LP / QP）。 连续 LP 和 QP 的解会提供对偶值（放宽紧约束一个单位时目标的边际变化：在哪里投入资源能改善结果）和约化成本（对于优化器取值为零的变量，该变量还需改善多少才能进入解：一种差一点就入选的情况）。MILP 解没有对偶值——整数最优解不是连续的，因此没有可返回的对偶值。如果模型包含二次约束，对偶值也不可用——二阶锥求解路径仅返回原始值。关于求解后如何获取这些值，请参阅对应语言的 API 技能。

必须明确的建模问题

如果以下问题尚不清楚，请进行询问：

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”）或隐式（“确定计划”＋成本 → 最小化总成本；＋收入 → 最大化利润）。说明目标后再建模。
• 已承诺的表述（“计划要”“运营”“雇用”）→ 不是决策。
• 可选的表述（“可能”“可以选择”“考虑”）→ 决策。
• 已写明由已承诺表述所隐含的约束（例如，“必须生产所有 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⁺）和松弛／闲置时间变量始终是连续变量。但是，当决策变量表示离散／可计数的数量（如生产的单位数、车辆数、工人数等）时，决策变量仍必须是整数变量。不要因为存在连续偏差变量，就将所有变量都设为连续变量——决策变量的整数性会直接影响可行性和目标值。

多周期库存／采购模型

在涉及多个周期的买入、卖出和仓库容量问题中，应根据问题对时间顺序的假设，决定纳入哪些容量约束。

模式

对于每个周期 t，库存平衡为 stock[t] = stock[t-1] + buy[t] - sell[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]，则不应将中间料分配给产品 j。单独使用原材料 C（或其他直接投入）也可能没有利润，例如 cost_C > sell_price[j]。
• 这种分析通常可以省去双线性拆分。