南京哪家做网站好,做冷库用什么网站发帖子好,建筑木工模板包工价格,中企z云邮企业邮箱登录文章目录 简单回顾线性规划LP整数规划IP0-1规划 简单回顾
线性规划是数学规划中的一类最简单规划问题#xff0c;常见的线性规划是一个有约束的#xff0c;变量范围为有理数的线性规划。如#xff1a; 使用matlab的linprog函数即可求解简单的线性规划问题#xff0c;可以参… 文章目录 简单回顾线性规划LP整数规划IP0-1规划 简单回顾
线性规划是数学规划中的一类最简单规划问题常见的线性规划是一个有约束的变量范围为有理数的线性规划。如 使用matlab的linprog函数即可求解简单的线性规划问题可以参考这篇博客 MATLAB求解线性规划含整数规划和0-1规划问题
matlab求解线性规划LP问题需要化为最小化问题所有约束条件必须为≤类型限制较多。本文介绍使用pythongurobi进行求解。 pythongurobi介绍参考这篇博客 gurobi最新下载安装教程 2023.11
线性规划LP import gurobipy
from gurobipy import GRB# 创建模型
c [7, 12]
a [[9, 4],[4, 5],[3, 10]]
b [300, 200, 300]
MODEL gurobipy.Model(Example)# 创建变量
x MODEL.addVars(2, lb0, ubgurobipy.GRB.INFINITY, namex)# 更新变量环境
MODEL.update()# 创建目标函数
MODEL.setObjective(x.prod(c), gurobipy.GRB.MAXIMIZE)# 创建约束条件
MODEL.addConstrs(x.prod(a[i]) b[i] for i in range(3))# 执行线性规划模型
MODEL.optimize()
print(Obj:, MODEL.objVal)
for v in MODEL.getVars():print(f{v.VarName}{round(v.X,3)})
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 3 rows, 2 columns and 6 nonzeros
Model fingerprint: 0x6b25b35d
Coefficient statistics:Matrix range [3e00, 1e01]Objective range [7e00, 1e01]Bounds range [0e00, 0e00]RHS range [2e02, 3e02]
Presolve time: 0.01s
Presolved: 3 rows, 2 columns, 6 nonzerosIteration Objective Primal Inf. Dual Inf. Time0 3.2500000e30 2.812500e30 3.250000e00 0s2 4.2800000e02 0.000000e00 0.000000e00 0sSolved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective 4.280000000e02
Obj: 428.0
x[0]20.0
x[1]24.0最终可得最优解为x 20, y 24, 最优值为428。 gurobi对最大化问题、最小化问题大于等于和小于等于约束都支持。
整数规划IP import gurobipy
from gurobipy import GRB
import numpy as np# 创建模型
c [3, 2]
a [[2, 3],[4, 2]]
b [14, 18]
MODEL gurobipy.Model(Example)# 创建变量
#x MODEL.addVars(2, lb0, ubgurobipy.GRB.INFINITY, namex)x1 MODEL.addVar(vtypeGRB.INTEGER,lb0,ubGRB.INFINITY, namex1)
x2 MODEL.addVar(vtypeGRB.INTEGER,lb0,ubGRB.INFINITY, namex2)
# 更新变量环境MODEL.update()# 创建目标函数
MODEL.setObjective(c[0]*x1c[1]*x2, gurobipy.GRB.MAXIMIZE)# 创建约束条件
for i in range(2):MODEL.addConstr(a[i][0]*x1 a[i][1]*x2 b[i])# 执行线性规划模型
MODEL.optimize()
print(Obj:, MODEL.objVal)
for v in MODEL.getVars():print(f{v.VarName}{round(v.X,3)})Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a6e8bd
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:Matrix range [2e00, 4e00]Objective range [2e00, 3e00]Bounds range [0e00, 0e00]RHS range [1e01, 2e01]
Found heuristic solution: objective 14.0000000
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)Solution count 1: 14 Optimal solution found (tolerance 1.00e-04)
Best objective 1.400000000000e01, best bound 1.400000000000e01, gap 0.0000%
Obj: 14.0
x14.0
x21.0可得该整数规划问题的最优解为x1 4, x2 1,最优值为14。
如果解其对应的松弛问题
import gurobipy
from gurobipy import GRB
import numpy as np# 创建模型
c [3, 2]
a [[2, 3],[4, 2]]
b [14, 18]
MODEL gurobipy.Model(Example)# 创建变量
x MODEL.addVars(2, lb0, ubgurobipy.GRB.INFINITY, namex)# 更新变量环境MODEL.update()# 创建目标函数
MODEL.setObjective(x.prod(c), gurobipy.GRB.MAXIMIZE)# 创建约束条件
MODEL.addConstrs(x.prod(a[i]) b[i] for i in range(2))# 执行线性规划模型
MODEL.optimize()
print(Obj:, MODEL.objVal)
for v in MODEL.getVars():print(f{v.VarName}{round(v.X,3)})Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a42e7d
Coefficient statistics:Matrix range [2e00, 4e00]Objective range [2e00, 3e00]Bounds range [0e00, 0e00]RHS range [1e01, 2e01]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzerosIteration Objective Primal Inf. Dual Inf. Time0 5.0000000e30 2.750000e30 5.000000e00 0s2 1.4750000e01 0.000000e00 0.000000e00 0sSolved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective 1.475000000e01
Obj: 14.75
x[0]3.25
x[1]2.5可以发现对应的解是x1 3.25, x2 2.5, 最优值为14.75。松弛问题的最优解总是优于整数规划问题的。
0-1规划
无论是matlab的linprog函数还是gurobi0-1规划实际上只需要在整数规划的基础上让决策变量的定义域在0-1之间即可。
仍然是上面的同一个问题
## 0-1规划import gurobipy
from gurobipy import GRB# 创建模型
c [3, 2]
a [[2, 3],[4, 2]]
b [14, 18]
MODEL gurobipy.Model(Example)# 创建变量
#x MODEL.addVars(2, lb0, ubgurobipy.GRB.INFINITY, namex)x1 MODEL.addVar(vtypeGRB.INTEGER,lb0,ub1, namex1)
x2 MODEL.addVar(vtypeGRB.INTEGER,lb0,ub1, namex2)
# 更新变量环境MODEL.update()# 创建目标函数
MODEL.setObjective(c[0]*x1c[1]*x2, gurobipy.GRB.MAXIMIZE)# 创建约束条件
for i in range(2):MODEL.addConstr(a[i][0]*x1 a[i][1]*x2 b[i])# 执行线性规划模型
MODEL.optimize()
print(Obj:, MODEL.objVal)
for v in MODEL.getVars():print(f{v.VarName}{round(v.X,3)})Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 3 rows, 2 columns and 6 nonzeros
Model fingerprint: 0x6b25b35d
Coefficient statistics:Matrix range [3e00, 1e01]Objective range [7e00, 1e01]Bounds range [0e00, 0e00]RHS range [2e02, 3e02]
Presolve time: 0.01s
Presolved: 3 rows, 2 columns, 6 nonzerosIteration Objective Primal Inf. Dual Inf. Time0 3.2500000e30 2.812500e30 3.250000e00 0s2 4.2800000e02 0.000000e00 0.000000e00 0sSolved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective 4.280000000e02
Obj: 428.0
x[0]20.0
x[1]24.0
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 3 rows, 6 columns and 18 nonzeros
Model fingerprint: 0x157f6a4a
Coefficient statistics:Matrix range [9e00, 6e01]Objective range [6e00, 1e01]Bounds range [0e00, 0e00]RHS range [6e01, 2e02]
Presolve time: 0.01s
Presolved: 3 rows, 6 columns, 18 nonzerosIteration Objective Primal Inf. Dual Inf. Time0 0.0000000e00 4.187500e01 0.000000e00 0s3 2.9842520e01 0.000000e00 0.000000e00 0sSolved in 3 iterations and 0.01 seconds (0.00 work units)
Optimal objective 2.984251969e01
Obj: 29.84251968503937
x[0]0.0
x[1]0.433
x[2]0.0
x[3]4.252
x[4]0.0
x[5]0.0
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a6e8bd
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:Matrix range [2e00, 4e00]Objective range [2e00, 3e00]Bounds range [0e00, 0e00]RHS range [1e01, 2e01]
Found heuristic solution: objective 14.0000000
Presolve time: 0.00s
Presolved: 2 rows, 2 columns, 4 nonzeros
Variable types: 0 continuous, 2 integer (0 binary)Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)Solution count 1: 14 Optimal solution found (tolerance 1.00e-04)
Best objective 1.400000000000e01, best bound 1.400000000000e01, gap 0.0000%
Obj: 14.0
x14.0
x21.0
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x15a42e7d
Coefficient statistics:Matrix range [2e00, 4e00]Objective range [2e00, 3e00]Bounds range [0e00, 0e00]RHS range [1e01, 2e01]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzerosIteration Objective Primal Inf. Dual Inf. Time0 5.0000000e30 2.750000e30 5.000000e00 0s2 1.4750000e01 0.000000e00 0.000000e00 0sSolved in 2 iterations and 0.01 seconds (0.00 work units)
Optimal objective 1.475000000e01
Obj: 14.75
x[0]3.25
x[1]2.5
Gurobi Optimizer version 10.0.3 build v10.0.3rc0 (win64)CPU model: Intel(R) Core(TM) i7-8565U CPU 1.80GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0xdff3d373
Variable types: 0 continuous, 2 integer (0 binary)
Coefficient statistics:Matrix range [2e00, 4e00]Objective range [2e00, 3e00]Bounds range [1e00, 1e00]RHS range [1e01, 2e01]
Found heuristic solution: objective 5.0000000Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 8 available processors)Solution count 1: 5 Optimal solution found (tolerance 1.00e-04)
Best objective 5.000000000000e00, best bound 5.000000000000e00, gap 0.0000%
Obj: 5.0
x11.0
x21.0可得0-1规划的最优解是x1 x2 1, 最优值 5。 当然0-1规划的典型应用场景是指派问题、运输问题、排班问题等。
