数学建模算法与应用|整数规划，背包问题、指派问题、钢管切割问题的Matlab和python实现 matlab|python

概述整数规划的定义

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

整数规划的分类

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

变量全部限制为整数时，称纯（完全）整数规划
变量部分限制为整数时，称混合整数规划

整数规划特点

原线性规划有最优解，当自变量限制为整数后，可能无可行解，可能最优解值变差
整数规划的最优解不能按照实数最优解直接取整得到

求解方法分类

分支定界法——纯或混合整数规划
割平面法——纯或混合整数规划
隐枚举法——0-1整数规划

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

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

0-1型整数规划

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

相互排斥的约束条件

两种运输方法只能选择一种，用车运输的约束条件 5 x 1 + 4 x 2 ≤ 24 5x_1+4x_2\le24 5x1?+4x2?≤24，用船运输的约束条件 7 x 1 + 3 x 2 ≤ 45 7x_1+3x_2\le45 7x1?+3x2?≤45，为了统一在一个问题中，引入0-1变量
y = { 1 船运 0 车运 y= \begin{cases} 1&船运\\ 0&车运 \end{cases} y={10?船运车运?
则约束条件可改为
{ 5 x 1 + 4 x 2 ≤ 24 + y M 7 x 1 + 3 x 2 ≤ 45 + ( 1 ? y ) M y = 0 或 1 M 为充分大的数 \begin{cases} 5x_1+4x_2\le24+yM\\ 7x_1+3x_2\le45+(1-y)M\\ y=0或1 \end{cases} \quad M为充分大的数 ??????5x1?+4x2?≤24+yM7x1?+3x2?≤45+(1?y)My=0或1?M为充分大的数
【数学建模算法与应用|整数规划，背包问题、指派问题、钢管切割问题的Matlab和python实现】 x 1 = 0 或 500 ≤ x 1 ≤ 800 x_1=0或500\le x_1 \le800 x1?=0或500≤x1?≤800，可改写为
{ 500 y ≤ x 1 ≤ 800 y y = 0 或 1 \begin{cases} 500y\le x_1\le 800y\\ y=0或1 \end{cases} {500y≤x1?≤800yy=0或1?
如果有m个约束条件
a i 1 x 1 + . . . + a i n x n ≤ b i , i = 1 , . . . , m a_{i1}x_1+...+a_{in}x_n\le b_i,i=1,...,m ai1?x1?+...+ain?xn?≤bi?,i=1,...,m
引入m个0-1变量
y i = { 1 第 i 个约束起作用 0 第 i 个约束不起作用 y_i= \begin{cases} 1&第i个约束起作用\\ 0&第i个约束不起作用 \end{cases} yi?={10?第i个约束起作用第i个约束不起作用?
则约束条件可改为
{ a i 1 x 1 + . . . + a i n x n ≤ b i + ( 1 ? y i ) M , i = 1 , . . . , m y 1 + . . . + y n = 1 M 为充分大的数 \begin{cases} a_{i1}x_1+...+a_{in}x_n\le b_i+(1-y_i)M,i=1,...,m\\ y_1+...+y_n=1 \end{cases}\quad M为充分大的数 {ai1?x1?+...+ain?xn?≤bi?+(1?yi?)M,i=1,...,my1?+...+yn?=1?M为充分大的数

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的火车能用来运送货物，所以只能选择部分货物进行运送
要求确定运送哪些货物，使得运送货物的总利润最大

分析

记
x i = { 1 运送了第 i 件货物 0 没有运送第 i 件货物 i = 1 , . . . , 10 x_i=\begin{cases} 1&运送了第i件货物\\ 0&没有运送第i件货物 \end{cases}\quad i=1,...,10 xi?={10?运送了第i件货物没有运送第i件货物?i=1,...,10
w i w_i wi?为第 i i i件货物的重量， p i p_i pi?为第 i i i件货物的利润
则
max ? ∑ i = 1 10 p i x i s . t . { ∑ i = 1 10 w i x i ≤ 10 x i = 0 或 1 \max\sum_{i=1}^{10}p_ix_i\\ s.t.\begin{cases} \sum_{i=1}^{10}w_ix_i\le10\\ x_i=0或1 \end{cases} maxi=1∑10?pi?xi?s.t.{∑i=110?wi?xi?≤10xi?=0或1?

Matlab求解

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

python求解

from pulp import * #设置对象 my_package=LpProblem(name='package probelm',sense=LpMaximize) #设置变量 var_num = 10 variables = [LpVariable(name='x%d' % i, lowBound=0,upBound=1,cat=const.LpInteger) for i in range(1, var_num+1)] #设置目标函数 p=[540,200,180,350,60,150,280,450,320,120] objective=sum([p[i]*variables[i] for i in range(0, var_num)]) #设置约束条件 constraints = [] w=[6,3,4,5,1,2,3,5,4,20] constraints.append(sum([w[i]*variables[i] for i in range(0, var_num)]) <= 30) #载入变量 my_package += objective for cons in constraints: my_package += cons #求解 status = my_package.solve()#0: 'Not Solved', 1: 'Optimal', -1: 'Infeasible', -2: 'Unbounded', -3: 'Undefined' #输出结果 if LpStatus[status]=='Optimal':#LpStatus是一字典 for v in my_package.variables(): print('%s %d'% (v.name,v.varValue)) 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人参加，总耗时要最小
记
x i j = { 1 队员 i 参加第 j 种泳姿 0 队员 i 不参加第 j 种泳姿 i = 1 , . . . , 5 ； j = 1 , . . . , 4 x_{ij}=\begin{cases} 1&队员i参加第j种泳姿\\ 0&队员i不参加第j种泳姿 \end{cases}\quad i=1,...,5；j=1,...,4 xij?={10?队员i参加第j种泳姿队员i不参加第j种泳姿?i=1,...,5；j=1,...,4
t i j t_{ij} tij?队员 i i i参加第 j j j种泳姿的耗时
则

min ? ∑ j = 1 4 ∑ i = 1 5 t i j x i s . t . { ∑ j = 1 4 x i j i = 1 , . . . , 5 ≤ 1 ∑ 1 = 1 5 x i j = 1 j = 1 , . . . , 4 x i j = 0 或 1 \min\sum_{j=1}^4\sum_{i=1}^{5}t_{ij}x_i\\ s.t.\begin{cases} \sum_{j=1}^{4}x_{ij}&i=1,...,5\le1\\ \sum_{1=1}^{5}x_{ij}=1&j=1,...,4\\ x_{ij}=0或1 \end{cases} minj=1∑4?i=1∑5?tij?xi?s.t.??????∑j=14?xij?∑1=15?xij?=1xij?=0或1?i=1,...,5≤1j=1,...,4?
Matlab求解

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]'; % 目标函数的系数矩阵（先列后行的写法） intcon = [1:20]; % 整数变量的位置(一共20个决策变量，均为0-1整数变量) % 线性不等式约束的系数矩阵和常数项向量（每个人只能入选四种泳姿之一，一共五个约束） A = [1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]; % A = zeros(5,20); % for i = 1:5 %A(i, (4*i-3): 4*i) = 1; % end b = [1; 1; 1; 1; 1]; % 线性等式约束的系数矩阵和常数项向量（每种泳姿有且仅有一人参加，一共四个约束） Aeq = [1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0; 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0; 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0; 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1]; % Aeq = [eye(4),eye(4),eye(4),eye(4),eye(4)]; % 或者写成 repmat(eye(4),1,5) beq = [1; 1; 1; 1]; lb = zeros(20,1); % 约束变量的范围下限 ub = ones(20,1); % 约束变量的范围上限 %最后调用intlinprog()函数 [x,fval] = intlinprog(c,intcon,A,b,Aeq,beq,lb,ub) % reshape(x,4,5)' %0001甲自由泳 %1000乙蝶泳 %0100丙仰泳 %0010丁蛙泳 %0000戊不参加

python求解指派问题

import numpy as np from scipy import optimize #函数优化器（最小化器） #指派矩阵 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]] c = np.array(c) 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]) re=np.zeros((5,4),dtype=int) re[row_id,col_id]=1 print(re) 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
钢管切割问题题目及分析

数学建模算法与应用|整数规划，背包问题、指派问题、钢管切割问题的Matlab和python实现

文章图片

Matlab求解

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

python求解

#设置对象 from pulp import * my_tube=LpProblem(name='tube probelm',sense=LpMinimize) #设置变量 var_num = 7 variables = [LpVariable(name='x%d' % i, lowBound=0,upBound=None,cat=const.LpInteger) for i in range(1, var_num+1)] #设置目标函数 c=[1]*7 objective=sum([c[i]*variables[i] for i in range(0, var_num)]) #设置约束条件 constraints = [] A=np.array([[1,2,0,0,0,0,1],[0,0,3,2,1,0,1],[4,1,0,2,4,6,1]]) b=np.array([100,100,100]) for i in range(3): constraints.append(sum([A[i][j]*variables[j] for j in range(0, var_num)]) >= b[i]) #载入变量 my_tube += objective for cons in constraints: my_tube += cons #求解 status = my_tube.solve()#0: 'Not Solved', 1: 'Optimal', -1: 'Infeasible', -2: 'Unbounded', -3: 'Undefined' #输出结果 if LpStatus[status]=='Optimal':#LpStatus是一字典 for v in my_tube.variables(): print('%s = %d'% (v.name,v.varValue)) print('目标函数值为：%g'% my_tube.objective.value())

my_tube tube_probelm: MINIMIZE 1*x1 + 1*x2 + 1*x3 + 1*x4 + 1*x5 + 1*x6 + 1*x7 + 0 SUBJECT TO _C1: x1 + 2 x2 + x7 >= 100_C2: 3 x3 + 2 x4 + x5 + x7 >= 100_C3: 4 x1 + x2 + 2 x4 + 4 x5 + 6 x6 + 7 x7 >= 100VARIABLES 0 <= x1 Integer 0 <= x2 Integer 0 <= x3 Integer 0 <= x4 Integer 0 <= x5 Integer 0 <= x6 Integer 0 <= x7 Integer

结果