当前位置：首页 > article >正文

[JuMP.jl] 线性规划

article 2024/12/5 3:35:37

线性规划模型

线性规划是起源最早，使用最为广泛的数学规划模型，

$\begin{aligned} \min_{x \in \mathbb{R}^n} & \sum\limits_{i=1}^n c_i x_i \\ \;\;\text{s.t.} & l_j \le \sum\limits_{i=1}^n a_{ij} x_i \le u_j & j = 1 \ldots m \\ & l_i \le x_i \le u_i & i = 1+m \ldots n.\end{aligned}$

[JuMP] 02 线性规划以及灵敏度分析

例子

using JuMP; import HiGHS; import DataFrames
model = Model(HiGHS.Optimizer)
# 变量
@variable(model, x >= 0); @variable(model, 0 <= y <= 3);@variable(model, z <= 1)  
# 目标函数
@objective(model, Min, 12x + 20y - z)
# 约束
@constraint(model, c1, 6x + 8y >= 100)
@constraint(model, c2, 7x + 12y >= 120)
@constraint(model, c3, x + y <= 20)
# 打印模型
print(model)

$\begin{aligned} \min ~& 12x+20y−z\\ \mathrm{Subject~to} ~ &6x+8y≥100.0\\ &7x+12y≥120.0\\ &x+y≤20.0\\ &x≥0.0\\ &y≥0.0\\ &y≤3.0\\ &z≤1.0 \end{aligned}$

#  求解
optimize!(model)
solution_summary(model; verbose = true)  # 汇总主要信息

线性规划灵敏性分析

report = lp_sensitivity_report(model)
function variable_report(xi)
    return (
        name = name(xi),   # 变量名
        lower_bound = has_lower_bound(xi) ? lower_bound(xi) : -Inf,  #下界
        value = value(xi),  # 数值解
        upper_bound = has_upper_bound(xi) ? upper_bound(xi) : Inf, # 上界
        reduced_cost = reduced_cost(xi),  # 降低成本, 等价于有效变量的影子价格
        obj_coefficient = coefficient(objective_function(model), xi),  # 目标函数的线性系数
         # 目标函数系数的变化范围, 保持基底最优性  
        allowed_decrease = report[xi][1], # 允许减少
        allowed_increase = report[xi][2], # 允许增长
    )
end
variable_report(x)
variable_df =  DataFrames.DataFrame(variable_report(xi) for xi in all_variables(model))

name	lower_bound	value	upper_bound	reduced_cost	obj_coefficient	allowed_decrease
String	Float64	Float64	Float64	Float64	Float64	Float64
1	x	0.0	15.0	Inf	0.0	12.0
2	y	0.0	1.25	3.0	0.0	20.0
3	z	-Inf	1.0	1.0	-1.0	-1.0

约束集合灵敏性

function constraint_report(ci)
    return (
        name = name(ci),  # 变量名
        value = value(ci),  # 约束左侧值
        rhs = normalized_rhs(ci),  # 约束右侧值
        slack = normalized_rhs(ci) - value(ci),
        shadow_price = shadow_price(ci), # 影子价格
        allowed_decrease = report[ci][1], # 基底最优性 
        allowed_increase = report[ci][2], # 基底最优性 
    )
end
c1_report = constraint_report(c1)
constraint_df = DataFrames.DataFrame(
    constraint_report(ci) for (F, S) in list_of_constraint_types(model) for 
    ci in all_constraints(model, F, S) if F == AffExpr
)

name	value	rhs	slack	shadow_price	allowed_decrease	allowed_increase
String	Float64	Float64	Float64	Float64	Float64	Float64
1	c1	100.0	100.0	0.0	-0.25	-4.0
2	c2	120.0	120.0	0.0	-1.5	-3.33333
3	c3	16.25	20.0	3.75	0.0	-3.75

分析问题

basic = filter(row -> iszero(row.reduced_cost), variable_df)  # 过滤等号成立的变量

name	lower_bound	value	upper_bound	reduced_cost	obj_coefficient	allowed_decrease
String	Float64	Float64	Float64	Float64	Float64	Float64
1	x	0.0	15.0	Inf	0.0	12.0
2	y	0.0	1.25	3.0	0.0	20.0

non_basic = filter(row -> !iszero(row.reduced_cost), variable_df)  # 过滤等号不成立的变量
binding = filter(row -> iszero(row.slack), constraint_df)  # 过滤等号成立的约束条件
binding2 = filter(row -> !iszero(row.shadow_price), constraint_df)#  过滤等号不成立的约束条件

查看全文

http://www.kler.cn/a/420667.html