glpk是一个开源的求解线性规划的包。
添加源：
deb http://us.archive.ubuntu.com/ubuntu saucy main universe
更新源并安装：
sudo apt-get update
sudo apt-get install glpk
写入如下glpsolEx.mod 文件
1 /* Variables */
2 var x1 >= 0;
3 var x2 >= 0;
4 var x3 >= 0;
5
6 /* Object function */
7 maximize z: x1 + 14*x2 + 6*x3;
8
9 /* Constrains */
10 s.t. con1: x1 + x2 + x3 <= 4;
11 s.t. con2: x1 <= 2;
12 s.t. con3: x3 <= 3;
13 s.t. con4: 3*x2 + x3 <= 6;
14
15 end;
运行 glpsol -m glpsolEx.mod -o glpsolEx.sol，输出到glpsolEx.sol文件中
结果为：
1 Problem: glpsolEx
2 Rows: 5
3 Columns: 3
4 Non-zeros: 10
5 Status: OPTIMAL
6 Objective: z = 32 (MAXimum)
7
8 No. Row name St Activity Lower bound Upper bound Marginal
9 ------ ------------ -- ------------- ------------- ------------- -------------
10 1 z B 32
11 2 con1 NU 4 4 2
12 3 con2 B 0 2
13 4 con3 B 3 3
14 5 con4 NU 6 6 4
15
16 No. Column name St Activity Lower bound Upper bound Marginal
17 ------ ------------ -- ------------- ------------- ------------- -------------
18 1 x1 NL 0 0 -1
19 2 x2 B 1 0
20 3 x3 B 3 0
21
22 Karush-Kuhn-Tucker optimality conditions:
23
24 KKT.PE: max.abs.err = 0.00e+00 on row 0
25 max.rel.err = 0.00e+00 on row 0
26 High quality
27
28 KKT.PB: max.abs.err = 4.44e-16 on row 4
29 max.rel.err = 1.11e-16 on row 4
30 High quality
31
32 KKT.DE: max.abs.err = 0.00e+00 on column 0
33 max.rel.err = 0.00e+00 on column 0
34 High quality
35
36 KKT.DB: max.abs.err = 0.00e+00 on row 0
37 max.rel.err = 0.00e+00 on row 0
38 High quality
39
40 End of output
帮助文档中一个求解八皇后的例子：
1 /* QUEENS, a classic combinatorial optimization problem */
2
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
4
5 /* The Queens Problem is to place as many queens as possible on the 8x8
6 (or more generally, nxn) chess board in a way that they do not fight
7 each other. This problem is probably as old as the chess game itself,
8 and thus its origin is not known, but it is known that Gauss studied
9 this problem. */
10
11 param n, integer, > 0, default 8;
12 /* size of the chess board */
13
14 var x{1..n, 1..n}, binary;
15 /* x[i,j] = 1 means that a queen is placed in square [i,j] */
16
17 s.t. a{i in 1..n}: sum{j in 1..n} x[i,j] <= 1;
18 /* at most one queen can be placed in each row */
19
20 s.t. b{j in 1..n}: sum{i in 1..n} x[i,j] <= 1;
21 /* at most one queen can be placed in each column */
22
23 s.t. c{k in 2-n..n-2}: sum{i in 1..n, j in 1..n: i-j == k} x[i,j] <= 1;
24 /* at most one queen can be placed in each "\"-diagonal */
25
26 s.t. d{k in 3..n+n-1}: sum{i in 1..n, j in 1..n: i+j == k} x[i,j] <= 1;
27 /* at most one queen can be placed in each "/"-diagonal */
28
29 maximize obj: sum{i in 1..n, j in 1..n} x[i,j];
30 /* objective is to place as many queens as possible */
31
32 /* solve the problem */
33 solve;
34
35 /* and print its optimal solution */
36 for {i in 1..n}
37 { for {j in 1..n} printf " %s", if x[i,j] then "Q" else ".";
38 printf("\n");
39 }
40
41 end;