Main Content

本页的翻译已过时。点击此处可查看最新英文版本。

混合整数线性规划基础:基于求解器

此示例说明如何求解混合整数线性问题。该示例虽不复杂,但它说明了使用 intlinprog 语法表示问题的典型步骤。

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

问题描述

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

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

IngotWeightinTons%Carbon%MolybdenumCostTon1553$3502343$3303454$3104634$280

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

Alloy%Carbon%MolybdenumCostTon186$500277$450368$400Scrap39$100

要表示此问题,首先要确定控制变量。以变量 x(1) = 1 表示您购买钢锭 1x(1) = 0 表示您不购买此钢锭。类似地,变量 x(2)x(4) 也是二元变量,用于指示您是否购买钢锭 24

变量 x(5)x(7) 分别是您购买的合金 123的吨数,x(8) 是您购买的废钢的吨数。

MATLAB® 表示

通过指定 intlinprog 的输入来表示问题。相关 intlinprog 语法如下:

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

intlinprog 创建输入,从第一个 (f) 到最后一个 (ub) 都包含在内。

f 是由成本系数组成的向量。表示钢锭成本的系数是钢锭重量与其每吨成本之积。

f = [350*5,330*3,310*4,280*6,500,450,400,100];

整数变量是前四个。

intcon = 1:4;

提示:要指定二元变量,请在 intcon 中将变量设置为整数,并指定其下界为 0,上界为 1

该问题没有线性不等式约束,因此 Ab 是空矩阵 ([])。

A = [];
b = [];

该问题有三个等式约束。第一个约束是总重量为 25 吨。

5*x(1) + 3*x(2) + 4*x(3) + 6*x(4) + x(5) + x(6) + x(7) + x(8) = 25

第二个约束是碳的重量为 25 吨的 5%,即 1.25 吨。

5*0.05*x(1) + 3*0.04*x(2) + 4*0.05*x(3) + 6*0.03*x(4)

+ 0.08*x(5) + 0.07*x(6) + 0.06*x(7) + 0.03*x(8) = 1.25

第三个约束是钼的重量为 1.25 吨。

5*0.03*x(1) + 3*0.03*x(2) + 4*0.04*x(3) + 6*0.04*x(4)

+ 0.06*x(5) + 0.07*x(6) + 0.08*x(7) + 0.09*x(8) = 1.25

指定约束,即采用矩阵形式的 Aeq*x = beq。

Aeq = [5,3,4,6,1,1,1,1;
    5*0.05,3*0.04,4*0.05,6*0.03,0.08,0.07,0.06,0.03;
    5*0.03,3*0.03,4*0.04,6*0.04,0.06,0.07,0.08,0.09];
beq = [25;1.25;1.25];

每个变量都以零为下界。整数变量以 1 为上界。

lb = zeros(8,1);
ub = ones(8,1);
ub(5:end) = Inf; % No upper bound on noninteger variables

求解问题

现已具备所有输入,请调用求解器。

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
LP:                Optimal objective value is 8125.600000.                                          

Cut Generation:    Applied 3 mir cuts.                                                              
                   Lower bound is 8495.000000.                                                      
                   Relative gap is 0.00%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap
tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default
value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

查看解。

x,fval
x = 8×1

    1.0000
    1.0000
         0
    1.0000
    7.2500
         0
    0.2500
    3.5000

fval = 8.4950e+03

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

设置 intcon = [],以查看在无整数约束情况下求解问题的效果。解不同且不现实,因为钢锭必须整块购买。

相关主题