优化软件语法

Author Avatar
huuhghhgyg 7月 12, 2022
  • 在其它设备中阅读本文章

最近上课自学了CPLEX，感觉和之前浅浅接触过的LINGO的语法很像。记录一下以免以后忘了怎么用。此外，还在其中记录一下本次自学的遗传算法。

概述

求解大规模线性优化问题的时候不可能使用单纯形算法一个个地列单纯形表去手算，必须借助计算机求解才能使求解精确解的求解速度在可接受的范围内。可接受的求解时间范围根据每个人的接受情况不同大多分布于3小时或1天之内。此处记录一下之前稍微了解到的LINGO软件的语言、这次自学的CPLEX软件的OPL语言，这两个软件都可以用于求解线性规划问题。

LINGO语法

LINGO的整个线性规划模型大致可以描述为：

LINGO的集合

先上一段代码

sets:
    S/1..6/: a, b, d ; // S为1~6的集合，a有6个分量（a1~a6)，b、d、e等同理
    T/1,2/: e, x, y; // T为1和2组成的集合，
    U(S,T): c ; // 定义了双下标的集合（c为双下标变量c_ij）
endsets

第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的变量

代码

data:
    a=1 2 3 4 5 6; // 定义a(n)的值
    b=1 2 3 4 5 6;
    x=5 2;
    y=1 7;
enddata

第2行表示a(1)到a(6)的值分别为1、2、3、4、5、6。

LINGO的模型

模型又可以分为两个部分：

  1. 目标函数
  2. 约束方程

在这之前，需要先了解集合函数，方便规模化地表示模型的目标函数和约束方程。

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中目标函数的表示

数学公式

`min\sum_{j=1}^2\sum_{i=1}^6\sqrt{(x_j-a_i)^2+(y_j-b_i)^2}`

LINGO代码：

min = @sum(T(j): @sum(S(i):
    c(i,j)*@sqrt( ( x(j) - a(i) )^2 + ( y(j) - b(i) )^2 )
) )

范围不同，需要使用两次@sum进行求和操作。@sum内表示了求和操作的对象，如T(j)和S(i)，其冒号后跟的是求和对象。

LINGO中约束方程的表示

数学公式

s.t. $ \left\{ \begin{array}{**lr**} \sum_{j=1}^2c_{ij}=d_i , i=1,2,...,6 \\ \sum_{i=1}^6c_{ij} \leq d_i, j=1,2 \end{array} \right. $

LINGO代码

min = @sum(T(j): @sum(S(i):
    c(i,j)*@sqrt( ( x(j) - a(i) )^2 + ( y(j) - b(i) )^2 )
) )

@for( S(i): @sum(T(j): c(i,j)) = d(i) );
@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，如下：

int c[1..3][1..3] = [
    [1,2,3],
    [4,5,6],
    [7,8,9]
];

最后需要添加分号结束

定义未知变量

dvar [关键字] [变量名];

如

dvar int x;

这些未知变量要么是求解变量，要么是过程变量。

目标函数的表示

目标函数要么求最大，要么求最小。

关键字 目标函数类型
minimize 最小化目标函数
maximize 最大化目标函数 
minimize 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

//sum的范围既可以分开写，也可以合并写。我更偏向于第二种
sum(i in 1..n) sum(j in 1..m) x[i][j];
sum(i in 1..n, j in 1..m) x[i][j];

此处的1..n和1..m都是范围，都可以使用range类型的变量代替

FORALL

我认为forall除了功能与sum不同（不进行操作，只遍历所有可能性），其他与sum完全相同。sum和forall同时使用的时候我一般把forall放在sum前面。

//forall的范围也可以合并写
forall(i in 1..n) sum(j in 1..m) x[i][j];
forall(i in 1..n, j in 1..m) sum(k in 1..p) x[i][j][k];

此外，有意思的是，forall的有效范围似乎是整行，而sum的有效范围只是后方紧跟的函数或变量。

约束条件

subject to {
    //在这里直接写约束条件;
    //里面每句最后都要跟分号，就和C语言一样
}

脚本

脚本这部分我还没用到，不太清楚。可以用于输出、修改数据。

execute {
    //脚本代码
}

代码实例

此部分只展示我作业OPL源代码中范围、决策变量、目标函数和约束方程的部分，我认为这些部分会对理解比较有帮助。

// 范围
range rk=1..K; //车辆
range rn=1..N; //所有节点
range rc=2..N; //客户

// 决策变量
dvar boolean x[k in rk][i in rn][j in rn]; //路线决策
dvar int+ y[i in rn][j in rn]; //路段总送货量
dvar int+ z[i in rn][j in rn]; //路段总收货量

// 目标函数
minimize sum(k in rk,i in rn,j in rn) x[k][i][j]*d[i][j]*P 
    + sum(k in rk, i,j in rn)(y[i][j]+z[i][j])*x[k][i][j]*d[i][j]*Pa/Q
    + sum(k in rk, i in rn, j in Med+1..N) x[k][i][j]*q[j]*Pm;

// 约束方程
subject to{
  forall(j in rc) sum(i in rn,k in rk) x[k][i][j] == 1; //每个客户都只访问一次
  forall(i in rn, k in rk) sum(j in rn) x[k][i][j] == sum(j in rn) x[k][j][i]; //到达节点的数量和离开节点的数量相同
  forall(k in rk) sum(j in rn) x[k][1][j] <= 1; //每辆车只能离开仓库一次
  forall(i,j in rn) y[i][j]+z[i][j] <= Q*sum(k in rk) x[k][i][j]; //任意路段的载重量不超过车辆容量
  forall(k in rk) sum(i,j in rn) x[k][i][j]*d[i][j] <= D; //每辆车的行驶里程上限
  forall(i in rc) sum(j in rn) y[j][i] - sum(j in rn) y[i][j] == q[i]; //所有客户的送货量递推约束
  forall(i in rc) sum(j in rn) z[i][j] - sum(j in rn) z[j][i] == p[i]; //所有客户的取货递推约束
  forall(k in rk) sum(i in rn) x[k][i][i] == 0; //不允许自己运给自己
  forall(k in rk) sum(i in rc, j in rn) x[k][i][j] <= V; //车辆服务客户数量限制
}

资料获取

如果有需要可以发邮件跟我索要我的物流软件上机实训的期末大作业示例，我最终得了94分，仅供参考😋
一般我回复邮件还挺快的，不会超过半天🤣

前往邮箱发送邮件 请顺便介绍一下你的情况，主要我也想知道你是谁🤣 Mail arrow_forward

下一篇是遗传算法，我会把源代码完整放到文章中，方便参考👏

link
本文链接：
https://huuhghhgyg.github.io/2022/07/12/optimization-code/
发文时间
7月 12, 2022
请遵循协议
CC BY-NC-SA 4.0