Engee 文档
Notebook

混合整数线性规划问题的解决方案

本例介绍如何解决混合整数线性规划（MILP）问题。这里给出了使用问题导向法制定问题的典型步骤。

我们将使用库 JuMP.jl 和线性优化库 GLPK.jl。

安装库

如果您的环境中没有安装最新版本的JuMP 软件包，请取消注释并运行下面的方框：

In [ ]: 
Pkg.add(["GLPK", "JuMP"])
In [ ]: 
#Pkg.add("JuMP");

要在安装完成后启动新版本的程序库，请单击 "我的账户 "按钮：

screenshot_20240710_134852.png 然后点击 "停止 "按钮：

screenshot_20240710_2.png

按下 "Start Engee "按钮重新启动会话：

screenshot_20240710_135431.png

任务描述

您需要混合不同化学成分的钢材，生产出 25 吨具有特定化学成分的钢材。生产出的钢材应含有总重量 5%的碳和 5%的钼，即 1.25 吨碳和 1.25 吨钼。

优化问题的目标是最大限度地降低混钢成本。

有四种不同的钢锭可供购买。每种钢锭只能购买一个。

| 钢锭 | 重量（吨） | 碳含量 | 钼含量 | 每吨成本 | ----------- | ----------- | ----------- | ----------- | ----------- | | 1 | 5 | 5 | 5 | 3 |$350 | | 2 | 3 | 4 | 3 | $330 | | 3 | 4 | 4 | 5 | 4 |$310 | | 4 | 6 | 3 | 4 | $280 |

此外，还出售三种等级的合金钢和一种等级的废钢。合金钢和废钢可零散购买。

| 合金 | 碳含量 | 钼含量 | 每吨成本 | ----------- | ----------- | ----------- | ----------- | | 1 | 8 | 8 | 6 |$500 | | 2 | 7 | 7 | $450 | | 3 | 6 | 8 |$400 | | Лом | 3 | 9 | $| 100 |

连接图书馆

连接图书馆JuMP ：

In [ ]: 
using JuMP;

连接求解器库GLPK ：

In [ ]: 
using GLPK;

创建优化问题

使用函数Model() 创建一个优化问题，并在括号中指定求解器的名称：

In [ ]: 
steel_prob = Model(GLPK.Optimizer)
Out[0]:
A JuMP Model
├ solver: GLPK
├ objective_sense: FEASIBILITY_SENSE
├ num_variables: 0
├ num_constraints: 0
└ Names registered in the model: none

创建变量ingots ，包含四个值（根据可购买的钢锭数量）。由于钢锭不能以小数购买，因此指定变量类型为Int 。所有变量的下限都是 0，因为我们不能购买负数。每块钢锭只有一份，因此该变量的上限为 1。

In [ ]: 
@variable(steel_prob, ingots[1:4], Int; lower_bound = 0, upper_bound = 1);

创建一个变量alloys ，其中包含三个值（根据可供购买的合金数量）。我们将把废钢单独列为一个变量。由于可购买的合金数量为零，因此无需指定变量类型。

In [ ]: 
@variable(steel_prob, alloys[1:3], lower_bound = 0);

为废钢创建变量scrap 。由于废钢可以按小数购买，因此无需指定变量类型。

In [ ]: 
@variable(steel_prob, scrap, lower_bound = 0);

由于每个钢锭的重量不同，必须先创建变量weightIngots 来计算购买钢锭的成本。计算每个组件的成本，然后创建变量cost ，其中包含购买组件的总成本。作为问题解决方案的一部分，我们将找出该变量的最小值。

In [ ]: 
weightIngots = [5,3,4,6];
costIngots = weightIngots.*[350,330,310,280];
costAlloys = [500,450,400];
costScrap = 100;
cost = sum(costIngots.*ingots) + sum(costAlloys.*alloys) + sum(costScrap*scrap)
Out[0]:
$ 1750 ingots_{1} + 990 ingots_{2} + 1240 ingots_{3} + 1680 ingots_{4} + 500 alloys_{1} + 450 alloys_{2} + 400 alloys_{3} + 100 scrap $

创建一个目标函数，使成本最小化，以解决我们的优化问题：

In [ ]: 
@objective(steel_prob, Min, cost)
Out[0]:
$ 1750 ingots_{1} + 990 ingots_{2} + 1240 ingots_{3} + 1680 ingots_{4} + 500 alloys_{1} + 450 alloys_{2} + 400 alloys_{3} + 100 scrap $

创建一个变量totalWeight ，其中包含所有组件的总重量：

In [ ]: 
totalWeight = sum(weightIngots.*ingots) + sum(alloys) + scrap
Out[0]:
$ 5 ingots_{1} + 3 ingots_{2} + 4 ingots_{3} + 6 ingots_{4} + alloys_{1} + alloys_{2} + alloys_{3} + scrap $

计算钢中碳的总重量：

In [ ]: 
carbonIngots = [5,4,5,3]/100;
carbonAlloys = [8,7,6]/100;
carbonScrap = 3/100;
totalCarbon = sum((weightIngots.*carbonIngots).*ingots) + sum(carbonAlloys.*alloys) + sum(carbonScrap.*scrap)
Out[0]:
$ 0.25 ingots_{1} + 0.12 ingots_{2} + 0.2 ingots_{3} + 0.18 ingots_{4} + 0.08 alloys_{1} + 0.07 alloys_{2} + 0.06 alloys_{3} + 0.03 scrap $

计算钢中钼的总质量：

In [ ]: 
molybIngots = [3,3,4,4]/100;
molybAlloys = [6,7,8]/100;
molybScrap = 9/100;
totalMolyb = sum((weightIngots.*molybIngots).*ingots) + sum(molybAlloys.*alloys) + sum(molybScrap.*scrap)
Out[0]:
$ 0.15 ingots_{1} + 0.09 ingots_{2} + 0.16 ingots_{3} + 0.24 ingots_{4} + 0.06 alloys_{1} + 0.07 alloys_{2} + 0.08 alloys_{3} + 0.09 scrap $

制定条件

为解决优化问题设定的第一个条件是，获得的钢材总重量应为 25 吨：

In [ ]: 
@constraint(steel_prob, C1, totalWeight == 25)
Out[0]:
$$ 5 ingots_{1} + 3 ingots_{2} + 4 ingots_{3} + 6 ingots_{4} + alloys_{1} + alloys_{2} + alloys_{3} + scrap = 25 $$

设置优化问题的第二个求解条件，即所得钢材中碳的总重量应为 1.25 吨：

In [ ]: 
@constraint(steel_prob, C2, totalCarbon == 1.25)
Out[0]:
$$ 0.25 ingots_{1} + 0.12 ingots_{2} + 0.2 ingots_{3} + 0.18 ingots_{4} + 0.08 alloys_{1} + 0.07 alloys_{2} + 0.06 alloys_{3} + 0.03 scrap = 1.25 $$

设定优化问题的第三个求解条件，即所得钢中钼的总重量应为 1.25 吨：

In [ ]: 
@constraint(steel_prob, C3, totalMolyb == 1.25)
Out[0]:
$$ 0.15 ingots_{1} + 0.09 ingots_{2} + 0.16 ingots_{3} + 0.24 ingots_{4} + 0.06 alloys_{1} + 0.07 alloys_{2} + 0.08 alloys_{3} + 0.09 scrap = 1.25 $$

问题的解决方案

解决优化问题：

In [ ]: 
optimize!(steel_prob)

检查是否找到了最优解：

In [ ]: 
if !is_solved_and_feasible(steel_prob)
    error("Solver did not find an optimal solution")
end

将感兴趣的值保存在变量中。您可以使用函数round ，对过于精确的数值进行四舍五入。

In [ ]: 
ingots_value = value.(ingots);
alloys_value = round.(value.(alloys); digits = 3);
scrap_value = round(value.(scrap); digits = 3);
fval = objective_value(steel_prob);

输出优化结果：

In [ ]: 
println("Ingots: ", ingots_value)
println("Alloys: ", alloys_value)
println("Scrap: ", scrap_value)
println("Objective Value: ", fval)

Ingots: [1.0, 1.0, 0.0, 1.0]
Alloys: [7.25, 0.0, 0.25]
Scrap: 3.5
Objective Value: 8495.0

最佳购买价格为 8495 美元。因此，应购买钢锭 1、2 和 4，但不应购买钢锭 3。同时购买 7.25 吨合金 1、0.25 吨合金 3 和 3.5 吨废钢。

结论

在本例中，我们解决了一个混合整数线性规划问题，并找到了以最低成本生产 25 吨化学成分符合要求的钢材所需的最佳部件组和数量。