- 1、本文档共7页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
一、编程
利用Matlab的线性规划指令:
[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)
编写计算整数规划函数,输入与输出与上述指令相同
分枝定界法(递归实现)
function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e)
%整数规划求解函数 intprog()
% 其中 f为目标函数向量
% A和B为不等式约束 Aeq与Beq为等式约束
% I为整数约束
% lb与ub分别为变量下界与上界
% x为最优解,fval为最优值
%例子:
% maximize 20 x1 + 10 x2
% S.T.
% 5 x1 + 4 x2 <=24
% 2 x1 + 5 x2 <=13
% x1, x2 >=0
% x1, x2是整数
% f=[-20, -10];
% A=[ 5 4; 2 5];
% B=[24; 13];
% lb=[0 0];
% ub=[inf inf];
% I=[1,2];
% e=0.000001;
% [x v s]= IP(f,A,B,I,[],[],lb,ub,,e)
% x = 4 1 v = -90.0000 s = 1
% 控制输入参数
if nargin < 9, e = 0.00001;
if nargin < 8, ub = [];
if nargin < 7, lb = [];
if nargin < 6, Beq = [];
if nargin < 5, Aeq = [];
if nargin < 4, I = [1:length(f)];
end, end, end, end, end, end
%求解整数规划对应的线性规划,判断是否有解
options = optimset('display','off');
[x0,fval0,exitflag] = linprog(f,A,B,Aeq,Beq,lb,ub,[],options);
if exitflag < 0
disp('没有合适整数解');
x = x0;
fval = fval0;
status = exitflag;
return;
else
%采用分支定界法求解
bound = inf;
[x,fval,status] = branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);
end
子函数
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 <= 0 || fval0 >= 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<=floor(x(n))
A
您可能关注的文档
- 重大版小学英语下Unit-5-Lesson-1.ppt
- 鼻饲、胃肠减压评分标准-Microsoft-Office-Word-文档.docx
- 24真遗憾-我没见过他.pptx
- 分析化学第六版第7章-氧化还原滴定法及答案.doc
- 2018中考专题训练-----词汇考察.doc
- 安康有限公司试生产运行方案.doc
- 2017最新人教版二年级数学下册期末试卷.doc
- 贝多芬《第十九号钢琴奏鸣曲》(Op.49 No.1)第一乐章音乐分析报告.docx
- 第一章-字体与版式概述.ppt
- 《第5课 真情传递》课件初中美术赣美版七年级下册.ppt.ppt
- 2023年09月江苏省靖江市下半年医疗卫生事业单位公开招聘11名卫生专业技术人员笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年10月广东广州市番禺区卫生系统事业单位公开招聘250人笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年10月海南省公路管理局51名事业编制人员笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年09月贵州省开阳县卫健系统简化程序择优公开招聘18名乡镇卫生院工作人员笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年10月河南安阳汤阴县引进6名高层次人才笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年11月安徽宿州市教育科学研究所招考聘用体育学科教研员笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年10月宁夏石嘴山市民政局所属市精神康复中心公开招聘编外人员13人笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年陕西佛坪国家级自然保护区管理局(大熊猫国家公园佛坪管理分局)招考聘用笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年10月浙江省东阳市教育系统华东师范大学南京师范大学专场引进39名人才笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
- 2023年10月下半年战略支援部队直接选拔招录军官笔试历年高频考点(难、易错点荟萃)附带答案详解.docx
文档评论(0)