Lib.rs

› 算法
#线性规划 #优化 #lp #单纯形 #模型 #算法 #丹齐格

linprog

一个线性规划库

由 Jonathan 编写

1 个不稳定版本

0.3.1 2019年10月11日
0.3.0 2019年10月11日

1746 在 算法 中

MIT 许可证

34KB
602 行

linprog

一个用于优化线性规划（LP）模型的 Rust 库，使用 丹齐格单纯形算法 实现。Linprog 提供了创建和优化动态 LP 模型的工具。

此库（尚不支持 🐢）不支持混合整数规划。

Linprog 在 crates.io 上提供！

目录

用法

将其添加到您的 Cargo.toml

[dependencies]
linprog = "0.3"

然后将库引入作用域

use linprog::{
    Model,
    Objective,
    Summand,
    Operator,
    Var
};

理解 linprog 中 LP 的生命周期

在此库中，线性规划通过一个名为 Model 的数据类型表示，创建如下

let mut model = Model::new("My LP", Objective::Max);

Model 的生命周期遵循三个严格分离的阶段

  • 在第一个（初始设置）阶段，可以注册变量。
let mut vars: Vec<Var> = vec![];
vars.push(model.reg_var(2.0));
// --snip--
  • 在第二个阶段，可以注册约束。
// model.update();
model.reg_constr(vec![Summand(1.0, &vars[0])], Operator::Le, 10.0);
// --snip--
  • 在第三个阶段，可以对 Model 进行优化。
// model.update();
model.optimize();

可以使用 update 方法显式地将 Models 的阶段更新到下一个阶段。或者隐式地，通过调用下一个阶段的方法。

在将变量或约束提交给 Model 后，它们不能再更改（阶段不能回退或修改）。

示例

下面的代码可以用于优化以下模型

max. 3x + 5y
st.   x + 2y <= 170
          3y <= 180

Rust 实现

let mut model = Model::new("Readme example", Objective::Max);
let mut vars: Vec<Var> = vec![];

vars.push(model.reg_var(3.0));
vars.push(model.reg_var(5.0));

model.reg_constr(
    vec![Summand(1.0, &vars[0]), Summand(2.0, &vars[1])],
    Operator::Le,
    170.0,
);
model.reg_constr(
    vec![Summand(1.0, &vars[0]), Summand(1.0, &vars[1])],
    Operator::Le,
    150.0,
);
model.reg_constr(
    vec![Summand(0.0, &vars[0]), Summand(3.0, &vars[1])],
    Operator::Le,
    180.0,
);

model.optimize();
print!("{}", model);

此程序将打印以下内容

Model "Readme example" [optimized]:
    Optimum: 490
    Variable "1": 130
    Variable "2": 20

带故事的示例

假设一家公司生产三种产品

  • 产品 A 售价 50$
  • 产品 B 售价 100$
  • 产品 C 售价 110$

公司有三台机器

  • 机器 X 每周最大运行分钟数为 2500
  • 机器 Y 每周最大运行分钟数为 2000
  • 机器 Z 每周最大运行时间 450 分钟

每个产品都需要由机器处理一定的时间

  • 一个单位的 A 需要
    • 10   分钟在 X
    • 4     分钟在 Y
    • 1     分钟在 Z
  • 一个单位的 B 需要
    • 5     分钟在 X
    • 10   分钟在 Y
    • 1.5 分钟在 Z
  • 一个单位的 C 需要
    • 6     分钟在 X
    • 9     分钟在 Y
    • 3     分钟在 Z

问题是：公司希望为每个产品生产多少单位，以最大化其利润？

在 Rust 程序中，数据可能看起来像这样

let products: HashMap<&str, f64> = [
    ("Product A", 50.0),
    ("Product B", 100.0),
    ("Product C", 110.0),
].iter().cloned().collect();

let machines: HashMap<&str, f64> = [
    ("Machine X", 2500.0),
    ("Machine Y", 2000.0),
    ("Machine Z", 450.0),
].iter().cloned().collect();

let mut time_needed: HashMap<(&str, &str), f64> = HashMap::new();
time_needed.insert(("Product A", "Machine X"), 10.0);
time_needed.insert(("Product A", "Machine Y"), 4.0);
time_needed.insert(("Product A", "Machine Z"), 1.0);

time_needed.insert(("Product B", "Machine X"), 5.0);
time_needed.insert(("Product B", "Machine Y"), 10.0);
time_needed.insert(("Product B", "Machine Z"), 1.5);

time_needed.insert(("Product C", "Machine X"), 6.0);
time_needed.insert(("Product C", "Machine Y"), 9.0);
time_needed.insert(("Product C", "Machine Z"), 3.0);

定义数据的一种更简洁的方法可能如下

let product_price: [f64;3] = [50.0, 100.0, 110.0];
let machine_max_workload: [f64;3] = [2500.0, 2000.0, 450.0];
let prod_machine_time_needed: [[f64;3];3] = [
    [10.0, 4.0, 1.0],
    [5.0, 10.0, 1.5],
    [6.0, 9.0, 3.0],
];

为了本例，我将使用前两种版本中的前一种。

现在开始构建模型

let mut model = Model::new("ABC_Company", Objective::Max);
let mut vars: HashMap<&str, Var> = HashMap::new();

然后注册变量及其名称和价格

for (product, &price) in &products {
    vars.insert(product, model.reg_var_with_name(price, product));
}

注册约束条件

for (&machine, &max_time) in &machines {
    let mut sum: Vec<Summand> = Vec::new();
    for (&product, _) in &products {
        sum.push(Summand(time_needed[&(product, machine)], &vars[product]));
    }
    model.reg_constr(sum, Operator::Le, max_time);
}

最后，模型得到优化，结果被打印出来

model.optimize();
print!("{}", model);

输出将如下所示

Model "ABC_Company" [optimized]:
    Optimum: 22738.095238095237
    Variable "Product C": 47.61904761904763
    Variable "Product A": 178.57142857142856
    Variable "Product B": 85.71428571428572

可以通过这种方式自定义解决方案的显示

println!("\nThe optimum is at {:.*}$.", 2, model.optimum().unwrap());
for (product, var) in &vars {
    println!("We need to produce {} units of product {}.", model.x(&var).unwrap().floor(), product);
}

从而得到以下输出

The optimum is at 22738.10$.
We need to produce 85 units of product Product B.
We need to produce 178 units of product Product A.
We need to produce 47 units of product Product C.

请随意使用它 🙆‍♀️

您如何帮助

作者

  • Jonathan S. - 开发者 - jonathansc(at)airmail.cc

许可证

本项目受 MIT 许可证许可 - 有关详细信息，请参阅 LICENSE 文件

依赖项

~560–790KB
~11K SLoC