穷举法求解0-1整数规划的matlab程序(原创)
Posted on 2006-06-29 00:58 realghost 阅读(4040) 评论(23) 收藏
0-1整数规划有很广泛的应用背景,比如指派问题,背包问题等等,实际上TSP问题也是一个0-1问题,当然这些问题都是NP问题,对于规模较大的问题用穷举法是没有办法在可接受的时间内求得最优解的,本程序只不过是一个练习,得意之处是用递归法把所有解都排列出来。另:胡运权所著的《运筹学基础及应用(第三版)》第97页的例3,我用本程序求解得到的结果是:最优解是x*=(1,0, 0, 0, 0),最优值是f(x*)=8,但书求得最优解是x*=(1,0, 1, 0, 0),最优值是f(x*)=4,是不是书中写错了,请大家验证。以下是源程序,大家可以任意使用无版权问题,另外,如果大家有大规模的0-1规划的问题也希望提供给我,谢谢。
%%% 用隐穷举法求解0-1线性规划
%%% min c'x
%%% s.t. Ax<=b
function [y,fval]=qiongju(c,A,b)
guimo=length(c);
suoyoujie=lingyi(guimo);?? % 所有可能解的排列
[m,n]=size(A);
opt_solution=inf;????????? % 解的上界
for i=1:2^guimo
??? yueshu=A*suoyoujie(i,:)';
??? for j=1:m
??????? if yueshu(j)>b(j)?? % 不满足某约束条件,则不是解
??????????? break;
??????? end
??? end
??? if j==m??????????? % 满足所有约束,则计算该的目标值,并与当前最优解相比较
??????? val=c'*suoyoujie(i,:)';
??????? if val<=opt_solution
??????????? opt_solution=val;
??????????? y=suoyoujie(i,:);
??????? end
??? end
end
fval=opt_solution;
?
function y=lingyi(k)
if k==3
??? y=[0 0 0;
?????? 0 0 1;
?????? 0 1 0;
?????? 0 1 1;
?????? 1 0 0;
?????? 1 0 1;
?????? 1 1 0;
?????? 1 1 1];
else
??? lc=2^(k-1);
??? xinlie1=zeros(lc,1);
??? xinlie2=ones(lc,1);
??? xinlie=[xinlie1;xinlie2];
??? pre_lingyi=lingyi(k-1);
??? pre_lingyi=[pre_lingyi;pre_lingyi];
??? y=[xinlie,pre_lingyi];
end
Feedback
# re: 穷举法求解0-1整数规划的matlab程序(原创)
2006-06-29 01:02 by realghost
忘了说了,变量个数至少是3个,要不然没办法运行了。^_^
# re: 穷举法求解0-1整数规划的matlab程序(原创)
2006-07-28 21:04 by 张敏
写的挺不错的
# re: 穷举法求解0-1整数规划的matlab程序(原创)
2006-09-13 17:14 by 周铁军
Matlab的求解线性规划的函数linprog不适应于0-1规划。我们采用穷举法编写了如下程序可以实现0-1规划的求解。
%0-1 program:linprog01.m
%%% min c'x
%%% s.t. Ax<=b
%%% Aeqx=beq
%%% Aieq~=bieq
function [x,fval]=linprog01(c,A,b,Aeq,beq,Aieq,bieq)
iVal=size(c,1);
xVal=zeros(size(c));
x=xVal;
opt_solution=c'*xVal;
for i=1:2^iVal-1
strBin_i=dec2bin(i);
xVal=zeros(size(c));
for k=1:length(strBin_i)
xVal(k)=str2num(strBin_i(k));
end
constrA=A*xVal<=b;
constrAeq=Aeq*xVal==beq;
cons
MATLAB枚举法求解0-1规划源程序及应用实例_数学_自然科学_专业资料。M文件 ... 穷举法求解0-1整数规划的... 3页 1下载券 层次分析法matlab源程序 6页 ...
根据这些性质, 设计出合理的算法,并用 MATLAB 实现该算法。实验表明,该算法是...这就给我 们指明了一个方向,求解非线性 0-1 整数规划的算法可以基于穷举法,...
0-1线性规划模型的MATLAB实现及应用_数学_自然科学...穷举法等方法求解要简单快捷 得多.1 O—l线性规划...一1整数规划.minf=c,*《,S.t.A*誓≤b,其中N...
Matlab程序 0-1整数线性规划_数学_自然科学_专业资料。Matlab 程序 0-1线性... matlab 整数规划程序 5页 免费 穷举法求解0-1整数规划的... 4页 1下载券...
0-1线性规划模型的MATLAB实现及应用_数学_自然科学...穷举法等方法求解要简单快捷 得多.1 O—l线性规划...一1整数规划.minf=c,*《,S.t.A*誓≤b,其中N...
此外,线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人员安 排、代码...变量的个数比较少、约束条件比较简单时,使用穷举法求解 0-1 整数规划问题比较 ...
原问题最优解。 ? 2005年 2005年8月 龙子泉 第二节 整数规划的解法 – ...0-1整数规划求解– 0-1整数规划的求解方法有穷举法、隐枚举法和分枝 - 整数...
x i ? 1 的整数规划来求解。 对于 n 个变量的 0-1 规划,如果使用穷举法...求解 0-1 型整数线性规划的 MATLAB 程序 Ⅰ、转换十进制数为二进制数的程序 ...
二 0-1型整数规划的一般解法---隐枚举法 ?解0-1型整数规划最容易想到的方法,和一般整数线性规划 的情形一样,就是穷举法,即检查变量取值为0或1的每一种 ...
热门文档