混合整数线性规划基础:基于问题
此示例说明如何求解混合整数线性问题。该示例并不复杂,但它说明了使用基于问题的方法表示问题的典型步骤。有关展示此示例的视频,请参阅使用优化建模求解混合整数线性规划问题。
要了解如何通过基于求解器的方法处理此问题,请参阅混合整数线性规划基础:基于求解器。
问题描述
您要混合具有不同化学组成的钢材,以获得 25 吨具有某一特定化学组成的钢材。所得钢材应包含 5% 的碳和 5% 的钼(以重量计),即 25 吨 *5% = 1.25 吨碳和 1.25 吨钼。目标是将混合钢材的成本降至最低。
此问题摘自以下文献:Carl-Henrik Westerberg, Bengt Bjorklund, and Eskil Hultman, “An Application of Mixed Integer Programming in a Swedish Steel Mill.”Interfaces February 1977 Vol. 7, No. 2 pp. 39–43,摘要可见于 https://doi.org/10.1287/inte.7.2.39。
有四种钢锭可供购买。每种钢锭只能购买一块。
有三种等级的合金钢和一种等级的废钢可供购买。合金和废钢不必整吨购买。
表示问题
要表示此问题,首先要确定控制项变量。以变量 ingots(1) = 1
表示您购买钢锭 1,ingots(1) = 0
表示您不购买此钢锭。类似地,变量 ingots(2)
至 ingots(4)
也是二元变量,用于指示您是否购买钢锭 2 至 4。
变量 alloys(1)
至 alloys(3)
分别是您购买的合金 1、2 和 3 的吨数,scrap
是您购买的废钢的吨数。
steelprob = optimproblem; ingots = optimvar('ingots',4,'Type','integer','LowerBound',0,'UpperBound',1); alloys = optimvar('alloys',3,'LowerBound',0); scrap = optimvar('scrap','LowerBound',0);
创建与变量相关联的成本表达式。
weightIngots = [5,3,4,6]; costIngots = weightIngots.*[350,330,310,280]; costAlloys = [500,450,400]; costScrap = 100; cost = costIngots*ingots + costAlloys*alloys + costScrap*scrap;
将成本作为目标函数包含在问题中。
steelprob.Objective = cost;
该问题有三个等式约束。第一个约束是总重量为 25 吨。计算钢的重量。
totalWeight = weightIngots*ingots + sum(alloys) + scrap;
第二个约束是碳的重量为 25 吨的 5%,即 1.25 吨。计算钢中碳的重量。
carbonIngots = [5,4,5,3]/100; carbonAlloys = [8,7,6]/100; carbonScrap = 3/100; totalCarbon = (weightIngots.*carbonIngots)*ingots + carbonAlloys*alloys + carbonScrap*scrap;
第三个约束是钼的重量为 1.25 吨。计算钢中钼的重量。
molybIngots = [3,3,4,4]/100; molybAlloys = [6,7,8]/100; molybScrap = 9/100; totalMolyb = (weightIngots.*molybIngots)*ingots + molybAlloys*alloys + molybScrap*scrap;
在问题中包含约束。
steelprob.Constraints.conswt = totalWeight == 25; steelprob.Constraints.conscarb = totalCarbon == 1.25; steelprob.Constraints.consmolyb = totalMolyb == 1.25;
求解问题
现已具备所有输入,请调用求解器。
[sol,fval] = solve(steelprob);
Solving problem using intlinprog. Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms Presolving model 3 rows, 8 cols, 24 nonzeros 3 rows, 8 cols, 18 nonzeros Solving MIP model with: 3 rows 8 cols (4 binary, 0 integer, 0 implied int., 4 continuous) 18 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 8125.6 inf inf 0 0 0 4 0.0s R 0 0 0 0.00% 8495 8495 0.00% 5 0 0 5 0.0s Solving report Status Optimal Primal bound 8495 Dual bound 8495 Gap 0% (tolerance: 0.01%) Solution status feasible 8495 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.01 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 5 (total) 0 (strong br.) 1 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06.
查看解。
sol.ingots
ans = 4×1
1
1
0
1
sol.alloys
ans = 3×1
7.2500
0
0.2500
sol.scrap
ans = 3.5000
fval
fval = 8495
最优购买成本为 8495 美元。购买钢锭 1、2 和 4,但不购买 3,并购买 7.25 吨合金 1、0.25 吨合金 3 和 3.5 吨废钢。