【学界|编码】整数规划求解方法大全（附Lingo代码）

↑↑↑↑↑点击上方蓝色字关注我们！

『运筹OR帷幄』转载

作者：张敬信

全部变量限制为整数的规划问题，称为纯整数规划；部分变量限制为整数的规划问题，称为混合整数规划；变量只取0或1的规划问题，称为0-1整数规划。

整数规划问题，建议使用Lingo软件求解。常用的整数规划问题解法有：

（1）分枝定界法：可求纯或混合整数线性规划。

（2）割平面法：可求纯或混合整数线性规划。

（3）隐枚举法：用于求解0-1整数规划，有过滤法和分枝法。

（4）匈牙利法：解决指派问题（0-1规划特殊情形）。

（5）蒙特卡罗法：求解各种类型规划。

分枝定界法

分支定界法的基本思想是：设有最大化的整数规划问题A，先解与之相应的线性规划问题B，若B的最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z2, 而A的任意可行解的目标函数值将是z*的一个下界z1, 分支定界法就是将B的可行域分成子区域（称为分支）的方法，逐步减小z2和增大z1，最终求到z*。

例1 分枝定界法原理示例：

Lingo代码：

model:

max=5*x1+8*x2;

x1+x2<6;

5*x1+9*x2<45;

@gin(x1);

@gin(x2);

end

运行结果：

Global optimal solution found.

Objective value: 40.00000

Variable Value

X1 0.000000

X2 5.000000

0-1整数规划

变量

只能取值

, 该约束条件可表示为：

1、隐枚举法

例2 求解下列0-1规划问题：

求解思路：

（1）先试探性地求一个可行解，易看出

满足约束条件，故是一个可行解，相应的目标函数值为

（2） 由于是求极大值，故目标值

的解，不必检验是否满足约束条件即可删除，于是可增加一个约束条件（称为过滤条件）：

（3）用全部枚举法，3个变量共

种可能的组合，用过滤条件（并计算目标函数值，不断改进过滤条件）筛选每个可能的组合，最终得到问题的最优解。

隐枚举法求解过程如下表所示：

从而得到最优解为

, 最优值为

。

Lingo代码：

model:

max=3*x1-2*x2+5*x3;

x1+2*x2-x3<2;

x1+4*x2+x3<4;

x1+x2<3;

4*x2+x3<6;

@bin(x1);

@bin(x2);

@bin(x3);

end

运行结果：

Global optimal solution found.

Objective value: 8.000000

Variable Value

X1 1.000000

X2 0.000000

X3 1.000000

2、指派问题

指派问题可以描述为整数规划问题，暂略（放图论部分）

蒙特卡罗法（随机取样法）

前面的方法，主要是针对线性整数规划而言，对于非线性整数规划没有通用的有效解法。

整数规划由于限制变量是整数，增加了求解难度，但整数解是有限个，所以可以采用枚举法。当枚举个数很多时，显性枚举是不现实的，但利用蒙特卡罗随机取样法，在一定的计算量下是可以得到满意解的。

例3 求解如下非线性整数规划问题：

若用显枚举法，共需

个点，计算量非常大。但用蒙特卡罗法随机计算

个点，便可找到满意解。

Matlab代码：

目标函数：

主程序：

运行结果（注意由于是随机取样，故每次的运行结果可能不一样）：

x0 = 43 94 1 99 5

p0 = 49298

Elapsed time is 45.494952 seconds.

Lingo代码：

model:

sets:

row/1..4/:b;

col/1..5/:c1,c2,x;

link(row,col):a;

endsets

data:

c1=1,1,3,4,2;

c2=-8,-2,-3,-1,-2;

a=1 1 1 1 1

1 2 2 1 6

2 1 6 0 0

0 0 1 1 5;

b=400,800,200,200;

enddata

[email protected](col:c1*x^2+c2*x);

@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));

@for(col:@gin(x));

@for(col:@bnd(0,x,99));

end

运行结果：

Local optimal solution found.

Objective value: 51568.00

Variable Value

X( 1) 50.00000

X( 2) 99.00000

X( 3) 0.000000

X( 4) 99.00000

X( 5) 20.00000

混合整数规划（配送选址问题）

物流配送中心选址问题，是在给定某一地区所有备选点的地址集合中选出一定数目的地址建立配送中心，从而建立一系列的配送区域，以实现选出点建立的配送中心与各需求点和工厂(供货点)形成的配送系统总物流费用最小。例如，如图1所示。

总费用=运输费用+配送费用+仓储费用+固定成本

设有

个供应工厂，

个客户，

个备选配送中心；

表示第

个工厂的产量

;

表示第

个客户的需求量

;

表示第

个配送中心的单位管理成本

;

表示建立第

个配送中心的固定成本；

指示是否选中第

个配送中心，

表示选中，

表示未选中；

表示配送中心的最大限制数目；

表示第

个供应工厂到第

个配送中心的运输单价；

表示第

个配送中心到第

个客户的配送单价；

表示第

个供应工厂到第

个配送中心的运量；

表示第

个配送中心到第

个客户的运量。

则配送选址问题数学模型的一般形式如下：

例4 设有4个备选物流配送中心地址，6个工厂为其供货，6个客户需要产品，最多设置3个物流配送中心。工厂到物流配送中心的运输价格见表2，物流配送中心到客户的运输价格见表3，工厂的总生产能力见表4，物流配送中心的固定成本、单位管理成本，及容量见表5，客户的需求量见表6：

Lingo代码：

model:

sets:

factory/p1..p6/:p;

warhouse/w1..w4/:a,f,g;

customer/c1..c6/:d;

tr/tr1..tr4/:z;

link1(factory,warhouse):c,w;

link2(warhouse,customer):h,x;

endsets

data:

p=40000,50000,60000,70000,60000,40000;

a=70000,60000,70000,50000;

f=500000,300000,400000,400000;

g=3,2,5,4;

d=10000,20000,10000,20000,30000,10000;

c = 6 5

4 2

2 3 4 9

6 8 7 5

7 4 2 3

4 2 5 1

3 4 1 7;

H = 3 2

7 4 7 5

6 1 4 2 5 3

2 4 5 3 6 8

5 6 3 7 4 6;

enddata

[email protected](link1(k,i):c(k,i)*w(k,i))[email protected](link2(i,j):h(i,j)*x(i,j))

[email protected](link1(k,i):g(i)*w(k,i))[email protected](warhouse(i):f(i)*z(i));

@for(factory(k):@sum(link1(k,i):w(k,i))<=p(k));

@for(warhouse(i):@sum(link2(i,j):x(i,j))[email protected](link1(k,i):w(k,i)));

@for(customer(j):@sum(link2(i,j):x(i,j))>=d(j));

@for(warhouse(i):@sum(link1(k,i):w(k,i))<=(a(i)*z(i)));

@sum(tr(i):z(i))<=3;

@for(tr(i):@bin(z));

end

运行结果：

Global optimal solution found.

Objective value: 1480000

Variable Value

Z(TR2) 1.000000

Z(TR4) 1.000000

W( P1,W4) 40000.00

W( P5,W2) 60000.00

X( W2,C2) 20000.00

X( W2,C3) 10000.00

X( W2,C4) 20000.00

X( W2,C6) 10000.00

X( W4,C1) 10000.00

X( W4,C5) 30000.00

结果表明，最小物流成本为1480000；最优方案是选择2号和4号备选地址作为物流配送中心；由工厂1向4号配送中心供应40000，由工厂5向2号配送中心供应60000；配送中心2分别向客户2、3、4、6供货20000、10000、20000、10000，配送中心4分别向客户1、5供货10000、30000。

主要参考文献：

1、吴刚, 张敬信等. 数学建模与数学实验，北京: 中国商业出版社，2017

2、卓金武等. Matlab在数学建模中的应用，北京：北京航空航天大学出版社，2011

3、谢金星，薛毅. 优化建模与LINDO/LINGO软件，北京：清华大学出版社，2006

4、司守奎，孙玺菁. 数学建模算法与应用，北京：国防工业出版社，2013

文章作者：张敬信（ 哈工大数学博士哈尔滨商业大学教师）

责任编辑：王源（东北大学系统工程博士生）

微信编辑：sunny