数学建模笔记—— 整数规划和0-1规划

整数规划和0-1规划

1. 模型原理

1.1 基本概念

在规划问题中，有些最优解可能是分数或小数，但对于某些具体问题,常要求某些变量(全部或部分)的解必须是整数。例如,当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。

整数规划：

1. 线性整数规划

   matlab可进行求解，在线性规划的基础上，加入决策变量取整数的条件

2. 非线性整数规划

   无特定算法，只能用近似算法，如蒙特卡罗模拟，智能算法

3. 0-1规划

   特殊的整数规划，matlab中也只能求解线性0-1规划，对于非线性0-1规划也只能求近似解

1.2 线性整数规划求解

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

其中：

• $f$——目标函数的系数变量（必须是求最小值形式下的）
• $intcon$——$intcon$中的值指示决策变量x中应取整数值的分量
• $A,b$——不等式约束条件的变量系数矩阵和常数项矩阵（必须是$\le$形式）
• $Aeq,beq$——等式约束条件的变量系数矩阵和常数项矩阵
• $lb,ub$——决策变量的最小取值和最大取值

$intcon$的用法：决策变量如果有三个：$x_1,x_2,x_3$；若$x_1$和$x_2$是整数，则$intcon=[1,3]$

1.3 线性0-1规划的求解

仍然使用$intlinprog$函数求解，只需要限定$lb$和$ub$即可

例如：三个决策变量：$x_1,x_2,x_3$，$x_1$和$x_3$是0-1变量，$x_2$不限制，则$intcon=[1,3]，lb=[0;-inf;0],ub=1;+inf;1$

2. 典型例题

2.1 背包问题

有10件资物要从中地运送到乙地。每件货物的重量(单位：吨)和利润(单位：元)如下表所示

物品	1	2	3	4	5	6	7	8	9	10
重量(t)	6	3	4	5	1	2	3	5	4	2
利润 (元)	540	200	180	350	60	150	280	450	320	120

由于只有一辆最大载重为30t的货车能用来运送货物，所以只能选择部分货物进行运送，要求觉得运送哪些货物，使得这些货物的总利润最大

记
$$x_i=\{\begin{array}{ll}1,\text{运送了第}i\text{件货物}& \\ 0\text{ 没有运送第}i\text{件货物}& \end{array},i=1,2,\dots ,10$$
记
$$\text{记}{w}_i\text{表示第}i\text{件物品的重量, }{p}_i\text{表示第}i\text{件物品的利润}$$
则有
m a x   ∑ i = 1 10 p i x i s . t . { ∑ i = 1 10 w i x i ≤ 30 x i ∈ { 0 , 1 } max\:\sum_{i=1}^{10}p_ix_i\\s.t.\begin{cases}\sum_{i=1}^{10}w_ix_i\leq30\\x_i\in\{0,1\}\end{cases} maxi=1∑10​pi​xi​s.t.{∑i=110​wi​xi​≤30xi​∈{0,1}​
转化后得
m i n   − ∑ i = 1 10 p i x i s . t . { ∑ i = 1 10 w i x i ≤ 30 x i ∈ { 0 , 1 } min\:-\sum_{i=1}^{10}p_{i}x_{i}\\s.t.\begin{cases}\sum_{i=1}^{10}w_ix_i\leq30\\x_i\in\{0,1\}\end{cases} min−i=1∑10​pi​xi​s.t.{∑i=110​wi​xi​≤30xi​∈{0,1}​

2.2 指派问题

已知5名游泳候选人的百米成绩怎么选拔队员组成$4\times 100$米混合泳接力队伍

候 选 人 ： $i=1,2,3,4,5$
泳姿：$j=1,2,3,4$

$x_{ij}=\{\begin{array}{l}1,\text{队员}i\text{参加第}j\text{种泳姿}\\ 0,\text{队员}i\text{不参加第}j\text{种泳姿}\end{array}$

$t_{ij}$：队员$i$参加第$j$种泳姿的耗时

建模如下：
m i n ∑ j = 1 4 ∑ i = 1 5 t i j x i j s . t . { ∑ j = 1 4 x i j ≤ 1 , i = 1 , 2 , 3 , 4 , 5 (每个人只能入选4种泳姿之一) ∑ i = 1 5 x i j = 1 , j = 1 , 2 , 3 , 4 (每种泳姿有且仅有1人参加) x i j ∈ { 0 , 1 } \begin{aligned}&min\quad\sum_{j=1}^4\sum_{i=1}^5t_{ij}x_{ij}\\&s.t.\begin{cases}\sum_{j=1}^4x_{ij}\leq1,i=1,2,3,4,5&\text{(每个人只能入选4种泳姿之一)}\\\sum_{i=1}^5x_{ij}=1,j=1,2,3,4&\text{(每种泳姿有且仅有1人参加)}\\x_{ij}\in\{0,1\}\end{cases}\end{aligned} ​minj=1∑4​i=1∑5​tij​xij​s.t.⎩ ⎨ ⎧​∑j=14​xij​≤1,i=1,2,3,4,5∑i=15​xij​=1,j=1,2,3,4xij​∈{0,1}​(每个人只能入选4种泳姿之一)(每种泳姿有且仅有1人参加)​​

3. matlab代码实现

3.1 背包问题

%% 背包问题（货车运送货物的问题）
clc
clear
c=-[540 200 180 350 60 150 280 450 320 120]; % 目标函数的系数矩阵
intcon=1:10; %整数变量的位置
A=[6 3 4 5 1 2 3 5 4 2]; %线性不等式约束系数矩阵
Aeq=[]; % 线性不等式约束
beq=[]; % 线性不等式约束
b=30; %线性不等式约束的常系数向量
lb=zeros(10,1); %约束变量的范围下限
ub=ones(10,1); %约束变量的范围上限
% 调用intlinprog()函数进行求解
[x,fval]=intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)
fval=-fval

输出：

Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
1 rows, 10 cols, 10 nonzeros
1 rows, 7 cols, 7 nonzeros
Objective function is integral with scale 0.1

Solving MIP model with:
   1 rows
   7 cols (6 binary, 1 integer, 0 implied int., 0 continuous)
   7 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -2650           inf                  inf        0      0      0         0     0.0s
 T       0       0         0   0.00%   -2650           -2410              9.96%        0      0      0         1     0.0s

Solving report
  Status            Optimal
  Primal bound      -2410
  Dual bound        -2410
  Gap               0% (tolerance: 0.01%)
  Solution status   feasible
                    -2410 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.01 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             1
  LP iterations     1 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

找到最优解。

Intlinprog 在根节点处停止，因为目标值在最优值的间隙容差范围内，options.AbsoluteGapTolerance = 1e-06。intcon 变量是
容差范围内的整数，options.ConstraintTolerance = 1e-06。


x =

     1
     1
     0
     1
     0
     1
     1
     1
     1
     1


fval =

       -2410


fval =

        2410

3.2 指派问题

%% 指派问题（选择队员去进行游泳接力比赛）
clear;clc
% 双下标要转化为单下标：x11(x1),x12(x2),...,x24(x8),...,x54(x20)
% 目标函数的系数矩阵（先列后行的写法）
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;
% 线性不等式约束的系数矩阵和常数项向量
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 ];
b=[1;1;1;1;1];
% 线性等式约束的系数矩阵和常数项向量
Aeq=[eye(4),eye(4),eye(4),eye(4),eye(4)];
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)'

输出：

%% 指派问题（选择队员去进行游泳接力比赛）
clear;clc
% 双下标要转化为单下标：x11(x1),x12(x2),...,x24(x8),...,x54(x20)
% 目标函数的系数矩阵（先列后行的写法）
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;
% 线性不等式约束的系数矩阵和常数项向量
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 ];
b=[1;1;1;1;1];
% 线性等式约束的系数矩阵和常数项向量
Aeq=[eye(4),eye(4),eye(4),eye(4),eye(4)];
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)'