优化软件语法
- huuhghhgyg
- 3 min read
最近上课自学了CPLEX，感觉和之前浅浅接触过的LINGO的语法很像。记录一下以免以后忘了怎么用。此外，还在其中记录一下本次自学的遗传算法。
概述
求解大规模线性优化问题的时候不可能使用单纯形算法一个个地列单纯形表去手算，必须借助计算机求解才能使求解精确解的求解速度在可接受的范围内。可接受的求解时间范围根据每个人的接受情况不同大多分布于3小时或1天之内。此处记录一下之前稍微了解到的LINGO软件的语言、这次自学的CPLEX软件的OPL语言，这两个软件都可以用于求解线性规划问题。
LINGO语法
LINGO的整个线性规划模型大致可以描述为：
LINGO的集合
先上一段代码
1sets:
2 S/1..6/: a, b, d ; // S为1~6的集合，a有6个分量（a1~a6)，b、d、e等同理
3 T/1,2/: e, x, y; // T为1和2组成的集合，
4 U(S,T): c ; // 定义了双下标的集合（c为双下标变量c_ij）
5endsets
第2行描述了三个变量abd各自都有6个分量，如a可以看成a1,a2,...,a6，在LINGO里面引用就是a(1),a(2),...,a(6)，剩下两个变量b和d同理。
第四行定义了U为双下标集合，如果将U的每个元素看作Uij，那么i的范围为[1,6]，整数；j的范围为{1,2}。在LINGO里面引用就是U(i,j)。根据定义的集合，U(i,j)共有12个变量。
LINGO的变量
代码
1data:
2 a=1 2 3 4 5 6; // 定义a(n)的值
3 b=1 2 3 4 5 6;
4 x=5 2;
5 y=1 7;
6enddata
第2行表示a(1)到a(6)的值分别为1、2、3、4、5、6。
LINGO的模型
模型又可以分为两个部分：
在这之前，需要先了解集合函数，方便规模化地表示模型的目标函数和约束方程。
LINGO的集合函数
我也不知道它是不是叫这个名字，姑且先用集合函数表示他们。当时简单了解到的集合函数有两个。
| 函数表示 | 功能 |
|---|---|
| @sum | 求和 |
| @for | 遍历，但不操作 |
仅求和而言，大致有以下2种情况：
-
`\sum_{i=1}^{n}\sum_{j=1}^{k}x_{ij}`：可以直接对集合`T(i,j)`使用结合函数
@sum进行求和 -
`\sum_{i=1}^n\sum_{j=1}^{k}x_{j}`或`\sum_{j=1}^kx_{ij}`,`i\in{1,2,3,...,6}`：可以直接对集合`T(i,j)`使用结合函数
@sum进行求和
如果同时用到两个下标进行求和的时候，可以直接使用集合函数
@sum对其直接进行求和，否则应考虑如何使用@for函数遍历所有情况。
LINGO中目标函数的表示
数学公式
LINGO代码：
1min = @sum(T(j): @sum(S(i):
2 c(i,j)*@sqrt( ( x(j) - a(i) )^2 + ( y(j) - b(i) )^2 )
3) )
范围不同，需要使用两次@sum进行求和操作。@sum内表示了求和操作的对象，如T(j)和S(i)，其冒号后跟的是求和对象。
LINGO中约束方程的表示
数学公式
LINGO代码
1min = @sum(T(j): @sum(S(i):
2 c(i,j)*@sqrt( ( x(j) - a(i) )^2 + ( y(j) - b(i) )^2 )
3) )
4
5@for( S(i): @sum(T(j): c(i,j)) = d(i) );
6@for( T(j): @sum(S(i): c(i,j)) ) <= e(j);
集合函数用法同函数表示中的描述。
OPL语法
OPL语法是CPLEX的线性规划求解语法，我认为语法类似LINGO，但是相比LINGO更清楚。 一个OPL描述的模型也可以分为几个区域：
- 定义已知变量
- 定义未知变量
- 目标函数
- 约束条件
变量类型
| 变量符号 | 含义 |
|---|---|
int |
整数 |
int |
非负整数 |
float |
实数 |
float+ |
非负实数 |
boolean |
0-1变量 |
range |
范围 |
举例说明
range
range k = 1..4;
利用range定义变量
定义p1~p4：p[1..4]=[12, 11, 9, 8];
矩阵描述
此处的矩阵描述方法类似json，如下：
1int c[1..3][1..3] = [
2 [1,2,3],
3 [4,5,6],
4 [7,8,9]
5];
最后需要添加分号结束
定义未知变量
1dvar [关键字] [变量名];
如
1dvar int x;
这些未知变量要么是求解变量，要么是过程变量。
目标函数的表示
目标函数要么求最大，要么求最小。
| 关键字 | 目标函数类型 |
|---|---|
minimize |
最小化目标函数 |
maximize |
最大化目标函数 |
1minimize 3*x + 2*y; //目标函数为3x+2y，求最小化值
集合语言
类似LINGO中的集合函数，此处分为3种情况
- `\sum_{j=1}^np_jx_j`：
sum(j in 1..n) p[j]*x[j] - `\sum_{i=1}^n\sum_{j=1}^mx_{ij}`：
sum(i in 1..n) sum(j in 1..m) x[i][j] - `\sum_{i=1}^nx_{ij}`：
forall(j in 1..m) sum(i in 1..n) x[i][j]
其实也就还是sum和for函数。建议sum和for函数里面使用range。
SUM
1//sum的范围既可以分开写，也可以合并写。我更偏向于第二种
2sum(i in 1..n) sum(j in 1..m) x[i][j];
3sum(i in 1..n, j in 1..m) x[i][j];
此处的
1..n和1..m都是范围，都可以使用range类型的变量代替
FORALL
我认为forall除了功能与sum不同（不进行操作，只遍历所有可能性），其他与sum完全相同。sum和forall同时使用的时候我一般把forall放在sum前面。
1//forall的范围也可以合并写
2forall(i in 1..n) sum(j in 1..m) x[i][j];
3forall(i in 1..n, j in 1..m) sum(k in 1..p) x[i][j][k];
此外，有意思的是，forall的有效范围似乎是整行，而sum的有效范围只是后方紧跟的函数或变量。
约束条件
1subject to {
2 //在这里直接写约束条件;
3 //里面每句最后都要跟分号，就和C语言一样
4}
脚本
脚本这部分我还没用到，不太清楚。可以用于输出、修改数据。
1execute {
2 //脚本代码
3}
代码实例
此部分只展示我作业OPL源代码中范围、决策变量、目标函数和约束方程的部分，我认为这些部分会对理解比较有帮助。
1// 范围
2range rk=1..K; //车辆
3range rn=1..N; //所有节点
4range rc=2..N; //客户
5
6// 决策变量
7dvar boolean x[k in rk][i in rn][j in rn]; //路线决策
8dvar int+ y[i in rn][j in rn]; //路段总送货量
9dvar int+ z[i in rn][j in rn]; //路段总收货量
10
11// 目标函数
12minimize sum(k in rk,i in rn,j in rn) x[k][i][j]*d[i][j]*P
13 + sum(k in rk, i,j in rn)(y[i][j]+z[i][j])*x[k][i][j]*d[i][j]*Pa/Q
14 + sum(k in rk, i in rn, j in Med+1..N) x[k][i][j]*q[j]*Pm;
15
16// 约束方程
17subject to{
18 forall(j in rc) sum(i in rn,k in rk) x[k][i][j] == 1; //每个客户都只访问一次
19 forall(i in rn, k in rk) sum(j in rn) x[k][i][j] == sum(j in rn) x[k][j][i]; //到达节点的数量和离开节点的数量相同
20 forall(k in rk) sum(j in rn) x[k][1][j] <= 1; //每辆车只能离开仓库一次
21 forall(i,j in rn) y[i][j]+z[i][j] <= Q*sum(k in rk) x[k][i][j]; //任意路段的载重量不超过车辆容量
22 forall(k in rk) sum(i,j in rn) x[k][i][j]*d[i][j] <= D; //每辆车的行驶里程上限
23 forall(i in rc) sum(j in rn) y[j][i] - sum(j in rn) y[i][j] == q[i]; //所有客户的送货量递推约束
24 forall(i in rc) sum(j in rn) z[i][j] - sum(j in rn) z[j][i] == p[i]; //所有客户的取货递推约束
25 forall(k in rk) sum(i in rn) x[k][i][i] == 0; //不允许自己运给自己
26 forall(k in rk) sum(i in rc, j in rn) x[k][i][j] <= V; //车辆服务客户数量限制
27}