GLPK的安装与使用

GLPK(GNU Linear Programming Kit)

http://www.gnu.org/software/glpk/#TOCdocumentation

GLPK是一个开源的求解线性规划问题的工具套件，这里简要的介绍一下GLKP在linux环境下的安装，并以一个简单的例子来介绍在C++中调用GLPK解决线性规划问题。

安装环境：

      OS:Ubuntu 16.04

      CPU:Intel i5-6200U

      Memory:DDR4 8G

      VM:YES

安装与配置：

      首先下载相应版本的GLPK，本人下载了4.60版本的套件。

      解压缩： tar -zxvf glpk-4.60.tar

      GLPK支持使用GMP来计算大数字以及高精度浮点，默认不适用，但是使用GMP的话效率更高，因此本人在配置时添加了对GMP的支持。进入解压安装文件目录，并配置：

./configure –with-gmp

      根据配置变异安装文件：

      make

      编译完成后可进行检查：

      makecheck

      然后就可以进行安装了，安装的默认路径是/usr/local/lib，因此需要取得管理员权限：       sudo make install

      等待一会即安装完成了，由于使用GLPK需要使用到其动态库，因此在安装完毕后需要更新动态库：

      ldconfig

GLPK的使用：

      在源文件中添加GLPK头文件即可：

      #include<glpk.h>

      编译时需要引用GLPK动态库：

      -lglpk

      注意事项：

GLPK并不是线程安全的！

             GLPK使用数组从下标1开始，而不从0开始。

      例子：

      求解目标函数最大值：

      约束条件：

      转换为求解LP问题的标准形式：

      设：

      则有：

      求解程序：

                #include <iostream>

       #include<glpk.h>

       usingnamespace std;

       intmain()

       {

                glp_prob *lp;

                int ia[1+1000], ja[1+1000];

                double ar[1+1000], z, x1, x2, x3;

                lp = glp_create_prob();

                glp_set_prob_name(lp,"sample");

                glp_set_obj_dir(lp,GLP_MAX);//maximization

                glp_add_rows(lp, 3);

                glp_set_row_name(lp, 1, "p");

                glp_set_row_bnds(lp, 1, GLP_UP, 0.0,100.0);//GLP_UP means it has a upper bound

                glp_set_row_name(lp, 2, "q");

                glp_set_row_bnds(lp, 2, GLP_UP, 0.0,600.0);

                glp_set_row_name(lp, 3, "r");

                glp_set_row_bnds(lp, 3, GLP_UP, 0.0,300.0);

                glp_add_cols(lp, 3);

                glp_set_col_name(lp, 1,"x1");

                glp_set_col_bnds(lp, 1, GLP_LO, 0.0,0.0);//GLP_LO means it has a lower bound

                glp_set_obj_coef(lp, 1, 10.0);//setobjective coefficient目标函数系数

                glp_set_col_name(lp, 2,"x2");

                glp_set_col_bnds(lp, 2, GLP_LO, 0.0,0.0);

                glp_set_obj_coef(lp, 2, 6.0);

                glp_set_col_name(lp, 3,"x3");

                glp_set_col_bnds(lp, 3, GLP_LO, 0.0,0.0);

                glp_set_obj_coef(lp, 3, 4.0);

                ia[1] = 1, ja[1] = 1, ar[1] = 1.0;//a[1,1] = 1

                ia[2] = 1, ja[2] = 2, ar[2] = 1.0; //a[1,2]= 1

                ia[3] = 1, ja[3] = 3, ar[3] = 1.0; //a[1,3]= 1

                ia[4] = 2, ja[4] = 1, ar[4] = 10.0;

                ia[5] = 3, ja[5] = 1, ar[5] = 2.0;

                ia[6] = 2, ja[6] = 2, ar[6] = 4.0;

                ia[7] = 3, ja[7] = 2, ar[7] = 2.0;

                ia[8] = 2, ja[8] = 3, ar[8] = 5.0;

                ia[9] = 3, ja[9] = 3, ar[9] = 6.0;

                glp_load_matrix(lp, 9, ia, ja, ar); //将约束系数矩阵导入

                glp_simplex(lp, NULL); //simplex method使用单纯形法求解

                z = glp_get_obj_val(lp); //获取目标函数最大值

                x1 = glp_get_col_prim(lp, 1); //获取目标函数最大值时相应结构变量的值

                x2 = glp_get_col_prim(lp, 2);

                x3 = glp_get_col_prim(lp, 3);

                cout<<"z ="<<z<<"; x1 = "<<x1<<"; x2 ="<<x2<<"; x3 = "<<x3<<endl; //输出

                glp_delete_prob(lp);

                return 0;

       }

最终输出结果：

GLPKSimplex Optimizer, v4.60

3 rows,3 columns, 9 non-zeros

*     0: obj = -0.000000000e+00 inf =   0.000e+00(3)

*     2: obj =  7.333333333e+02 inf =   0.000e+00(0)

OPTIMALLP SOLUTION FOUND

z =733.333; x1 = 33.3333; x2 = 66.6667; x3 = 0