混合整数线性规划基础：基于求解器 -凯发k8网页登录

问题描述

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

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

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

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

变量 x(5) 至 x(7) 分别是您购买的合金 1、2 和 3的吨数，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。

该问题没有线性不等式约束，因此 a 和 b 是空矩阵 ([])。

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 美元。购买钢锭 1、2 和 4，但不购买 3，并购买 7.25 吨合金 1、0.25 吨合金 3 和 3.5 吨废钢。

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