1. 从两个经典案例看整数规划与0-1规划的价值在资源分配、项目选择、人员调度这些日常决策中我们常常会遇到一些“非此即彼”或者“必须整数”的约束。比如公司有一笔预算要在几个潜在项目中做选择每个项目要么投、要么不投不能投一半又比如人力资源部门要组建一个团队每个人要么被聘用、要么不被聘用不能聘用0.7个人。这些“要么全有要么全无”的决策就是典型的0-1规划问题它是整数规划的一个特例。而整数规划顾名思义就是要求决策变量必须取整数值的优化问题。今天我们就以两个非常接地气的场景——“投资组合问题”和“人员聘用方案”——作为切入点手把手地带你用MATLAB和LINGO这两款强大的工具把整数规划和0-1规划从抽象的数学公式变成能解决实际问题的“利器”。你会发现这些听起来高深的优化方法其实离我们的工作决策并不遥远。MATLAB以其强大的矩阵运算和丰富的优化工具箱闻名适合进行算法原型验证和复杂模型的求解而LINGO则是专为线性、非线性和整数优化设计的语言环境建模语法直观求解大规模整数规划问题效率很高。两者结合能让我们从建模到求解的路径更加清晰。2. 案例一0-1规划下的项目投资决策假设你是一家公司的投资经理手头有1000万的预算。市场部经过调研筛选出了5个潜在的投资项目。每个项目需要的投资额、预计的净现值NPV可以简单理解为项目带来的价值以及风险评估等级都不同。公司管理层要求总风险不能超过某个阈值并且由于管理精力有限最多只能从5个项目中选择3个进行投资。你的任务就是从这5个项目中做出选择在满足预算、风险和控制项目数量的前提下使得所选项目的总净现值最大。这正是一个标准的0-1背包问题Knapsack Problem的变体。每个项目就像一个“物品”投资额是它的“重量”净现值是它的“价值”而我们的背包容量就是总预算。额外的约束是“最多选3个”和“总风险控制”。2.1 问题建模与数学公式表达首先我们需要用数学语言把这个问题清晰地定义出来。这是最关键的一步模型建错了后面工具用得再熟也是徒劳。我们定义决策变量 ( x_i ) (i1,2,...,5)。这是一个0-1变量( x_i 1 ) 表示投资第 ( i ) 个项目。( x_i 0 ) 表示不投资第 ( i ) 个项目。假设我们有了以下数据表项目(i)所需投资额 ( a_i ) (万元)预计净现值 ( p_i ) (万元)风险系数 ( r_i )13001500.722001200.534002200.942501300.453501800.6目标函数 我们的目标是最大化总净现值。 [ \text{Maximize } Z 150x_1 120x_2 220x_3 130x_4 180x_5 ]约束条件预算约束总投资额不能超过1000万。 [ 300x_1 200x_2 400x_3 250x_4 350x_5 \leq 1000 ]项目数量约束最多选择3个项目。 [ x_1 x_2 x_3 x_4 x_5 \leq 3 ]风险约束假设公司要求总风险系数各项目风险系数加权和不超过2.0。 [ 0.7x_1 0.5x_2 0.9x_3 0.4x_4 0.6x_5 \leq 2.0 ]0-1变量约束 [ x_i \in {0, 1}, \quad i 1,2,...,5 ]这样一个完整的0-1整数规划模型就建立起来了。接下来我们分别用MATLAB和LINGO来求解它。2.2 使用MATLAB求解intlinprog函数详解MATLAB的优化工具箱Optimization Toolbox提供了intlinprog函数专门用于求解混合整数线性规划问题。对于我们的0-1规划只需将整数约束设置为对所有变量有效即可。第一步准备输入参数intlinprog的基本调用格式是[x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub)f 目标函数的系数向量。注意intlinprog默认是最小化问题。我们的目标是最大化总净现值因此需要将目标函数系数取负号转化为最小化问题Minimize -Z。f -[150; 120; 220; 130; 180]; % 系数取负intcon 指定哪些变量是整数。我们的变量x1到x5都是整数0-1所以这是一个包含所有变量索引的向量。intcon [1; 2; 3; 4; 5];A, b 线性不等式约束A*x ≤ b。我们的预算、项目数量、风险约束都是不等式。A [300, 200, 400, 250, 350; % 预算约束系数 1, 1, 1, 1, 1; % 项目数量约束系数 0.7, 0.5, 0.9, 0.4, 0.6]; % 风险约束系数 b [1000; 3; 2.0];Aeq, beq 线性等式约束Aeq*x beq。本例中没有等式约束用空矩阵[]表示。Aeq []; beq [];lb, ub 变量的下界和上界。对于0-1变量下界是0上界是1。lb [0; 0; 0; 0; 0]; ub [1; 1; 1; 1; 1];第二步调用函数并解读结果将上述参数组合调用函数[x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub); disp(最优解项目选择1为选中); disp(x); disp([最大净现值万元, num2str(-fval)]); % 注意fval是取负后的最小值所以要再取负运行后你可能会得到类似这样的结果最优解项目选择1为选中 1 1 0 1 0 最大净现值万元400这意味着最优投资方案是选择项目1、项目2和项目4。总投资额为 300200250750万小于1000万预算项目数量为3满足要求总风险为 0.70.50.41.6小于2.0。总净现值为150120130400万。注意intlinprog求解整数规划使用的是分支定界法Branch and Bound。对于小规模问题它会很快。但对于变量很多的大规模0-1规划求解时间可能会指数级增长。这时初始点的设置、求解器的参数调整如MaxTime或者问题本身的重新表述利用特殊结构就可能变得很重要。2.3 使用LINGO求解直观的建模语言LINGO的建模哲学是“让模型看起来像数学公式”。对于同样的问题LINGO的模型文件.lg4或直接在代码窗口输入非常直观。LINGO模型代码MODEL: SETS: PROJECT /1..5/: INVEST, NPV, RISK, X; ENDSETS DATA: INVEST 300 200 400 250 350; ! 投资额; NPV 150 120 220 130 180; ! 净现值; RISK 0.7 0.5 0.9 0.4 0.6; ! 风险系数; BUDGET 1000; ! 总预算; MAX_PROJ 3; ! 最大项目数; MAX_RISK 2.0; ! 最大风险容忍度; ENDDATA ! 目标函数最大化总净现值; MAX SUM(PROJECT(I): NPV(I) * X(I)); ! 约束条件; SUM(PROJECT(I): INVEST(I) * X(I)) BUDGET; ! 预算约束; SUM(PROJECT(I): X(I)) MAX_PROJ; ! 项目数量约束; SUM(PROJECT(I): RISK(I) * X(I)) MAX_RISK; ! 风险约束; ! 定义X为0-1变量; FOR(PROJECT(I): BIN(X(I))); END代码解读与LINGO优势集合定义(SETS:): 使用PROJECT /1..5/定义了一个包含5个成员的集合并声明了与之关联的属性投资额、净现值等。这种基于集合的建模方式在变量和约束很多时比MATLAB逐条写系数要简洁、不易出错。数据输入(DATA:): 将数据与模型分离方便修改。你可以轻松地将DATA部分替换为从Excel或数据库读取。目标与约束 几乎就是数学公式的直译。SUM是求和函数FOR是循环函数语义非常清晰。变量类型BIN(X(I))直接将变量X(I)声明为0-1变量。在LINGO中点击“求解”按钮会弹出一个求解状态窗口显示找到最优解目标函数值为400。在“Solution Report”窗口中你可以清晰地看到每个X变量的值1或0以及各个约束的松弛/剩余Slack or Surplus情况这能帮你分析哪些约束是“紧的”刚好达到边界。MATLAB vs LINGO 在这个案例中的体会MATLAB更像是在“编程求解”。你需要将问题转化为矩阵向量形式对编程思维要求高但灵活性极强可以轻松地将优化求解嵌入到更大的算法流程或图形界面如App Designer中实现仿真结果的动态展示。LINGO更像是在“描述问题”。它的语法就是优化模型的语言建模速度快易于理解和维护特别适合专注于模型本身而非编程实现的运筹学研究者或决策分析人员。3. 案例二整数规划下的最优人员聘用方案现在我们把场景切换到人力资源部门。公司需要组建一个新的项目组需要覆盖4类技能A编程、B设计、C测试、D项目管理。现有8位候选人每位候选人具备其中若干项技能且对薪资有不同要求。我们的目标是以最低的总薪资成本聘用若干位候选人确保这4类技能至少各有一人掌握。同时公司希望团队规模尽量精简但这不是硬约束我们可以将其作为一个次要目标或通过分析不同团队规模下的成本来决策。这是一个**集合覆盖问题Set Covering Problem**的典型应用。我们需要用一个“成本”最小的候选人集合“覆盖”所有必须的技能要求。3.1 问题建模与数据准备定义决策变量 ( y_j ) (j1,2,...,8)。这也是一个0-1变量( y_j 1 ) 表示聘用第 ( j ) 位候选人。( y_j 0 ) 表示不聘用。假设候选人技能矩阵和薪资要求如下1表示掌握该技能候选人(j)技能A技能B技能C技能D月薪 ( c_j ) (千元)11010202100125301102240101285110030600111871011358011132目标函数 最小化总薪资成本。 [ \text{Minimize } Z 20y_1 25y_2 22y_3 28y_4 30y_5 18y_6 35y_7 32y_8 ]约束条件 确保每项技能至少被一位聘用的候选人覆盖。技能A覆盖约束 候选人1, 2, 5, 7掌握技能A。至少聘用其中一人。 [ y_1 y_2 y_5 y_7 \geq 1 ]技能B覆盖约束 [ y_3 y_4 y_5 y_8 \geq 1 ]技能C覆盖约束 [ y_1 y_3 y_6 y_7 y_8 \geq 1 ]技能D覆盖约束 [ y_2 y_4 y_6 y_7 y_8 \geq 1 ]0-1变量约束 [ y_j \in {0, 1}, \quad j 1,2,...,8 ]这个模型没有不等式上限约束但有了“大于等于”的约束。它仍然是一个0-1整数线性规划。3.2 MATLAB求解处理“≥”约束与多方案分析在MATLAB中intlinprog处理的是A*x ≤ b形式的不等式。对于“≥”约束我们需要两边同时乘以-1来转换。 例如技能A的约束 ( y_1 y_2 y_5 y_7 \geq 1 ) 等价于 ( -y_1 - y_2 - y_5 - y_7 \leq -1 )。MATLAB代码实现% 目标函数系数 (最小化总薪资) f [20; 25; 22; 28; 30; 18; 35; 32]; % 整数变量索引 (全部8个变量都是0-1整数) intcon 1:8; % 不等式约束 A*y b % 四个技能覆盖约束转换为“”形式 A_cover -[1, 0, 0, 0, 1, 0, 1, 0; % 技能A: -y1 -y2 -y5 -y7 -1 0, 0, 1, 1, 1, 0, 0, 1; % 技能B: -y3 -y4 -y5 -y8 -1 1, 0, 1, 0, 0, 1, 1, 1; % 技能C: -y1 -y3 -y6 -y7 -y8 -1 0, 1, 0, 1, 0, 1, 1, 1]; % 技能D: -y2 -y4 -y6 -y7 -y8 -1 b_cover -ones(4, 1); % 右边全部是-1 % 变量上下界 (0-1) lb zeros(8, 1); ub ones(8, 1); % 无等式约束 Aeq []; beq []; % 求解 [y, min_cost] intlinprog(f, intcon, A_cover, b_cover, Aeq, beq, lb, ub); disp(最优聘用方案1为聘用); disp(y); disp([最低总月薪千元, num2str(min_cost)]);运行求解可能会得到结果聘用候选人3和候选人6。候选人3掌握技能B和C月薪22。候选人6掌握技能C和D月薪18。 总薪资为40千元。检查覆盖情况技能A无人掌握这显然不符合约束。问题出在哪里常见陷阱与排查仔细检查我们的约束转换。技能A的约束是 ( y_1 y_2 y_5 y_7 \geq 1 )我们写成了-y1 - y2 - y5 - y7 -1。但在矩阵A_cover的第一行我们写的是[1, 0, 0, 0, 1, 0, 1, 0]前面已经有一个负号了所以这行实际代表-1*y1 -0*y2 ...即-y1 -0 -y5 -0 -y7。这里漏掉了y2的系数y2是第二个变量但在第一行它的位置是0这意味着在约束中它没有被考虑。正确的第一行应该是[1, 1, 0, 0, 1, 0, 1, 0]。修正后的A_cover矩阵A_cover -[1, 1, 0, 0, 1, 0, 1, 0; % 技能A: 候选人 1,2,5,7 0, 0, 1, 1, 1, 0, 0, 1; % 技能B: 候选人 3,4,5,8 1, 0, 1, 0, 0, 1, 1, 1; % 技能C: 候选人 1,3,6,7,8 0, 1, 0, 1, 0, 1, 1, 1]; % 技能D: 候选人 2,4,6,7,8重新求解得到的结果可能是聘用候选人1和候选人4。候选人1掌握技能A和C月薪20。候选人4掌握技能B和D月薪28。 总薪资为48千元。此时所有技能都被覆盖A和C由1覆盖B和D由4覆盖。实操心得在MATLAB中手动构建大型系数矩阵时非常容易出错尤其是“≥”约束需要取负的时候。一个很好的习惯是先写出原始的数学约束式在旁边标注好每个变量对应的列索引然后像填表格一样逐行构建矩阵A。或者可以考虑用循环来生成这个矩阵逻辑会更清晰。3.3 LINGO求解与灵敏度分析在LINGO中我们同样可以优雅地描述这个集合覆盖问题。LINGO模型代码MODEL: SETS: SKILL /A, B, C, D/: ; CANDIDATE /1..8/: SALARY, HIRE; LINK(SKILL, CANDIDATE): HAS_SKILL; ! 技能-候选人关联矩阵; ENDSETS DATA: ! 薪资数据; SALARY 20 25 22 28 30 18 35 32; ! 技能矩阵 (行:技能 列:候选人); HAS_SKILL 1 1 0 0 1 0 1 0 ! 技能A 0 0 1 1 1 0 0 1 ! 技能B 1 0 1 0 0 1 1 1 ! 技能C 0 1 0 1 0 1 1 1; ! 技能D ENDDATA ! 目标最小化总薪资; MIN SUM(CANDIDATE(J): SALARY(J) * HIRE(J)); ! 约束每种技能至少被一个聘用的候选人覆盖; FOR(SKILL(I): SUM(CANDIDATE(J): HAS_SKILL(I, J) * HIRE(J)) 1 ); ! 定义HIRE为0-1变量; FOR(CANDIDATE(J): BIN(HIRE(J))); ENDLINGO的求解报告不仅会给出最优解HIRE变量还会提供丰富的灵敏度分析信息比如约束的“对偶价格”Dual Price。在这个模型中对偶价格可以解释为如果某种技能“至少需要一人”的约束右端项从1增加到2即要求该技能至少两人掌握总成本会增加多少。这为人力资源的弹性决策提供了量化依据。结果讨论与方案扩展 我们得到的最优解是聘用候选人1和4成本48。但这是唯一最优解吗我们可以思考如果希望团队规模更小虽然成本可能更高或者想看看有没有其他成本也为48的方案该怎么办寻找多个最优解或近似解在LINGO中你可以通过“求解”菜单下的“求多个解”选项来尝试寻找不同的最优解。在MATLAB中则需要更复杂的操作比如在找到第一个最优解后添加一个约束禁止当前解然后重新求解看目标函数值是否变化。分析“团队规模”与“成本”的权衡我们可以修改模型将团队规模SUM(CANDIDATE: HIRE)作为一个约束比如 N然后改变N的值从1到8分别求解得到一系列“成本-规模”的帕累托前沿点。这能帮助决策者清晰地看到多增加一个人成本能降低多少从而做出更全面的决策。4. 进阶技巧当问题变得更复杂时现实中的投资和聘用问题往往比上述案例复杂。例如项目间可能存在互斥或依赖关系投了项目A就不能投项目B或者投项目C必须先投项目D候选人之间可能有合作效率问题需要同时聘用某两人才能发挥最大价值。这些都需要在模型中引入额外的约束。4.1 处理项目间的逻辑关系互斥关系项目A和项目B至多选一个。 [ x_A x_B \leq 1 ]依赖关系如果选择项目C则必须选择项目D。 [ x_C \leq x_D \quad \text{或等价地} \quad x_C - x_D \leq 0 ] 这个约束保证了当 ( x_C 1 ) 时( x_D ) 也必须为1当 ( x_C 0 ) 时( x_D ) 可以是0或1。多选一关系项目E、F、G中必须恰好选择一个。 [ x_E x_F x_G 1 ]在LINGO中添加这些约束非常直接。在MATLAB中则需要将它们转化为A*x b或Aeq*x beq的形式添加到相应的矩阵中。4.2 处理固定成本与资源约束在投资问题中有时启动一个项目需要一笔固定的前期成本无论投资额多少。这可以通过引入辅助的0-1变量和“大M法”来建模。假设项目i有一个固定启动成本 ( S_i )只有当 ( x_i 1 )决定投资时这个成本才发生。 我们可以引入一个连续变量 ( y_i ) 表示是否发生固定成本并添加约束 [ y_i \leq M \cdot x_i \ S_i \cdot x_i \leq y_i \ ] 其中 ( M ) 是一个足够大的数。这样当 ( x_i0 ) 时( y_i ) 被强制为0当 ( x_i1 ) 时( y_i ) 必须至少为 ( S_i )在最小化成本的目标下( y_i ) 会取到 ( S_i )。然后将 ( y_i ) 加入目标函数。4.3 模型调试与求解策略从松弛问题开始在求解复杂的整数规划前可以先求解其线性松弛问题即去掉整数约束让变量在[0,1]区间连续变化。松弛问题的最优解提供了一个目标函数值的下界对于最小化问题。如果松弛解恰好是整数解那恭喜你它就是原问题的最优解。如果不是这个下界可以帮助你评估分支定界法的求解进度。利用LINGO的调试功能如果LINGO报告模型无可行解可以使用“求解”菜单下的“调试”功能。LINGO会尝试找出导致不可行的一组最小的约束集合这对于排查模型逻辑错误非常有帮助。MATLAB求解器参数调整对于大规模问题intlinprog的求解时间可能很长。可以尝试调整选项例如options optimoptions(intlinprog, Display, iter, MaxTime, 300); [x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, options);Display, iter会输出迭代过程方便观察求解进度。MaxTime可以设置最大求解时间秒防止程序长时间运行。启发式与近似求解对于超大规模的0-1规划比如成千上万个变量精确求解可能不现实。这时可以考虑启发式算法如遗传算法、模拟退火等来寻找一个高质量的近似解。MATLAB的全局优化工具箱提供了这些算法的实现。5. 从求解到决策结果解读与报告拿到求解器的输出x[1,0,1,...],fval48000并不是终点。如何向非技术背景的决策者解释这个结果同样重要。解读解向量的含义清晰地列出被选中的项目或候选人并说明他们如何满足所有约束。例如“我们建议投资项目A、C、E。该组合总投资额XX万预计总净现值YY万风险控制在ZZ且满足了项目间的依赖关系...”进行“What-If”分析这是优化模型最大的价值之一。你可以向决策者展示预算敏感性如果预算增加或减少10%最优方案和最大收益会如何变化约束松弛分析如果风险容忍度稍微提高一点能带来多少收益的提升这可以帮助评估当前约束是否过于严格。参数变动分析如果某个项目的净现值预测发生了波动当前的最优方案还稳健吗在多大范围内波动最优方案不变呈现替代方案如前所述可能存在多个成本相同的最优解或者成本略高但具备其他优势如团队经验更均衡的方案。将这些方案及其优缺点一并呈现将最终的决策权交给管理者。说明模型局限性诚实地告知决策者模型的假设和局限。例如模型中的净现值和风险系数都是点估计实际可能存在不确定性模型没有考虑项目执行过程中的动态调整等。这能增加报告的可信度。通过MATLAB和LINGO我们将整数规划和0-1规划从教科书上的理论变成了辅助实际决策的得力工具。关键在于准确地将现实问题翻译成数学模型然后选择合适的工具高效求解最后将冰冷的数字结果转化为有温度、有洞见的决策建议。这个过程本身就是一次严谨的逻辑思维训练。
MATLAB与LINGO实战：整数规划与0-1规划解决投资与人员聘用决策
1. 从两个经典案例看整数规划与0-1规划的价值在资源分配、项目选择、人员调度这些日常决策中我们常常会遇到一些“非此即彼”或者“必须整数”的约束。比如公司有一笔预算要在几个潜在项目中做选择每个项目要么投、要么不投不能投一半又比如人力资源部门要组建一个团队每个人要么被聘用、要么不被聘用不能聘用0.7个人。这些“要么全有要么全无”的决策就是典型的0-1规划问题它是整数规划的一个特例。而整数规划顾名思义就是要求决策变量必须取整数值的优化问题。今天我们就以两个非常接地气的场景——“投资组合问题”和“人员聘用方案”——作为切入点手把手地带你用MATLAB和LINGO这两款强大的工具把整数规划和0-1规划从抽象的数学公式变成能解决实际问题的“利器”。你会发现这些听起来高深的优化方法其实离我们的工作决策并不遥远。MATLAB以其强大的矩阵运算和丰富的优化工具箱闻名适合进行算法原型验证和复杂模型的求解而LINGO则是专为线性、非线性和整数优化设计的语言环境建模语法直观求解大规模整数规划问题效率很高。两者结合能让我们从建模到求解的路径更加清晰。2. 案例一0-1规划下的项目投资决策假设你是一家公司的投资经理手头有1000万的预算。市场部经过调研筛选出了5个潜在的投资项目。每个项目需要的投资额、预计的净现值NPV可以简单理解为项目带来的价值以及风险评估等级都不同。公司管理层要求总风险不能超过某个阈值并且由于管理精力有限最多只能从5个项目中选择3个进行投资。你的任务就是从这5个项目中做出选择在满足预算、风险和控制项目数量的前提下使得所选项目的总净现值最大。这正是一个标准的0-1背包问题Knapsack Problem的变体。每个项目就像一个“物品”投资额是它的“重量”净现值是它的“价值”而我们的背包容量就是总预算。额外的约束是“最多选3个”和“总风险控制”。2.1 问题建模与数学公式表达首先我们需要用数学语言把这个问题清晰地定义出来。这是最关键的一步模型建错了后面工具用得再熟也是徒劳。我们定义决策变量 ( x_i ) (i1,2,...,5)。这是一个0-1变量( x_i 1 ) 表示投资第 ( i ) 个项目。( x_i 0 ) 表示不投资第 ( i ) 个项目。假设我们有了以下数据表项目(i)所需投资额 ( a_i ) (万元)预计净现值 ( p_i ) (万元)风险系数 ( r_i )13001500.722001200.534002200.942501300.453501800.6目标函数 我们的目标是最大化总净现值。 [ \text{Maximize } Z 150x_1 120x_2 220x_3 130x_4 180x_5 ]约束条件预算约束总投资额不能超过1000万。 [ 300x_1 200x_2 400x_3 250x_4 350x_5 \leq 1000 ]项目数量约束最多选择3个项目。 [ x_1 x_2 x_3 x_4 x_5 \leq 3 ]风险约束假设公司要求总风险系数各项目风险系数加权和不超过2.0。 [ 0.7x_1 0.5x_2 0.9x_3 0.4x_4 0.6x_5 \leq 2.0 ]0-1变量约束 [ x_i \in {0, 1}, \quad i 1,2,...,5 ]这样一个完整的0-1整数规划模型就建立起来了。接下来我们分别用MATLAB和LINGO来求解它。2.2 使用MATLAB求解intlinprog函数详解MATLAB的优化工具箱Optimization Toolbox提供了intlinprog函数专门用于求解混合整数线性规划问题。对于我们的0-1规划只需将整数约束设置为对所有变量有效即可。第一步准备输入参数intlinprog的基本调用格式是[x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub)f 目标函数的系数向量。注意intlinprog默认是最小化问题。我们的目标是最大化总净现值因此需要将目标函数系数取负号转化为最小化问题Minimize -Z。f -[150; 120; 220; 130; 180]; % 系数取负intcon 指定哪些变量是整数。我们的变量x1到x5都是整数0-1所以这是一个包含所有变量索引的向量。intcon [1; 2; 3; 4; 5];A, b 线性不等式约束A*x ≤ b。我们的预算、项目数量、风险约束都是不等式。A [300, 200, 400, 250, 350; % 预算约束系数 1, 1, 1, 1, 1; % 项目数量约束系数 0.7, 0.5, 0.9, 0.4, 0.6]; % 风险约束系数 b [1000; 3; 2.0];Aeq, beq 线性等式约束Aeq*x beq。本例中没有等式约束用空矩阵[]表示。Aeq []; beq [];lb, ub 变量的下界和上界。对于0-1变量下界是0上界是1。lb [0; 0; 0; 0; 0]; ub [1; 1; 1; 1; 1];第二步调用函数并解读结果将上述参数组合调用函数[x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub); disp(最优解项目选择1为选中); disp(x); disp([最大净现值万元, num2str(-fval)]); % 注意fval是取负后的最小值所以要再取负运行后你可能会得到类似这样的结果最优解项目选择1为选中 1 1 0 1 0 最大净现值万元400这意味着最优投资方案是选择项目1、项目2和项目4。总投资额为 300200250750万小于1000万预算项目数量为3满足要求总风险为 0.70.50.41.6小于2.0。总净现值为150120130400万。注意intlinprog求解整数规划使用的是分支定界法Branch and Bound。对于小规模问题它会很快。但对于变量很多的大规模0-1规划求解时间可能会指数级增长。这时初始点的设置、求解器的参数调整如MaxTime或者问题本身的重新表述利用特殊结构就可能变得很重要。2.3 使用LINGO求解直观的建模语言LINGO的建模哲学是“让模型看起来像数学公式”。对于同样的问题LINGO的模型文件.lg4或直接在代码窗口输入非常直观。LINGO模型代码MODEL: SETS: PROJECT /1..5/: INVEST, NPV, RISK, X; ENDSETS DATA: INVEST 300 200 400 250 350; ! 投资额; NPV 150 120 220 130 180; ! 净现值; RISK 0.7 0.5 0.9 0.4 0.6; ! 风险系数; BUDGET 1000; ! 总预算; MAX_PROJ 3; ! 最大项目数; MAX_RISK 2.0; ! 最大风险容忍度; ENDDATA ! 目标函数最大化总净现值; MAX SUM(PROJECT(I): NPV(I) * X(I)); ! 约束条件; SUM(PROJECT(I): INVEST(I) * X(I)) BUDGET; ! 预算约束; SUM(PROJECT(I): X(I)) MAX_PROJ; ! 项目数量约束; SUM(PROJECT(I): RISK(I) * X(I)) MAX_RISK; ! 风险约束; ! 定义X为0-1变量; FOR(PROJECT(I): BIN(X(I))); END代码解读与LINGO优势集合定义(SETS:): 使用PROJECT /1..5/定义了一个包含5个成员的集合并声明了与之关联的属性投资额、净现值等。这种基于集合的建模方式在变量和约束很多时比MATLAB逐条写系数要简洁、不易出错。数据输入(DATA:): 将数据与模型分离方便修改。你可以轻松地将DATA部分替换为从Excel或数据库读取。目标与约束 几乎就是数学公式的直译。SUM是求和函数FOR是循环函数语义非常清晰。变量类型BIN(X(I))直接将变量X(I)声明为0-1变量。在LINGO中点击“求解”按钮会弹出一个求解状态窗口显示找到最优解目标函数值为400。在“Solution Report”窗口中你可以清晰地看到每个X变量的值1或0以及各个约束的松弛/剩余Slack or Surplus情况这能帮你分析哪些约束是“紧的”刚好达到边界。MATLAB vs LINGO 在这个案例中的体会MATLAB更像是在“编程求解”。你需要将问题转化为矩阵向量形式对编程思维要求高但灵活性极强可以轻松地将优化求解嵌入到更大的算法流程或图形界面如App Designer中实现仿真结果的动态展示。LINGO更像是在“描述问题”。它的语法就是优化模型的语言建模速度快易于理解和维护特别适合专注于模型本身而非编程实现的运筹学研究者或决策分析人员。3. 案例二整数规划下的最优人员聘用方案现在我们把场景切换到人力资源部门。公司需要组建一个新的项目组需要覆盖4类技能A编程、B设计、C测试、D项目管理。现有8位候选人每位候选人具备其中若干项技能且对薪资有不同要求。我们的目标是以最低的总薪资成本聘用若干位候选人确保这4类技能至少各有一人掌握。同时公司希望团队规模尽量精简但这不是硬约束我们可以将其作为一个次要目标或通过分析不同团队规模下的成本来决策。这是一个**集合覆盖问题Set Covering Problem**的典型应用。我们需要用一个“成本”最小的候选人集合“覆盖”所有必须的技能要求。3.1 问题建模与数据准备定义决策变量 ( y_j ) (j1,2,...,8)。这也是一个0-1变量( y_j 1 ) 表示聘用第 ( j ) 位候选人。( y_j 0 ) 表示不聘用。假设候选人技能矩阵和薪资要求如下1表示掌握该技能候选人(j)技能A技能B技能C技能D月薪 ( c_j ) (千元)11010202100125301102240101285110030600111871011358011132目标函数 最小化总薪资成本。 [ \text{Minimize } Z 20y_1 25y_2 22y_3 28y_4 30y_5 18y_6 35y_7 32y_8 ]约束条件 确保每项技能至少被一位聘用的候选人覆盖。技能A覆盖约束 候选人1, 2, 5, 7掌握技能A。至少聘用其中一人。 [ y_1 y_2 y_5 y_7 \geq 1 ]技能B覆盖约束 [ y_3 y_4 y_5 y_8 \geq 1 ]技能C覆盖约束 [ y_1 y_3 y_6 y_7 y_8 \geq 1 ]技能D覆盖约束 [ y_2 y_4 y_6 y_7 y_8 \geq 1 ]0-1变量约束 [ y_j \in {0, 1}, \quad j 1,2,...,8 ]这个模型没有不等式上限约束但有了“大于等于”的约束。它仍然是一个0-1整数线性规划。3.2 MATLAB求解处理“≥”约束与多方案分析在MATLAB中intlinprog处理的是A*x ≤ b形式的不等式。对于“≥”约束我们需要两边同时乘以-1来转换。 例如技能A的约束 ( y_1 y_2 y_5 y_7 \geq 1 ) 等价于 ( -y_1 - y_2 - y_5 - y_7 \leq -1 )。MATLAB代码实现% 目标函数系数 (最小化总薪资) f [20; 25; 22; 28; 30; 18; 35; 32]; % 整数变量索引 (全部8个变量都是0-1整数) intcon 1:8; % 不等式约束 A*y b % 四个技能覆盖约束转换为“”形式 A_cover -[1, 0, 0, 0, 1, 0, 1, 0; % 技能A: -y1 -y2 -y5 -y7 -1 0, 0, 1, 1, 1, 0, 0, 1; % 技能B: -y3 -y4 -y5 -y8 -1 1, 0, 1, 0, 0, 1, 1, 1; % 技能C: -y1 -y3 -y6 -y7 -y8 -1 0, 1, 0, 1, 0, 1, 1, 1]; % 技能D: -y2 -y4 -y6 -y7 -y8 -1 b_cover -ones(4, 1); % 右边全部是-1 % 变量上下界 (0-1) lb zeros(8, 1); ub ones(8, 1); % 无等式约束 Aeq []; beq []; % 求解 [y, min_cost] intlinprog(f, intcon, A_cover, b_cover, Aeq, beq, lb, ub); disp(最优聘用方案1为聘用); disp(y); disp([最低总月薪千元, num2str(min_cost)]);运行求解可能会得到结果聘用候选人3和候选人6。候选人3掌握技能B和C月薪22。候选人6掌握技能C和D月薪18。 总薪资为40千元。检查覆盖情况技能A无人掌握这显然不符合约束。问题出在哪里常见陷阱与排查仔细检查我们的约束转换。技能A的约束是 ( y_1 y_2 y_5 y_7 \geq 1 )我们写成了-y1 - y2 - y5 - y7 -1。但在矩阵A_cover的第一行我们写的是[1, 0, 0, 0, 1, 0, 1, 0]前面已经有一个负号了所以这行实际代表-1*y1 -0*y2 ...即-y1 -0 -y5 -0 -y7。这里漏掉了y2的系数y2是第二个变量但在第一行它的位置是0这意味着在约束中它没有被考虑。正确的第一行应该是[1, 1, 0, 0, 1, 0, 1, 0]。修正后的A_cover矩阵A_cover -[1, 1, 0, 0, 1, 0, 1, 0; % 技能A: 候选人 1,2,5,7 0, 0, 1, 1, 1, 0, 0, 1; % 技能B: 候选人 3,4,5,8 1, 0, 1, 0, 0, 1, 1, 1; % 技能C: 候选人 1,3,6,7,8 0, 1, 0, 1, 0, 1, 1, 1]; % 技能D: 候选人 2,4,6,7,8重新求解得到的结果可能是聘用候选人1和候选人4。候选人1掌握技能A和C月薪20。候选人4掌握技能B和D月薪28。 总薪资为48千元。此时所有技能都被覆盖A和C由1覆盖B和D由4覆盖。实操心得在MATLAB中手动构建大型系数矩阵时非常容易出错尤其是“≥”约束需要取负的时候。一个很好的习惯是先写出原始的数学约束式在旁边标注好每个变量对应的列索引然后像填表格一样逐行构建矩阵A。或者可以考虑用循环来生成这个矩阵逻辑会更清晰。3.3 LINGO求解与灵敏度分析在LINGO中我们同样可以优雅地描述这个集合覆盖问题。LINGO模型代码MODEL: SETS: SKILL /A, B, C, D/: ; CANDIDATE /1..8/: SALARY, HIRE; LINK(SKILL, CANDIDATE): HAS_SKILL; ! 技能-候选人关联矩阵; ENDSETS DATA: ! 薪资数据; SALARY 20 25 22 28 30 18 35 32; ! 技能矩阵 (行:技能 列:候选人); HAS_SKILL 1 1 0 0 1 0 1 0 ! 技能A 0 0 1 1 1 0 0 1 ! 技能B 1 0 1 0 0 1 1 1 ! 技能C 0 1 0 1 0 1 1 1; ! 技能D ENDDATA ! 目标最小化总薪资; MIN SUM(CANDIDATE(J): SALARY(J) * HIRE(J)); ! 约束每种技能至少被一个聘用的候选人覆盖; FOR(SKILL(I): SUM(CANDIDATE(J): HAS_SKILL(I, J) * HIRE(J)) 1 ); ! 定义HIRE为0-1变量; FOR(CANDIDATE(J): BIN(HIRE(J))); ENDLINGO的求解报告不仅会给出最优解HIRE变量还会提供丰富的灵敏度分析信息比如约束的“对偶价格”Dual Price。在这个模型中对偶价格可以解释为如果某种技能“至少需要一人”的约束右端项从1增加到2即要求该技能至少两人掌握总成本会增加多少。这为人力资源的弹性决策提供了量化依据。结果讨论与方案扩展 我们得到的最优解是聘用候选人1和4成本48。但这是唯一最优解吗我们可以思考如果希望团队规模更小虽然成本可能更高或者想看看有没有其他成本也为48的方案该怎么办寻找多个最优解或近似解在LINGO中你可以通过“求解”菜单下的“求多个解”选项来尝试寻找不同的最优解。在MATLAB中则需要更复杂的操作比如在找到第一个最优解后添加一个约束禁止当前解然后重新求解看目标函数值是否变化。分析“团队规模”与“成本”的权衡我们可以修改模型将团队规模SUM(CANDIDATE: HIRE)作为一个约束比如 N然后改变N的值从1到8分别求解得到一系列“成本-规模”的帕累托前沿点。这能帮助决策者清晰地看到多增加一个人成本能降低多少从而做出更全面的决策。4. 进阶技巧当问题变得更复杂时现实中的投资和聘用问题往往比上述案例复杂。例如项目间可能存在互斥或依赖关系投了项目A就不能投项目B或者投项目C必须先投项目D候选人之间可能有合作效率问题需要同时聘用某两人才能发挥最大价值。这些都需要在模型中引入额外的约束。4.1 处理项目间的逻辑关系互斥关系项目A和项目B至多选一个。 [ x_A x_B \leq 1 ]依赖关系如果选择项目C则必须选择项目D。 [ x_C \leq x_D \quad \text{或等价地} \quad x_C - x_D \leq 0 ] 这个约束保证了当 ( x_C 1 ) 时( x_D ) 也必须为1当 ( x_C 0 ) 时( x_D ) 可以是0或1。多选一关系项目E、F、G中必须恰好选择一个。 [ x_E x_F x_G 1 ]在LINGO中添加这些约束非常直接。在MATLAB中则需要将它们转化为A*x b或Aeq*x beq的形式添加到相应的矩阵中。4.2 处理固定成本与资源约束在投资问题中有时启动一个项目需要一笔固定的前期成本无论投资额多少。这可以通过引入辅助的0-1变量和“大M法”来建模。假设项目i有一个固定启动成本 ( S_i )只有当 ( x_i 1 )决定投资时这个成本才发生。 我们可以引入一个连续变量 ( y_i ) 表示是否发生固定成本并添加约束 [ y_i \leq M \cdot x_i \ S_i \cdot x_i \leq y_i \ ] 其中 ( M ) 是一个足够大的数。这样当 ( x_i0 ) 时( y_i ) 被强制为0当 ( x_i1 ) 时( y_i ) 必须至少为 ( S_i )在最小化成本的目标下( y_i ) 会取到 ( S_i )。然后将 ( y_i ) 加入目标函数。4.3 模型调试与求解策略从松弛问题开始在求解复杂的整数规划前可以先求解其线性松弛问题即去掉整数约束让变量在[0,1]区间连续变化。松弛问题的最优解提供了一个目标函数值的下界对于最小化问题。如果松弛解恰好是整数解那恭喜你它就是原问题的最优解。如果不是这个下界可以帮助你评估分支定界法的求解进度。利用LINGO的调试功能如果LINGO报告模型无可行解可以使用“求解”菜单下的“调试”功能。LINGO会尝试找出导致不可行的一组最小的约束集合这对于排查模型逻辑错误非常有帮助。MATLAB求解器参数调整对于大规模问题intlinprog的求解时间可能很长。可以尝试调整选项例如options optimoptions(intlinprog, Display, iter, MaxTime, 300); [x, fval] intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, options);Display, iter会输出迭代过程方便观察求解进度。MaxTime可以设置最大求解时间秒防止程序长时间运行。启发式与近似求解对于超大规模的0-1规划比如成千上万个变量精确求解可能不现实。这时可以考虑启发式算法如遗传算法、模拟退火等来寻找一个高质量的近似解。MATLAB的全局优化工具箱提供了这些算法的实现。5. 从求解到决策结果解读与报告拿到求解器的输出x[1,0,1,...],fval48000并不是终点。如何向非技术背景的决策者解释这个结果同样重要。解读解向量的含义清晰地列出被选中的项目或候选人并说明他们如何满足所有约束。例如“我们建议投资项目A、C、E。该组合总投资额XX万预计总净现值YY万风险控制在ZZ且满足了项目间的依赖关系...”进行“What-If”分析这是优化模型最大的价值之一。你可以向决策者展示预算敏感性如果预算增加或减少10%最优方案和最大收益会如何变化约束松弛分析如果风险容忍度稍微提高一点能带来多少收益的提升这可以帮助评估当前约束是否过于严格。参数变动分析如果某个项目的净现值预测发生了波动当前的最优方案还稳健吗在多大范围内波动最优方案不变呈现替代方案如前所述可能存在多个成本相同的最优解或者成本略高但具备其他优势如团队经验更均衡的方案。将这些方案及其优缺点一并呈现将最终的决策权交给管理者。说明模型局限性诚实地告知决策者模型的假设和局限。例如模型中的净现值和风险系数都是点估计实际可能存在不确定性模型没有考虑项目执行过程中的动态调整等。这能增加报告的可信度。通过MATLAB和LINGO我们将整数规划和0-1规划从教科书上的理论变成了辅助实际决策的得力工具。关键在于准确地将现实问题翻译成数学模型然后选择合适的工具高效求解最后将冰冷的数字结果转化为有温度、有洞见的决策建议。这个过程本身就是一次严谨的逻辑思维训练。
![2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符]](http://pic.xiahunao.cn/yaotu/2026学术工具专业测评｜Paperxie全维度性能实测报告[特殊字符])
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
