http://www.ma-xy.com

第一章整数规划和混合整数规划 1

1.1 整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 0-1 整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 混合整数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3.2 混合整数规划的一般形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3.3 MATLAB

应用实例

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3.4 工厂选址问题：混合整数规划求解 . . . . . . . . . . . . . . . . . . . . . . 4

http://www.ma-xy.com

第一章整数规划和混合整数规划

1.1 整数规划

在广义的整数规划中，我们要求某一规划问题中的变量 x = (x

, x

, . . . , x

) 有一部分取整

数。下面提到的整数规划是指，在线性规划的基础上，要求变量 x 全部为整数，此类问题亦称为

线性整数规划，其一般形式为

max c

s.t.







A(x) ⩽ b

x ∈ Z

其中：Z

表示非负整数的集合。x ∈ Z

，A ∈ R

m×n

，b ∈ R

，c ∈ R

。设其可行域 S = {x ∈

|Ax ⩽ b}。通常采用割平面法和分支定界法来求解整数规划，这里不做详细介绍。

1.2 0-1 整数规划

线性整数规划是线性规划的特例，但其又有自身的特性，当整数规划中的整数变量只允许在

0 或者 1 内取值时，被称为 0-1 整数规划

min c

s.t.







Ax ⩾ b

= 0/1

其中：x = (x

, x

, . . . , x

)，A ∈ R

m×n

，b ∈ R

，c ∈ R

。由于自变量 x 的取值有限，因此，自

变量个数不变的情况下，可以采用穷举法得到最优解。在 MATLAB 低版本中，采用 bintprog 来

求解 0-1 整数规划，之后的高版本采用 intlinprog 来求解。bintprog 的调用格式为

[x,fval,exitag,output]=bintprog(f,A,b,Aeq,beq,x0,options)

http://www.ma-xy.com

1.3 混合整数规划第一章整数规划和混合整数规划

用 bintprog 求解如下 0-1 规划问题

min f (x) = x

+ 2x

+ 3x

+ x

s.t.











+ 3x

+ 5x

+ 4x

+ 7x

⩾ 8

+ x

+ 4x

+ 2x

⩾ 5

= 0/1

求解程序如下

1 f = [ 1 , 2 , 3 , 1 , 1 ] ;

2 A = [−2,−3,− 5,−4,−7;−1,−1,−4,−2,−2];

3 b = [ −8; −5];

4 [ x , f v al ] = bint pro g ( f , A, b)

1.3 混合整数规划

1.3.1 问题的引入与分析

考虑如下物流选址问题：设有客户 M = {1, 2, . . . , m}，地点集 N = {1, 2, . . . , n}。我们希望

从地点集 N 中选择若干个地点修建设备。假设在第 j ∈ N 个地点修建设备的费用为 f

，设 x

表示客户 i 从 j 中获得的商品量，c

表示商家运输单位商品所能产生的效应。我们的目标是求

最小费用。

解：引入二元变量 y ∈ B

，其中 y

= 1 表示在 j 地修建设备

max



i=1



j=1

−



j=1

s.t.













j∈N

= b

i ∈ M



i∈M

− µ

⩽ 0 j ∈ N

⩾ 0, i ∈ M, j ∈ N, y ∈ B

待解变量为 (x, y)。

当然，如果不考虑 j 地的建设费用 f

，则不需要引入 0-1 变量 y，于是有

max



i=1



j=1

s.t.













= b

i ∈ M



= µ

j ∈ N

⩾ 0, i ∈ M, j ∈ N

http://www.ma-xy.com 2 http://www.ma-xy.com

http://www.ma-xy.com

第一章整数规划和混合整数规划 1.3 混合整数规划

进而，如果产量和销量相等则有 s.t.



。于是物流选址问题就变成产销运输问题。

可以发现，上述问题的优化变量有 x, y，x ∈ R

m×n

, y ∈ B

，这是一个既有实数变量又有整

数变量 y 的混合优化问题。

1.3.2 混合整数规划的一般形式

我们称优化变量中既有实数变量又有整数变量的优化问题为混合整数优化问题，其一般形式

为

max c

x + h

s.t.











Ax + Gy ⩽ b

x ∈ Z

y ∈ R

其中：A ∈ R

m×n

，G ∈ R

m×p

，c ∈ R

，b ∈ R

，Z

表示非负整数，R

表示非负实数。

1.3.3 MATLAB 应用实例

MATLAB 中，用 intlinprog 求解整数规划、0-1 规划和混合整数规划问题。其调用格式为

[x,fval,exitag,output]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,options)

其中：intcon 为整数变量的序号：设优化变量为 x = (x

, x

, . . . , x

)

，如果 x

为整数变量，

则 intcon = [2, 3]。

混合整数优化的一般形式为

min

s.t.











Ax ⩽ b

Aeqx ⩽ beq

lb ⩽ x ⩽ ub

x为部分整数

用 intlinprog 求解如下混合整数规划问题

min

+ x

s.t.











+ 2x

⩾ −14

− 4x

− x

⩽ −33

+ x

⩽ 20

为整数

求解程序如下

http://www.ma-xy.com 3 http://www.ma-xy.com

http://www.ma-xy.com

1.3 混合整数规划第一章整数规划和混合整数规划

1 f = [ 8 ; 1 ] ;

2 int con = 2 ;

3 A = [ −1 ,− 2; −4 , −1;2,1];

4 b = [14 ; − 3 3; 20 ];

5 x = i n t li n p r og ( f , incon , A, b , opt ions ) ;

6 opti ons = optimoptions ( ’ i n t li n p ro g ’ , ’ Display ’ , ’ o f f ’ )

如果还要求整数变量 x

为 0-1 变量，可进行如下设置

1 lb = [ 0 ; 0 ] ;

2 ub = [ i n f ; 1 ] ;

1.3.4 工厂选址问题：混合整数规划求解

前面的引例中，我们介绍了工厂选址问题：但其仅有工厂和销售点 M，在实际过程中，我们

知道还应存在仓库，商家生产产品，然后将产品运输到仓库存储，零销商从仓库中进货去销售。

现在，我们要确定一个工厂，仓库销售点的匹配，来使商家的利润最大。即在哪进、在哪销以及

销多少的问题。

设 F 为工厂的数量，W 为仓库的数量，S 为销售点的数量，f 为第 f 个工厂，w 为第 w 个

仓库，s 为第 s 个销售点，用 □ 表示工厂，∗ 表示仓库，◦ 表示销售点。工厂选址问题如图 (1.1)

所示

图 1.1: 工厂选址问题示意图

假设我们已经知道各 f, w, s 的位置，并且假设有 p 种可销售的产品，p 为第 p 种产品。设

每个销售点 S 对产品 p 的销售量为 d(s, p)，每个工厂 f 对产品 p 的产量不超过 pcap(f, p)，仓

库 w 的容量为 wcap(w)，从仓库 w 转移到销售点 s 的产品 p 的量小于 turn(p) ∗ wcap(p)，其中

turn(p) 为产品转移率，并且假设每个销售点 s 只能有一个进货仓库。

商品的转移费用依赖于 f, w, s 之间的距离，设 dist(a, b) 表示 ab 之间的距离，并且已知。则

a 到 b 转移产品 p 的花费为 dist(a, b) ∗ tcost(p)。其中：tcost(p) 为产品单位距离的转移费用。

设 pcost(f, p) 为工厂 f 生产单位产品 p 的费用。

http://www.ma-xy.com 4 http://www.ma-xy.com

http://www.ma-xy.com

第一章整数规划和混合整数规划 1.3 混合整数规划

现在求工厂到仓库的产品转移量 x(p, f, w)，使费用最小。并且求销售点 s 从哪个仓库进货

使得费用最小 (y(s, w) = 1 表示 s 从 w 进货)，则目标为

目标 1：运输量 × (成本费 + 运输费)

obj1 =



x(p, f, w) · (pcost(f, p) + tcost(p) · dist(f, w))

目标 2：需求量 × 运输费

obj2 =



d(s, p) · tcost(p) · dist(s, w) · y(s, w)

综合目标为

min

obj = obj1 + obj2

约束条件：

¬工厂 f 的生产限制



x(p, f, w) ⩽ pcap(f, p)

要满足需求量



x(p, f, w) =



(d(s, p) · y(s, w))

®仓库 W 的容量限制



(d(s, p)/turn(p)) · y(s, w) ⩽ wcap(w)

¯每个 s 只能有一个进货仓库 w



y(s, w) = 1

x ⩾ 0

y ∈ {0, 1}

上述问题是一个混合线性规划问题，其求解程序如下

1 %% 工厂，仓库和销售网点

2 % 这个例子说明了如何建立和求解混合整数线性规划问题。

3 % 问题是要找到一组工厂，仓库和销售网点之间的最佳生产和分销水平。

4 %% 随机生成位置

5 rng de f au lt % for r e pro d u c i bi l i t y

6 N = 20 ; % N from 10 to 30 seems to work . Choose lar ge value s with caut io n .

7 N2 = N*N;

8 f = 0 . 05 ; % 比重 o f f a c t o r i e s

9 w = 0 .05 ; % de nsi ty of warehouses

http://www.ma-xy.com 5 http://www.ma-xy.com

http://www.ma-xy.com

1.3 混合整数规划第一章整数规划和混合整数规划

10 s = 0 . 1 ; % d ens ity o f s a l e s o utl e t s

11 F = f l o o r ( f *N2) ; % number of f a c t o r i e s

12 W = f l o o r (w*N2) ; % number o f warehouses

13 S = f l o o r ( s *N2) ; % number of s a l e s out l e ts

14 x yl oc = randperm (N2, F+W+S) ; % unique l o c at i o ns of f a c i l i t i e s

15 [ xloc , yl oc ] = ind2sub ( [N N] , xylo c ) ;

16 h = f i g u r e ;

17 p lot ( x loc ( 1 :F) , y loc ( 1 :F) , ’ r s ’ , x lo c (F+1:F+W) , ylo c (F+1:F+W) , ’ k* ’ , . . .

18 xl oc (F+W+1:F+W+S) , ylo c (F+W+1:F+W+S ) , ’ bo ’ ) ;

19 legend ( ’ 工厂 ’ , ’ 仓库 ’ , ’ 销售网点 ’ , ’ Location ’ , ’ EastOutside ’ )

20 xlim ( [ 0 N+1]) ; ylim ( [ 0 N+1])

22 %% 生成随机容量 , 成本 , 和需求

23 P = 20 ; % 20 种产品

24 % 产品的生产成本在 20 到 100 之间

25 pcost = 80*rand (F,P) + 2 0;%每个工厂F生产产品P的成本矩阵 pcos t

26 % 产品生产的限量 between 500 and 1500 f or each product/ f ac tor y

27 pcap = 1000* rand (F,P) + 50 0;%每个工厂F生产产品P的限量

28 % 仓库容量限制 between P*400 and P*800 f or each product/warehouse

29 wcap = P*400* rand (W,P) + P*400;%每个仓库W存储产品P的限量

30 % 产品转移率 between 1 and 3 f or each product

31 turn = 2*rand ( 1 ,P) + 1 ;%20 个产品的转移率在 1−3之间

32 % 单位距离转移产品的花费 between 5 and 10 f o r each product

33 t c os t = 5* rand ( 1 ,P) + 5 ;

34 % 销售点的产品需求 between 200 and 500 f or each product/ o u tle t

35 d = 300*rand (S ,P) + 20 0;

36 %% 生成目标和约束矩阵和向量

37 obj1 = z eros (P, F,W) ;

38 obj2 = z eros (S ,W) ;

39 dist fw = z er os (F,W) ; % 距离矩阵：工厂−仓库

40 f o r i i = 1 :F

41 f o r j j = 1 :W

42 di st fw ( i i , j j ) = abs ( x loc ( i i ) − x loc (F + j j ) ) + abs ( ylo c ( i i ) − yl oc (F + j j ) ) ;

43 end

44 end

45 dist sw = z er os (S ,W) ; % 距离矩阵：销售网点−仓库

46 f o r i i = 1 : S

47 f o r j j = 1 :W

48 dists w ( i i , j j ) = abs ( x loc (F + W + i i ) − x loc (F + j j ) ) . . .

49 + abs ( yl oc (F + W + i i ) − y loc (F + j j ) ) ;

50 end

51 end

52 % 构建目标 1 和目标 2 obj1 and obj2 .

53 f o r i i = 1 :P

54 f o r j j = 1 :F

55 f o r kk = 1:W

56 obj1 ( i i , j j , kk) = pcos t ( j j , i i ) + t co s t ( i i ) * di st fw ( jj , kk) ;

57 end

58 end

59 end

60 f o r i i = 1 : S

61 f o r j j = 1 :W

62 obj2 ( i i , j j ) = d istsw ( i i , j j ) *sum(d( i i , : ) .* t co s t ) ;

http://www.ma-xy.com 6 http://www.ma-xy.com

http://www.ma-xy.com

第一章整数规划和混合整数规划 1.3 混合整数规划

63 end

64 end

65 % 合并目标

66 obj = [ obj1 ( : ) ; obj2 ( : ) ] ; % obj i s the o bj e ct i ve fun ction ve ctor

67 matwid = l engt h ( obj ) ;

68 Aineq = s p a llo c (P*F + W, matwid ,P*F*W + S*W) ; % 配置 sp ars e Aeq为非零元素配置内存

69 bineq = ze ro s (P*F + W,1 ) ; % A ll oca te bineq as f u l l

70 % Zero mat rices o f convenient s i z e s :

71 c l e a re r 1 = z er os ( s i z e ( obj1 ) ) ;

72 c l ea r er 1 2 = c l e ar e r 1 ( : ) ;

73 c l e a re r 2 = z er os ( s i z e ( obj2 ) ) ;

74 c l ea r er 2 2 = c l e ar e r 2 ( : ) ;

75 % 首先，工厂生产量的约束

76 counter = 1 ;

77 f o r i i = 1 :F

78 f o r j j = 1 :P

79 xtemp = c le a r e r1 ;

80 xtemp ( j j , i i , : ) = 1; % Sum over warehouses f o r each product and f ac to ry 为每个产品

和工厂仓库求和

81 xtemp = sp ars e ( [ xtemp ( : ) ; c l ea r er 2 2 ] ) ; % Convert to spar se

82 Aineq ( counter , : ) = xtemp ’ ; % F i l l in the row

83 bineq ( counter ) = pcap ( i i , j j ) ;

84 counter = counter + 1 ;

85 end

86 end

87 % 然后，仓库容量约束

88 vj = zero s ( S , 1) ; % The m ult i p l i er s

89 f o r j j = 1 : S

90 vj ( j j ) = sum(d ( jj , : ) . / turn ) ; % A sum of P elements

91 end

92 f o r i i = 1 :W

93 xtemp = c le a r e r2 ;

94 xtemp ( : , i i ) = v j ;

95 xtemp = sp ars e ( [ cle a re r 12 ; xtemp ( : ) ] ) ; % Convert to s par se

96 Aineq ( counter , : ) = xtemp ’ ; % F i l l in the row

97 bineq ( counter ) = wcap( i i ) ;

98 counter = counter + 1 ;

99 end

100 Aeq = s p a llo c (P*W + S , matwid ,P*W*(F+S) + S*W) ; % A ll oca te as spar se

101 beq = ze ro s (P*W + S, 1 ) ; % Allo cate ve ct or s as f u l l 分配向量为满

102 % 然后，需求满足

103 counter = 1 ;

104 f o r i i = 1 :P

105 f o r j j = 1 :W

106 xtemp = c le a r e r1 ;

107 xtemp ( i i , : , j j ) = 1 ;

108 xtemp2 = c l ea r e r 2 ;

109 xtemp2 ( : , j j ) =

−

d ( : , i i ) ;

110 xtemp = sp ars e ( [ xtemp ( : ) ; xtemp2 ( : ) ] ’ ) ; % Change to sp ars e row

111 Aeq( counter , : ) = xtemp ; % F i l l in row

112 counter = counter + 1 ;

113 end

114 end

http://www.ma-xy.com 7 http://www.ma-xy.com

http://www.ma-xy.com

1.3 混合整数规划第一章整数规划和混合整数规划

115 % 最终，每一个销售网点只有一个仓库对于

116 f o r i i = 1 : S

117 xtemp = c le a r e r2 ;

118 xtemp ( i i , : ) = 1 ;

119 xtemp = sp ars e ( [ cle a re r 12 ; xtemp ( : ) ] ’ ) ; % Change to s par se row 改变稀疏的行

120 Aeq( counter , : ) = xtemp ; % F i l l in row

121 beq ( counter ) = 1 ;

122 counter = counter + 1 ;

123 end

124 %% 设置变量界限和整数变量

125 int con = P*F*W+1: leng th ( obj ) ;%整数变量

126 lb = zero s ( lengt h ( obj ) , 1) ;

127 ub = I nf ( len gth ( obj ) , 1) ;

128 ub(P*F*W+1:end ) = 1;

129 %% 求解问题

130 opts = optimoptions ( ’ i n tli n p ro g ’ , ’ Display ’ , ’ o f f ’ , ’ PlotFcns ’ , @optimplotmilp ) ;

131 [ s olu ti on , f va l , e x i t f l ag , output ] = i nt l i n pr o g ( obj , intcon , . . .

132 Aineq , bineq , Aeq , beq , lb , ub , opts ) ;

133 i f isempty ( s ol u ti o n ) % 如果问题是不可行的，或者你提前停止没有解决方案

134 disp ( ’ i n t li n p r og did not ret urn a s ol u ti o n . ’ )

135 retu rn

136 end

137 %% 检查解决方案

138 e x i t f l a g

139 i n f ea s 1 = max( Aineq* s ol u ti o n − bineq )

140 i n f ea s 2 = norm(Aeq* s ol u ti o n − beq , Inf )

141 d i f f i n t = norm( so l ut i on ( i ntcon ) − round ( s o lu t io n ( in tcon ) ) , I nf )

142 s o lu t io n ( intc on ) = round ( so l uti on ( intcon ) ) ;

143 i n f ea s 1 = max( Aineq* s ol u ti o n − bineq )

144 i n f ea s 2 = norm(Aeq* s ol u ti o n − beq , Inf )

145 d if fr ou nd in g = norm( f v a l − obj ( : ) ’* so lutio n , I n f )

146 s ol uti on 1 = s ol u ti o n ( 1 :P*F*W) ; % The continuous v ar i abl e s

147 s ol uti on 2 = s ol u ti o n ( intc on ) ; % The int e ge r v a ria b le s

148 s ol uti on 1 = reshape ( solut ion 1 ,P, F,W) ;

149 s ol uti on 2 = reshape ( solut ion 2 , S ,W) ;

150 o u t l et s = sum( so lu tio n2 , 1 ) % Sum over the s a l e s ou t l e ts

151 f i g ure ( h) ;

152 hold on

153 f o r i i = 1 : S

154 j j = f ind ( s ol u ti on 2 ( i i , : ) ) ; % Index of warehouse a ss oci at ed with i i

155 x s al e s = xl oc (F+W+i i ) ; y s al e s = yl oc (F+W+i i ) ;

156 xwarehouse = x loc (F+j j ) ; ywarehouse = y loc (F+j j ) ;

157 i f rand ( 1) < .5 % Draw y d i r ec t i o n f i r s t h al f the time

158 pl ot ( [ x sa les , x sa le s , xwarehouse ] , [ ys al es , ywarehouse , ywarehouse ] , ’ g−−’ )

159 e l s e % Draw x d i r ec t i on f i r s t the r e s t o f the time

160 pl ot ( [ x sa les , xwarehouse , xwarehouse ] , [ ys al es , y sa le s , ywarehouse ] , ’ g−−’ )

161 end

162 end

163 hold o f f

164 t i t l e ( ’ Mapping of s a l e s ou t l ets to warehouses ’ )

165

http://www.ma-xy.com 8 http://www.ma-xy.com