用DOcplex建立线性规划模型

发表于 更新于 分类于 阅读次数：

模型建立基本步骤

建立一个数学规划模型，需要三个步骤：

  1. 定义决策变量
  2. 生成约束条件（关于变量的关系表达式）
  3. 定义目标函数

定义决策变量

模型中的决策变量可以通过Model类中的内置方法定义，定义时可以一次生成一个决策变量、决策变量列表或决策变量字典。下表列出了常用的决策变量定义方法：

Function Creates
binary_var() 单个二进制变量
binary_var_list() 二进制变量列表
binary_var_dict() 二进制变量字典
binary_var_matrix() 二进制变量矩阵
integer_var() 单个整数变量
integer_var_list() 整数变量列表
integer_var_dict() 整数变量字典
integer_var_matrix() 整数变量矩阵
continuous_var() 单个连续变量
continuous_var_list() 连续变量列表
continuous_var_dict() 连续变量字典
continuous_var_matrix() 连续变量矩阵

详细函数的使用方法请参考docplex.MP参考手册。

目标函数

可以通过modle.minimize()和model.maximize()定义模型的目标函数，其参数为决策变量的线性表达式。譬如：

1
model.minimize(model.total_inside_cost + mdl.total_outside_cost)

生成约束条件

线性规划模型中的约束条件是决策变量的线性表达式。Python中的算数运算符（+,-,*，/）和关系运算符（==,<=,>=）可以直接使用，譬如：如果x,y,z是决策变量，3*x + 5*y + 7*z就是一个合法的线性表达式，3*x + 5*y + 7*z <= 1就是一个约束条件。

更多情况下，线性规划模型中约束条件为聚合表达式，譬如\(\sum_{i \in N} x_{i} \leq 1\)。DOcplex.MP可以通过Model.sum方法生成类似约束，model.sum(x[i] for i in N) <= 1

下表给出了常用添加约束的方法：

Function Add
add_constraint(ct, ctname=None) 添加一个线性约束
add_constraints(cts, names=None) 批量添加线性约束

模型建立后，可以将模型输出为LP格式，以进行检验，仿真出现错误。导出为LP格式的方法为：model.export_as_lp()。

模型求解

可以通过模型的parameters属性设置模型求解参数，譬如，设置线性整数规划的MIP Gap可以这样操作：model.parameters.mip.tolerances.mip_gap=0.05。设置完成后可以直接通过solve()函数求解。

模型的求解结果以类SolveSolution形式返回，其中包含了：

  • 全部模型信息，譬如求解状态、目标函数值，以及
  • 每个变量的值

模型无解时，solve()返回None，因此可以直接基于返回结果判断求解结果。对于每个变量对象，可以通过solution[vname]的形式获取变量的值。

下面以运输问题为例，说明用DOcplex建立线性规划模型的过程。

运输问题模型

问题描述

已知有6个供给点、8个需求点，各供给点的供给量为\(S=\{60, 55, 51, 43, 41, 52\}\)，各需求点的需求量为\(D=\{35, 37, 22, 32, 41, 32, 43, 38\}\)，各供给点和需求点之间的单位运输成本为 $$ \[\begin{equation} c = \left[ \begin{matrix} 6 & 2 & 6 & 7 & 4 & 2 & 9 & 5\\ 4 & 9 & 5 & 3 & 8 & 5 & 8 & 2\\ 5 & 2 & 1 & 9 & 7 & 4 & 3 & 3\\ 7 & 6 & 7 & 3 & 9 & 2 & 7 & 1\\ 2 & 3 & 9 & 5 & 7 & 2 & 6 & 5\\ 5 & 5 & 2 & 2 & 8 & 1 & 4 & 8 \end{matrix} \right] \nonumber \end{equation}\] $$

设该问题的决策变量\(x_{ij}\)表示从供给点\(i \in I\)到需求点\(j \in J\)的供给量，模型的目标函数为 \[ \begin{equation} \min \sum_{i \in I} \sum_{j \in J} C_{ij} x_{ij} \end{equation} \] 约束条件 \[ \begin{equation} \sum_{i} x_{ij} = d_{j} \qquad \forall j \in J \end{equation} \]

\[ \begin{equation} \sum_{j \in J} x_{ij} \leq s_{i} \qquad \forall i \in I \end{equation} \]

\[ \begin{equation} x_{ij} \geq 0 \qquad i \in I, j \in J \end{equation} \]

DoCplex模型

下面是上述运输问题模型在DoCplex中实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# 导入模型库
from docplex.mp.model import Model

# 已知参数
Supply = (60, 55, 51, 43, 41, 52)
Demand = (35, 37, 22, 32, 41, 32, 43, 38)
Cost = ((6,2,6,7,4,2,9,5),
        (4,9,5,3,8,5,8,2),
        (5,2,1,9,7,4,3,3),
        (7,6,7,3,9,2,7,1),
        (2,3,9,5,7,2,6,5),
        (5,5,2,2,8,1,4,8))

# 创建模型
model = Model("transport")

# 定义决策变量:索引下标从0开始
x = model.continuous_var_matrix(keys1=range(len(Supply)),
                                keys2=range(len(Demand)),name="x")

# 目标函数
model.minimize(model.sum(Cost[i][j] * x[(i,j)] for i in range(len(Supply)) for j in range(len(Demand))))

# 添加约束条件:需求约束
for j, d in enumerate(Demand):
    model.add_constraint(model.sum(x[(i, j)] for i in range(len(Supply))) == d,
                         ctname="Demand%s" % j)

#供给约束
for i, s in enumerate(Supply):
    model.add_constraint(model.sum(x[(i, j)] for j in range(len(Demand))) <= s,
                         ctname="Supply%s" % i)

# 导出模型
model.export_as_lp("transport.lp")

# 模型求解
solution = model.solve()

# 输出求解结果
from sys import stdout
if solution:
    print("The optimal objective is: %6.3f" % solution.objective_value)
    stdout.write("Solution:\n")
    for i in range(len(Supply)):
        for j in range(len(Demand)):
            stdout.write("  %6.2f" % (solution[x[(i,j)]],))
        stdout.write("\n")
else:
    stdout.write("Solve status:" + solution.get_solve_status() + "\n")

上述代码完整版，可以在我的Github中找到，下载地址。