专栏首页数据魔术师干货 | 关于数学规划求解器lp_solve 超全面超详细的教程

干货 | 关于数学规划求解器lp_solve 超全面超详细的教程

前言

最近小编学了运筹学中的单纯形法。

于是,很快便按奈不住跳动的心。

这不得不让我拿起纸和笔思考着,

一个至关重要的问题:

如何用单纯形法装一个完备的13?

恰巧,在我坐在图书馆陷入沉思的时候,

一位漂亮的小姐姐靠过来,

说:“同学,你是在看线性规划吗?

你能帮我看看这道题该怎么解好吗?”

纳尼?还真是瞌睡来了送枕头。

但是,尽管心里万马奔腾,

还是要装作若无其事的样子,蛋蛋一笑。

“这个啊,简单!让我来算算。”

但是一拿到题目之后,扫了一眼。

惊得差点没把笔吞下去。

这……城里人都这么会play的吗?

我*,25个变量。

看着那一堆约束条件,

看着这堆变量x1,x2,x3,...,x25。

总感觉,这次真的是玩脱了。

用Table?开什么国际玩笑,

且不说这得算到猴年马月,

在这期间如果搞错一个数,

那简直比吃了老坛酸菜牛肉面还酸爽。

用C++,

写个Simple algorithm用电脑跑一跑?

但是,像小编这种,

上不知虚函数,下不晓纯虚函数,

左不清explicit,右不明volatile。

连虚函数表都说不清道不明的小白,

打个simple algorithm的拼写还差不多。

气氛陷入了尴尬的沉默,

沉默是今晚的康桥。

在我快急哭了的时候,

小姐姐却淡淡一笑。

“解不出来吗?”

“嗯……这个是有点麻烦。”

“哈哈~解不出来也没关系啦。

哎,学弟你想考托福雅思吗?”

小姐姐话锋一转。“嗯哼???”

“我知道有几家托福雅思的培训机构,

那里的老师很厉害,

你可以了解一下哦。”

“……”

“……”

不过话说回来,

对于复杂的线性规划问题,

特别是变量很多的那种,

有什么办法呢?

难道真的要亲自撸一遍单纯形法?

那你就真的是out了。

今天给大家介绍一款神器:lpsolve

一款狂拽炫酷吊炸天阿姆斯特朗回旋加速棒棒的神器。

Part1 科普篇

lpsolve是什么?

lpsolve是sourceforge下的一个开源项目,它的介绍如下:

Mixed Integer Linear Programming (MILP) solver lp_solve solves pure linear, (mixed) integer/binary, semi-cont and special ordered sets (SOS) models.lp_solve is written in ANSI C and can be compiled on many different platforms like Linux and WINDOWS

它的特点有:

  • Linear and Integer programming solver
  • Sensitivity analysis
  • Very strong API with many programming language examples
  • IDE
  • Open source
  • Pure C code
  • Windows, Unix, Linux, Mac OSX
  • 32 and 64 bit
  • Also precompiled binaries provided

它是一个混合整数线性规划求解器,可以求解纯线性、(混合)整数/二值、半连续和特殊有序集模型。并且经过实际验证,有极高的求解效率。

应用领域:科学与研究,高级用户终端,程序开发等

开发语言:C

应用平台:可应用于Linux和WINDOWS等所有平台。

相关资源

sourceforge主页:http://sourceforge.net/projects/lpsolve/?source=directory

有关lpsolve的所有资源都可以在这个主页上找到。

包括本文后面介绍的所有文件。

有关lpsolve的详细说明文档:http://web.mit.edu/lpsolve/doc/

Part2 入门篇

简单上手

看完了上面的介绍,相信大部分小伙伴还是一脸懵逼。说了这么多牛逼,转了半天,还没告诉我怎么用呢!(汗)

小编也不指望大家能耐下心来好好去读那让人头大的英语说明文档了。今天,本编就带领大家一步一步上手这个神器的求解器……

说到这里,可能有小伙伴又不乐意了,不会又要撸代码吧?呃……不撸代码是不可能了,这辈子都不可能了。

好在,天无绝人之路,lpsolver也提供了一个简易的IDE(别问我什么是IDE。IDE就是集成开发环境Integrated Development Environment ),提供给像小编这种小白使用。下面就给大家慢慢道来。

LPSolve IDE

LPSolve IDE可谓是大大方便了各位新手朋友了。它的界面还算友好,功能十分强大。

界面如下:

它的介绍如下:

The LPSolve IDE (Integrated Development Interface) is a very user friendly Windows interface to the lpsolve API. All functionality of lpsolve can be accessed via a graphical and very user friendly application.

Many thanks to Henri Gourvest for making this nice interface to lpsolve and making it available to the community.

它的几个特点如下:

  • Everything is graphical and mouse controled
  • Enter your lp model in all supported formats and even via an XLI interface (See External Language Interfaces)
  • Convert your lp model from any supported format to another supported format and even via an XLI interface (See External Language Interfaces)
  • Very user friendly editor to enter/change the model with syntax highlight.
  • Syntax checking of the model
  • Solve the model
  • See the results in grids
  • Control every possible lpsolve option (tolerances, presolve, scaling, ...)
  • View the matrix in grids
  • Export model to HTML, RTF, LaTeX output
  • Export matrix to CSV, HTML, RTF output
  • Export results to CSV, HTML, RTF output
  • Show statistics about the model.

...

只需要把需要求解的线性规划问题输入到求解器里面,然后点一下绿色的run按钮,就能马上出结果了。

如下面所示:

关于x,y的取值和目标最优值已经求出来了。

还可以进行灵敏度等相关分析:

上面对应每个约束的条件的影子价格,以及变化范围等等一应俱全。

此外,lpsolveIDE还提供了很多选项,大家根据自己的需要勾选相应的功能即可。

IDE的使用很简单,在这里不再详细说明了。另外输入语法格式等问题,可以点下面的链接查看详细说明:http://web.mit.edu/lpsolve/doc/

在左侧列表定位到lp file format 即可。

另外,lpsolve还支持其他求解器的语法格式。具体有以下:

  • MPS file format
  • CPLEX lp file format
  • LINDO lp file format
  • GNU MathProg file format
  • LPFML XML file format

具体说明也可以点击上面提供的链接,左侧定位到

Formulation of an lp model in lpsolve 即可。

怎样?是不是很神奇?

Part3 进阶篇

MPL下调用lpsolve

有些同学问我MPL是什么,我……,MPL就是Mathematical Programming Language 数学编程语言。lpsolve支持很多数学编程语言,有:

  • AMPL
  • MATLAB
  • O-Matrix
  • Sysquake
  • Scilab
  • Octave
  • FreeMat
  • Euler
  • Python
  • Sage
  • PHP
  • R
  • Microsoft Solver Foundation

碍于文章篇幅等原因,小编选取几种常用的数学编程语言,来给大家演示怎么在程序里使用lpsolve求解相关线性规划问题。

matlab下使用lpsolve

环境配置

在sourceforge网站(https://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.0/)

下载相应系统所需的文件,如需配置matlab中的lpsolve则下载xxx_dev_win64/32以及xxx_MATLAB_exe_win64/32,不过在此之前你需要先确认自己的操作系统是多少位的,一般来说都是64位的Windows 10操作系统了。 如图所示:

32位系统请下载这两个文件:

64位系统请下载这两个文件:

由于小编的电脑是64位win 10系统,所以下面的演示都是基于64位Windows系统的演示。

将下载的两个文件夹解压:

先进入文件夹lp_solve_5.5.2.0_MATLAB_exe_win64:

将解压后...\lp_solve_5.5.2.0_MATLAB_exe_win64\bin\win64目录下的mxlpsove.mexw64拷贝到...\lp_solve_5.5.2.0_MATLAB_exe_win64根目录下,如图所示:

注意:如果系统是32位的,则将mxlpsolve.dll文件一同拷贝到根目录下。

下面设置 matlab 的 path 变量,使其能搜索到 lp_solve_5.5.2.0_MATLAB_exe_win32 目录,在 命令行窗口中输入: pathtool,并添加刚刚解压设置好的lp_solve_5.5.2.0_MATLAB_exe_win32 目录到 path 中,保存。设置如下图:

这时心急的小伙伴感觉打开MATLAB运行一下,结果还是会出错。会提示:

这下哦豁了。心急吃不了热豆腐,我们还需要在做一步工作。

在之前下载的lp_solve_5.5.2.0_dev_win64文件夹中找到lpsolve55.dll文件,

然后在matlab命令行窗口输入“!path”命令 (注意,不是 path 命令,前面多了个英文状态下的感叹号) ,输出结果包含一堆路径:

PATH=C:\Program Files\MATLAB\R2014b\bin\win64;C:\ProgramData\Oracle\Java\javapath;C:\WINDOWS\system32;C:\WINDOWS;C:\WINDOWS\System32\Wbem;.....(此处省略一万字).....;C:\Users\xuesheng\AppData\Local\GitHubDesktop\bin;

其中每个目录都是以分号隔开的。我们lpsolve55.dll文件拷贝到任意一个目录下都可行的,如果不可行,那原因很有可能是(敲黑板!)因为下载的.dll文件版本不是对应64位的,如果是按照第一步下载的dev压缩包,那应该是不会出问题的。

在 matlab 中 输入 mxlpsolve 命令进行测试,如果输出如下信息表明配置成功。则可以愉快的运行啦~:

mxlpsolve MATLAB Interface version 5.5.0.6

using lpsolve version 5.5.2.0

Usage: [ret1, ret2, ...] = mxlpsolve('functionname', arg1, arg2, ...)

至此,环境配置完成。

如何调用

以一个具体的例子说明用lpsolve求解数学规划问题的方法。

假设我们要用matlab解决如下线性规划问题:

max x1 + 3x2 + 6.24x3 + 0.1x4 s. t. 78.26x2 + 2.9x4 >= 92.3

0.24x1 + 11.31x3 <= 14.8 12.68x1 + 0.08x3 + 0.9x4 >= 4 x1 >= 28.6 x4 >= 18 x4 <= 48.98

matlab语句如下:

 1>> lp=mxlpsolve('make_lp', 0, 4);
 2>> mxlpsolve('set_verbose', lp, 3);
 3>> mxlpsolve('set_obj_fn', lp, [1, 3, 6.24, 0.1]);
 4>> mxlpsolve('add_constraint', lp, [0, 78.26, 0, 2.9], 2, 92.3);
 5>> mxlpsolve('add_constraint', lp, [0.24, 0, 11.31, 0], 1, 14.8);
 6>> mxlpsolve('add_constraint', lp, [12.68, 0, 0.08, 0.9], 2, 4);
 7>> mxlpsolve('set_lowbo', lp, 1, 28.6);
 8>> mxlpsolve('set_lowbo', lp, 4, 18);
 9>> mxlpsolve('set_upbo', lp, 4, 48.98);
10>> mxlpsolve('set_col_name', lp, 1, 'COLONE');
11>> mxlpsolve('set_col_name', lp, 2, 'COLTWO');
12>> mxlpsolve('set_col_name', lp, 3, 'COLTHREE');
13>> mxlpsolve('set_col_name', lp, 4, 'COLFOUR');
14>> mxlpsolve('set_row_name', lp, 1, 'THISROW');
15>> mxlpsolve('set_row_name', lp, 2, 'THATROW');
16>> mxlpsolve('set_row_name', lp, 3, 'LASTROW');
17>> mxlpsolve('write_lp', lp, 'a.lp');
18>> mxlpsolve('get_mat', lp, 1, 2)
19
20ans =
21
22   78.2600
23
24>> mxlpsolve('solve', lp)
25
26ans =
27
28     0
29
30>> mxlpsolve('get_objective', lp)
31
32ans =
33
34   31.7828
35
36>> mxlpsolve('get_variables', lp)
37
38ans =
39
40   28.6000
41         0
42         0
43   31.8276
44
45>> mxlpsolve('get_constraints', lp)
46
47ans =
48
49   92.3000
50    6.8640
51  391.2928

代码下载请在后台回复【lpsolve】即可下载。

如果需还要其他功能,请参考包含完整API文档的网址(重要,推荐看!!!):http://web.mit.edu/lpsolve/doc/MATLAB.htm 从以上的过程我们看到用 lpsolve 建立一个规划问题的代码还是够麻烦的,想必你刚开始看到上面那些语句的时候,也是一头雾水。不要着急,对于这类简单的问题,还有更简便的方法。

lpsolve 为我们提供了一种简化的途径,我们注意到以上文件列表中有一个lp_maker.m和lp_solve.m文件。lp_maker.m文件的功能是创建一个(混合整数)线性规划问题,调用格式类似于其他matlab自带的优化工具箱,你只需要为它提供f、A、b、l、u几个矩阵,它会自动为你实现创建模型、设置目标函数、添加约束的过程。

类似的,假设我们要用matlab解决如下线性规划问题:

max 4x1 + 2x2 + x3 s. t. 2x1 + x2 <= 1 x1 + 2x3 <= 2 x1 + x2 + x3 = 1 x1 >= 0 x1 <= 1 x2 >= 0 x2 <= 1 x3 >= 0 x3 <= 2

可以用如下语句简化过程(lp_maker版):

 1>> f = [4 2 1];
 2>> A = [2 1 0; 1 0 2; 1 1 1];
 3>> b = [1; 2; 1];
 4>> l = [ 0 0 0];
 5>> u = [ 1 1 2];
 6>> lp = lp_maker(f, A, b, [-1; -1; 0], l, u, [], 1, 0); 
 7>> solvestat = mxlpsolve('solve', lp)  
 8
 9     solvestat = 0  
10
11>> obj = mxlpsolve('get_objective', lp)  
12
13     obj = 2.5000  
14
15>> x = mxlpsolve('get_variables', lp)  
16
17     x = 0.5000           
18
19         0      
20
21         0.5000  
22
23>> mxlpsolve('delete_lp', lp)

代码下载请在后台回复【lpsolve】即可下载。

或者只需要一句(lp_solve版):

>> [obj,x,duals,stat] = lp_solve(f, A, b, [-1; -1; 0], l, u, [], 1, 0); 高层次的包装带来简便的同时也会让我们失去对问题更精细化的控制。例如,要使用 lp_solve.m 和 lp_maker.m,你必须事先知道约束系数矩阵A,然而对于很多实际问题,由于问题规模太大或者其他限制,你不能事先知道A矩阵,而是要用嵌套的for循环一步步建立起约束条件的时候,这两个高层包装就显得力不从心了。

关于MATLAB下使用lpsolve的更多说明,请访问:http://web.mit.edu/lpsolve/doc/

左侧定位到Using lpsolve from MATLAB 即可。

Python下使用lpsolve

环境配置

lpsolve目前最新也只能支持到Python2.6版本而已了,所以下面的演示也是基于Python2.6版本的,系统是64位Windows10系统。

首先大家根据自己的系统版本下载相应的包。

然后在电脑上把Python2.6版本也给装上。

把刚刚下载的包解压出来,找到如下文件,双击安装,然后一路向西即可。(注意,此步要先安装好Python2.6版本。)

最后还有一步,就是把之前lp_solve_5.5.2.0_dev_win64包下的dll文件复制到C:\Windows\System32目录里面。

复制到C:\Windows\System32:

最后,打开Python2.6(如果电脑装了多个Python,注意打开的版本。),输入:

>>> from lpsolve55 import * >>> lpsolve()

如果显示以下信息,则大功告成:

至此,环境配置已经完成。

Python调用

在Python下,lpsolve 同样为我们提供了一种简化的途径。直接举个例子吧。

假如我们要用Python解决以下线性规划问题:

max 4x1 + 2x2 + x3 s. t. 2x1 + x2 <= 1 x1 + 2x3 <= 2 x1 + x2 + x3 = 1 x1 >= 0 x1 <= 1 x2 >= 0 x2 <= 1 x3 >= 0 x3 <= 2

从中我们可以得出几个相关矩阵:

f = [4, 2, 1] A = [[2, 1, 0], [1, 0, 2], [1, 1, 1]] b = [1, 2, 1]

注意到我们的单个变量约束并没有放进条件约束里面,lp_solve 可以设置单个变量的界限,它们是:

l = [ 0, 0, 0] u = [ 1, 1, 2]

现在在Python里输入下面代码:

1>>> f = [4, 2, 1]
2>>> A = [[2, 1, 0], [1, 0, 2], [1, 1, 1]]
3>>> b = [1, 2, 1]
4>>> l = [ 0, 0, 0]
5>>> u = [ 1, 1, 2]

然后开始求解我们的问题:

 1>>> from lpsolve55 import *
 2>>> from lp_maker import *
 3>>> lp = lp_maker(f, A, b, [-1, -1, 0], l, u, None, 1, 0)
 4>>> solvestat = lpsolve('solve', lp)
 5>>> obj = lpsolve('get_objective', lp)
 6>>> print obj
 72.5
 8>>> x = lpsolve('get_variables', lp)[0]
 9>>> print x
10[0.5, 0.0, 0.5]
11>>> lpsolve('delete_lp', lp)

关于Python下使用lpsolve的更多说明,请访问:http://web.mit.edu/lpsolve/doc/ ,

左侧定位到Using lpsolve from Python即可。

Part4 实战篇

高级编程语言使用lpsolve

上面讲了几种MPL怎么调用lpsolve,可能又有部分小伙伴不乐意了。咱平时撸的都是C/C++、Java这等高级语言的代码啊,哪里用过什么MATLAB什么的。别急,万能lpsolve怎么可能不支持高级编程语言呢!下面小编就一一为各位看官道来。

lpsolve支持以下几种编程语言:

  • C/C++
  • Java
  • Delphi, Free Pascal
  • VB, VBScript
  • VB.NET
  • C#.NET

官方介绍如下:

In several cases it is required that the solver is called from within the programming language in which an application is build. All the data is in memory and no files are created to provide data to the solver. lpsolve has a very rich, yet easy, API to do this.

碍于文章篇幅,我们还是挑几个大家常用的语言来讲解吧~。

C/C++使用lpsolve

在C/C++下配置lpsolve确实有点麻烦,所以,这里大家一定要看仔细,操作仔细了。每一步都不能出错,不然很难把程序编译出来的。

首先,大家找到去在sourceforge网站(https://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.5/)把这个文件下载下来:

为什么是下载32位的文件呢,因为我们编译的程序是x86程序,所以用的是32位的链接库,下载后解压出来,得到lp_solve_5.5.2.5_dev_win32文件夹:

小编用的编译器是微软的Visual Studio 2017。无论什么编译器,都需要确保以下几点才能运行成功:

  1. 添加头文件目录
  2. 添加库文件目录
  3. 链接时把库文件添加进去

下面小编以自己的编译环境为例,配置一下。

打开Visual Studio 2017,新建一个空项目,名字随便写,这里写的是lptest。

然后在右侧解决方案资源管理器里面-源文件里面添加一个.c文件。代码先别写,后面会给出。

配置头文件目录,在右侧解决方案资源管理器里面找到项目名称,右键属性:

包含目录库目录里面将我们的lp_solve_5.5.2.5_dev_win32文件夹路径添加进去,这个文件夹包含了程序所需的头文件库文件目录

最后,就是在程序开头,将这一句话添加进去,表示链接目标文件时,将lpsolve库给链接进去。否则,编译器将找不到函数的定义而报一堆错误。

可能,这样设置一开始代码还是不能编译成功,小编在好几台电脑上测试了,不知道是不是编译器的BUG。大家设置好以后生成提示未定义标识符之类的,请关掉编译器,重新打开,多试几次。

至此,环境配置完成。可以开始写代码了。下面一个代码演示了求解一个线性规划模型的示范,注释也说得足够清楚了,大家直接看代码吧。

  1#include "lp_lib.h"
  2   # define WIN32
  3#pragma comment(lib, "lpsolve55.lib")
  4
  5int demo()
  6{
  7    lprec *lp;
  8    int Ncol, *colno = NULL, j, ret = 0;
  9    REAL *row = NULL;
 10
 11    /* We will build the model row by row
 12    So we start with creating a model with 0 rows and 2 columns */
 13    Ncol = 2; /* there are two variables in the model */
 14    lp = make_lp(0, Ncol);
 15    if (lp == NULL)
 16        ret = 1; /* couldn't construct a new model... */
 17
 18    if (ret == 0) {
 19        /* let us name our variables. Not required, but can be useful for debugging */
 20        set_col_name(lp, 1, "x");
 21        set_col_name(lp, 2, "y");
 22
 23        /* create space large enough for one row */
 24        colno = (int *)malloc(Ncol * sizeof(*colno));
 25        row = (REAL *)malloc(Ncol * sizeof(*row));
 26        if ((colno == NULL) || (row == NULL))
 27            ret = 2;
 28    }
 29
 30    if (ret == 0) {
 31        set_add_rowmode(lp, TRUE);  /* makes building the model faster if it is done rows by row */
 32
 33                                    /* construct first row (120 x + 210 y <= 15000) */
 34        j = 0;
 35
 36        colno[j] = 1; /* first column */
 37        row[j++] = 120;
 38
 39        colno[j] = 2; /* second column */
 40        row[j++] = 210;
 41
 42        /* add the row to lpsolve */
 43        if (!add_constraintex(lp, j, row, colno, LE, 15000))
 44            ret = 3;
 45    }
 46
 47    if (ret == 0) {
 48        /* construct second row (110 x + 30 y <= 4000) */
 49        j = 0;
 50
 51        colno[j] = 1; /* first column */
 52        row[j++] = 110;
 53
 54        colno[j] = 2; /* second column */
 55        row[j++] = 30;
 56
 57        /* add the row to lpsolve */
 58        if (!add_constraintex(lp, j, row, colno, LE, 4000))
 59            ret = 3;
 60    }
 61
 62    if (ret == 0) {
 63        /* construct third row (x + y <= 75) */
 64        j = 0;
 65
 66        colno[j] = 1; /* first column */
 67        row[j++] = 1;
 68
 69        colno[j] = 2; /* second column */
 70        row[j++] = 1;
 71
 72        /* add the row to lpsolve */
 73        if (!add_constraintex(lp, j, row, colno, LE, 75))
 74            ret = 3;
 75    }
 76
 77    if (ret == 0) {
 78        set_add_rowmode(lp, FALSE); /* rowmode should be turned off again when done building the model */
 79
 80                                    /* set the objective function (143 x + 60 y) */
 81        j = 0;
 82
 83        colno[j] = 1; /* first column */
 84        row[j++] = 143;
 85
 86        colno[j] = 2; /* second column */
 87        row[j++] = 60;
 88
 89        /* set the objective in lpsolve */
 90        if (!set_obj_fnex(lp, j, row, colno))
 91            ret = 4;
 92    }
 93
 94    if (ret == 0) {
 95        /* set the object direction to maximize */
 96        set_maxim(lp);
 97
 98        /* just out of curioucity, now show the model in lp format on screen */
 99        /* this only works if this is a console application. If not, use write_lp and a filename */
100        write_LP(lp, stdout);
101        /* write_lp(lp, "model.lp"); */
102
103        /* I only want to see important messages on screen while solving */
104        set_verbose(lp, IMPORTANT);
105
106        /* Now let lpsolve calculate a solution */
107        ret = solve(lp);
108        if (ret == OPTIMAL)
109            ret = 0;
110        else
111            ret = 5;
112    }
113
114    if (ret == 0) {
115        /* a solution is calculated, now lets get some results */
116
117        /* objective value */
118        printf("Objective value: %f\n", get_objective(lp));
119
120        /* variable values */
121        get_variables(lp, row);
122        for (j = 0; j < Ncol; j++)
123            printf("%s: %f\n", get_col_name(lp, j + 1), row[j]);
124
125        /* we are done now */
126    }
127
128    /* free allocated memory */
129    if (row != NULL)
130        free(row);
131    if (colno != NULL)
132        free(colno);
133
134    if (lp != NULL) {
135        /* clean up such that all used memory by lpsolve is freed */
136        delete_lp(lp);
137    }
138
139    return(ret);
140}
141
142int main()
143{
144    demo();
145}

最后,还差一步,程序编译完成以后,运行时可能会提示找不到dll文件。这时候,要回到lp_solve_5.5.2.5_dev_win32文件夹,找到lpsolve55.dll文件。

将这个文件复制到可执行程序目录

终于,我们的程序运行成功了。

这只是一个非常简单的例子,关于更多lpsolve接口的使用,请访问:http://web.mit.edu/lpsolve/doc/ ,

左侧定位到lp_solve API reference即可。

Java下使用lpsolve

环境配置

在这里,要求的java是64位的JDK。

首先,大家找到去在sourceforge网站(https://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.5/)把这两个文件下载下来:

下载完成以后,分别解压两个包,得到lp_solve_5.5.2.5_dev_win64lp_solve_5.5.2.5_java两个文件夹。然后需要进行下面步骤:

lp_solve_5.5.2.5_dev_win64文件夹中的lpsolve55.dll

拷贝到C:\Windows\System32文件下:

lp_solve_5.5.2.5_java中lp_solve_5.5_java\lib\win64文件夹下的lpsolve55j.dll

拷贝到C:\Windows\System32文件下:

在项目中添加相应的jar包。这里我们新建一个演示项目名为lpsolve_test。右击“lpsolve_test”→选择Properties,在弹出的对话框左侧列表中选择Java Build Path,定位到Libraries,然后选择右侧的Add Exteral JARs

在弹出的对话框中,选择我们之前lp_solve_5.5.2.5_java/lp_solve_5.5_java/lib下的lpsolve55j.jar这个包。

这样,就可以愉快使用lpsolve了。

使用的话,Java和C/C++的API是差不多的。只不过由于Java的面向对象的特性,lpsolve API做了一层包装,Java和C/C++的API详细对照可以访问以下链接:http://web.mit.edu/lpsolve/doc/Java/docs/reference.html

关于C/C++详细的API可以参考官方说明文档。访问:http://web.mit.edu/lpsolve/doc/

定位到lp_solve API reference即可。

使用Java调用lpsolve求解混合线性最优化问题,由于lpsolve的说明文档模糊,仅提供了一个Demo说明如何调用,以及API文档,并且API文档说明非常简陋!不过小编为大家总结了一下使用的具体步骤:

  1. 创建LpSolve对象
  2. 添加目标函数
  3. 添加不等式约束
  4. 添加等式约束
  5. 设置参数是否为整数(默认为实数)
  6. 设置参数的上限值
  7. (可选)打印具体的矩阵
  8. 进行求解
  9. 提取出最优结果
  10. 提取出最优结果对应的参数值

下面提供一个比较通用的类:

  1package lpsolve_test;
  2import lpsolve.*;
  3import java.util.Arrays;
  4
  5
  6public class Optimator {
  7    private static LpSolve problem;
  8    /**
  9     * 求解整数规划问题
 10     * @param goal          目标函数矩阵,由于LpSolve读取数组时从下标1开始读取,数据需从下标1开始填充,0-1的放前面,有上限的放后面
 11     * @param stIeMatrix    不等式约束方程矩阵,由于LpSolve读取数组时从下标1开始读取,内层数据需从下标1开始填充
 12     * @param stEqMatrix    等式约束方程矩阵,由于LpSolve读取数组时从下标1开始读取,内层数据需从下标1开始填充
 13     * @param stIeRest      不等式约束条件矩阵,每次传入的是单个数字,不需要从1开始填充
 14     * @param stEqRest      等式约束条件矩阵,每次传入的是单个数字,不需要从1开始填充
 15     * @param ups           上限约束矩阵
 16     */
 17    public static void optimate(double[] goal,double[][] stIeMatrix,double[][] stEqMatrix,
 18            double[] stIeRest,double[] stEqRest,double[] ups) throws LpSolveException{
 19
 20        //1、创建LpSolve对象
 21        problem = LpSolve.makeLp(0, goal.length-1);
 22        //2、添加目标函数,会从下标1开始读取!下标1的参数会被忽略
 23        problem.setObjFn(goal);
 24
 25        //3、循环添加不等式约束,外层循环一次代表一个不等式
 26        if(stIeMatrix!=null){
 27            for(int i=0;i<stIeMatrix.length;i++){
 28                //同样数组的读取会从下标1开始
 29                problem.addConstraint(stIeMatrix[i], LpSolve.LE, stIeRest[i]);
 30            }
 31        }
 32
 33        //4、循环添加等式约束,外层循环一次代表一个等式
 34        if(stEqMatrix!=null){
 35            for(int i=0;i<stEqMatrix.length;i++){
 36                //同样数组的读取会从下标1开始
 37                problem.addConstraint(stEqMatrix[i], LpSolve.EQ, stEqRest[i]);
 38            }
 39        }
 40
 41        //5、设置参数的整数约束,1代表第一个参数
 42        for(int i=1;i<goal.length;i++){
 43            problem.setInt(i, true);
 44        }
 45
 46        //6、设置指定参数的上限值
 47        for(int i=1;i<=ups.length;i++){
 48            problem.setUpbo(i, ups[i-1]);
 49        }
 50
 51        problem.printLp();
 52        //求解
 53        problem.solve();
 54    }
 55    /**
 56     * 得到最优解
 57     * @return
 58     * @throws LpSolveException
 59     */
 60    public static double getObjective() throws LpSolveException{
 61        if(problem!=null){
 62            return problem.getWorkingObjective();
 63        }else{
 64            try {
 65                throw new Exception("还没有进行求解!");
 66            } catch (Exception e) {
 67                // TODO Auto-generated catch block
 68                e.printStackTrace();
 69            } 
 70            return 0;
 71        }
 72    }
 73    /**
 74     * 得到最优解对应的变量
 75     * @return
 76     * @throws LpSolveException
 77     */
 78    public static double[] getVariables() throws LpSolveException{
 79        if(problem!=null){
 80            return problem.getPtrVariables();
 81        }else{
 82            try {
 83                throw new Exception("还没有进行求解!");
 84            } catch (Exception e) {
 85                // TODO Auto-generated catch block
 86                e.printStackTrace();
 87            } 
 88            return null;
 89        }
 90    }
 91
 92//测试
 93    public static void main(String[] args) {
 94        try {
 95            double[][] stIeMatrix = new double[1][];
 96            stIeMatrix[0] = new double[]{0,1,2,3,4};
 97            double[] stRest = new double[]{1};
 98            optimate(new double[]{0,1,2,3,4},stIeMatrix,stIeMatrix,stRest,stRest,new double[]{1,1,5,6});
 99            System.out.println(getObjective());
100            System.out.println(Arrays.toString(getVariables()));
101        } catch (LpSolveException e) {
102            // TODO Auto-generated catch block
103            e.printStackTrace();
104        }
105    }
106}

这是运行结果:

关于更多Java下lpsolve的使用,请访问:http://web.mit.edu/lpsolve/doc/ ,左侧定位到Using lpsolve from Java即可。

Part5 总结

前面说了这么多,总之,总结起来,使用lpsolve就是以下三种方式:

  • 通过LPSolve IDE编写模型或者读取模型文件进行求解。
  • 使用数学编程语言创建模型,调用lpsolve求解。
  • 使用高级编程语言创建模型,调用lpsolve相关API进行求解。

至此,关于lpsolve的已经差不多讲解完了。这么长的文件,想必各位小伙伴看到这里也不容易。可能还有很多细节没有讲解,要想面面俱到的小伙伴只能去看官方的doc了。

---The End---

文案 && 编辑:邓发珩

审稿:江玉萍

测试:翟希鲁

指导老师: 秦时明岳(华中科技大学管理学院)

如对文中内容有疑问,欢迎交流。PS:部分资料来自网络。

如有需求,可以联系:

秦虎老师(professor.qin@qq.com)

邓发珩 (华中科技大学管理学院本科二年级:2638512393@qq.com、个人公众号:程序猿声)

江玉萍 (南京大学工程管理学院研究生三年级:jiangyuping@smail.nju.edu.cn)

翟希鲁 (华中科技大学管理学院本科二年级:17021983211171@qq.com)

本文分享自微信公众号 - 数据魔术师(data-magician),作者:邓发珩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

    上一篇文章代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析讲解了destroy和repair方法的具体实现代码,好多读者...

    用户1621951
  • 星座数据说 | 金牛最浪双鱼最富,摩羯男最爱姐弟恋

    用户1621951
  • 运筹学教学|十分钟快速掌握单纯形法(附C++代码及算例)

    国庆节就要到了! 不如今儿咱就来讨论一下去哪玩耍吧! 南京?丽江?西安?…… 众人(汗):一个月前就没票了。。。 哦……那么,就只能……学习了…… 好巧不巧,运...

    用户1621951
  • 干货 | 关于数学规划求解器lp_solve 这里有份超全面超详细的教程,你离lpsolve高手只有一步之遥!

    Mixed Integer Linear Programming (MILP) solver lp_solve solves pure linear, (mix...

    短短的路走走停停
  • 用对偶法求解 SVR

    即 它在线性函数两侧制造了一个“间隔带”,对于所有落入到间隔带内的样本,都不计算损失;只有间隔带之外的,才计入损失函数

    杨熹
  • Python将图片转化成文字

    我们之前学过词云能将数据变成图片展示出来,那么今天我们就来看个不同的,将图片变成字符输出。

    我被狗咬了
  • Netty学习笔记(一)

    Netty是一种可以轻松快速的开发类似协议服务器和客户端网络应用程序的NIO客户端服务器框架,它大大简化了TCP或者UDP服务器的网络编程,但是你仍然可以访问和...

    加多
  • “想哭”蠕虫病毒来自朝鲜?神秘黑客大军在西方已成传说

    朝鲜是个什么样的国家?对于身处智能时代的“低头族”,大多数人脑海中闪现的第一个念头必然是——没有WIFI,互联网技术落后!但是西方媒体和专家认为,这种认知大错特...

    企鹅号小编
  • 杨老师课堂_安卓教程第一篇之入门

    杨校
  • Java魔法堂:以Windows服务的形式运行Java程序

    一、前言                               由于防止维护人员误操作关闭Java控制台程序,因此决定将其改造为以Windows服务的形式...

    ^_^肥仔John

扫码关注云+社区

领取腾讯云代金券