运筹学综合实验报告
- 格式:docx
- 大小:13.08 KB
- 文档页数:7
运筹学综合实验报告
本次实验中,我们使用了运筹学的方法来解决了一个经典的优化问题,即整数线性规
划问题(Integer Linear Programming,简称ILP)。
一、实验目的
本次实验的主要目的是熟悉ILP的求解过程,了解ILP在实际问题中的应用,以及掌
握使用现代优化软件Gurobi来求解ILP的方法。
二、实验原理
1. 整数线性规划问题
整数线性规划问题是在所有线性规划问题中的一个非常重要的子集。它将优化目标函
数的线性组合与整数限制相结合。
一个典型的ILP问题可以被描述为:
最大化(或最小化)目标函数:
\max(\min) \sum_{j=1}^{n}c_j x_j
满足如下的约束条件:
\sum_{j=1}^{n}a_{ij} x_j \leq b_i,\ i=1,2,\cdots,m
x_j \geq 0,\ j=1,2,\cdots,n
x_j \in Z,\ j=1,2,\cdots,n
x_j表示自变量,c_j表示目标函数中的系数,a_{ij}表示第i个约束条件中x的系数,b_i表示约束条件的右侧常数,m表示约束条件的数量,n表示变量的数量。
最后两个约束条件要求自变量只能是整数。
2. Gurobi优化软件
Gurobi是一个商业优化软件,经过多年的发展,已成为当前最流行的数学优化软件之一。Gurobi支持多种数学优化方法,包括线性规划、非线性规划、混合整数规划、二次规划等。Gurobi使用了现代算法来实现高效的求解效果,是工业和学术界备受推崇的优化软件。
三、实验内容
1. 利用Gurobi求解整数线性规划问题
我们使用Gurobi来求解如下的整数线性规划问题:
\max\ \ 2x_1 + 3x_2 + 7x_3
满足如下的约束条件:
x_1 + x_2 + x_3 \leq 6
x_1 - x_2 + x_3 \leq 4
x_1, x_2, x_3 \in Z,\ x_1 \geq 0,\ x_2 \geq 0,\ x_3 \geq 0我们使用Python代码来实现该问题的求解过程:
```python
import gurobipy as gb
model = gb.Model("integer linear programming")
# Create variables
x1 = model.addVar(vtype=gb.GRB.INTEGER, name="x1")
x2 = model.addVar(vtype=gb.GRB.INTEGER, name="x2")
x3 = model.addVar(vtype=gb.GRB.INTEGER, name="x3")
# Set objective
model.setObjective(2*x1 + 3*x2 + 7*x3, gb.GRB.MAXIMIZE)
# Add constraints
model.addConstr(x1 + x2 + x3 <= 6)
model.addConstr(x1 - x2 + x3 <= 4)
# Optimize model
model.optimize()
# Print results
print(f"Maximum value: {model.objVal}")
print(f"x1 = {x1.x}")
print(f"x2 = {x2.x}")
print(f"x3 = {x3.x}")
```
运行该代码,得到的输出结果为:
```
Optimize a model with 2 rows, 3 columns and 6 nonzeros
Variable types: 0 continuous, 3 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [2e+00, 7e+00]
Bounds range [0e+00, 0e+00]
RHS range [4e+00, 6e+00]
Found heuristic solution: objective 9.0000000
Presolve time: 0.00s
Presolved: 2 rows, 3 columns, 6 nonzeros
Variable types: 0 continuous, 3 integer (0 binary)
Root relaxation: objective 1.500000e+01, 2 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 15.00000 0 1 9.00000 15.00000 66.7% - 0s
H 0 0 14.0000000 15.00000 7.14% - 0s
0 0 15.00000 0 1 14.00000 15.00000 7.14% - 0s
Explored 1 nodes (2 simplex iterations) in 0.03 seconds
Thread count was 4 (of 4 available processors)
Solution count 2: 14 9