精彩文章免费看

cplex入门系列(二)--- 线性规划求解

一、cplex项目模板

一般一个的cplex项目,一般分为五个模块,分别是创建模型、定义优化参数、设置目标函数、设置约束和模型求解及输出。下面针对这五个模块使用cplex的Java API来进行介绍。

1.1 创建模型

即在内存中开辟一个空间来实例化IloCplex类;

IloCplex cplex = new IloCplex(); // 创建一个模型

1.2 定义优化参数

这里定义将要求解的优化参数,常见的参数类型包括单个变量、一维及二维数组类型。

1.2.1 单变量定义

在实际生产问题中,常见的变量类型就实数,整数比较常见:
○ 实数型变量 cplex.numVar
○ 整数型变量 cplex.intVar
单变量参数,主要是值变量的取值范围,例如该变量取值范围为0≤x≤5,若不想定义范围也可以设置为-Double.MAX_VALUE和Double.MAX_VALUE,表示负无穷到正无穷;比如cplex.numVar(0,5),表示0≤x≤5

1.2.2 一维数组定义

○ 实数型变量 cplex.numVarArray(num,min,max)
○ 整数型变量 cplex.intVarArray(num,min,max)
参数表示数组的大小(num),最小值(min)和最大值(max),这样定义的就是三个定义域相同的变量;
如果要为每个变量设置不同的范围

double[] rangeVar = {0,3,2,8,1,7}; // 每个变量的最小值和最大值
IloNumVar[] x = new IloNumVar[3];
for(int i=0;i<3;i++){
    x[i] = cplex.numVar(rangeVar[2*i], rangeVar[2*i+1]);

这样就将数组中的三个变量设置了不同的取值范围,分别为[0,3],[2,8],[1,7]

1.2.3 二维数组定义

IloNumVar[][] x2array1 = new IloNumVar[2][];
for (int i=0; i<2; i++){
    x2array1[i] = cplex.numVarArray(2, 0.0, 5.0);
IloIntVar[][] x2array2 = new IloIntVar[2][];
for (int i=0; i<2; i++){
    x2array2[i] = cplex.intVarArray(2, 0, 5);

1.3 设置目标函数和约束

目标函数一般是取一个表达式的最大值或者最小值,约束一般是设定一个表达式的取值范围,一个共同点就是都需要先定义表达式,而且它们定义表达式的方式是完全相同的。

1.3.1 定义表达式

官方根据表达式类型的不同提供了不同的接口,包括:

需要根据模型表达式类型选择合适自己的接口形式,比如x_1+2x_2+3x_3,属于线性类型,那么就可以一次线性表达式的接口:

IloNumVar[] x =cplex.numVarArray(3, -5, 5);
IloLinearNumExpr cs = cplex.linearNumExpr();
cs.addTerm(1, x[0]);
cs.addTerm(2, x[1]);
cs.addTerm(3, x[2]);

每个接口都提供了非常多的方法,详细参考官方文档的使用方法和说明。尽管官方为不同形式的表达式提供了不同的接口,但是存在一定的问题,比如无法在一次线性规划表达式中添加二次项,当表达式比较复杂的时候通常不止一种类型。因此一般就用最基本的公式接口IloNumExpr,在这个接口中可以利用cplex模型库中的加减乘除来添加任何形式的表达式。

先创建模型Ilocplex cplex = new IloCplex(); 然后通过cplex.xxx的方式使用模型中的各种运算方法,常用的包括:

有了以上这四种方法基本就可以应对大部分的表达式了,比如x_1+2x_2+3x_3,用基本公共接口表示为:

IloNumVar[] x =cplex.numVarArray(3, -5, 5);
double[] vars = {1,2,3};
IloNumExpr cs = cplex.numExpr();
for(int i=0;i<3;i++){
    cs = cplex.sum(cs, cplex.prod(x[i], vars[i]));

虽然这种方式增加了代码量,但是代码可读性增强了,所以这种方式会更好,再比如,求变量x的平方和绝对值之和:

IloNumVar[] x =cplex.numVarArray(3, -5, 5);
IloNumExpr cs1 = cplex.numExpr();
IloNumExpr cs2 = cplex.numExpr();
for(int i=0;i<3;i++){
    cs1 = cplex.sum(cs1, cplex.abs(x[i]));
    cs2 = cplex.sum(cs2, cplex.prod(x[i], x[i]));

1.3.2 定义目标函数

假设定义后目标函数的表达式用obj表示:

在添加了约束后我们可以通过cplex.diff(cs,cs)来清空表达式cs,然后就可以在cs中添加新的表达式。

1.4 清空表达式

有时候在定义目标函数和约束时需要通过循环来定义新的表达式,每次重新初始化表达式很麻烦,这时候就需要清空表达式:

  • cplex.diff(cs,cs)
  • cplex.numExpr()
    第一种方式有时候会爆出内存溢出的错误,因此更推荐使用第二种方式。
  • 1.5 模型求解及输出

    模型求解以及输出的模板如下所示:

    if (cplex.solve()) {
        cplex.output().println("Solution status = " + cplex.getStatus());
        cplex.output().println("Solution value = " + cplex.getObjValue());
        double[] val = cplex.getValues(x);
        for (int j = 0; j < val.length; j++){
            System.out.println("x" + (j+1) + "  = " + val[j]);
    cplex.end();
                // 2. 定义优化参数
                IloNumVar[] x = cplex.numVarArray(2, 0, Double.MAX_VALUE);
                double[] c = {2,3};
                IloNumExpr cs1 = cplex.numExpr();
                for(int i=0;i<2;i++){
                    cs1 = cplex.sum(cs1,cplex.prod(c[i], x[i]));
                // 3. 设置目标函数
                cplex.addMaximize(cs1);
                // 4. 设置约束
                cplex.addLe(cplex.sum(x[0], cplex.prod(2, x[1])), 8);
                cplex.addLe(cplex.prod(4, x[0]), 16);
                cplex.addLe(cplex.prod(4, x[1]), 12);
                // 5. 模型求解及输出
                if(cplex.solve()){
                    cplex.output().println("Solution status = " + cplex.getStatus());
                    cplex.output().println("Solution Value = " + cplex.getObjValue());
                    double[] val = cplex.getValues(x);
                    for(int j=0;j<2;j++){
                        System.out.println("x" + (j+1) + " = " + val[j]);
                cplex.end();
            } catch (IloException e){
                System.err.println("Concert exception caught: " + e);
    
    Tried aggregator 1 time.
    LP Presolve eliminated 2 rows and 0 columns.
    Reduced LP has 1 rows, 2 columns, and 2 nonzeros.
    Presolve time = 0.00 sec. (0.00 ticks)
    Iteration log . . .
    Iteration:     1   Dual objective     =            14.000000
    Solution status = Optimal
    Solution Value = 14.0
    x1 = 4.0
    x2 = 2.0
    

    可以根据上面的运行结果获悉,该问题为LP(线性规划)求解问题,迭代了一次,对偶目标解为14,解的状态为Optimal,即找到了一个最优的解决方案,目标函数的最优解为14,对应的变量x1和x2分别取4和2。

    2.2 案例二

    该案例为《运筹学》清华大学第四版P60例2-10题目,具体应用场景请参考教材。
    目标函数:min⁡ z=0x_1+0.1x_2+0.2x_3+0.3x_4+0.8x_5
    约束条件:
    // 2. 定义优化参数 IloNumVar[] x = cplex.numVarArray(5, 0, Double.MAX_VALUE); double[] c = {0, 0.1, 0.2, 0.3, 0.8}; IloNumExpr cs1 = cplex.numExpr(); for(int i=0;i<5;i++){ cs1 = cplex.sum(cs1,cplex.prod(c[i], x[i])); // 3. 设置目标函数 cplex.addMinimize(cs1); // 4. 设置约束 cplex.addEq(cplex.sum(x[0], cplex.prod(2, x[1]), x[3]), 100); cplex.addEq(cplex.sum(cplex.prod(2, x[2]), cplex.prod(2, x[3]), x[4]), 100); cplex.addEq(cplex.sum(cplex.prod(3, x[0]), x[1], cplex.prod(2, x[2]), cplex.prod(3, x[4])), 100); cplex.addGe(x[0], 0); cplex.addGe(x[1], 0); cplex.addGe(x[2], 0); cplex.addGe(x[3], 0); cplex.addGe(x[4], 0); // // 5. 模型求解及输出 if(cplex.solve()){ cplex.output().println("Solution status = " + cplex.getStatus()); cplex.output().println("Solution Value = " + cplex.getObjValue()); double[] val = cplex.getValues(x); for(int j=0;j<5;j++){ System.out.println("x" + (j+1) + " = " + val[j]); cplex.end(); } catch (IloException e){ System.err.println("Concert exception caught: " + e);

    Tried aggregator 1 time.
    LP Presolve eliminated 5 rows and 0 columns.
    Reduced LP has 3 rows, 5 columns, and 10 nonzeros.
    Presolve time = 0.02 sec. (0.00 ticks)
    Initializing dual steep norms . . .
    Iteration log . . .
    Iteration:     1   Dual objective     =            10.000000
    Solution status = Optimal
    Solution Value = 16.0
    x1 = 0.0
    x2 = 40.0
    x3 = 30.0
    x4 = 20.0
    x5 = 0.0
    

    可以根据上面的运行结果获悉,该问题为LP(线性规划)求解问题,迭代了一次,对偶目标解为10,解的状态为Optimal,即找到了一个最优的解决方案,目标函数的最优解为16,对应的变量x2、x3、x4分别取40、30和20。这好像和教材上的解不一样,带入原约束条件都满足,带入目标函数其方案同样是使用了90跟原材料制造了100套钢材。这里似乎出现了第二个最优解,这也是实际问题中经常出现的情况,多个最优解,这里在下一节进行讨论。