Engee 文档
Notebook

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

这个例子展示了如何解决混合整数线性规划（英文Mixed Integer Linear Programming，MILP）的问题。 以下是使用面向问题的方法制定问题的典型步骤。

我们将使用[跳转的功能。jl]图书馆(https://github.com/jump-dev/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 | 3 | $350 |
| 2 | 3 | 4 | 3 | $330 |
| 3 | 4 | 5 | 4 | $310 |
| 4 | 6 | 3 | 4 | $280 |

三个等级的合金钢和一个等级的废钢也可以出售. 合金钢和废料可以部分购买.

/合金/%碳/%钼/每吨成本|
| ----------- | ----------- | ----------- | ----------- |
| 1 | 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

最佳购买价格为$8,495。 因此，有必要购买元宝1，2和4，但不是3。 并且还要采购7.25吨合金1、0.25吨合金3和3.5吨废钢。

结论

在这个例子中，我们解决了混合整数线性规划的问题，并找到了最优的组件集和数量，以最低价格生产具有所需化学成分的25吨钢。