专栏首页程序猿声干货 数学规划求解器lp_solve超详细教程 已
原创

干货 数学规划求解器lp_solve超详细教程 已

前言

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

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

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

一个至关重要的问题:

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

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

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

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

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

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

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

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

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

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

惊得差点没把笔吞下去。

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

我*,25个变量。

看着那一堆约束条件,

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

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

用Table?开什么国际玩笑,

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

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

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

用C++,

写个Simple algorithm用电脑跑一跑?

但是,像小编这种,

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

左不清explicit,右不明volatile。

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

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

气氛陷入了尴尬的沉默,

沉默是今晚的康桥。

在我快急哭了的时候,

小姐姐却淡淡一笑。

“解不出来吗?”

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

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

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

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

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

那里的老师很厉害,

你可以了解一下哦。”

“……”

“……”

image

不过话说回来,

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

特别是变量很多的那种,

有什么办法呢?

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

那你就真的是out了。

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

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

![
image

](http://upload-images.jianshu.io/upload_images/10386940-53bfe8b6039283f2?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

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的所有资源都可以在这个主页上找到。

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

image

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

Part2

入门篇

简单上手

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

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

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

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

LPSolve

IDELPSolve

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

界面如下:

image

它的介绍如下:

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按钮,就能马上出结果了。

image

如下面所示:

image

关于x,y的取值和目标最优值已经求出来了。还可以进行灵敏度等相关分析:

image

上面对应每个约束的条件的影子价格,以及变化范围等等一应俱全。此外,lpsolveIDE还提供了很多选项,大家根据自己的需要勾选相应的功能即可。

image

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位系统请下载这两个文件:

image

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

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

image

先进入文件夹lp_solve_5.5.2.0_MATLAB_exe_win64:

image

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

image
image

注意:如果系统是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 中,保存。设置如下图:

image

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

image

这下哦豁了。心急吃不了热豆腐,我们还需要在做一步工作。在之前下载的lp_solve_5.5.2.0_dev_win64文件夹中找到lpsolve55.dll文件,

image

然后在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.6using lpsolve version 5.5.2.0Usage: 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

如果需还要其他功能,请参考包含完整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几个矩阵,它会自动为你实现创建模型、设置目标函数、添加约束的过程

从以上的过程我们看到用 lpsolve 建立一个规划问题的代码还是够麻烦的,想必你刚开始看到上面那些语句的时候,也是一头雾水。不要着急,对于这类简单的问题,还有更简便的方法。

Python下使用lpsolve

环境配置

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

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

image

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

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

image
image

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

image

复制到C:\Windows\System32:

image

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

>>> from lpsolve55 import *

>>> lpsolve()

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

image

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

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支持以下几种编程语言:

官方介绍如下:

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/)把这个文件下载下来:

image

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

image

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

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

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

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

image

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

image

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

image

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

image

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

image

可能,这样设置一开始代码还是不能编译成功,小编在好几台电脑上测试了,不知道是不是编译器的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}

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

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

image

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

image

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

image

这只是一个非常简单的例子,关于更多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/)把这两个文件下载下来:

image
image

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

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

image

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

image

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

image

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

image

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

image

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

image
image

这样,就可以愉快使用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}

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

这是运行结果:

image

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

Part5

总结

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

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

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

Part6

欲获取代码,请关注我们的微信公众号【程序猿声】,在后台回复:lpsolve。即可获取。

微信公众号

推荐文章:10分钟教你用Python做个打飞机小游戏超详细教程

推荐文章:10分钟教你用python下载和拼接微信好友头像图片

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    短短的路走走停停
  • 教你使用Column Generation求解VRPTW的线性松弛模型

    此前向大家介绍了列生成算法的详细过程,以及下料问题的代码。相信各位小伙伴对Column Generation已经有了一个透彻的了解了。

    短短的路走走停停
  • 【算法】用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle)

    那么,我们将8皇后问题推广一下,就可以得到我们的N皇后问题了。N皇后问题是一个经典的问题,在一个NxN的棋盘上放置N个皇后,使其不能互相攻击 (同一行、同一列、...

    短短的路走走停停
  • Python 算法实战系列:栈

    学Python最简单的方法是什么?推荐阅读:Python开发工程师成长魔法 栈(stack)又称之为堆栈是一个特殊的有序表,其插入和删除操作都在栈顶进行操作,并...

    小小科
  • 文本相似性的总结

    说到文本相似性可以有很多种划分的方式,从文章的长短可以分别处理,从计算的方式可以分为深度学习和机器学习方式,从实现目的上可以分为去重和匹配...

    sladesal
  • Oracle的二维表管理

    –创建表: –使用:create table 表名(字段名 类型,字段名 类型,…); –数据类型: –number类型 –数值类型 –整数类型 nu...

    葆宁
  • ORDER BY导致未按预期使用索引

    在MySQL中经常出现未按照理想情况使用索引的情况,今天记录一种Order by语句的使用导致未按预期使用索引的情况。

    July
  • 关于索引以及B-Tree的实现

    对于多数的应用系统来说,查询数据的频率是远远高于写入或者更新数据的频率,在大数据量的场景中,常规的查询方式可能在效率上达不到预期, 此时我们需要对SQL查询语句...

    每天学Java
  • 论文赏析[EMNLP18]用序列标注来进行成分句法分析

    Constituent Parsing as Sequence Labelinggodweiyang.com

    godweiyang
  • 千米感知误差低于5%,嬴彻发布全球领先的超长距精准3D感知技术

    行驶在高速公路上的自动驾驶重卡,时速保持在 80-100 km/h,即每秒移动大约 25 米。

    量子位

扫码关注云+社区

领取腾讯云代金券