混合整数线性规划基础：基于问题

此示例说明如何求解混合整数线性问题。该示例并不复杂，但它说明了使用基于问题的方法表示问题的典型步骤。有关展示此示例的视频，请参阅使用优化建模求解混合整数线性规划问题。

要了解如何通过基于求解器的方法处理此问题，请参阅混合整数线性规划基础：基于求解器。

问题描述

您要混合具有不同化学组成的钢材，以获得 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。

有四种钢锭可供购买。每种钢锭只能购买一块。

$\begin{array}{ccccc} I n g o t & W e i g h t i n T o n s & % C a r b o n & % M o l y b d e n u m & \frac{C o s t}{T o n} \\ 1 & 5 & 5 & 3 & $ 350 \\ 2 & 3 & 4 & 3 & $ 330 \\ 3 & 4 & 5 & 4 & $ 310 \\ 4 & 6 & 3 & 4 & $ 280 \end{array}$

有三种等级的合金钢和一种等级的废钢可供购买。合金和废钢不必整吨购买。

$\begin{array}{cccc} A l l o y & % C a r b o n & % M o l y b d e n u m & \frac{C o s t}{T o n} \\ 1 & 8 & 6 & $ 500 \\ 2 & 7 & 7 & $ 450 \\ 3 & 6 & 8 & $ 400 \\ S c r a p & 3 & 9 & $ 100 \end{array}$

表示问题

要表示此问题，首先要确定控制项变量。以变量 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.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Matrix [3e-02, 6e+00]
  Cost   [1e+02, 2e+03]
  Bound  [1e+00, 1e+00]
  RHS    [1e+00, 2e+01]
Presolving model
3 rows, 8 cols, 24 nonzeros  0s
3 rows, 8 cols, 18 nonzeros  0s

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.02 (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

sol.alloys

sol.scrap

ans = 
3.5000

fval

fval = 
8495

最优购买成本为 8495 美元。购买钢锭 1、2 和 4，但不购买 3，并购买 7.25 吨合金 1、0.25 吨合金 3 和 3.5 吨废钢。

混合整数线性规划基础：基于问题

问题描述

表示问题

求解问题

另请参阅

主题