cplex入門(mén)系列（二）--- 線性規(guī)劃求解

一每辟、cplex項(xiàng)目模板

一般一個(gè)的cplex項(xiàng)目，一般分為五個(gè)模塊包斑，分別是創(chuàng)建模型流礁、定義優(yōu)化參數(shù)、設(shè)置目標(biāo)函數(shù)罗丰、設(shè)置約束和模型求解及輸出神帅。下面針對(duì)這五個(gè)模塊使用cplex的Java API來(lái)進(jìn)行介紹。

1.1 創(chuàng)建模型

即在內(nèi)存中開(kāi)辟一個(gè)空間來(lái)實(shí)例化IloCplex類(lèi)萌抵；

IloCplex cplex = new IloCplex(); // 創(chuàng)建一個(gè)模型

1.2 定義優(yōu)化參數(shù)

這里定義將要求解的優(yōu)化參數(shù)找御，常見(jiàn)的參數(shù)類(lèi)型包括單個(gè)變量、一維及二維數(shù)組類(lèi)型绍填。

1.2.1 單變量定義

在實(shí)際生產(chǎn)問(wèn)題中霎桅，常見(jiàn)的變量類(lèi)型就實(shí)數(shù)，整數(shù)比較常見(jiàn)：
○ 實(shí)數(shù)型變量 cplex.numVar
○ 整數(shù)型變量 cplex.intVar
單變量參數(shù)讨永，主要是值變量的取值范圍滔驶，例如該變量取值范圍為 $0≤x≤5$ ，若不想定義范圍也可以設(shè)置為-Double.MAX_VALUE和Double.MAX_VALUE,表示負(fù)無(wú)窮到正無(wú)窮卿闹；比如cplex.numVar(0,5)揭糕，表示 $0≤x≤5$ 萝快。

1.2.2 一維數(shù)組定義

○ 實(shí)數(shù)型變量 cplex.numVarArray(num,min,max)
○ 整數(shù)型變量 cplex.intVarArray(num,min,max)
參數(shù)表示數(shù)組的大小(num)，最小值(min)和最大值(max)著角，這樣定義的就是三個(gè)定義域相同的變量杠巡；
如果要為每個(gè)變量設(shè)置不同的范圍

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

這樣就將數(shù)組中的三個(gè)變量設(shè)置了不同的取值范圍，分別為[0,3]雇寇，[2,8]，[1,7]

1.2.3 二維數(shù)組定義

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 設(shè)置目標(biāo)函數(shù)和約束

目標(biāo)函數(shù)一般是取一個(gè)表達(dá)式的最大值或者最小值蚌铜，約束一般是設(shè)定一個(gè)表達(dá)式的取值范圍锨侯，一個(gè)共同點(diǎn)就是都需要先定義表達(dá)式，而且它們定義表達(dá)式的方式是完全相同的冬殃。

1.3.1 定義表達(dá)式

官方根據(jù)表達(dá)式類(lèi)型的不同提供了不同的接口囚痴，包括：

接口	描述
IloIntExpr/IloNumExpr	整數(shù)/實(shí)數(shù)表達(dá)式的基本公共接口
IloLinearIntExpr/IloLinearNumExpr	整數(shù)/實(shí)數(shù)類(lèi)型變量的一次線性表達(dá)式的接口
IloLQIntExpr/IloLQNumExpr	具有線性和二次項(xiàng)的一般表達(dá)式
IloQuadIntExpr/IloQuadNumExpr	整數(shù)/實(shí)數(shù)型二次數(shù)值表達(dá)式

需要根據(jù)模型表達(dá)式類(lèi)型選擇合適自己的接口形式，比如 $x_1+2x_2+3x_3$ 审葬，屬于線性類(lèi)型深滚，那么就可以一次線性表達(dá)式的接口：

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]);

每個(gè)接口都提供了非常多的方法，詳細(xì)參考官方文檔的使用方法和說(shuō)明涣觉。盡管官方為不同形式的表達(dá)式提供了不同的接口痴荐，但是存在一定的問(wèn)題，比如無(wú)法在一次線性規(guī)劃表達(dá)式中添加二次項(xiàng)官册，當(dāng)表達(dá)式比較復(fù)雜的時(shí)候通常不止一種類(lèi)型生兆。因此一般就用最基本的公式接口IloNumExpr，在這個(gè)接口中可以利用cplex模型庫(kù)中的加減乘除來(lái)添加任何形式的表達(dá)式膝宁。

先創(chuàng)建模型Ilocplex cplex = new IloCplex(); 然后通過(guò)cplex.xxx的方式使用模型中的各種運(yùn)算方法鸦难，常用的包括：

方法	說(shuō)明
sum	求和
diff	求差
prod	乘積
abs	絕對(duì)值

有了以上這四種方法基本就可以應(yīng)對(duì)大部分的表達(dá)式了，比如 $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]));
}

雖然這種方式增加了代碼量合蔽，但是代碼可讀性增強(qiáng)了，所以這種方式會(huì)更好介返，再比如拴事，求變量x的平方和絕對(duì)值之和：

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 定義目標(biāo)函數(shù)

假設(shè)定義后目標(biāo)函數(shù)的表達(dá)式用obj表示：

函數(shù)	說(shuō)明
cplex.addMinimize(obj)	求obj的最小值
cplex.addMaximize(obj)	求obj的最大值

1.3.3 定義約束

假設(shè)定義后約束的表達(dá)式用cs表示：

函數(shù)	說(shuō)明
cplex.addEq(cs,a)	$cs=a$
cplex.addLe(cs,a)	$cs{\le}a$
cplex.addGe(cs,a)	$cs{\ge}a$
cplex.addRange(a,cs,b)	$a{\le}cs{\le}b$

在添加了約束后我們可以通過(guò)cplex.diff(cs,cs)來(lái)清空表達(dá)式cs，然后就可以在cs中添加新的表達(dá)式映皆。

1.4 清空表達(dá)式

有時(shí)候在定義目標(biāo)函數(shù)和約束時(shí)需要通過(guò)循環(huán)來(lái)定義新的表達(dá)式挤聘，每次重新初始化表達(dá)式很麻煩，這時(shí)候就需要清空表達(dá)式：

cplex.diff(cs,cs)
cplex.numExpr()
第一種方式有時(shí)候會(huì)爆出內(nèi)存溢出的錯(cuò)誤捅彻，因此更推薦使用第二種方式组去。

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();

其中

函數(shù)	說(shuō)明
cplex.getStatus()	獲得模型求解的狀態(tài)
cplex.getObjValue()	獲取目標(biāo)函數(shù)的值
cplex.getValues(x)	獲取優(yōu)化變量的值
cplex.end()	結(jié)束模型

模型求解包括以下幾個(gè)狀態(tài)

狀態(tài)	說(shuō)明
Optimal	找到了一個(gè)最優(yōu)的解決方案
Feasible	找到了一個(gè)可行的解決方案
Infeasible	該模型不可行
Error	遇到了錯(cuò)誤
Bounded	模型不是無(wú)界的
Unbounded	模型是無(wú)界的

二、cplex 項(xiàng)目實(shí)戰(zhàn)

2.1 案例一

該案例為《運(yùn)籌學(xué)》清華大學(xué)第四版P15例2-1題目步淹，具體應(yīng)用場(chǎng)景請(qǐng)參考教材从隆。
目標(biāo)函數(shù)： $max? z=2x_1+3x_2$
約束條件：
$x_1+2x_2≤8$
$4x_1≤16$
$4x_2≤12$
$x_1,x_2≥0$

package com.opreation.research;
import ilog.concert.*;
import ilog.cplex.IloCplex;

public class CplexTest {
    public static void main(String[] args) throws IloException {
        try{
            // 1. 創(chuàng)建模型
            IloCplex cplex = new IloCplex();

            // 2. 定義優(yōu)化參數(shù)
            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. 設(shè)置目標(biāo)函數(shù)
            cplex.addMaximize(cs1);
            // 4. 設(shè)置約束
            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);
        }

    }
}

運(yùn)行結(jié)果

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

可以根據(jù)上面的運(yùn)行結(jié)果獲悉诚撵，該問(wèn)題為L(zhǎng)P(線性規(guī)劃)求解問(wèn)題，迭代了一次键闺，對(duì)偶目標(biāo)解為14寿烟，解的狀態(tài)為Optimal，即找到了一個(gè)最優(yōu)的解決方案辛燥，目標(biāo)函數(shù)的最優(yōu)解為14筛武，對(duì)應(yīng)的變量x1和x2分別取4和2。

2.2 案例二

該案例為《運(yùn)籌學(xué)》清華大學(xué)第四版P60例2-10題目挎塌，具體應(yīng)用場(chǎng)景請(qǐng)參考教材徘六。
目標(biāo)函數(shù)： $min? z=0x_1+0.1x_2+0.2x_3+0.3x_4+0.8x_5$
約束條件：
$x_1+2x_2+x_4=100$
$2x_3+2x_4+x_5=100$
$3x_1+x_2+2x_3=3x_5=100$
$x_1,x_2,x_3,x_4,x_5≥0$

package com.opreation.research;
import ilog.concert.*;
import ilog.cplex.IloCplex;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.util.HashSet;
import java.util.Random;

public class CplexTest {

    public static void main(String[] args) throws IloException {
        try{


            // 1. 創(chuàng)建模型
            IloCplex cplex = new IloCplex();


            // 2. 定義優(yōu)化參數(shù)
            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. 設(shè)置目標(biāo)函數(shù)
            cplex.addMinimize(cs1);
            // 4. 設(shè)置約束
            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);
        }

    }
}