概述

整数规划的定义

  • 数学规划中的变量部分或者全部限制为整数时，称为整数规划。整数规划又分为整数线性规划和整数非线性规划，现流行的求解整数规划的问题往往只适用于求解整数线性规划，故我们提到整数规划都是指整数线性规划。

    整数规划的分类

  • 如不加说明整数规划就是指整数线性规划

  1. 变量全部限制为整数时，称纯（完全）整数规划

  2. 变量部分限制为整数时，称混合整数规划

    整数规划特点

  3. 原线性规划有最优解，当自变量限制为整数后，可能无可行解，可能最优解值变差

  4. 整数规划的最优解不能按照实数最优解直接取整得到

    求解方法分类

  5. 分支定界法——纯或混合整数规划

  6. 割平面法——纯或混合整数规划
  7. 隐枚举法——0-1整数规划

①过滤隐枚举法
②分支隐枚举法

  1. 匈牙利法——指派问题（0-1规划特殊情形）
  2. 蒙特卡洛法——各种类型规划

    0-1型整数规划

  • 在实际问题中，引入0-1型变量，就可以把有各种情况需要分别讨论的数学规划问题统一在一个问题中讨论

    相互排斥的约束条件

  1. 两种运输方法只能选择一种，用车运输的约束条件整数规划 - 图1，用船运输的约束条件整数规划 - 图2，为了统一在一个问题中，引入0-1变量

整数规划 - 图3
则约束条件可改为
整数规划 - 图4

  1. 整数规划 - 图5

可改写为
整数规划 - 图6

  1. 如果有m个约束条件

整数规划 - 图7
引入m个0-1变量
整数规划 - 图8
则约束条件可改为
整数规划 - 图9

Matlab、python线性整数规划求解

  • Matlab求解混合整数线性规划的命令为

[x,fval]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

背包问题

例题

  • 有10件货物从甲地运送到乙地，每件货物的重量（单位：吨）和利润（单位：元）如下表所示： | 物品 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | 重量 | 6 | 3 | 4 | 5 | 1 | 2 | 3 | 5 | 4 | 2 | | 利润 | 540 | 200 | 180 | 350 | 60 | 150 | 280 | 450 | 320 | 120 |

  • 由于只有一辆载重为30t的火车能用来运送货物，所以只能选择部分货物进行运送

  • 要求确定运送哪些货物，使得运送货物的总利润最大

    分析

  • 记

整数规划 - 图10
整数规划 - 图11为第整数规划 - 图12件货物的重量，整数规划 - 图13为第整数规划 - 图14件货物的利润

  • 则

整数规划 - 图15

Matlab求解

  1. c = -[540 200 180 350 60 150 280 450 320 120];  % 目标函数的系数矩阵(最大化问题记得加负号)
  2. intcon=[1:10];  % 整数变量的位置(一共10个决策变量，均为0-1整数变量)
  3. A = [6 3 4 5 1 2 3 5 4 2];  b = 30;   % 线性不等式约束的系数矩阵和常数项向量（物品的重量不能超过30）
  4. Aeq = []; beq =[];  % 不存在线性等式约束
  5. lb = zeros(10,1);  % 约束变量的范围下限
  6. ub = ones(10,1);  % 约束变量的范围上限
  7. %最后调用intlinprog()函数
  8. [x,fval]=intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)；
  9. fval = -fval

python求解

  1. from pulp import *
  2. #设置对象
  3. my_package=LpProblem(name='package probelm',sense=LpMaximize)
  4. #设置变量
  5. var_num = 10
  6. variables = [LpVariable(name='x%d' % i, lowBound=0,upBound=1,cat=const.LpInteger) for i in range(1, var_num+1)]
  7. #设置目标函数
  8. p=[540,200,180,350,60,150,280,450,320,120]
  9. objective=sum([p[i]*variables[i] for i in range(0, var_num)])
  10. #设置约束条件
  11. constraints = []
  12. w=[6,3,4,5,1,2,3,5,4,20]
  13. constraints.append(sum([w[i]*variables[i] for i in range(0, var_num)]) <= 30)
  14. #载入变量
  15. my_package += objective
  16. for cons in constraints:
  17.     my_package += cons
  18. #求解
  19. status = my_package.solve()#0: 'Not Solved', 1: 'Optimal', -1: 'Infeasible', -2: 'Unbounded', -3: 'Undefined'
  20. #输出结果
  21. if LpStatus[status]=='Optimal':#LpStatus是一字典
  22.     for v in my_package.variables():
  23.         print('%s %d'% (v.name,v.varValue))
  24.     print('目标函数值为：%g'% my_package.objective.value())

结果

x1 1 x10 1 x2 1 x3 0 x4 1 x5 0 x6 1 x7 1 x8 1 x9 1
目标函数值为：2410

指派问题

题目

  • 5名候选人的百米成绩（S）如下，怎么选拔队员组成4×100米混合泳接力队伍？ | | 蝶泳 | 仰泳 | 蛙泳 | 自由泳 | | —- | —- | —- | —- | —- | | 甲 | 66.8 | 75.6 | 87 | 58.6 | | 乙 | 57.2 | 66 | 66.4 | 53 | | 丙 | 78 | 67.8 | 84.6 | 59.4 | | 丁 | 70 | 74.2 | 69.6 | 57.2 | | 戊 | 67.4 | 71 | 83.8 | 62.4 |

分析

  • 每个人只能入选4种泳姿之一，每种泳姿有且仅有1人参加，总耗时要最小
  • 记

整数规划 - 图16
整数规划 - 图17队员整数规划 - 图18参加第整数规划 - 图19种泳姿的耗时

  • 则

整数规划 - 图20

Matlab求解

  1. c = [66.8 75.6 87 58.6 57.2 66 66.4 53 78 67.8 84.6 59.4 70 74.2 69.6 57.2 67.4 71 83.8 62.4]';  % 目标函数的系数矩阵（先列后行的写法）
  2. intcon = [1:20];  % 整数变量的位置(一共20个决策变量，均为0-1整数变量)
  3. % 线性不等式约束的系数矩阵和常数项向量（每个人只能入选四种泳姿之一，一共五个约束）
  4. A = [1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
  5.        0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
  6.        0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
  7.        0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;
  8.        0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];
  9. % A = zeros(5,20);
  10. % for i = 1:5
  11. %     A(i, (4*i-3): 4*i) = 1;
  12. % end
  13. b = [1;1;1;1;1];
  14. % 线性等式约束的系数矩阵和常数项向量 （每种泳姿有且仅有一人参加，一共四个约束）
  15. Aeq = [1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
  16.           0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
  17.           0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
  18.           0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1];
  19. % Aeq = [eye(4),eye(4),eye(4),eye(4),eye(4)];  % 或者写成 repmat(eye(4),1,5)  
  20. beq = [1;1;1;1];
  21. lb = zeros(20,1);  % 约束变量的范围下限
  22. ub = ones(20,1);  % 约束变量的范围上限
  23. %最后调用intlinprog()函数
  24. [x,fval] = intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)
  25. % reshape(x,4,5)'
  26. %      0     0     0     1    甲自由泳
  27. %      1     0     0     0    乙蝶泳
  28. %      0     1     0     0    丙仰泳
  29. %      0     0     1     0    丁蛙泳
  30. %      0     0     0     0    戊不参加

python求解指派问题

  1. import numpy as np
  2. from scipy import optimize #函数优化器（最小化器）
  3. #指派矩阵
  4. c = [[66.8, 75.6, 87, 58.6],[ 57.2, 66, 66.4, 53],[ 78, 67.8, 84.6, 59.4],[ 70, 74.2, 69.6, 57.2],[67.4, 71, 83.8, 62.4]]
  5. c = np.array(c)
  6. row_id,col_id=optimize.linear_sum_assignment(c)#row_id：array([0, 1, 2, 3], dtype=int64) col_id：array([3, 0, 1, 2])
  7. re=np.zeros((5,4),dtype=int)
  8. re[row_id,col_id]=1
  9. print(re)
  10. print(c[row_id,col_id ].sum())

结果

[[0 0 0 1] [1 0 0 0] [0 1 0 0] [0 0 1 0] [0 0 0 0]]
253.20000000000002

钢管切割问题

题目及分析

DB8D58C9BDF41D263BA83D477135543D.png

Matlab求解

  1. %% (1)枚举法找出同一个原材料上所有的切割方法
  2. for i = 0: 2  % 2.9m长的圆钢的数量
  3.     for j = 0: 3  % 2.1m长的圆钢的数量
  4.         for k = 0:6   % 1m长的圆钢的数量
  5.             if 2.9*i+2.1*j+1*k >= 6 && 2.9*i+2.1*j+1*k <= 6.9
  6.                 disp([i, j, k])
  7.             end
  8.         end
  9.     end
  10. end
  11. %% (2) 线性整数规划问题的求解
  12. c = ones(7,1);  % 目标函数的系数矩阵
  13. intcon=[1:7];  %  整数变量的位置(一共7个决策变量，均为整数变量)
  14. A = -[1 2 0 0 0 0 1;  
  15.          0 0 3 2 1 0 1;
  16.          4 1 0 2 4 6 1];  % 线性不等式约束的系数矩阵
  17. b = -[100 100 100]'; %  线性不等式约束的常数项向量
  18. lb = zeros(7,1); % 约束变量的范围下限
  19. [x,fval]=intlinprog(c,intcon,A,b,[],[],lb)

python求解

  1. #设置对象
  2. from pulp import *
  3. my_tube=LpProblem(name='tube probelm',sense=LpMinimize)
  4. #设置变量
  5. var_num = 7
  6. variables = [LpVariable(name='x%d' % i, lowBound=0,upBound=None,cat=const.LpInteger) for i in range(1, var_num+1)]
  8. #设置目标函数
  9. c=[1]*7
  10. objective=sum([c[i]*variables[i] for i in range(0, var_num)])
  11. #设置约束条件
  12. constraints = []
  13. A=np.array([[1,2,0,0,0,0,1],[0,0,3,2,1,0,1],[4,1,0,2,4,6,1]])
  14. b=np.array([100,100,100])
  15. for i in range(3):
  16.     constraints.append(sum([A[i][j]*variables[j] for j in range(0, var_num)]) >= b[i])
  17. #载入变量
  18. my_tube += objective
  19. for cons in constraints:
  20.     my_tube += cons
  22. ###或将以上三步写成
  23. # my_tube += x1+x2+x3+x4+x5+x6+x7, 'obj'
  24. # my_tube += x1 + 2*x2 + x7 >=100, 'c1'
  25. # my_tube += 3*x3+2*x4+x5+x7 >=100, 'c2'
  26. # my_tube += 4*x1+x2+2*x4+4*x5+6*x6+x7 >=100
  28. #求解
  29. status = my_tube.solve()#0: 'Not Solved', 1: 'Optimal', -1: 'Infeasible', -2: 'Unbounded', -3: 'Undefined'
  30. #输出结果
  31. if LpStatus[status]=='Optimal':#LpStatus是一字典
  32.     for v in my_tube.variables():
  33.         print('%s = %d'% (v.name,v.varValue))
  34.     print('目标函数值为：%g'% my_tube.objective.value())
  1. my_tube
  2. tube_probelm:
  3. MINIMIZE
  4. 1*x1 + 1*x2 + 1*x3 + 1*x4 + 1*x5 + 1*x6 + 1*x7 + 0
  5. SUBJECT TO
  6. _C1: x1 + 2 x2 + x7 >= 100
  8. _C2: 3 x3 + 2 x4 + x5 + x7 >= 100
  10. _C3: 4 x1 + x2 + 2 x4 + 4 x5 + 6 x6 + 7 x7 >= 100
  12. VARIABLES
  13. 0 <= x1 Integer
  14. 0 <= x2 Integer
  15. 0 <= x3 Integer
  16. 0 <= x4 Integer
  17. 0 <= x5 Integer
  18. 0 <= x6 Integer
  19. 0 <= x7 Integer

结果

  • Matlab求解结果为：

x =

14.0000
43.0000
32.0000
2.0000
0
0
0

fval =

  1. 91
  • python求解结果为：

x1 = 8 x2 = 46 x3 = 26 x4 = 11 x5 = 0 x6 = 0 x7 = 0
目标函数值为：91

  • 说明不止一个最优解