割平面法Gommoy_第1页
割平面法Gommoy_第2页
割平面法Gommoy_第3页
割平面法Gommoy_第4页
免费预览已结束,剩余1页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论