



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、.割平面法Gommoy算法步骤:1 求解原整数规划对应的线性规划 min f(x)=cx, .,设最优解为x*.2 如果最优解的分量均为整数,则x*为原整数规划的最优解:否则任选一个x*中不是整数的分量,设其对应的基变量为xp , 定义包含这个基变量的切割约束方程,其中xj为非基变量.3 令,其中为高斯函数符号,表示不大于某数的最大整数. 将切割约束方程变换为,由于,所以有1,因为自变量为整数,则也为整数,所以进一步有=0.4 将切割方程加入约束方程中,用对偶单纯算法求解线性规划,转.算法MATLAB实现代码:function intx,intf=Gomory(A,c,b,base)%约束矩阵
2、:A;%目标函数系数向量:c%约束右端向量:b%初始基向量base%目标函数取最小化时的自变量值:x%目标函数的最小值:minfsz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia; if length(base)=n disp(基变量的个数要与约束矩阵的行数相等!); mx=NaN; mf=NaN; return;end M=0;sigma=-transpose(c) zeros(1,(nVia-length(c);xb=b;while 1 maxs,ind=max(sigma); if maxs=0 vr=find(c=0,1,last); for l=1:vr
3、ele=find(base=l,1); if(isempty(ele) mx(l)=0; else mx(l)=xb(ele); end end if max(abs(round(mx)-mx)=0 if max(abs(round(xb)-xb)1.0e-7 %用对偶单纯形法求得了整数解 vr=find(c=0 ,1,last); for l=1:vr ele =find (base=l,1); if(isempty(ele) mx_1(l)=0; else mx_1(l)=xb(ele); end end intx=mx_1; intf=mx_1*c; return; else sz=si
4、ze(A); sr=sz(1); sc=sz(2); max_x,index_x=max(abs(round(mx_1)-mx_1); isB,num=find(index_x=base); fi=xb(num)-flooor(xb (num); for i=1:(index_x-1) Atmp(1,i)=a(num,i)-floor(A(num,i); end for i=(index_x+1):sc Atmp(1,i)=a(num,i)-floor(a(num,i); end %下一次对偶单纯形法迭代的初始表格 Atmp(1,index_x)=0; A=A zeros(sr,1);-Atmp(1,:) 1; xb=xb;-fi; base=base sc+1; sigma=sigma 0; continue; end %对偶单纯形法的换基变量过程 else minb_1=inf; chagB_1=inf; sA=size(A); br,idb=min(xb); for j=1:sA(2) if A(idb,j)0 bm=sigma(j)/A(idb,j); if bm0 bz=xb(j)/A(j,ind); if bz A=-1 2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 基地管理喷雾管理制度
- 催收外包公司管理制度
- 医疗公司就医管理制度
- 食堂装饰施工技术措施
- 农用灌溉机井管理制度
- 公司员工待岗管理制度
- 健全项目绩效管理制度
- 公司雨伞领用管理制度
- 第七章羧酸及其衍生物CarboxylicAcidandDe
- 医疗公益项目管理制度
- 2025八省适应性考试语文的3道作文题深度解析和写作指导(真题+审题立意+标题+范文)【技法精研】高考语文议论文写作
- 集中供热基础知识
- 食堂原材料采购管理方案及食品保存管理方案
- 幼儿园运动与健康幼儿园运动与健康教案
- 2025年贵州贵安发展集团有限公司招聘笔试参考题库含答案解析
- 《小米智能家居》课件
- 俄语阅读知到智慧树章节测试课后答案2024年秋哈尔滨师范大学
- DG-TJ 08-2343-2020 大型物流建筑消防设计标准
- 燃气公司生产安全事故隐患排查治理体系手册
- 操作系统(鲁东大学)知到智慧树章节测试课后答案2024年秋鲁东大学
- 2024年安徽省合肥市公开招聘警务辅助人员(辅警)笔试必刷测试卷(2)含答案
评论
0/150
提交评论