马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
整数规划和0-1规划
1. 模子原理
1.1 根本概念
在规划题目中，有些最优解大概是分数或小数，但对于某些具体题目,常要求某些变量(全部或部分)的解必须是整数。比方,当变量代表的是呆板的台数，工作的人数或装货的车数等。为了满意整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。现实上化整后的数不见得是可行解和最优解，以是应该有特别的方法来求解整数规划。在整数规划中，假如全部变量都限定为整数，则称为纯整数规划；假如仅一部分变量限定为整数，则称为肴杂整数规划。整数规划的一种特别情况是0-1规划，它的变数仅限于0或1。
整数规划：
- 线性整数规划
matlab可举行求解，在线性规划的根本上，参加决议变量取整数的条件
- 非线性整数规划
无特定算法，只能用近似算法，如蒙特卡罗模仿，智能算法
- 0-1规划
特别的整数规划，matlab中也只能求解线性0-1规划，对于非线性0-1规划也只能求近似解
1.2 线性整数规划求解
[ x , f v a l ] = i n t l i n p r o g ( f , i n t c o n , A , b , A e q , b e q , l b , u b , x 0 ) [x,fval]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0) [x,fval]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)
此中：
- f f f——目的函数的系数变量（必须是求最小值情势下的）
- i n t c o n intcon intcon—— i n t c o n intcon intcon中的值指示决议变量x中应取整数值的分量
- A , b A,b A,b——不等式束缚条件的变量系数矩阵和常数项矩阵（必须是 ≤ \le ≤情势）
- A e q , b e q Aeq,beq Aeq,beq——等式束缚条件的变量系数矩阵和常数项矩阵
- l b , u b lb,ub lb,ub——决议变量的最小取值和最大取值
i n t c o n intcon intcon的用法：决议变量假如有三个： x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3；若 x 1 x_1 x1和 x 2 x_2 x2是整数，则 i n t c o n = [ 1 , 3 ] intcon=[1,3] intcon=[1,3]
1.3 线性0-1规划的求解
仍然利用 i n t l i n p r o g intlinprog intlinprog函数求解，只必要限定 l b lb lb和 u b ub ub即可
比方：三个决议变量： x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3， x 1 x_1 x1和 x 3 x_3 x3是0-1变量， x 2 x_2 x2不限定，则 i n t c o n = [ 1 , 3 ] ， l b = [ 0 ; − i n f ; 0 ] , u b = 1 ; + i n f ; 1 intcon=[1,3]，lb=[0;-inf;0],ub=1;+inf;1 intcon=[1,3]，lb=[0;−inf;0],ub=1;+inf;1
2. 范例例题
2.1 背包题目
有10件资物要从中地运送到乙地。每件货品的重量(单元：吨)和利润(单元：元)如下表所示
物品12345678910重量(t)6345123542利润 (元)54020018035060150280450320120 由于只有一辆最大载重为30t的货车能用来运送货品，以是只能选择部分货品举行运送，要求以为运送哪些货品，使得这些货品的总利润最大
记
x i = { 1 , 运送了第 i 件货品 0 没有运送第 i 件货品 , i = 1 , 2 , … , 10 x_i=\begin{cases}1,\text{运送了第}i\text{件货品}\\0\text{ 没有运送第}i\text{件货品}&\end{cases},i=1,2,\ldots,10 xi={1,运送了第i件货品0 没有运送第i件货品,i=1,2,…,10
记
记 w i 体现第 i 件物品的重量, p i 体现第 i 件物品的利润 \text{记}w_i\text{体现第}i\text{件物品的重量, }p_i\text{体现第}i\text{件物品的利润} 记wi体现第i件物品的重量, pi体现第i件物品的利润
则有
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∑10pixis.t.{∑i=110wixi≤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∑10pixis.t.{∑i=110wixi≤30xi∈{0,1}
2.2 指派题目
已知5名游泳候选人的百米结果怎么选拔队员构成 4 × 100 4\times100 4×100米肴杂泳接力队伍
蝶泳仰泳蛙泳自由泳 甲66.875.68758.6乙57.26666.453丙7867.884.659.4丁7074.269.657.2戊67.47183.862.4 候 选 人 ： i = 1 , 2 , 3 , 4 , 5 i= 1, 2, 3, 4, 5 i=1,2,3,4,5
泳姿： j = 1 , 2 , 3 , 4 j=1,2,3,4 j=1,2,3,4
x i j = { 1 , 队员 i 参加第 j 种泳姿 0 , 队员 i 不参加第 j 种泳姿 x_{ij}=\left\{\begin{array}{l}1,\text{队员}i\text{参加第}j\text{种泳姿}\\0,\text{队员}i\text{不参加第}j\text{种泳姿}\end{array}\right. xij={1,队员i参加第j种泳姿0,队员i不参加第j种泳姿
t i j t_{ij} tij：队员 i i i参加第 j j 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∑4i=1∑5tijxijs.t.⎩ ⎨ ⎧∑j=14xij≤1,i=1,2,3,4,5∑i=15xij=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
- %% 指派问题（选择队员去进行游泳接力比赛）
- 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)'
|
发表于 2026-1-25 23:13:11