【数学建模方法笔记】整数规划 |
您所在的位置：网站首页 › 整数规划指派问题 › 【数学建模方法笔记】整数规划 |
【数学建模方法笔记】整数规划
|
整数规划模型与求解
1.整数规划问题分类2.整数规划模型3.算法与matlab求解(1)分枝定界法a.算法思路：b.matlab求解
（2）割平面法a.算法思路b.matlab求解应用举例
(3)0-1规划问题与匈牙利算法a.常见0-1规划问题b.指派问题的标准形式c.非标准形式的指派问题d.匈牙利算法c.matlab求解
4.旅行商问题5.固定费用问题6.蒙特卡洛法求解非线性整数规划
1.整数规划问题分类
（1）纯整数规划：决策变量要求取整，但松弛变量、剩余变量不需取整。 （2）全整数规划：决策变量、松弛变量、剩余变量都要取整。 （3）混合整数变量：部分决策变量取整。 （4）0-1整数规划：指派问题，决策变量只取0或1. 若线性规划无可行解，则相应的整数变量也无可行解。 2.整数规划模型我们在这里只讨论线性整数规划，其标准模型为标准模型： 不考虑整数限制，先求相应松弛问题的最优解； 若松弛问题无可行解，则整数规划问题无可行解； 若松弛问题最优解符合整数要求，则该解也是整数规划的最优解； 若不满足整数条件 则任选一个不满足整数条件的变量 x i 0 x_i^0 xi0来构造一个新的约束，添加到松弛问题中形成两个子问题 x i ≤ [ x i 0 ] ; x i ≥ [ x i 0 ] + 1 x_i\le[x_i^0] \ ;\quad x_i\ge[x_i^0]+1 xi≤[xi0] ;xi≥[xi0]+1 依次缩小可行域，求解新构造的线性规划最优解，并重复上述过程，直到问题误解或有整数最优解（被查清） 若最后还未成功，则考虑其他方法，分枝定界法失效。 分支定界法可用于解纯整数和混合整数问题 b.matlab求解主函数： %例子 f = [-20 -10]; A = [5 4;2 5]; B = [24 13]; lb = [0 0]; [x,fval,status] = intprog(f,A,B,[1 2],[],[],lb)二叉树函数branchbound function [newx,newfval,status,newbound] = branchbound(f,A,B,I,x,fval,bound,Aeq,Beq,lb,ub,e) % 分支定界法求解整数规划 % f,A,B,Aeq,Beq,lb,ub与线性规划相同 % I为整数限制变量的向量 % x为初始解，fval为初始值 options = optimset('display','off'); [x0,fval0,status0]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options); %递归中的最终退出条件 %无解或者解比现有上界大则返回原解 if status0 = bound newx = x; newfval = fval; newbound = bound; status = status0; return; end %是否为整数解,如果是整数解则返回 intindex = find(abs(x0(I) - round(x0(I))) > e); if isempty(intindex) %判断是否为空值 newx(I) = round(x0(I)); newfval = fval0; newbound = fval0; status = 1; return; end %当有非整可行解时，则进行分支求解 %此时必定会有整数解或空解 %找到第一个不满足整数要求的变量 n = I(intindex(1)); addA = zeros(1,length(f)); addA(n) = 1; %构造第一个分支 x 0 && bound1 0 && bound2 |
【本文地址】
今日新闻 |
推荐新闻 |