gusucode.com > 十大算法matlab程序说明 > 十大算法matlab程序说明/穷举法求解0-1整数规划的matlab程序.txt
穷举法求解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;
constrAieq=Aieq*xVal~=bieq;
if all(constrA) & all(constrAeq) & all(constrAieq)
objVal=c'*xVal;
if objVal<=opt_solution
opt_solution=objVal;
x=xVal;
end
end
end
fval=opt_solution;
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-09-14 09:40 by realghost
回周铁军：你的程序很巧妙，佩服。能给出你的博客吗，欢迎常交流！
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-10-25 11:37 by li
有大规模0-1规划问题需要帮忙,能把的email地址给我吗,有相关资料给你
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-10-25 14:14 by realghost
slqinyi@gliet.edu.cn
谢谢！
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-10-31 21:08 by sheepdeer
请问高手:怎样用matlab,采用穷举法求解最优问题？
http://blog.sina.com.cn/u/1232543805
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-11-01 13:45 by realghost
回sheepdeer：那就把所有的解算一遍，结果最好的就是最优解了。我不知道你所说的具体问题是什么。
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-11-11 15:03 by 黄文
你好！
我在建模的时候遇到这样的一个问题，就是最佳阵容问题，不知道你做过没有？里面建模和求解的时候遇到了一点问题。也是0-1问题，我想用穷举法做 ，但编程时没会，请指教。要是你有这题的解答的话也可以跟我说一声，谢谢，我的邮箱是huangwen1984@163.com.
或者我的QQ是229146995，我们可以讨论一下。谢谢
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-11-12 14:24 by realghost
最佳阵容？好象应该是指派问题了，用匈牙利算法比较好吧？
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-11-21 11:05 by 小脸蛋
这哪效率很低的 会出现组合爆炸情况 应该用其他的智能算法
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2006-11-21 14:01 by realghost
回小脸蛋：你说得没错。我现在只是把这个算法编出来，可解决小规模的问题。我的目的只是实现算法。
# re: 穷举法求解0-1整数规划的matlab程序（原创）
2007-01-08 09:56 by 天涯过客
也许我可以做点什么.我有动态规划的程序.比如下面的问题(来自网上)
50 //物品数
1000 //最大载重
value[N]={220,208,198,192,180,180,165,162,160,158,
155,130,125,122,120,118,115,110,105,101,
100,100,98,96,95,90,88,82,80,77,
75,73,70,69,66,65,63,60,58,56,
50,30,20,15,10,8,5,3,1,1};
weight[N]={80,82,85,70,72,70,66,50,55,25,
50,55,40,48,50,32,22,60,30,32,
40,38,35,32,25,28,30,22,50,30,
45,30,60,50,20,65,20,25,30,10,
20,25,15,10,10,10,4,4,2,1};
我解决的结果是
最大价值 3090
装箱方法
1 1 0 1 1 1 0 1 1 1
1 0 1 0 0 1 1 0 1 1
0 1 1 1 1 1 1 1 0 1
0 0 0 0 1 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
验证
Index*v'
ans =
3090
>> Index*w'
ans =
1000
我的邮箱0927Ldw@163.com