个人类网站类网站,建设网站的功能定位是什么意思,拼多多网站建设合同,wordpress媒体库搬家数学建模笔记—— 整数规划和0-1规划 整数规划和0-1规划1. 模型原理1.1 基本概念1.2 线性整数规划求解1.3 线性0-1规划的求解 2. 典型例题2.1 背包问题2.2 指派问题 3. matlab代码实现3.1 背包问题3.2 指派问题 整数规划和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],ub1;inf;1 intcon[1,3]lb[0;−inf;0],ub1;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},i1,2,\ldots,10 xi{1,运送了第i件货物0 没有运送第i件货物,i1,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_{i1}^{10}p_ix_i\\s.t.\begin{cases}\sum_{i1}^{10}w_ix_i\leq30\\x_i\in\{0,1\}\end{cases} maxi1∑10pixis.t.{∑i110wixi≤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_{i1}^{10}p_{i}x_{i}\\s.t.\begin{cases}\sum_{i1}^{10}w_ix_i\leq30\\x_i\in\{0,1\}\end{cases} min−i1∑10pixis.t.{∑i110wixi≤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 i1,2,3,4,5 泳姿 j 1 , 2 , 3 , 4 j1,2,3,4 j1,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_{j1}^4\sum_{i1}^5t_{ij}x_{ij}\\s.t.\begin{cases}\sum_{j1}^4x_{ij}\leq1,i1,2,3,4,5\text{(每个人只能入选4种泳姿之一)}\\\sum_{i1}^5x_{ij}1,j1,2,3,4\text{(每种泳姿有且仅有1人参加)}\\x_{ij}\in\{0,1\}\end{cases}\end{aligned} minj1∑4i1∑5tijxijs.t.⎩ ⎨ ⎧∑j14xij≤1,i1,2,3,4,5∑i15xij1,j1,2,3,4xij∈{0,1}(每个人只能入选4种泳姿之一)(每种泳姿有且仅有1人参加)
3. matlab代码实现
3.1 背包问题
%% 背包问题货车运送货物的问题
clc
clear
c-[540 200 180 350 60 150 280 450 320 120]; % 目标函数的系数矩阵
intcon1:10; %整数变量的位置
A[6 3 4 5 1 2 3 5 4 2]; %线性不等式约束系数矩阵
Aeq[]; % 线性不等式约束
beq[]; % 线性不等式约束
b30; %线性不等式约束的常系数向量
lbzeros(10,1); %约束变量的范围下限
ubones(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.1Solving MIP model with:1 rows7 cols (6 binary, 1 integer, 0 implied int., 0 continuous)7 nonzerosNodes | BB Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time0 0 0 0.00% -2650 inf inf 0 0 0 0 0.0sT 0 0 0 0.00% -2650 -2410 9.96% 0 0 0 1 0.0sSolving reportStatus OptimalPrimal bound -2410Dual bound -2410Gap 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 1LP iterations 1 (total)0 (strong br.)0 (separation)0 (heuristics)找到最优解。Intlinprog 在根节点处停止因为目标值在最优值的间隙容差范围内options.AbsoluteGapTolerance 1e-06。intcon 变量是
容差范围内的整数options.ConstraintTolerance 1e-06。x 1101011111fval -2410fval 24103.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];
% 整数变量的位置
intcon1: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];
% 约束变量的范围下限
lbzeros(20,1);
% 约束变量的范围上限
ubones(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];
% 整数变量的位置
intcon1: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];
% 约束变量的范围下限
lbzeros(20,1);
% 约束变量的范围上限
ubones(20,1);
% 约束变量的范围上限
% 调用intlinprog()函数进行求解
[x,fval]intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)
reshape(x,4,5)
