- 数学规划中的变量部分或者全部限制为整数时，称为整数规划。
整数规划又分为整数线性规划和整数非线性规划，现流行的求解整数规划的问题往往只适用于求解整数线性规划，故我们提到整数规划都是指整数线性规划。
- 如不加说明整数规划就是指整数线性规划
- 变量全部限制为整数时，称纯（完全）整数规划
- 变量部分限制为整数时，称混合整数规划
- 原线性规划有最优解，当自变量限制为整数后，可能无可行解，可能最优解值变差
- 整数规划的最优解不能按照实数最优解直接取整得到
- 分支定界法——纯或混合整数规划
- 割平面法——纯或混合整数规划
- 隐枚举法——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或1M为充分大的数
- 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
ai1x1+...+ainxn≤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为充分大的数
{ai1x1+...+ainxn≤bi+(1−yi)M,i=1,...,my1+...+yn=1M为充分大的数
- 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} max∑i=110pixis.t.{∑i=110wixi≤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
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} min∑j=14∑i=15tijxis.t.⎩⎪⎨⎪⎧∑j=14xij∑1=15xij=1xij=0或1i=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)'
% 0 0 0 1 甲自由泳
% 1 0 0 0 乙蝶泳
% 0 1 0 0 丙仰泳
% 0 0 1 0 丁蛙泳
% 0 0 0 0 戊不参加
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
%% (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)
#设置对象
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 >= 100
VARIABLES
0 <= x1 Integer
0 <= x2 Integer
0 <= x3 Integer
0 <= x4 Integer
0 <= x5 Integer
0 <= x6 Integer
0 <= x7 Integer
- Matlab求解结果为：
x =
14.0000
43.0000
32.0000
2.0000
0
0
0
fval =
91
- python求解结果为：
x1 = 8 x2 = 46 x3 = 26 x4 = 11 x5 = 0 x6 = 0 x7 = 0
目标函数值为：91
- 说明不止一个最优解
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）